(57)【要約】【課題】方法は、問題の現在の解と、現在のモビリティの集合と、要素のリストとを保持する。モビリティは要素に割り当てられる。【解決手段】各繰り返しにおいて、本方法はまず、どれが最良解をもたらすのかを特定するために、現在のモビリティから判断して現在の解に対する全ての正当な移動を評価する。次に、本方法はこの移動を適用して新たな現在の解を提供し、反復を避けて探索空間の新たな領域の探求を促すために、モビリティの集合を更新する。このプロセスは、ユーザが最終解に満足するまで繰り返される。【選択図】　　　　図３
2004038936.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法であって、
前記要素を順序付けリストに保持するステップと、
モビリティの集合を保持するステップと、
前記モビリティの集合からの１つのモビリティを要素のそれぞれに割り当てるステップと、
それぞれが対応する解を提供する複数回の移動を、前記割り当てられたモビリティに従って前記アプリケーションの前記要素に適用するステップと、
コスト関数に従って各解を評価して、最良解を求めるステップと、
最終解に到達するまで、前記割り当てる処理、前記適用する処理、および前記評価する処理を繰り返すステップと
を含む複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項２】
前記モビリティの集合は、高モビリティと、中モビリティと、低モビリティとを含む
請求項１記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項３】
前記移動は、タブー探索により求められる
請求項１記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項４】
前記移動のそれぞれは、前記割り当てられた高モビリティを有する少なくとも１つの要素に対して行われる
請求項２記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項５】
前記要素の前記割り当てられた高モビリティは、前記移動が前記要素に適用された後に、前記中モビリティに変化する
請求項２記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項６】
特定のモビリティを所定回数の移動の完了時に特定の要素に再割り当てするステップ
をさらに含む請求項５記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項７】
要素のそれぞれに適用された前記移動の回数に従って、前記複数回の移動を前記アプリケーションの前記要素に適用するステップ
をさらに含む請求項１記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項８】
前記モビリティは、視覚化のために色分けされる
請求項２記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項９】
前記色分けされたモビリティは表示される
請求項８記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項１０】
前記最良解を表示するステップ
をさらに含む請求項１記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【請求項１１】
前記複数回の移動の前記移動の回数は所定である
請求項１記載の複数の要素を有するアプリケーションを最適化するためのユーザのガイドによる方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、包括的には最適化システムに関し、特に、対話型最適化システムに関する。
【０００２】
【従来の技術】
対話型最適化
対話型、すなわちユーザのガイドによる最適化システムは、様々なアプリケーション、たとえば、スペースシャトルのスケジューリング、グラフ作成、グラフ分割、および配送経路決定のために開発されてきた。自動最適化システムは通常、単純に定式化され過ぎた現実世界の問題（ｏｖｅｒ−ｓｉｍｐｌｉｆｉｅｄ　ｆｏｒｍｕｌａｔｉｏｎ　ｏｆ　ａｒｅａｌ−ｗｏｒｌｄ　ｐｒｏｂｌｅｍ）を解決するが、ユーザは、現実世界の制約に関する自らの選好および知識に基づいて、対話型システムをガイドすることができる。
【０００３】
対話型最適化はまた、現在ユーザがコンピュータをしのぐ能力を発揮する領域のスキル、たとえば視覚認知、戦略的思考、および学習能力も利用する。対話型システムのさらなる利点は、ユーザが自ら構築を援助した解を信用、正当化、および修正しやすいことである。
【０００４】
ユーザおよびコンピュータの両方の力を利用する対話型システムは、通常、最適化タスクに関与する作業をユーザとコンピュータとに分配する。従来技術のシステムは、この分業を様々な方法で実施してきた。
【０００５】
対話型最適化システムによっては、ユーザが現在の問題に対する解に間接的にしか影響を与えることができないものがある。たとえば、設計問題に本来適用された手法である対話型進化では、コンピュータが解を生成し、ユーザが解を選択して次の繰り返しで使用する（Ｔｏｄｄ等の著「Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｒｔ　ａｎｄ　Ｃｏｍｐｕｔｅｒｓ」Ａｃａｄｅｍｉｃ　Ｐｒｅｓｓ，　１９９２参照）。
【０００６】
他のシステムは、ユーザに探索パラメータを制御させるか、または探索が展開する際に制約を追加させることによって、さらなる対話性を提供する。Ｃｏｌｇａｎ等の著「Ｔｈｅ　ｃｏｃｋｐｉｔ　ｍｅｔａｐｈｏｒ，　Ｂｅｈａｖｉｏｒ　＆　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ」１４（４），　ｐｐ．　２５１−２６３，　１９９５を参照されたい。当該文献では、回路設計問題の候補解を評価するのに用いるパラメータをユーザが対話的に制御できるシステムについて記載している。ユーザには最適化プロセスの可視化が提供されるため、設計空間におけるトレードオフをよりよく理解することができる。
【０００７】
いくつかの制約ベースシステムが、製図のアプリケーションのために開発されてきた（Ｒｙａｌｌ等の著「Ｇｌｉｄｅ，　ａｎｄ　ｉｎｔｅｒａｃｔｉｖｅ　ｓｙｓｔｅｍ　ｆｏｒ　ｄｒａｗｉｎｇｓ　ｇｒａｐｈｓ」Ｐｒｏｃ．　ｏｆ　ｔｈｅ　１９９７　ＡＣＭ　ＳＩＧＧＲＡＰ，　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｕｓｅｒ　Ｉｎｔｅｒｆａｃｅ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，　ｐｐ．　９７−１０４，　１９９７参照）。ここでは、後続の操作が設計空間の有用な領域に制約されるように、進行中の図面に対してユーザが幾何学的または位相的な制約を課す。
【０００８】
システムによっては、ユーザは、コンピュータが生成した解をほとんどまたは全く制約されずに直接修正し、次いで修正した解に対して種々のコンピュータ解析を呼び出すことができる。たとえば、配送経路決定システムにより、ユーザは、最初の解に対してスケジュールの微調整を行った後に改善の提案を要求することができる（Ｗａｔｅｒｓの著「Ｉｎｔｅｒａｃｔｉｖｅ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ」Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ　Ｓｏｃｉｅｔｙ，　３５（９），　ｐｐ．８１２−８２６参照）。
【０００９】
対話型スペースシャトルオペレーションスケジューリングシステムにより、ユーザは、手動で修正したスケジュールに対して修復プロセスを呼び出し、自らが導入したいかなる矛盾をも解決することができる（Ｃｈｉｅｎの著「Ａｕｔｏｍａｔｉｎｇ　ｐｌａｎｎｉｎｇ　ａｎｄ　ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｐａｙｌｏａｄｓ　ｏｐｅｒａｔｉｏｎｓ」Ｊ．　ＡＩ，　ｐｐ．　１１４−２３９，　１９９９参照）。
【００１０】
あるシステム例（ＨＵＧＧＳ）は、従来の対話型最適化手法よりも高度の制御をユーザに提供するが、比較的弱い最適化プロセスを用いる（Ａｎｄｅｒｓｏｎ等の著「Ｈｕｍａｎ　Ｇｕｉｄｅｄ　Ｓｉｍｐｌｅ　Ｓｅａｒｃｈ」Ｐｒｏｃ．　１７ｔｈ　Ｎａｔ．　Ｃｏｎｆ．　ＡＩ．，　ｐｐ．　２０９−２１６，　２０００を参照）。ＨｕＧＳＳでは、ユーザは手動で解を修正し、以前の解をバックトラッキングし、網羅的な幅優先探索を呼び出し、監視し、停止させることができる。さらに注目すべきことに、ユーザは網羅的探索プロセスに制約を与え、探索の焦点を合わせることができる。実験により、ユーザのガイダンスによって、時間窓を用いた容量制約付き配送経路決定の問題（ｃａｐａｃｉｔａｔｅｄ−ｖｅｈｉｃｌｅ−ｒｏｕｔｉｎｇ−ｗｉｔｈ−ｔｉｍｅ−ｗｉｎｄｏｗｓ　ｐｒｏｂｌｅｍ）に対する網羅的探索プロセスの性能が、対話型最適化プロセスが最もよく知られた自動システムに対抗できる程度まで向上し得ることが示された。
【００１１】
タブー探索
タブー探索は、大きな解空間を探求するヒューリスティック手法である（Ｇｌｏｖｅｒ等の著「Ｔａｂｕ　Ｓｅａｒｃｈ」Ｋｌｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ，　１９９７参照）。他の局所探索技法のように、タブー探索は、解空間で定義された近傍構造を利用する。各繰り返しにおいて、タブー探索は、現在の解の近傍全てを評価し、最適解を選択する。近傍は、問題についての目的関数に関してだけではなく、解空間の未探求領域の探求を促すように設計された様々な要素によって評価される。さらに、ユーザは見込みのある領域を徹底的に探求することができる。探求を促す一般的な機構は、一時的に禁止される「タブー」移動のリストを維持することである。この一般的手法は、通常、近傍を評価するために用いる要素を微調整することによって個別のアプリケーションにカスタマイズされる。
【００１２】
【発明が解決しようとする課題】
本発明は、タブー探索プロセスを組み込んだ一般的なユーザのガイドによる最適化方法を提供することである。
【００１３】
【課題を解決するための手段】
従来技術の対話型最適化方法が概して単一の特定の問題を扱っているのに対して、本発明による方法は、複数のアプリケーションの包括的な集合に用いることができる。本方法は、探索に制約を与え、探索の焦点を合わせることができるという点でガイド可能であり、タブー探索プロセスの自然な視覚化を提供する。また、本発明による制御パラメータは、主な焦点が禁止される移動に当てられている従来技術の自動タブー探索の性能を微調整するのに用いられる制約より理解しやすい。
【００１４】
本発明によるユーザのガイドによる最適化システムは、ガイド付き網羅的探索よりかなり効率がよい。具体的には、ユーザのガイドによる最適化では、ガイドのないタブー検索より迅速によりよい解が得られる。また、本発明によるユーザのガイドによるタブー探索では、貪欲な山登り法のみに基づくガイド付き探索技法より迅速によりよい解が得られる。実験的研究では、人間のガイドによる探索の力と本発明によるユーザのガイドによるタブー探索の明確な有効性との両方が実証される。
【００１５】
【発明の実施の形態】
用語
まず、本発明によるユーザのガイドによる最適化方法を説明するために用いる用語を説明する。特定の最適化問題に関して、候補解の集合および問題要素の集合があるものとする。解は順序付けされており、結合可能であるものとする。
【００１６】
関数ＢＥＴＴＥＲ（ｓ１、ｓ２）は、解ｓ１が解ｓ２より適している場合にのみ真の状態を返し、そうでない場合には偽の状態を返す。関数ＩＮＩＴ（ｐ）は、問題ｐの初期解を返す。
【００１７】
移動は、現在の解に適用して新たな解を生成することができる変換である。各移動は、１つの問題要素ｅに対して行われ、その要素およびおそらく他の要素を変更するものと定義される。たとえば、リスト中の要素を３番目から８番目の位置へ移動させること、および４番目から８番目までの要素を上に１つずつシフトすることは、３番目の要素に対して行われ、３番目から８番目までの要素を変更する。関数ＭＯＶＥＳ（ｓ、ｅ）は、解ｓにおける要素ｅに対して行われる変換の集合を返す。関数ＡＬＴＥＲＥＤ（ｍ）は、ｍによって変更された要素の集合を返す。要素の定義は、アプリケーションごとに異なる。
【００１８】
アプリケーション例
本発明のよりよい理解のために、本最適化方法を４つのアプリケーション例に適用する。
【００１９】
交差アプリケーションはグラフレイアウトの問題である（Ｅａｄｅｓ　ｅｔ　ａｌ等の著「Ｅｄｇｅ　ｃｒｏｓｓｉｎｇ　ｉｎ　ｄｒａｗｉｎｇ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈｓ」Ａｌｇｏｒｉｔｈｍｉｃａ，　１１，　ｐｐ．　３７９−４０３参照）。ここで、問題はそれぞれが要素ｅとしてｎ個のノードを有するｍ個のレベルと、隣接レベルのノードに接続するエッジとを有する。目標は、ノードをそれらそれぞれのレベル内に再配列してエッジ間の交点の数を最小にすることである。このアプリケーションは多層回路基板を設計するものであり得る。
【００２０】
配達アプリケーションは、全ての場所を訪問する必要がない既知の「巡回セールスマン問題」の変形である（Ｆｅｉｌｌｅｔ等の著「Ｔｈｅ　ｓｅｌｅｃｔｉｖｅ　Ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ　ａｎｄ　ｅｘｔｅｎｓｉｏｎｓ：　ａｎｄ　ｏｖｅｒｖｉｅｗ」ＴＲ−ＣＲＴ−２００１−２５，　Ｌａｂｏｒａｔｏｉｒｅ　Ｐｒｏｄｕｃｔｉｑｕｅ　Ｌｏｇｉｓｔｉｑｕｅ，　Ｅｃｏｌｅ　Ｃｅｎｔｒａｌｅ　Ｐａｒｉｓ参照）。この問題は、出発点と、最長距離と、それぞれが所与の数の要求パッケージを有する所定の地理的場所にある、要素ｅとしての顧客の集合とによって特定される。目標は、所与の最長距離を上回って走行することなく、できる限り多くのパッケージを配達することである。
【００２１】
タンパク質アプリケーションは、タンパク質フォールディング問題の簡略化バージョンであり、Ｄｉｌｌの著「Ｔｈｅｏｒｙ　ｆｏｒ　ｆｏｌｄｉｎｇ　ａｎｄ　ｓｔａｂｉｌｉｔｙ　ｏｆ　ｇｌｏｂｕｌａｒ　ｐｒｏｔｅｉｎｓ」Ｂｉｏｃｈｅｍｉｓｔｒｙ，　２４：１５０１，　１９８５に記載される疎水・親水モデルを用いる。ここでは、問題の要素ｅはアミノ酸配列である。各要素は疎水または親水としてラベル付けされる。配列は重複せずに二次元格子上に配置し、配列中の隣接アミノ酸は格子において隣接したままとしなければならない。目標は、隣接する疎水対の数を最大にすることである。これは、タンパク質に対応する最小エネルギー構造の発見に相当する。
【００２２】
ジョブショップアプリケーションは、広範に研究されているタスクスケジューリング問題である（Ａａｒｔ等の著「Ａ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｓｔｕｄｙ　ｏｆ　ｌｏｃａｌ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｊｏｂ−ｓｃｈｅｄｕｌｉｎｇ」ＯＲＳＡ　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｐｕｔｉｎｇ　６（２），　ｐｐ．　１１８−１２５を参照）。一変形において、ｎ個のジョブおよびｍ個の機械に関する問題を考える。各ジョブは、要素ｅとしてのｍ個の操作、すなわち、各機械に対して１つの操作からなる。操作は指定された順序で実行しなければならない。操作は、１つの機械に対して重複してはならず、所与の機械に割り当てられる操作はいかなる順序で処理してもよい。目標は、最後のジョブが終了する時間を最短にすることである。
【００２３】
モビリティ
モビリティは、コンピュータ探索プロセスをガイドして解を改良するために、ユーザがこの解の要素に視覚的に注釈を付けることができる機構である。各要素ｅには、たとえば、高、中、および低の尺度でモビリティが割り当てられる。探索プロセスは、各移動が少なくとも１つの高モビリティ要素に対して行われるように、一連の移動を現在の解に適用することによって到達することができる解を探求するだけであり、いかなる低モビリティ要素も変更しない。視覚化のために、モビリティは色分けすることができる。
【００２４】
図１に示すように、単純な例を用いてモビリティをさらに説明する。ある問題が７個の要素１〜７を有し、この問題に対する解はこれら要素の全ての可能な順序付けである。要素に対して唯一可能な移動は、隣接要素とその要素との交換である。現在の解は以下であり、要素３に低モビリティ（Ｌ）、要素４および５に中モビリティ（Ｍ）、他の要素全てに高モビリティ（Ｈ）を割り当てた。
【００２５】
図２に示すように、少なくとも１つの要素が高モビリティを有し、いずれの要素も低モビリティを有さない場合にのみ、探索プロセスは隣接要素の対を交換することができる。探索は、一連のかかる交換によって到達することができる解の空間に制限される。要素３を低モビリティに設定することで、要素３は移動することができないため、本質的に問題は２つのさらに小さい下位問題に分割されることに留意されたい。また、中モビリティ要素は位置を変更することができるが、それらの相対順序は変更することができない。モビリティ制約は探索空間を大幅に減少させる。この例に関しては、可能な解は１２個しかないが、モビリティがない場合、７！＝５０４０個の可能な解がある。モビリティのこの一般化バージョンは、上述の４つの既知の最適化問題を含む、多種多様なアプリケーションにおいて有用である。
【００２６】
タブー検索を用いたユーザのガイド可能な最適化
次に、図３に示すように、本発明によるタブー探索を用いたユーザのガイドによる最適化方法３００を説明する。方法３００は、問題の現在の解１０１と、現在のモビリティの集合１０２と、要素のリスト１０５とを保持する。モビリティは要素に割り当てられる（１３０）。
【００２７】
各繰り返しにおいて、本方法はまず、どれが最良解１０３をもたらすのかを特定するために、現在のモビリティ１０２から判断して現在の解１０１に対する全ての正当な移動を評価する（１１０）。次に、本方法は、この移動を適用して（１２０）新たな現在の解を提供し、反復（ｃｙｃｌｉｎｇ）を避けて探索空間の新たな領域の探求を促すために、モビリティの集合１０２を更新する（１４０）。このプロセスは、ユーザが最終解１０４に満足するまで繰り返される。方法（ＧＴａｂｕ）３００の擬似コードを図４に示し、サポート関数５００を図５に示す。
【００２８】
モビリティの更新
本方法は、２つの方法でモビリティの集合１０２を更新する。まず、ＭＥＭＯＲＹ関数の呼び出しは、現在の移動によって変更された要素を中モビリティに設定することによって、タブー探索が即座にバックトラッキング、すなわち反復することを防ぐ。たとえば、交差アプリケーションにおいて、現在の移動が２つのノードを交換する場合、両方のノードが中モビリティに設定されるため、これら２つのノードはそれらの元の場所に単に再交換されることはできない。それらノードは、ユーザが定義した回数の繰り返しが経過した後でそれらの元のモビリティに復元され、方法ＧＴａｂｕへの入力である整数ｍｅｍＳｉｚｅによって制御される。
【００２９】
多様化
ＤＩＶＥＲＳＩＦＹ関数によって実行される第２の機構は、過去の繰り返しにおいてあまり頻繁に変更されなかった要素を変更する移動を選択するように本方法を促す。したがって、本方法は、変更された回数によって降順に分類された、順序付けされた要素のリスト１０５を保持する。
【００３０】
要素の多様度は、要素の総数によって分けられたリスト上のその位置である。移動の多様度は、移動によって変更された要素の平均多様度である。探索の多様度は、最後に最良解が特定された時から行われた移動の平均多様度である。ユーザ１０６は、探索に対して０〜１の目標最小多様度ｍｉｎＤｉｖ閾値１０７を示すことができる。平均多様度がこの閾値未満である場合、ｍｉｎＤｉｖ未満の多様度を有するいかなる要素も１回の繰り返しの間、中モビリティに設定される。これにより、本方法は高多様度での移動を行わざるを得ない。ユーザはまた、メモリサイズ（ｍｅｍＳｉｚｅ）を指定することができる。
【００３１】
従来技術のタブープロセスは、移動の値が、現在の解のコストと移動の多様度の何らかの定義とにどのように影響を与えるかに基づいている、多様化を促す機構を有する。これら２つの構成要素は、多様化要因の重みを指定する制御パラメータを用いて結合される。しかしながら、ユーザは概して、この制御パラメータを理解および使用するのに苦労する。
【００３２】
システムがより理解しやすければよりガイドしやすいという仮定の下で、本方法を理解しやすいように構成した。下記のトレーニングセッションから経験したのは、ｍｉｎＤｉｖ制御パラメータは従来技術の制御パラメータより理解しやすいということである。
【００３３】
視覚化
本方法のわかりやすさはまた、本方法がモビリティの集合１０２を修正することによってその探索を制御するという事実によって大幅に高められる。本システムのユーザは、モビリティを用いて探索を制御し、探索の焦点を合わせることによって、モビリティの集合１０２の意味を学習する。４つのアプリケーション全てが、ユーザの現在のモビリティ設定を色分けして視覚化する。同様にこの機構を用いてモビリティを表示することができる。
【００３４】
ユーザが探索を通して一度に１回の繰り返しを行うか、または各繰り返しにおいて簡単に現在の解１０１およびモビリティの集合１０２を見ることができる、いくつかの異なる視覚化モードを提供する。これらの視覚化はシステムの効率を低下させるため、最適化セッションの間は、これらの視覚化は通常オフにされる。しかしながら、システムの使用法を学習する間は、これらの視覚化モードは、本方法がどのように働くかをユーザが理解する助けとなる。
【００３５】
たとえば、ｍｉｎＤｉｖ閾値１０７が非常に高く設定される場合、ユーザは１回の繰り返しの間、中モビリティに設定されることがある問題要素の割合の大きさ（ｌａｒｇｅ）を見ることができ、かつ、本方法が全く異なる解を探求せざるを得ないことを見ることができる。
【００３６】
【発明の効果】
発明の効果
本発明は、ユーザのガイドによるタブー探索方法を提供する。ユーザのガイドによるタブー探索は、従来技術では知られていない。本方法は、対話型最適化の明らかな進歩を表す。タブー探索は概して網羅的探索より強力な探索戦略を提供するため、人間のガイドによるタブー探索は、最適化プロセスに人が関与する利点を依然として享受しながら、よりよい解を提供することができる。ユーザが本方法を理解、制御、およびガイドして、いくつかのドメインにおけるガイド付きの網羅的探索より優れた結果を得ることができることを実証した。特に、人間によるわずかなガイドで、ガイドのないコンピュータがかなりの時間をかけるのと同じ価値が得られる。
【００３７】
問題のアプリケーションそれぞれが固有の「感覚（ｆｅｅｌ）」を有していたが、４つのアプリケーション例において本最適化をガイドするための、共通の特性および一般的戦略がいくつかある。たとえば、共通のパターンは、ユーザがいくつかの手動の移動を行うことによって、著しい局所極小を避けようとすることである。これらの移動により、スコアが一時的に悪くなることが多いが、プロセスを繰り返すことで、通常は解が改善する。
【００３８】
概して、ユーザは、コンピュータがすぐに考えないであろう移動の組み合わせを探す。たとえば、配達アプリケーションでは、全体として経路から遠い顧客のクラスタを移動させ、それらを低モビリティに設定し、探索を繰り返すことが優れた戦略である。完全に自動化された探索では、このオプションをすぐには探求しないであろう。これは、一度に１つまたは２つの顧客を移動させることで、経路の距離が著しく短縮されることはないからである。同様に、交差アプリケーションにおいて、ユーザは、全て新たな場所に移動させることができるノードの、略独立したクラスタを探すことが多い。ジョブショップでは、機械にさらに柔軟性を与えるために、自身の機械に対するいくつかの操作を移動させることが一般的である。
【００３９】
本発明は好ましい実施形態の例によって説明したが、様々な他の適合および変更を本発明の精神および範囲内で行うことができることを理解すべきである。したがって、本発明の真の精神および範囲内に入る全ての変形および変更を包含することが、併記の特許請求の範囲の目的である。
【図面の簡単な説明】
【図１】本発明によるユーザのガイドによる最適化方法によって最適化することができる複数の要素に関する順序付け問題の一例である。
【図２】図１の構成について許容される解を示す。
【図３】本発明によるユーザのガイドによる最適化方法のフロー図である。
【図４】本発明による方法の擬似コードである。
【図５】図３における方法のサポート機能の擬似コードである。
【図１】
2004038936.tif 000003
【図２】
2004038936.tif 000004
【図３】
2004038936.tif 000005
【図４】
2004038936.tif 000006
【図５】
2004038936.tif 000007
【外国語明細書】
2004038936.tif 000008
2004038936.tif 000009
2004038936.tif 000010
2004038936.tif 000011
2004038936.tif 000012
2004038936.tif 000013
2004038936.tif 000014
2004038936.tif 000015
2004038936.tif 000016
2004038936.tif 000017
2004038936.tif 000018
2004038936.tif 000019
2004038936.tif 000020
2004038936.tif 000021
2004038936.tif 000022
2004038936.tif 000023
2004038936.tif 000024
2004038936.tif 000025
2004038936.tif 000026
2004038936.tif 000027