(57)【要約】【課題】一連の制約の元における最適化問題の解決方法及びそのシステムを提供する。【解決手段】一連の制約のもとで一連の解を評価する。制約に違反した解に対応する少なくとも１つの制約に基づいて、初期違反計量及び状態を生成する。一連の演算子を用いて現有の一連の解から一連の解候補を生成する。その一連の解候補を増分評価する。その方式は演算子及び制約と関係ない。評価された解が受け入れられると、受け入れられた解に基づいて違反計量及び状態を更新する。評価された解が受け入れられないと、次の解候補を増分評価する。全ての解候補の受け入れ性が検査されるまで、この過程を繰り返して実行する。最後に、終了基準を満足すると、該方法を終了させる。【選択図】図２
2008518359.tif 000002
【特許請求の範囲】
【請求項１】
一連の制約下における最適化問題の解決方法であって、
ａ）一連の制約のもとで最適化問題の一連の解を評価するステップと、
ｂ）評価期間の間に少なくとも１つの制約に違反した一連の解に対応する一連の制約に基づいて、違反計量及び状態の初期組を生成するステップと、
ｃ）一連の演算子を用いて一連の解から派生された一連の解候補を生成するステップであって、前記各演算子は一連の変化点によって特徴づけられるステップと、
ｄ）前記変化点において一連の解候補を評価するステップと、
ｅ）受入れ基準に基づいて、評価された解候補の受け入れ可能性をテストするステップと、
ｆ）前記テストした解候補が受け入れられると、受け入れられた解候補に基づいて違反計量及び状態を更新するステップと、
ｇ）全ての評価された解候補の受け入れ性がテストされるまでにステップｅからステップｆを繰り返して実行するステップと、
ｈ）終了基準を満足するまでにステップｃからステップｇを繰り返して実行するステップと、を含むことを特徴とする最適化問題の解決方法。
【請求項２】
前記最適化問題の一連の解を評価するステップは、空値状態を用いてその一連の解を評価する過程を含むことを特徴とする請求項１記載の最適化問題の解決方法。
【請求項３】
前記各違反計量をコストに反映するステップを含み、
その反映ステップは、
ａ）定義関数に基づいて各違反計量を変換する過程と、
ｂ）変換した各違反計量を規範化する過程と、
ｃ）各制約に関連する優先権に基づいて規範化した各違反計量を換算する過程と、
ｄ）換算した違反計量を合計し、制約違反に関連のあるコストを生成する過程とを備えることを特徴とする請求項１記載の最適化問題の解決方法。
【請求項４】
前記一連の演算子によって執行された演算は、解の“交換”、“挿入”、“変位”及び“削除”演算のうち少なくとも１つを含むことを特徴とする請求項１記載の最適化問題の解決方法。
【請求項５】
前記一連の解候補を評価するステップは、対応する演算子と関連のあるそれぞれの変化点における前記一連の解候補うちの１つの解候補を増分評価する過程を含むことを特徴とする請求項１記載の最適化問題の解決方法。
【請求項６】
前記解候補が対応する解と論理的に等しくなり、かつ前記解候補に対応する状態が前記対応する解に対応する状態と論理的に等しくなるまでに、前記解候補を増分評価することを特徴とする請求項１記載の最適化問題の解決方法。
【請求項７】
ａ）予定数の逐次代入を完了した場合、或いは、ｂ）予定数の逐次代入を経過した後、前記一連の解候補の改善程度が所定の改善程度より小さい場合の何れかの一方が発生すると、前記終了基準を満足することを特徴とする請求項１記載の最適化問題の解決方法。
【請求項８】
前記予定数の逐次代入は、ａ）前記最適化問題の複雑度と、ｂ）前記最適化問題の解決には使用可能な時間に基づくことを特徴とする請求項7記載の最適化問題の解決方法。
【請求項９】
一連の制約下における最適化問題の解決システムであって、
ａ）一連の制約のもとで最適化問題の一連の解を評価する手段と、
ｂ）評価期間の間に少なくとも１つの制約に違反した一連の解に対応する一連の制約に基づいて、違反計量及び状態の初期組を生成する手段と、
ｃ）一連の解を演算して一連の解候補を生成する手段と、
ｄ）解及び状態を比較する手段と、
ｅ）受入れ基準に基づいて評価された解を受け入れる手段と、
ｆ）前記受け入れられた解に基づいて違反計量を更新する手段と、を含むことを特徴とする最適化問題の解決システム。
【請求項１０】
一連の制約下における最適化問題の解決システムであって、
ａ）最適化問題の解を評価し、解の違反計量を生成し、並びに違反計量及び状態を更新する評価ユニットと、
ｂ）１つの解を演算して１つの解候補を生成する演算子と、
ｃ）該最適化問題の解を受け入れる受け入れユニットと、を含むことを特徴とする最適化問題の解決システム。
【請求項１１】
前記評価ユニットは、違反計量を生成・更新するステッパーを含むことを特徴とする請求項１０記載の最適化問題の解決システム。
【請求項１２】
前記ステッパーは、少なくとも一つの制約の違反を決定するための少なくとも１つの規則に基づいて、違反を判定することを特徴とする請求項１１記載の最適化問題の解決システム。
【請求項１３】
前記評価ユニットは、一対の解及び一対の状態を比較するコンパレータを含むことを特徴とする請求項１０記載の最適化問題の解決システム。
【請求項１４】
前記評価ユニットは、状態に対応する情報をストレージするストレージアレイを含むことを特徴とする請求項１０記載の最適化問題の解決システム。
【請求項１５】
前記評価ユニットは、生成された解をストレージするストレージアレイを含むことを特徴とする請求項１０記載の最適化問題の解決システム。
【請求項１６】
一連の制約下における最適化問題の解決に用いるコンピュータプログラム製品であって、
ａ）一連の制約のもとで最適化問題の一連の解を評価するプログラム指令手段と、
ｂ）評価期間の間に少なくとも１つの制約に違反した一連の解に対応する一連の制約に基づいて、違反計量及び状態の初期組を生成するプログラム指令手段と、
ｃ）一連の演算子を用いて一連の解から派生された一連の解候補を生成するプログラム指令手段であって、前記各演算子は一連の変化点によって特徴づけられるものと、
ｄ）前記生成した変化点において前記一連の解候補を評価するプログラム指令手段と、
ｅ）受入れ基準に基づいて、評価された解候補の受け入れ可能性をテストするプログラム指令手段と、
ｆ）前記受け入れられた解候補に基づいて違反計量及び状態を更新するプログラム指令手段と、
ｇ）終了基準を満足するか否かを検査するプログラム指令手段と、を含むことを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化領域に係り、特に、ローカルサーチ技術に基づいて一連の制約における最適化問題の解決方法及びそのシステムを指すものである。
【背景技術】
【０００２】
全ての工業においては、最適化問題が存在している。例えば、最適化問題は、生産ラインでの計画や、調達及び製品製造のプロセスに関わっている。これらのプロセスは通常、比較的複雑で、しかも多くの要因、例えば、設備の生産可変量や、製造過程の複数の段階、単一資源を用いた多種の製品の生産、人力或いはプロセス制限、及び具体的な工業上の他の特定要素（例えば、製品生産周期）等に依存している。一般的に言えば、これらの工程を管理するたくさんの規則や制約が存在可能である。そのため、環境制約条件内において、どのように計画、調達または配置してこれらのプロセスを最適に完了させるのかが、最も重要である。
【０００３】
最適化問題を解決する一般的な技術は、人工及び自動最適化方法を含む。人工方法は人的介入が必要である。人工方法により得られる最適化の程度は、関わる人の技能や経験、及び最適化問題の大きさ（該最適化問題に対応する潜在的解決法(potential solutions)の数及び制約の数で示される）に大きく依存する。それと同時に、人工方法は、時間を費やし面倒で、しかも例えば不当な解及び人的誤りを招いてしまうなどの問題がある。最適化問題に関わる範囲が益々広がることに伴い、人工方法は不可能になる。一方、自動最適化方法は、定義された演算法で最適化問題を解決するものである。よく見られる自動最適化方法の１つとして、ローカルサーチ(LS)の概念に従うものを挙げられる。該技術は、一連の組合せヒューリスティクスアルゴリズム(combinatorial heuristics algorithms)、例えば、シミュレーテッドアニーリング(焼きなまし法、Simulated Annealing：SA)アルゴリズムや、遺伝的アルゴリズム法(genetic  algorithm)、タブーサーチ(taboo search)演算法及び進化的アルゴリズム法(evolutionary algorithms)を含む。そのようなヒューリスティクスアルゴリズムの一つは、、“Facts, Conjectures and Improvements for Simulated Annealing”（P.Salamon、P.Sibani及びR.Frost著、2002、SIAM Monograph出版）に提供されている。
【０００４】
別のそのようなヒューリスティクスアルゴリズムは、“Genetic, Algorithms and EngineeringDesign”（M.Gen及びR.Chang著、1997、John Wiley& Sons出版）に提供されている。
【０００５】
また、さらに別のヒューリスティクスアルゴリズムは、“Modern Heuristic Techniques for Combinatorial Problems”（Colin Reeves著、1993、HalstedPress出版）に提供されている。
【０００６】
LS技術は、解の空間内において、局所運動(local  move)を作ることで最適化問題を解決しようとする。例えば、製造工程問題の解は生産スケジュールの数学演算式であれば良く、実際には、異なる商品が製造されるのに従った時間表（タイムテーブル）を作ることである。全てのLSヒューリスティクスアルゴリズムでは、都合のよい仕組みで１以上の初期解を発生させる。解の初期組は如何なる制約をも満足する必要がないため、あらゆる都合のよい仕組みを使用しても良く、これらをランダムに発生しても良い。LSヒューリスティクスアルゴリズムは、細かな変更及び局所的な変更によって体系的に解の組を精錬する。これにより、一連の新しい解候補が発生される。これら局所的な変更を生じる技術は、使用されているLSヒューリスティクスアルゴリズムの違いに応じて異なる。その後、該組の解候補を評価し、現有の制約に対する不足または違反を判断する。使用されているヒューリスティクスアルゴリズムの違いに応じて変化する受け入れ基準に基づいて、これらの解候補うちの１または１以上を受け入れる。このプロセスは、解が改善できるところがなくなるか、或いは演算の予算が超えるまでに繰り返して実行される。実際には、高品質の解を得るのは、多量の運動(move)が必要で、LSヒューリスティクスアルゴリズムの現実的な実用性は、多数の制約を対照しながら大量（約１０６〜１０８個）の解候補をいかに効率的に評価するかにかかっている。
【０００７】
従来、解への評価は、ソリューション全体に対して行われている。これには、高速かつ記憶容量が大きいコンピュータが必要である。もし評価が増分的（即ち、変化が発生する解の近隣領域のみを評価する）に行われるのであれば、その方法は、特に、所定の制約に特有で、かつ局所運動の発生に依存した方式である。これには、幅広く継続的なソフトウェアの発展、或いは他の製品の開発が必要である。そのため、ローカルサーチに基づく方法の実際の使用が、長期間の演算時間及び高コストに制限されてしまうことは、明らかである。
【０００８】
そのため、演算処理を速くするとともに、実際の最適化問題を効率的に解決できる技術の開発が強く求められる。このような技術はコスト的にも効率的である。また、ワークステーションやパソコンに導入することも可能で、しかも人力の関わりを最小限にとどめたプロセスである必要がある。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、一連の制約下における最適化問題の解決方法及びそのシステムを提供することである。
【００１０】
本発明の他の目的は、一連の制約下における最適化問題の一連の解を増分評価する解決方法及びそのシステムを提供することにある。
【００１１】
本発明のもう１つの目的は、解への評価が制約の特性に関わらない最適化問題用の解決方法及びそのシステムを提供することにある。
【００１２】
本発明のもう１つの目的は、解への評価が解候補がどのような方式で発生されるのかに関わらない最適化問題用の解決方法及びそのシステムを提供することにある。
【課題を解決するための手段】
【００１３】
前記目的を達成するため、本発明では、一連の制約下における最適化問題の解決方法及びそのシステムを提供した。該方法では、前記制約に対して一連の解を評価する。該評価は、一連の初期違反計量(violation metrics)、及び一連のLS手順の間に増分評価を実行するのに必要となる情報を捕らえる一連の状態を生じる。この初期評価の後に、使用されるLSヒューリスティクスアルゴリズムの特徴である形式で、一連の演算子によって一連の解から一連の解候補を生成する。演算子が解に及ぼす影響は、一連の変化点によって示される。そして、演算された状態と関連のある情報を用いて、各変化点の近隣領域で各解候補を評価する。この増分評価の出力は、一連の新たな違反計量及び解の変化点に対応する新しい状態である。各制約についての違反計量の変化は、コスト関数の変化に変換される。増分評価及びLSヒューリスティクスアルゴリズムの特性である受入れ基準に基づいて、１つの解候補が受け入れられる。各解候補に対して上記の過程を繰り返して実行させる。例えば逐次代入数が所定の逐次代入数を越えたり、或いは、多くのの逐次代入を経ても解がこれ以上に改良できなくなった場合など、終了基準を満足すると、前記の過程を終了する。
【００１４】
前記目的を達成するため、本発明は、一連の制約下における最適化問題の解決方法及びそのシステムを提供した。該システムは、最適化問題の解を評価し、解の違反計量及び状態を生成し、違反計量及び状態を更新する手段を含む。該システムは、さらに、一連の解を演算して一連の解候補を生じる手段と、最適化問題の解を受け入れる手段と、解及び状態を比較するための手段とを含む。
【発明を実施するための最良の形態】
【００１５】
明瞭に説明できるようにするため、本明細書に用いる術語は、以下のように定義する。
【００１６】
解：解は、機能またはプロセスの数学的表現であり、最適化問題から得られる所望の結果である。これは、要素一覧表で示すことができ、要素自体が他の一覧表になることもできる。解の要素は、一連の座標｛i1, i2, …, iN｝でインデックスする（示される）。例えば、解が二次元で表現される問題の場合、インデックス一覧表｛2，3｝は、解における２列目の表の第３要素を指す。生産ラインでの調達を表すガントチャート(Gantt chart)は、このような表現方法の一例である。
【００１７】
制約：制約は、解が理想的に満足すべき規則である。その規則は、解のある単一の点に適用でき、或いは、一連の点の特徴を制御（支配）できるものである。制約に違反すれば、コストまたは懲罰(penalty)を直接的或いは間接的に被り、また、制約の違反は、違反計量によって定量化される。
【００１８】
評価ユニット(Evaluator)：評価ユニットは、１つの制約または一連の制約に対して一つの解を検査する。評価ユニットの出力は、一連の違反計量である。違反計量は、最適化の目標関数である、コスト関数またはコストに変換される。
【００１９】
目標関数：目標関数は、最適化された関数として定義される。例えば、典型的な製造の場合、解は生産ラインの調達（スケジュール）であり、目標関数は、最小化すべき懲罰またはコストである。
【００２０】
状態：状態は、ある制約に対する解の要素ごとに規定される。１つの要素の状態は、他の全ての要素がその制約に対してその要素に及ぼす影響をエンコード（符号化）する。
【００２１】
演算子（演算ユニット）：演算子は、解の空間内で運動を生じさせることによって、現有の一連の解のうちから解候補を発生させる。
【００２２】
運動（移動）：演算子より生じた運動は、変化点の一覧表で示される。典型的な実施例では、各変化点は、２つの要素を含む一覧表である。第１要素は座標範囲であり、第２要素は該座標範囲に対応する変化の一覧表である。典型的な運動では、変化点の第１要素によってインデックスされた解の要素は、その変化点の第２要素によって置き替えられることができる。
【００２３】
本発明は、一連の制約下における最適化問題を解決するための方法、システム及びコンピュータのプログラムを提供する。典型的な最適化問題は巡回セールスマン問題(TSP)であっても良い。この問題の解は、一連のシティーを訪問する最適な順序を探し出し、コスト関数、例えば、巡回距離や時間を最小化する。全ての一対のシティー間の移動コストは提供されている。他の典型的な最適化問題は、製造環境化における生産ラインでの一連の生産タスクの順序付けの問題である。各タスクは関連づけられた期限を有することができる。また、例えば、タスクの継承や優先、一定期間内または周期内で順序付けすることのできる任意のタスクの最大または最小数、及びタスク間の間隔、のような大量の関連する制約を有することも可能である。最適化の目標は、ある関連する期限や全ての関連する制約が満足できるように、各タスクを計画することである。本発明は、配分計画や、車両行程配置、複数レベルの調達領域、及びこれらの例に限定されない他の最適化問題の分野で、様々な最適化問題を解くのに適している。
【００２４】
理解を容易にするため、次の例でさらに定義された用語を説明する。巡回セールスマン問題(TSP)では、問題の解は、訪問すべきシティーの順番に対応するシティー一覧表である。移動距離を支配する制約に対して、あるシティーの状態とは、そのシティーへ到達するために移動（旅行）した累計距離である。局所運動（局所移動）を生じる演算子の例は、一覧表にある２つのシティーを交換させる演算子である。もし一覧表うちの２つのシティーＱ及びＣｊが交換されると、その結果生じた運動(移動)はリスト：｛｛｛i, i｝,｛Cj｝｝,｛｛j,j｝,｛C,｝｝｝で示される。ここで注意すべきは、問題の解が変化を生じると、対応している一連の状態もそれに応じて変化するということである。
【００２５】
本発明の方法は、コンピュータシステムにおいて実現され、該コンピュータシステムはさらに、ユーザ入力装置及びユーザ出力装置を含む。図１は、本発明の実施例に係る最適化問題を解く方法を実現（実行）するためのコンピュータシステム１００を示す。コンピュータシステム１００は、最適化を実行するプロセッサ１０２を含む。プロセッサ１０２は、１以上の汎用のプロセッサまたは専用プロセッサ、例えば、Pentium（登録商標）、Centrino（登録商標）、Power PC（登録商標）及びデジタル信号プロセッサ(DSP)である。コンピュータシステム１００は、さらに、１以上のユーザ入力装置１０４、例えば、マウスや、キーボード及び他のユーザ入力装置を含む。コンピュータシステム１００は、さらに、処理する作業に応じて、１以上の出力装置１０６、例えば、適切なディスプレイや、アクチュエータ、電子装置及び他の出力装置を含む。メモリ１０８、例えば、ROM、RAMまたはキャッシュメモリ（cache memory））は、最適化問題を解決する過程において発生した計算値を格納するのに必要な記憶領域を提供する。メモリ１０８は、さらに、１以上のアプリケーションプログラムや、移動コード及び必要なアプリケーションプログラムを実行するデータを含むことができるが、これらに限られるものではない。プロセッサ１０２は、オペレーティングシステム(OS)１１０を含んでいてもい。OS１１０のタイプは、コンピュータシステム１００の機能や、特定のデバイス、或いは、コンピュータシステム１００の特徴に依存する。典型的なOS１１０は、Windows、WindowsCE、Mac OS X、Linux、Unix、種々のPalm OS、メーカ独自のOS、及び他のOS１１０である。ストレージデバイス１１２は、必要なデータ及びその他のアプリケーションプログラムをストレージすることができ、例えば、ハードディスク、フローピーディスク、光ディスク、DVD、一部または全部がハード化されたリムーバブルメディア、及びその他のリムーバブルディスクである。
【００２６】
１以上の通信インターフェース１１４は、２つの装置間の直接通信、或いは適切な私有または公共ネットワークを介した通信を提供し、最適化問題にかかわるデータ及び他の情報を交換する。通信インターフェース１１４は、モデムや、DSL、赤外線送受信機、無線周波数（ＲＦ）送受信機、または他の適切な送受信機である。上述のシステムの構成要素は、通信経路１１６、例えば、バスを介して接続される。通信経路１１６はさらに並行処理またはクラスター実装(cluster implementation)のためのデバイスを含んでいてもよいが、これらに限られるものではない。
【００２７】
図２は、本発明の実施例に係る最適化問題の解決方法を示すフローチャートである。該方法は、LSヒューリスティクスアルゴリズムに基づき、一連制約下における最適化問題を解決することに関する。LSヒューリスティクスアルゴリズムの例としては、シミュレーテッドアニーリング(Simulated Annealing：SA)アルゴリズムや、遺伝的アルゴリズム(genetic  algorithm)、タブーサーチ(taboo search)及び進化的アルゴリズム(evolutionary algorithms)が含まれる。ステップ２０２では、一連の制約条件の下で、最適化問題の一連の解を評価する。一連の解の評価に基づいて、ステップ２０４では、初期違反計量組（違反軽量の初期組）及び状態組（状態の初期組）を生じる。その後、使用されているLSヒューリスティクスアルゴリズムに特有の一連の演算子を用いることによって、ステップ２０６で、一連の解から導き出された一連の解候補を生じさせる。
【００２８】
本発明の一実施例では、各演算子は、本質的に全て数学関数であり、一連の変化点を生成することで一連の解の中から１つの解を修正する。演算子とそれに関連する変化点の定義は、すでに述べた。解に数学関数を適用することによって解候補を生じさせ、その結果は、一連の変化点によって記述される。それに対応して、これらの変化点に基づいて、状態から新たな一連の状態が発生される。ステップ２０８では、前記解候補を増分評価する。増分評価は、特定変化点の近隣領域の近傍で局所的に実行される。ここで注意すべきは、その評価が完全に（i）ソリューションポイント及び（ii）そのポイントでの状態によって定められるということである。そのため、増分評価は、解候補が論理上解と等しくない、或いは状態が新たな状態と等しくない限り、実行される。増分評価の過程については、後に説明する。ステップ２１０では、評価された解候補が最適化問題の解として受け入れられるか否かを検査する。この検査は受け入れ基準に基づく。
【００２９】
受け入れ基準は、LSヒューリスティクスアルゴリズムに応じて定められる。例えば、シミュレーテッドアニーリングアルゴリズムでは、解候補のコストの方がより低ければ、解候補が受け入れられることになり、そのコストが高くても、確率的に言えば、それが受け入れられる可能性も有る。遺伝的アルゴリズムでは、コストや適応度の関数の順序付けランクに基づいて、一連の初期の解候補から一連の解が選択される。続いて、ステップ２１２では、解が受け入れられると、違反計量及び状態を更新する。
【００３０】
ステップ２１４では、全ての解候補がテストされたか否かを検査し、ステップ２１６では、終了基準を満足したか否かを検査する。或いは、終了基準を満足するまで再び新たな一連の解候補を発生して評価させる。本発明の一実施例では、終了基準は予定数の逐次代入を完成したものであり、例えば、最適化問題の複雑性及び最適化問題を解決する際に使用できる時間などの要素に決められる。他の終了基準は数回の逐次代入の後に、解全体の品質が殆ど如何なる改良もない場合である。このような方式で、制約に違反した解ごとに対して、各変化点に１つの解候補を生じて評価させ、複数の逐次代入を経過してから改良された解を発生させる。
【００３１】
図３は、本発明の実施例に係る最適化問題を解決するためのシステム３００を示す。システム３００は、評価ユニット３０２、演算子３０４及び受け入れユニット３０６を含む。本発明の様々な実施例では、システム３００は、さらに、ストレージアレイ３０８、３１０、３１２及び３１４を含む。ストレージアレイ３０８及び３１０は、それぞれ解と対応する状態をストレージする。ストレージアレイ３１２及び３１４は、それぞれ新たな状態及び違反計量をストレージする。評価ユニット３０２は、ステッパー３１６及びコンパレータ３１８を含む。本発明の一実施例では、評価ユニット３０２は、さらにストレージアレイ３２０を含む。ステッパー３１６は、制約を対照しながら解候補を逐一評価する。コンパレータ３１８は、２つのパラメータ（例えば、２つのソリューションポイント及び２つの状態）の論理同等性を比較できる。ストレージアレイ３２０は、さらに、解や、解候補、違反計量、及び評価期間に生じた様々な状態をストレージできる。
【００３２】
前記方法によると、ストレージアレイ３０８及び３１０は、解及び対応する状態を評価ユニット３０２に入力する。評価ユニット３０２は、解への評価に基づいて、一連の初期違反計量及び新しい状態を発生する。ストレージアレイ３０８は、さらに、解を演算子３０４に入力する。演算子３０４は、解を演算し解候補を生成する。解候補は、新たな状態において評価ユニット３０２の評価を受ける。受け入れユニット３０６は解候補を受け入れると、ストレージされた初期違反計量及び状態を更新する。
【００３３】
各システム素子（例えば、ステッパー３１６及びコンパレータ３１８）は、論理回路またはソフトウェアモジュールで実現できる。各ストレージアレイ３０８、３１０、３１２、３１４及び３２０は、ストレージデバイス、例えば、RAM及びROMである。
【００３４】
評価ユニット３０２は、最適化問題の解を評価し、対応する違反計量を生じるとともに、新たな違反計量及び状態を更新する。評価ユニット３０２は、これらの状態に対応する情報をストレージする。評価ユニット３０２は、さらに設定された制約下における一連の解を評価する。本発明の一実施例では、ソフトウェアコードとして実行できるあらゆる制約がサポートされる。不規則統計技術、または現有技術のうち既に知られている他の技術で一連の解を生成できる。例えば、より簡単な貪欲法（グリーディ・ヒューリスティクスアルゴリズム）やパターンベース、または優先解（prior solutions）により縮小制約(reduced constraintset)に対して、一連の解の中から解が生成される。評価ユニット３０２は、さらに、現在の解及び解候補の座標間の関係をマッピングする関数を含む。
【００３５】
本発明の一実施例では、評価は二段階に分けて発生することができる。第１の評価段階では、評価ユニット３０２は、一連の初期組中の各解に対応して、制約設定に対する一連の初期違反計量(VM)及び状態を生成する。この段階において、評価ユニット３０２は、空値状態(NULLstate)の解を評価する。空値状態は、全ての変化量の数値が０である状態に対応する。ステッパー３１６には、空値状態に用いる規則が設置されている。評価を完了すると、評価ユニット３０２は、様々な状態を繁殖(投入、populate)する。この評価は“EVAL”という関数で実行する。
【００３６】
VMは、制約の違反の程度、即ち、制約に対して解がどの程度満足しているかということを意味する。違反は、可変数値を有し、異なる違反は異なる様式で解のコストを影響を及ぼす。状態機械の用語では、VMはステッパー３１６の出力である。例えば、TSP（巡回セールスマン問題）において、巡回中の同一地域内で３つ以上のシティーを連続して回ってはいけないという１つの制約が存在するとする。この場合に、VMはベクトルであり、各ベクトルは、巡回中の全ての地域の変化に対応する成分を有し、ベクトルの大きさは、該地域内におけるシティーのラン長(ランレングス、run length)に対応する。これは、異なる方式でコストに影響を及ぼす。ある場合は、ラン長が幾らで有っても（即ち、ラン長が４でも４０であっても）、制約の違反（即ち、ある地域における全てのランが３つ以上のシティーを有すること）が同じように、好ましくないかもしれない。他の場合では、コストは、違反の関数であっても良く、違反の二乗またはより高い乗に換算しても良い。そのため、VMは、違反に対応し、１つの独立の数学関数がこれをコストに変換、規範化（正規化）、換算（スケーリング）する（図４参照）。本実施例のVMは、１つのベクトルであるが、一般に、解と同じ構造の一覧表であっても良い。
【００３７】
図４は、VMをコストに反映（マッピング）する方法を説明する。VM｛VM-i,,VMj,…,VMn｝のコストへの反映は４つのステップを含む。ステップ４０２では、一定義関数に基づいてVM変換が行われる。この変換は、違反の影響を反映することを目的とする。ステップ４０４では、変換したVMを規範化（正規化）し、異なる制約で発生しうるVMの大きさの内因性の変化（intrinsic variation）の影響を解消する。ステップ４０６では、規範化されたVMを換算（スケーリング、拡大縮小）する。該換算は各制約に与える優先権（優先度）を反映する。そのため、優先権の低い制約より、優先権の高い制約の方が高いスケール係数(scale factor)を有する。ステップ４０８でスケーリングされたＶＭが集約され、違反に関連するコストが発生される。図４のように計算されたコストは、使用されているLSヒューリスティクスアルゴリズムに固有の方式によって、受け入れ基準に対して評価される。
【００３８】
つまり、コストは、行為の範囲及び効果を達成するための、制約の違反、違反に関連する規則及び他の可変パラメータの関数である。“コスト”という用語は、本発明を実施するLSアルゴリズムに応じて定められ、ペナルティー関数(penalty function)または適応度関数(適合度関数、fitness function) と称しても良い。
【００３９】
第１段階を評価した後に、一連の解に対応する一連の初期VM及び状態を発生する。その後、演算子で解を演算して解の局所運動（局所移動）を発生する。最適化問題では、解を演算（操作）する目的は解を補正（修正）するためである。本発明の典型的な実施例では、増分評価は、演算（操作）とは無関係に進行する。これにより、本実施例はあらゆる数の演算子を有することができ、各演算子は特定のアプリケーションに適用できる。
【００４０】
本発明の一実施例では、演算子によって解に対して行われる操作はいくつか存在してもよい。これらの演算は、“交換(swap)”、“差込(insert)”、“変位(shift)”及び“削除delete”演算を含むが、これらに限定されるものではない。本発明の典型的な実施例では、演算期間に解の座標を変位できる。例えば、解の交換演算（交換操作）は、該演算に関わっていない要素、または要素の一部分の座標を変更しないことが可能である。しかし、解の一部の“削除”演算及び“差込”演算は、解の要素の座標を変更することもある。演算の効果が、解の他の領域にまで持続(persist)または波及(spill over)することもある。例えば、TSPにおいて、もし状態が部分的な距離の一覧表と対応しているのであれば、２つのシティーを含むいかなる交換も、交換を発生した２つのシティー間の全てのシティーの部分距離を変化させる。
【００４１】
演算した後に、解から派生した（引き出された）少なくとも１つの解候補が生成される。解候補には第２段階の評価が行われる。
【００４２】
この評価段階では、一連の制約の下で、新しい状態の演算子に対応する変化点について解候補を評価する。この過程は増分評価と称される。増分評価は“INC＿EVAL”関数で実行できる。増分評価はステップに応じて行われる。各ステップは、一連の整数でインデックスする。各ステップでは、解候補が変化に対して評価される。該変化は、解に作用した演算子に対応する変化点に対応し、解候補の生成に寄与する。評価ユニット３０２は、新しい状態の解候補を評価して、対応するVM及び次の状態を計算する。このVMは増量VM(INC＿VM)と称される。
【００４３】
第２段階を評価した後に、解候補が受け入れられる。本発明の一実施例では、評価ユニット３０２の外部のロジックに基づいて解候補が受け入れる。該ロジックは、“ACCEPT”関数の形式で実行できる。一旦解候補が受け入れられると、受け入れられた解に基づいて、増量VM及び新しい状態を更新する。更新された増量VMは、更新VMと称される。解候補が受け入れられなければ、次の解候補が評価される。一連の解候補のうちの全ての解候補が評価されるまで、前記過程を繰り返して実行する。
【００４４】
つまり、評価ユニット３０２は、“EVAL”、“INC＿EVAL”及び“ACCEPT”関数を含む。１つの解及び相応する状態を入力として設定すれば、前記関数が、評価の過程において出力VM、INC＿VM及び新しい状態を生成する。
【００４５】
図５は、本発明の実施例に係る増分評価を可能とするシステムを実現するための回路図である。この例では、解はベクトルであり、かつ、座標を離散のクロックティック(clock  tick)として解釈できる。前記のように、ストレージアレイ３０８は解をストレージし、且つストレージアレイ３１０は解の状態をストレージする。Clock0５０２は、ストレージアレイ３０８にストレージされた解の座標を生成する。ストレージアレイ５０４は、解候補をストレージし、且つストレージアレイ３１２は解候補に対応する新しい状態をストレージする。Clock0５０６は、ストレージアレイ５０４にストレージされた解候補の座標を生成する。この２つのクロックは、演算効果が座標を変位させるという事実に対応する一連の“位相変位(phase shifts)”によって異なっている。本発明の実施例では、Clock0５０６は、あらゆる標準のクロック発生回路(clock-generating circuit)により実現でき、適当な変位を実施してClock0５０２を派生させる。本発明の他の実施例では、Clock0５０２及びClockO５０６は、ソフトウェアコードで実現できる。
【００４６】
ストレージアレイ５０４にストレージされた解候補及びストレージアレイ３０８にストレージされた解は、不等式(IEQ)手段５０８の入力である。ストレージアレイ３１２にストレージされた新しい状態及びストレージアレイ３１０にストレージされた状態は、IEQ手段５１０の入力である。各IEQ手段５０８または５１０は、その２つの入力の間が論理同等であるか否かを検査し、入力が等しくないと、“１”を出力する。IEQ手段５０８または５１０の出力は、ORロジックブロック５１２の入力である。ORロジックブロック５１２の出力は、“１”（即ち、解候補と解とが論理的に同等でない、或いは、状態と新たな状態とが同等ではない）であれば、ステッパー３１６は、ストレージアレイ５０４にストレージされた解候補を入力として用いる。ステッパー３１６は、少なくとも１つの制約に対して違反を検査する。ステッパー３１６は、解候補を評価する際に増量VM(INC＿VM)を生成する。生成したINC＿VMは、ストレージアレイ５１４にストレージされる。各増分評価の後に、新しい状態も更新される。増分評価してから解候補が受け入れられると、新しい状態をステッパー３１６及びIEQ手段５１０にフィードバックする。IEQ手段５１０の出力状況に応じて、前記過程が繰り返して行われる。本発明の実施例では、IEQ手段５０８、５１０とORロジックブロック５１２は、図３のコンパレータ３１８に含まれる。前記比較は、INC＿VMに対応する解候補及び新しい状態を、初期VMに対応する解及び状態と比べることで実現される。他にVMを比較する手段があっても良い。
【００４７】
ステッパー３１６の手段“CompRule”５１６は、解或いは解候補がある点で違反を発生したか否かを判断し、もし違反を発生していれば違反程度を決定する規則に特有のロジックをエンコードする。すなわち、Comp Rule５１６は、VM及び状態を発生させるロジックをエンコードする。ステッパー３１６（特に‘Comp Rule’５１６）は、プログラマブルロジックアレイ(PLA)で実行できる。
【００４８】
本発明は、コストに効果的な方式で、複数の制約に対して大量の解候補（約１０６〜１０８個）を評価するのに適している。本発明の一実施例では、評価ユニット３０２は、状態情報をストレージし、該状態情報は、評価ユニット３０２がそれ自身の中であらゆる点から一連の解または一連の解候補を評価することを可能とする。各評価ユニットは、現有する解と異なる点でのみ、解候補を増加評価（増分評価）する。評価ユニット３０２は、現有の解と異なる解中の部分のみの近隣領域を考える（考慮する）ことによって、これらの差異を速く算出できる。
【００４９】
各評価ユニットは、同じ構造を有し、制約及び現有する（現存する）解から解候補を導く方式とは関係ない。各評価ユニットは、状態情報を含んでおり、該状態情報は、解の全ての点において、その点における解の残りの影響を集約する。この方式によって、評価ユニット３０２は、解全体を評価することなく、解のうち差異がある部分のみを処理できる。ここで注意すべきは、Comp Rule５１６は、制約の違反に関連する規則に従って変化する配列のうち唯一の要素であり、他の全ての要素は、全ての規則に対して不変である。また、評価ユニットの全ての要素は、全ての演算子に対して不変である。そのため、本発明の実施例では、新しい制約や演算子を添加することは、本発明を実施するために最小限の付加ロジックしか必要としない。本発明は従来の方法と比べて、最適化問題を解決するために必要となる時間を２〜３桁程度減らすことができるという利点がある。本発明は、また現有する解から解候補を生成するあらゆる仕組みをサポートする。
【００５０】
本発明は、図３及び図５に示すように、ハードウェアにおいて実行できる。本発明は、例えば、アプリケーション特有の集積回路や、フィールドプログラマブルゲートアレイ、プログラマブルロジックアレイ、および完全受託開発の集積回路のような、集積回路または集積回路の一部において実行できる。
【００５１】
本発明は、ソフトウェアによっても実行できる。具体的にいえば、本発明の典型的な実施例では、シミュレーテッドアニーリングアルゴリズムによりJavaで本発明を実現できる。評価ユニットは、共通構造を共有し、かつ特定の制約を反映した計算規則の点のみ異なるため、各評価ユニットは、本発明のオブジェクト指向の実装(object-oriented implementation)では、一つのメソッドにおいて異なっている。例えば、C言語変体（例えば、C++、C#）に準拠したプログラミング言語や、他のプログラミング言語など、特定のアプリケーションの要求に従って、様々なプログラミング言語または他のツールを使用できる。
【００５２】
本発明や本発明のあらゆる素子で述べられたシステムは、コンピュータシステムの形式で具現化できる。よく見られるコンピュータシステムの例は、汎用のコンピュータや、プログラマブルマイクロプロセッサ、マイクロコントローラ、周辺集積回路素子、および他の本発明の方法を構成する工程を実現できる他の装置または装置配置を含む。
【００５３】
コンピュータシステムは、コンピュータや、入力装置、表示ユニット及びインターネットを含む。コンピュータはマイクロプロセッサを含む。マイクロプロセッサは通信バスに接続される。コンピュータはさらにメモリを含む。メモリはRAM、ROMを含む。コンピュータシステムは、さらにストレージデバイスを含む。これは、ハードディスク駆動或いは移動可能なストレージデバイス、例えば、フローピーディスク、光ディスクなどであれば良い。また、ストレージデバイスは、コンピュータプログラム或いは他の指令をコンピュータシステムにダウンロードする他の類似手段であっても良い。
【００５４】
コンピュータシステムは、１以上のメモリ素子内に記憶された一連の指令を実行し入力データを処理する。メモリ素子は、さらに、必要に応じてデータまたは他の情報を保存できる。これらは、情報源の形式やプロセッサ内に存在する物理メモリ素子であっても良い。
【００５５】
一連の指令は、プロセッサに特定のタスク（例えば、本発明の方法を構成するステップ）を実行させる様々な命令を含む。指令はソフトウェアの形式でよい。前記ソフトウェアは、例えば、システムソフトウェアやアプリケーションソフトウェアのように、様々な形式でよい。また、ソフトウェアは、独立プログラムの集合体や、大きなプログラムを備えたプログラムモジュール、或いはプログラムモジュールの一部の形式であっても良い。ソフトウェアは、さらに、オブジェクト指向プログラミング形式のモジュールプログラミングであっても良い。プロセッサによる入力データへの処理は、ユーザコマンドや、前回の処理の結果、或いは他のプロセッサからのリクエストに応じて行われる。
【００５６】
前記の説明は、単に本発明の好ましい具体的な実施例の詳細説明及び図面に過ぎず、本発明の特許請求の範囲を局限するものではなく、本発明の主張する範囲は、下記の特許請求の範囲に基づくべきであり、いずれの当該分野における通常の知識を有する専門家が本発明の分野の中で、適当に変更や修飾などを実施できるが、それらの実施のことが本発明の主張範囲内に納入されるべきことは言うまでもないことである。
【図面の簡単な説明】
【００５７】
【図１】図１は、本発明の実施例に係る最適化問題の解決方法が実装されたコンピュータシステムを示す図である。
【図２】図２は、本発明の実施例に係る最適化問題の解決方法を示すフローチャートである。
【図３】図３は、本発明の実施例に係る最適化問題の解決システムを説明する図である。
【図４】図４は、本発明の実施例に係る違反計量をコストに反映する方法を説明する図である。
【図５】図５は、本発明の実施例に係る増分評価が可能なシステムを実現するための回路図である。
【符号の説明】
【００５８】
１００  コンピュータシステム
１０２  プロセッサ
１０４  ユーザ入力装置
１０６  出力装置
１０８  メモリ
１１０  OS
１１２  ストレージデバイス
１１４  通信インターフェース
１１６  通信経路
３００  解決システム
３０２  評価ユニット
３０４  演算子
３０６  受け入れユニット
３０８、３１０、３１２、３１４、３２０、５０４、５１４  ストレージアレイ
３１６  ステッパー
３１８  コンパレータ
３２０  ストレージアレイ
５０２  Clock0
５０６  Clock0
５０８、５１０  IEQ手段
５１６  Comp Rule 
【図１】
2008518359.tif 000003
【図２】
2008518359.tif 000004
【図３】
2008518359.tif 000005
【図４】
2008518359.tif 000006
【図５】
2008518359.tif 000007
【国際調査報告】
2008518359.tif 000008