(57)【要約】閉形式又はブラックボックスの目的関数を有する一般最適化問題の大域最適解を得るための動的方法であって、まず、初期点からスタートする１つの局所最適解を決定性手法で見つけるステップと、続いて、各初期点からスタートする全ての局所最適解が見つかるまで、先に見つけられた局所最適解からスタートするもう１つの局所最適解を見つけるステップと、そして次に、上記の点から大域最適解を見つけるステップと、を含んでいる。
2005527034.tif 000002
【特許請求の範囲】
【請求項１】
目的関数と有限次元の解空間を有する一般無制約最適化問題を解くための連続ベース動的方法であって、
a)選択された性質を有する非線形連続動的システムを構築するステップであって、該選択された性質は、無制約最適化問題の局所最適解である場合及びその場合にのみ、点が前記構築された非線形動的システムの安定平衡点であるという性質を少なくとも含む、前記非線形連続動的システムを構築するステップと、
b)一般無制約最適化問題の全ての局所最適解を、
i)初期点からスタートするステップと、
ii)局所最適解を見つけるステップと、
iii)ステップ(b)(ii)で見つけられた局所最適解からスタートし、出口点（ＥＰ）法と動的分解点（ＤＤＰ）法により構築されたグループから選択された方法により、段段に、前記構築された非線形動的システムの全ての安定平衡点である局所最適解の集合を見つけるステップと、
によって見つけるステップと、
c)ステップ(b)(iii)で見つけられた安定平衡点間から最良最適解としての大域最適解を選択するステップと、
を備える方法。
【請求項２】
前記一般無制約最適化問題が最小化ＵＣ(x)の形式のものであり、ここで、目的関数
2005527034.tif 000840
は、閉形式表現とブラックボックス表現とを備えるグループから選択され、関数ＵＣ(x)は、大域最適解が存在し、かつ局所最適解の数が有限であるように、下に有界である請求項１記載の方法。
【請求項３】
前記一般無制約最適化問題が最小化ＵＣ(x)の形式のものであり、ここで、目的関数
2005527034.tif 000841
（Ｓは離散解空間）は、閉形式表現とブラックボックス表現とを備えるグループから選択され、前記関数ＵＣ(x)は、大域最適解が存在し、かつ局所最適解の数が有限であるように、下に有界である請求項１記載の方法。
【請求項４】
ステップ(a)における前記構築された非線形動的システムは、
2005527034.tif 000842
の形式のものであり、ここで、
2005527034.tif 000843
であり、ｎは前記最適化問題の解空間の次元であり、そして、前記構築された動的システムは、
a)ベクトル場ｆ(x)は解の存在及び一意性を満たすという性質、
b)前記構築された非線形動的システムの全ての軌道は収束し、平衡点の１つに収束するという性質、及び、
c)前記最適解問題の目的関数は、前記構築された非線形動的システムの全ての軌道に沿って低下するという性質、
の全てを満たす請求項１記載の方法。
【請求項５】
前記連続最適化問題が閉形式の目的関数ＵＣ(x)を有し、ステップ(a)で構築された前記非線形動的システムが動的システム
2005527034.tif 000844
であり、ここで、
2005527034.tif 000845
は目的関数ＵＣ(x)の勾配ベクトルである請求項４記載の方法。
【請求項６】
前記連続最適化問題が、ブラックボックスの目的関数ＵＣ(x)を有し、ステップ(a)で構築された前記非線形動的システムは、動的システム
2005527034.tif 000846
であり、ここで、xのi番目の要素に係わるＵＣ(x)の導関数は片側偏差により近似され、ｅiはi番目カーテジアンン基本ベクトルであり、ｈは十分小さなスカラーである請求項４記載の方法。
【請求項７】
前記連続最適化問題が、ブラックボックスの目的関数ＵＣ(x)を有し、ステップ(a)で構築された前記非線形動的システムは、動的システム
2005527034.tif 000847
であり、ここで、xのi番目の要素に係わるＵＣ(x)の導関数は中心偏差により近似され、ｅiはi番目カーテジアンン基本ベクトルであり、ｈは十分小さなスカラーである請求項４記載の方法。
【請求項８】
前記最適化問題が離散であり、ステップ(a)の前に、前記最適化問題を連続最適化問題へ変換するステップを更に備える請求項３記載の方法。
【請求項９】
前記変換が、
a)前記離散最適化問題の大域最適解と前記変換された連続最適化問題の大域最適解とは近いという性質と、
b)前記離散最適化問題の局所最適解の集合が、前記変換された連続最適化問題の局所最適解の集合に近いという性質と、
を満たす請求項８記載の方法。
【請求項１０】
前記変換ステップで実行される前記変換は、変調器を付加することによる変換
2005527034.tif 000848
であり、ここで係数
2005527034.tif 000849
であり、そしてLはオリジナル目的関数ＵＣ(x)のリプシュッツ定数である請求項８記載の方法。
【請求項１１】
前記変換ステップで実行される前記変換は、区分線形変換
2005527034.tif 000850
であり、ここで、dist(x,y)はxとyの距離であり、
2005527034.tif 000851
であり、
2005527034.tif 000852
であり、
2005527034.tif 000853
はｘi以上の最少整数を表し、
2005527034.tif 000854
であり、
2005527034.tif 000855
はｘi以下の最少整数を表す請求項８記載の方法。
【請求項１２】
前記最適化問題は連続であり、局所最適解を見つける請求項１のステップ(b)(ii) が、
a)初期点ｘ0からスタートし、局所探索アルゴリズムを前記最適化問題へ適用するステップと、
b)前記局所探索アルゴリズムが局所最適解へ収束すれば終了し、そうでなければ次のステップへ進むステップと、
c)初期点ｘ0からスタートする前記構築された非線形動的システムを、終点を得るために数タイムステップ積分するステップと、
d)前記終点を前記初期点としてセットするステップと、
e)ステップ(a)へ進むステップと、
を備えるハイブリッド局所探索法である請求項２記載の方法。
【請求項１３】
ステップ(a)の前記局所探索アルゴリズムが、前から存在する局所探索アルゴリズムである請求項１２記載の方法。
【請求項１４】
前記最適化問題が離散であり、局所最適解を見つける請求項１のステップ(b)(ii)が、
a)初期点ｘ0からスタートし、局所探索アルゴリズムを前記最適化問題へ適用するステップと、
b)前記局所探索アルゴリズムが局所最適解ｘsへ収束すればステップ(e)へ進み、そうでなければ次のステップへ進むステップと、
c)初期点ｘ0からスタートする前記構築された非線形動的システムを、終点を得るために数タイムステップ積分し、前記終点を前記初期点としてセットするステップと、
d)ステップ(a)へ進むステップと、
e)前記局所最適解ｘsを、該局所最適解として最小値を有する点の選択と終了とを備えるグループから選択されたステップにより、複数のm個の最近接離散点に丸め、該複数の最近接離散点をステップ(f)のための初期点として採用するステップと、
f)最良近傍局所探索法を各初期点へそれぞれ適用して、m個の局所最適解ｘs1,・・・,ｘsmを得るステップと、
g)前記最適化問題の局所最適解として、最小値を有する点を選択するステップと、
を備えるハイブリッド局所探索法である請求項３記載の方法。
【請求項１５】
ステップ(a)の前記局所探索アルゴリズムが既に存在する局所探索アルゴリズムである請求項１４記載の方法。
【請求項１６】
出口点ベース法により全ての局所最適解を計算するステップ(b)(iii)は、
a)既知の局所最適解ｘ0からスタートするステップと、
b)j=0をセットし、局所最適解の集合Ｖs＝{ｘs0}及びティアj局所最適解の集合Ｖnewj＝{ｘs0}を初期化するステップと、
c)ティア(j+1)局所最適解の集合Ｖnewj+1＝{φ}を初期化するステップと、
d)Ｖnewj,ｘsjの各局所最適解に対し、全ての新しいティア１局所最適解を見つけ、集合Ｖs及びＶnewj+1内に新しいティア１局所最適解を記録するステップと、
e)全ての新しく計算された局所最適解の集合Ｖnewj+1が空でなければ、j=j+1をセットしてステップ(c)へ進むステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項１記載の方法。
【請求項１７】
出口点法により既知の局所最適解のティア１局所最適解の集合を見つけるステップ(d)は、
a)既知の局所最適解ｘs0と、見つけられた局所最適解の集合Ｖsと、与えられた局所最適解の集合Ｖnewj+1とからスタートするステップと、
b)ｘs0i=1,...,m
に対し、探索経路Ｓiの集合を定義するステップと、
c)i=1をセットするステップと、
d)各探索経路Ｓiに対し、
i)別の局所最適解を見つけ、局所最適解が見つかれば、該局所最適解をｘsiとしてステップ(ii)へ進み、そうでなければステップ(iii)へ進むステップと、
ii)ｘsiが既に見つけられたことを示すｘsi∈Ｖsであるかをチェックし、既に見つけられたものでなければ、Ｖs＝Ｖs∪{ｘsi}及びＶnewj+1＝Ｖnewj+1∪{ｘsi}をセットするステップと、
iii)i=i+1をセットするステップと、
iv)i>mとなるまでステップ(i)からステップ(iii)を繰り返すステップと、
により、対応した局所最適解を計算するステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項１６記載の方法。
【請求項１８】
出口点ベース法により、別の局所最適解を見つけるステップ(d)(i)は、
a)既知の局所最適解ｘsと予め定義された探索経路とからスタートするステップと、
b)前記予め定義された探索経路と前記構築された非線形動的システムの安定平衡点ｘs
に関する、ｘexとして示される出口点（ＥＰ）を計算するステップと、
c)εをより小さな数として、ｘ0＝ｘs+(1+ε)(ｘex-ｘs)をセットするステップと、
d)ｘ0からスタートし、システム軌道を経由して過渡探索を導くステップであって、局所探索法が該過渡探索を上回るインターフェース点ｘinfに到達するまで該過渡探索を導くステップと、
e)前記インターフェース点ｘinfからスタートし、ステップ(d)で選択された前記局所探索法を適用して近接局所最適解を見つけるステップと、
を備える請求項１７記載の方法。
【請求項１９】
ステップ(d)の前記局所探索法が、既存の局所探索アルゴリズムである請求項１８記載の方法。
【請求項２０】
探索経路に関する出口点を計算するステップ(b)は、
i)既知の局所最適解ｘsからスタートするステップと、
ii)前記予め定義された探索経路に沿った、前記最適化問題の目的関数の最初の局所最大値である前記出口点を計算するため、前記予め定義された探索経路にそって移動するステップと、
を備える請求項１８記載の方法。
【請求項２１】
与えられた探索経路に関する前記出口点を見つけるステップ(b)は、
i)既知の局所最適解ｘsからスタートするステップと、
ii)各タイムステップで、前記与えられた探索経路に沿って移動し、前記探索経路の導関数と前記構築された非線形動的システムのベクトル場との内積を計算するステップと、
iii)内積の符号が、インターバル［ｔ1,ｔ2］間で正から負へ変化した時、前記出口点を近似するために、時間ｔ1における探索経路である点と時間ｔ2における探索経路である点とを備えるグループから選択された点を用いるステップと、
を備える請求項１８記載の方法。
【請求項２２】
前記過渡探索を導くステップ(d)は、前記構築された非線形動的システムを積分するステップを備える請求項１８記載の方法。
【請求項２３】
前記最適化問題が離散であり、前記過渡探索を導くステップ(d)は、ｘ0を、ｘsから離れる方向であるが(ｘep-ｘs)の方向に近づくように丸めて新しい点ｘ0'とし、続いてｘ0'
からスタートし、最良近傍探索法を適用するステップを備える請求項１８記載の方法。
【請求項２４】
ＤＤＰベース法により全ての局所最適解を計算するステップ(b)(iii)は、
a)既知の最適解ｘs0からスタートするステップと、
b)j=0をセットし、局所最適解の集合Ｖs＝{ｘs0}と、ティアj局所最適解の集合Ｖnewj＝{ｘs0}と、見つけられた動的分解点の集合Ｖddp＝{φ}とを初期化するステップと、
c)ティア(j+1)局所最適解の集合Ｖnewj+1＝{φ}を初期化するステップと、
d)Ｖnewj,ｘsjの各局所最適解に対し、全ての新しいティア１局所最適解を見つけ、Ｖs
及びＶnewj+1内に前記新しいティア１局所最適解を記録するステップと、
e)全ての新しく計算された局所最適解の集合Ｖnewj+1が空でなければ、j=j+1をセットしてステップ(c)へ進むステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項１記載の方法。
【請求項２５】
既知の局所最適解ｘs0のティア１局所最適解の集合を見つけるステップ(d)は、
a)既知の局所最適解ｘs0、見つけられた局所最適解の集合Ｖsと、見つけられた動的分解点（ＤＤＰｓ）の集合Ｖddpと、与えられた局所最適解の集合Ｖnewj+1とからスタートするステップと、
b)ｘs0i=1,...,mjに対し、探索経路Ｓiの集合を定義し、i=1をセットするステップと、
c)各探索経路Ｓiに対し、その対応した局所最適解を、
i)対応したＤＤＰを見つけ、ＤＤＰが見つかれば次のステップへ進み、そうでなければステップ(vii)へ進むステップと、
ii)前記見つかったＤＤＰをｘddp,iとし、それが集合Ｖddpに属するか、すなわちｘddp,i∈Ｖddpであるかチェックし、属せばステップ(vii)へ進み、そうでなければＶddp＝Ｖddp∪{ｘddp}をセットして次のステップへ進むステップと、
iii)εを小さな数として、ｘ0,i＝ｘs0+(1+ε)(ｘddp,i-ｘs0)をセットするステップと、
iv)ｘ0,iからスタートし、過渡探索を導いて、局所探索法が該過渡探索を上回るインターフェース点ｘinf,iを得るステップと、
v)前記インターフェース点ｘinfからスタートし、ステップ(iv)で選択された前記ハイブリッド局所探索法を適用して、ｘddp,iに関する対応した局所最適解を見つけ、ｘsi
として示すステップと、
vi)ｘis,jが既に見つけられたか、すなわち、ｘis,j∈Ｖsであるかチェックし、見つけられていなければ、Ｖs＝Ｖs∪{ｘsj}、Ｖnewj+1＝Ｖnewj+1∪{ｘsj}、をセットするステップと、
vii)i=i+1をセットするステップと、
viii) i>mjとなるまでステップ(i)からステップ(vii)を繰り返すステップと、
により計算するステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項２４記載の方法。
【請求項２６】
前記過渡探索を導くステップ(c)(iv)は、前記構築された非線形動的システムを積分するステップを備える請求項２５記載の方法。
【請求項２７】
前記最適化問題が離散であり、前記過渡探索を導くステップ(c)(iv)は、ｘsからは離れる方向だが(ｘep-ｘx)の方向には近づくようにｘ0を丸めて新しい点ｘ0'とし、そしてｘ0'からスタートして、最良近傍探索法を適用するステップを備える請求項２５記載の方法。
【請求項２８】
ステップ(c)(iv)の前記局所探索法が既存の局所探索アルゴリズムである請求項２５記載の方法。
【請求項２９】
与えられた探索経路と前記安定平衡点ｘsとに関する動的分解点（ＤＤＰ）を見つけるステップ(c)(i)は、
a)既知の局所最適解ｘsと予め定義された探索経路とからスタートするステップと、
b)前記出口点を計算し、該出口点をｘexとするステップと、
c)ｘexからスタートし、前記最小距離点（ＭＤＰ）を、
i)前記構築された非線形動的システム
2005527034.tif 000856
を数タイムステップ積分し、前記終点を現在出口点とするステップと、
ii)前記現在出口点と前記局所最適解ｘsとを結ぶ直線を描き、前記出口点を、ｘsから始まる前記直線に沿った目的関数の最初の局所最大点である修正された出口点に置きかえるステップと、
iii)ステップ(ii)で得られた前記出口点におけるベクトル場ＦU(x)のノルムが閾値より小さくなるまで、ステップ(i)から(ii)を繰り返すステップと、
iv)前記現在出口点を最小距離点（ＭＤＰ）ｘd0とするステップと、
により計算するステップと、
d)前記ＭＤＰｘd0を初期の推測点として使い、前記安定平衡点ｘsと前記探索経路とに関する解がＤＤＰｘddpであるベクトル場の非線形代数方程式ＦU(x)＝０の集合を解くステップと、
を備える請求項２５記載の方法。
【請求項３０】
目的関数と有限次元解空間を有する一般離散最適化問題を解く離散ベース動的方法であって、
a)点が前記離散最適化問題の安定不動点である場合及びその場合に限り、該点が前記離散最適化問題の局所最適解であるという性質を少なくとも含む選択された性質を有する離散非線形動的システムを構築するステップと、
b)前記一般離散最適化問題の全ての局所最適解を、
i)初期値ｘ0からスタートするステップと、
ii)局所最適解を見つけるステップと、
iii)ステップ(b)(ii)にて見つけられた前記局所最適解からスタートし、前記構築された離散非線形動的システムの全ての安定不動点である局所最適解の集合を見つけるステップと、
により見つけるステップと、
c)ステップ(b)(iii)で見つけられた前記安定不動点の中から大域最適解を最良最適解として選択するステップと、
を備える方法。
【請求項３１】
前記一般離散最適化問題が最小化ＵＣ(x)の形式のものであり、ここで、Ｓが離散解空間である目的関数
2005527034.tif 000857
は閉形式表現とブラックボックス表現を備えるグループから選択され、前記関数ＵＣ(x)
は、大域最適解が存在し、かつ局所最適解の数が有限であるように、下に有界である請求項３０記載の方法。
【請求項３２】
前記一般離散最適化問題がＧ(x)＜０を条件とする最小化Ｃ(x)の形式のものであり、ここで、目的関数
2005527034.tif 000858
は閉形式表現とブラックボックス表現で構成されたグループから選択され、前記関数Ｃ(x)は、大域最適解が存在し、局所最適解の数が有限であり、かつ制約関数ベクトル
2005527034.tif 000859
が閉形式表現を有するように、実行可能領域全体において下に有界である請求項３０記載の方法。
【請求項３３】
ステップ(a)の前記構築された離散非線形動的システムがｘk+1＝ｆ(xx)の形式のものであり、ここで、ｘ∈Ｓであって、Ｓは前記最適化問題の解空間であり、前記構築された離散非線形動的システムは、以下の全ての性質、すなわち、
a)前記構築された離散非線形動的システムの全ての軌道は収束し、その不動点の１つに収束するという性質と、
b)前記離散最適化問題の目的関数は前記構築された離散非線形動的システムの全ての軌道に沿って減少するという性質と、
を満たす請求項３０記載の方法。
【請求項３４】
前記離散最適化問題は無制約であり、局所最適解を見つけるステップ(a)(ii)は、
a)初期点ｘ0からスタートし、反復改良局所探索アルゴリズムを前記離散最適化問題へ適用するステップと、
b)前記局所探索アルゴリズムが局所最適解へ収束すれば終了し、そうでなければ次のステップへ進むステップと、
c)終点を得るために、前記初期点ｘ0からスタートして数タイムステップ、最良近傍探索法を使うステップと、
d)前記終点を前記初期点としてセットし、ステップ(a)へ進むステップと、
を備えるハイブリッド局所探索法である請求項３０記載の方法。
【請求項３５】
ステップ(a)の前記反復改良局所探索アルゴリズムが既存の局所探索アルゴリズムである請求項３４記載の方法。
【請求項３６】
前記最適化問題が無制約であり、全ての局所最適解を計算するステップ(b)(iii)は、
a)既知の局所最適解ｘs0からスタートするステップと、
b)j=0をセットし、局所最適解の集合Ｖs＝{ｘs0}と、ティアj局所最適解の集合Ｖnewj＝{ｘs0}とを初期化するステップと、
c)ティアj+1局所最適解の集合Ｖnewj+1＝{φ}を初期化するステップと、
d)Ｖnewj,ｘsj内の各局所最適解に対し、全ての新しいティア１局所最適解を見つけ、Ｖs及びＶnewj+1内に前記全ての新しいティア１局所最適解を記録するステップと、
e)新しく計算された局所最適解の集合Ｖnewj+1が空でなければ、j=j+1をセットしてステップ(c)へ進むステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにした請求項３０記載の方法。
【請求項３７】
ティア１最適解の集合を見つけるステップ(d)は、ｘs0と、見つけられた局所最適解の集合Ｖsと、与えられた局所最適解の集合Ｖnewj+1とからスタートし、ｘs0i=1,2,...,mに対する探索経路Ｓiの集合を定義し、i=1をセットするステップと、
b)各探索経路Ｓiに対し、出口点（ＥＰ）法及び動的分解点（ＤＤＰ）法を備えるグループから選択された方法により別の局所最適解を見つけ、局所最適解が見つかれば、それをＸsiとして次のステップへ進み、そうでなければステップ(d)へ進むステップと、
c)Ｘsiが既に見つかったか、すなわちＸsi∈Ｖsであるかをチェックし、見つかっていなければ、Ｖs＝Ｖs∪{ｘsj}及びＶnewj+1＝Ｖnewj+1∪{ｘsj}をセットするステップと、
d)i=i+1をセットするステップと、
e)i>mとなるまでステップ(b)からステップ(d)を繰り返すステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項３６記載の方法。
【請求項３８】
出口点ベース法により別の局所最適解を見つけるステップ(b)は、
a)既知の局所最適解ｘsと、予め定義された探索経路とからスタートするステップと、
b)対応する出口点（ＥＰ）ｘexを計算するステップと、
c)ＥＰが見つからなければ終了し、そうでなければ次のステップへ進むステップと、
d)前記見つけられた出口点ｘexからスタートし、(i)ｘsから新しい点ｘ0へ１ステップづつ、前記予め定義された探索経路に沿って動くステップと、(ii)表現が可能であれば、εが小さな数であるｘ0＝ｘs+(1+ε)(ｘex-ｘs)を使うステップとを備えるグループから選択されたステップにより進むステップと、
e)ｘ0からスタートして、局所探索法が最良近接探索法を上回るインターフェース点ｘinfに到達するまで、該最良近接探索法を適用するステップと、
f)前記インターフェース点ｘinfからスタートし、ステップ(e)で選択された前記ハイブリッド局所探索法を適用してその対応した近接局所最適解を見つけるステップと、
を備える請求項３７記載の方法。
【請求項３９】
ステップ(e)の前記局所探索法が既存の局所探索アルゴリズムである請求項３８記載の方法。
【請求項４０】
与えられた探索経路に関する出口点を見つけるステップ(b)は、
i)既知の局所最適解ｘsからスタートするステップと、
ii)前記予め定義された探索経路に沿って移動して、該予め定義された探索経路に沿った前記最適化問題の目的関数の最初の局所最大点である出口点を計算するステップと、
を備える請求項３８記載の方法。
【請求項４１】
ＤＤＰベース法により別の局所最適解を見つけるステップ(b)は、
a)既知の局所最適解ｘsと、予め定義された探索経路とからスタートするステップと、
b)対応する動的分解点（ＤＤＰ）ｘddpを計算するステップと、
c)ＤＤＰが見つからなければ終了し、そうでなければステップ(d)へ進むステップと、
d)前記見つけられたＤＤＰｘddpからスタートし、(i)最後の出口点ｘexをｘsから遠く新しい点ｘ0へ調整するために使用されたアップデートされた探索経路に沿って１ステップ動くステップと、(ii)表現が利用可能であれば、εが小さな数であるｘ0＝ｘs+(1+ε)(ｘddp-ｘs)を使うステップとを備えるグループから選択されたステップにより進むステップと、
e)ｘ0からスタートし、局所探索法が最良近傍探索法を上回るインターフェース点ｘinfに到達するまで、該最良近傍探索法を適用するステップと、
f)前記インターフェース点ｘinfからスタートし、ステップ(e)で選択された前記局所探索法を適用してその対応した近接局所最適解を見つけるステップと、
を備える請求項３７記載の方法。
【請求項４２】
ステップ(e)の前記局所探索法が既存在の局所探索アルゴリズムである請求項４１記載の方法。
【請求項４３】
与えられた探索経路に関する動的分解点（ＤＤＰ）を見つけるステップ(b)は、
a)既知の局所最適解ｘsからスタートし、前記予め定義された探索経路に沿って動くステップと、
b)対応する出口点（ＥＰ）ｘexを計算するステップと、
c)ＥＰが見つからなければ終了するステップと、
d)ｘexからスタートし、最良の近傍探索法を適用してｘexを新しい点ｘcへ１（前方）反復移動させるステップと、
e)以下のステップ、すなわち、
i)ｘsとｘcとを結ぶ直線を形成するステップと、
ii)ベクトル(ｘs-ｘex)及び(ｘc-ｘex)が利用可能であれば、２つのベクトル(ｘs-ｘex)及び(ｘc-ｘex)間の角度εを計算し、εが０度もしくは１８０度に近ければ、ｘexがＤＤＰであり終了し、そうでなければステップ(e)(iv)へ進むステップと、
iii)ベクトル(ｘs-ｘex)及び(ｘc-ｘex)が利用可能でなければ、前記探索経路をアップデートして現在のｘexを該アップデートされた探索経路上にのせ、点ｘex,ｘc,ｘsが前記アップデートされた探索経路上であれば、ｘexがＤＤＰであり、終了するステップと、
iv)ｘcを、ｘsからスタートする直線に沿った目的関数の最初の局所最大点である点ｘc'へ修正するステップと、
v)ｘc'がｘexと同じ点であれば終了してｘc'をＤＤＰとして出力し、そうでなければステップ(f)へ進むステップと、
によって直線修正手順を実施するステップと、
f)前記出口点としてｘc'を使い、すなわち、ｘc'→ｘexとし、ステップ(d)へ進むステップと、
を備える請求項４１記載の方法。
【請求項４４】
前記離散最適化問題が有制約であって、閉形式制約方程式の集合を有しており、前記方法は、ステップ(a)の前に、全ての実行可能領域の集合を見つけるための連続非線形動的システムを構築するステップを更に備えて、
a)前記連続非線形動的システムの全てのシステム軌道は、その平衡多様体の１つに収束するという条件と、
b)集合は、該集合が前記連続非線形動的システムの安定平衡多様体である場合及びその場合に限り、制約方程式の集合の実行可能成分であるという条件と、
を満足するようにした請求項３２記載の方法。
【請求項４５】
前記離散最適化問題が有制約であって、閉形式制約方程式の集合を有しており、局所最適解を見つける請求項１９のステップ(b)(ii)は、
a)初期点ｘ0からスタートし、ここでいくつかの制約条件は禁止されるステップと、
b)局所最適解を、
i)k=1をセットするステップと、
ii)方程式
2005527034.tif 000860
からＵ(k)を計算し、ここで、λi(k-1)は前記探索プロセスを以前の遭遇した違反から離す力を決定する非負修正ファクタであり、そして、スラック変数yは
2005527034.tif 000861
として決定するステップと、
iii)ｘ0が実行可能領域内にあれば、有制約のより良い近傍法の方向と、
2005527034.tif 000862
とを使って、Ｌ(x,λ)がラグランジェ関数であるΔxＬ(x,λ)を計算し、そうでなければ、オリジナル解空間内のより良い近傍方向を使ってΔxＬ(x,λ)を計算するステップと、
iv)Ｕ(k)とΔxＬ(x,λ)の両方が十分小さければステップ(c)へ進み、そうでなければｘk＝ｘk-1+ΔxＬ(ｘk-1,λk-1),λk＝λk-1+Ｕ(k)に基づきxとλを更新するステップと、
v)k=k+1をセットし、予め定義された繰り返し数でステップ(ii)からステップ(iv)を繰り返すステップと、
により見つけるステップと、
c)ステップ(c)が収束すれば、現在の点ｘ0を局所最適解として出力するステップと、
を備える請求項３２記載の方法。
【請求項４６】
局所最適解を見つける請求項３０のステップ(b)(ii)が、実行可能点からスタートする有制約局所最適化法を適用するステップを備える請求項３２記載の方法。
【請求項４７】
前記最適化問題が有制約で、閉形式有制約方程式を有し、全ての局所最適解を計算する請求項３０のステップ(b)(iii)が、
a)既知の局所最適解ｘs0から開始するステップと、
b)j=0をセットし、局所最適解の集合Ｖs＝{ｘs0}と、ティア０実行可能成分の集合Ｖ0j＝{ｘs0}とを初期化するステップと、
c)ティア(j+1)実行可能成分の集合Ｖ0j+1＝{φ}を初期化するステップと、
d)Ｖ0j，ｘ0j内の各実行可能点に対し、
i)ｘ0jを含む有制約最適化問題の実行可能成分内にある全ての局所最適解を見つけるステップと、
ii)ｘ0j,i=1,2,...,kに対し、探索経路Ｓijの集合を定義するステップと、
iii)各探索経路Ｓijに対し、
1)i=1をセットするステップと、
2)近傍実行可能成分内にある点ｘj0,iを見つけるステップと、
3)ｘj0,iからスタートし、局所探索法を適用して局所最適解ｘjs,iを見つけ、ｘjs,iがまだ見つかっていなければ、Ｖ0j+1＝Ｖ0j+1∪{ｘj0,i}とＶs＝Ｖs∪{ｘjs,i}をセットするステップと、
4)i=i+1をセットするステップと、
5)i>kとなるまでステップ(d)(iii)(2)から(d)(iii)(4)を繰り返すステップと、
により近接実行可能成分を見つけるステップと、
e)全ての新しく計算された実行可能点Ｖ0j+1の集合が空でなければ、j=j+1をセットし、ステップ(c)からステップ(d)を繰り返すステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項４４記載の方法。
【請求項４８】
近接実行可能成分内にある点を見つけるステップ(d)(iii)(2)が、
a)εが小さな数であるｘ0+ε×Ｓijからスタートし、逆時間軌道を得るための逆時間モードにおいて前記連続非線形動的システムを積分して、前記構築された連続非線形動的システムの不安定平衡多様体中にある点ｘdiを見つけ、該点ｘdiがみつからなければ終了するステップと、
b)εが小さな数であるｘpi＝ｘdi+(1+ε)(ｘdi-ｘ0)をセットするステップと、
c)ｘpiからスタートし、結合実行可能成分内の実行可能点ｘ0iを、
i)ｘ0からスタートし前記構築された連続非線形動的システムを積分して、数タイムステップのシステム軌道を得るステップと、
ii)前記軌道が実行可能点へ収束すれば、終了するステップと、
iii)ｘ0からスタートして反復改善局所探索アルゴリズムを適用するステップと、
iv)前記局所探索アルゴリズムが実行可能点へ収束すれば終了するステップと、
v)前記終点を前記初期点ｘ0としてセットし、ステップ(c)(i)へ進むすテップと、
により見つけるステップと、
を備える請求項４７記載の方法。
【請求項４９】
実行可能成分内の局所最適解を見つけるステップ(d)(iii)(3)はハイブリッド局所探索法であり、
a)初期点ｘ0からスタートし、反復改善局所探索アルゴリズムを前記離散最適化問題へ適用するステップと、
b)前記局所探索アルゴリズムが局所最適解へ収束すれば、終了するステップと、
c)数反復毎に初期点ｘ0からスタートして、有制約の最良近傍探索法と有制約のより良い近傍局所探索法とを備えるグループから選択された方法を使って、終了点を得るステップと、
d)前記終点を前記初期点としてセットするステップと、
e)ステップ(a)へ進むステップと、
を備える請求項４７記載の方法。
【請求項５０】
ステップ(a)の前記局所探索アルゴリズムが既存の有制約局所探索アルゴリズムである請求項４９記載の方法。
【請求項５１】
実行可能成分内の局所最適解の集合を見つけるステップ(d)(i)が、
a)既知の局所最適解ｘs0と、見つけられた局所最適解の集合Ｖsとからスタートするステップと、
b)j=0をセットし、ティアｊ局所最適解の集合Ｖnewj＝{ｘs0}と、現在の実行可能成分内の局所最適解の集合Ｖsc＝{ｘs0}とを初期化するステップと、
c)ティアj+1局所最適解の集合Ｖnewj+1＝{φ}を初期化するステップと、
d)Ｖnewj内の各局所最適解ｘsjに対し、ｘsjを含む実行可能成分内の全ての新しいティア１局所最適解を見つけ、集合Ｖs,Ｖnewj+1,Ｖsc内に前記新しいティア１局所最適解を記録するステップと、
e)全ての新しく計算された局所最適解の集合Ｖnewj+1が空でなければ、j=j+1をセットし、ステップ(c)へ進むステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項４７記載の方法。
【請求項５２】
ティア１局所最適解の集合を見つけるステップ(d)が、
a)既知の局所最適解ｘs0と、局所最適解の集合Ｖsと、与えられた局所最適解の集合Ｖnewj+1と、現在成分内の局所最適解の集合Ｖscとからスタートし、ｘs0,i=1,2,...,mに対する探索経路Ｓiの集合を定義するステップと、
b)各探索経路Ｓiに対し、出口点法と動的分解点法とを備えるグループから選択された方法により別の局所最適解を見つけるステップと、
c)局所最適解ｘsiが見つからなければステップ(e)へ進むステップと、
d)ｘsiがまだ見つかっていなければ、Ｖs＝Ｖs∪{ｘsi},Ｖnewj+1＝Ｖnewj+1∪{ｘsi},Ｖsc＝Ｖsc∪{ｘsi}をセットするステップと、
e)i=i+1をセットするステップと、
f)i>mとなるまでステップ(b)からステップ(e)を繰り返すステップと、
を備えることで、Ｖsがｘs0の局所最適解の集合を備えるようにする請求項５１記載の方法。
【請求項５３】
出口点法により別の局所最適解を見つけるステップ(b)が、
a)既知の局所最適解ｘs0と予め定義された探索経路とからスタートするステップと、
b)対応する出口点（ＥＰ）ｘexを計算し、ＥＰが見つからなければ終了するステップと、
c)前記見つけられた出口点ｘexからスタートし、(i)ｘsから新しい点ｘ0へ１ステップ予め定義された探索経路に沿って動くステップと、(ii)εが小さな数であるｘ0＝ｘs+(1+ε)(ｘex-ｘs)を、もしこの表現を利用可能ならば使うステップと、を備えるグループから選択されたステップにより進むステップと、
d)有制約最良近接探索法を、ｘ0からスタートして、有制約局所探索法が前記有制約最良近接探索法を上回るインターフェース点ｘinfに前記有制約最良近接探索法が到達するまで、適用するステップと、
e)前記インターフェース点ｘinfからスタートし、ステップ(d)で選択された前記有制約局所探索法を適用して、対応した近接局所最適解を見つけるステップと、
を備える請求項５２記載の方法。
【請求項５４】
ステップ(d)の前記有制約局所探索法が既存の局所探索アルゴリズムである請求項５３記載の方法。
【請求項５５】
与えられた探索経路に関する前記出口点を見つけるステップ(b)が、
i)既知の局所最適解ｘsからスタートし、前記予め定義された探索経路に沿って移動して、前記予め定義された探索経路に沿った前記最適解問題の目的関数の最初の局所最大点である前記出口点を計算するステップと、
ii)該プロセス中に制約の禁止状態をチェックし、制約条件が禁止であれば、前記探索プロセスを終了し、前記出口点が見つからない旨を出力するステップと、
を備える請求項５３記載の方法。
【請求項５６】
動的分解点（ＤＤＰ）法により別の局所最適解を見つけるステップ(b)は、
a)既知の局所最適解ｘsと予め定義された探索経路とからスタートするステップと、
b)対応する動的分解点（ＤＤＰ）ｘddpを計算し、ＤＤＰが見つからなければ終了するステップと、
c)前記見つけられたＤＤＰｘddpからスタートし、(i)最後の出口点ｘexをｘsから更に遠く新しい点ｘ0へ調整するのに使用される更新された探索経路に沿って１ステップ動くプロセスと、(ii)εが小さな数であるｘ0＝ｘs+(1+ε)(ｘddp-ｘs)を、その表現が利用可能であれば用いるプロセスと、を備えるグループから選択されたプロセスにより進むステップと、
d)有制約最良近傍探索法を、ｘ0からスタートし、有制約局所探索法が前記有制約最良近接探索法を上回るインターフェース点ｘinfに前記有制約最良近接探索法が到達するまで、適用するステップと、
e)前記インターフェース点ｘinfからスタートし、ステップ(d)で選択された前記有制約局所探索法を適用して、対応した近接局所最適解を見つけるステップと、
を備える請求項５２記載の方法。
【請求項５７】
ステップ(d)の前記有制約局所探索法が既存の局所探索アルゴリズムである請求項５６記載の方法。
【請求項５８】
与えられた探索経路に関する動的分解点（ＤＤＰ）を見つけるステップ(b)は、
a)既知の局所最適解ｘsと、予め定義された探索経路とからスタートするステップと、
b)対応する出口点（ＥＰ）ｘexを計算し、該プロセス中に制約の禁止状態をチェックし、制約条件が禁止もしくは、ＥＰが見つからなければ、該プロセスを終了するステップと、
c)ｘexからスタートし、有制約最良近接探索法を適用して、ｘexを新しい点ｘcへ１前方反復移動させるステップと、
d)直線修正手順を、
i)ｘsとｘcとを結ぶ直線を形成するステップと、
ii)ベクトル(ｘs-ｘex)と(ｘc-ｘex)が利用可能であれば、２つのベクトル(ｘs-ｘex)と(ｘc-ｘex)との間の角度εを計算し、εが０度もしくは１８０度に近ければ、ｘexはＤＤＰで終了し、そうでなければステップ(d)(iv)へ進むステップと、
iii)ベクトル(ｘs-ｘex)と(ｘc-ｘex)が利用可能でなければ、前記探索経路を更新して、現在のｘexを前記更新された探索経路上にのせ、点ｘex,ｘc,ｘsが前記更新された探索経路上であれば、ｘexはＤＤＰであり終了するステップと、
iv)ｘcを、ｘsからスタートする直線の最初の局所最大点である点ｘc'へ修正するステップと、
v)ｘc'がｘexと同じであれば、ｘc'をＤＤＰとして終了するステップと、
により実施するステップと、
e)ｘc'を前記出口点として使い、ｘc'→ｘexとして、ステップ(d)へ進むステップと、
を備える請求項５６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，数学的な解析，モデリング，非線形プログラミング及び最適化技術の分野に関する。特に，本発明は，連続最適化問題及び離散最適化問題の局所最適解及び大域最適解をシステマテッィクに求める動的方法に関する。
【背景技術】
【０００２】
決定，デザイン，運転，計画，スケジューリングのような様々な定量的問題は，連続もしくは離散最適化問題として理解，モデル化できる科学，工学，経済分野の実システム内にあふれている。標準的に，システムの全体性能（もしくは計測）は，目的関数とよばれる多変数関数により記述できる。この一般的な記述によれば，すべての提示された実行可能な制約を満たし，かつ目的関数値を最小化（もしくは最大化）する解空間内において，通常実ベクトルで表現される最適化問題の最良解を探す。このベクトルが存在すれば，大域最適解とよばれる。ほとんどの実アプリケーションに対し，基礎となる目的関数は，通常非線形であり，多くの変数に依存し，大域最適解を見つけるために解空間を探索する作業を非常に難しいものとする。主要課題は，高次元解空間に加え，解空間には多くの局所最適解があり，大域最適解はそれらの高々１つであり，しかも，大域最適解と局所最適解は同じ局所的な性質を有することである。
【０００３】
一般に，最適化問題の解空間は有限（ふつうは非常に大きい）もしくは無限数の実行可能解を有する。この実行可能解において，ただ１つの大域最適解，更に複数の局所最適解がある。（局所最適解は解空間の局所領域内で最適であり，大域解空間内ではそうではない。）標準的に，局所最適解の数は知られておらず数は非常に大きい。更に，局所最適解と大域最適解における目的関数の値はかなり違うであろう。従って，大域最適解探索の効果的な手法を開発する強い動機付けとなる。
【０００４】
次に離散最適化問題について考察する。離散最適化問題解法の作業は非常に難しい。これらは一般にＮＰ困難（これらを解くための多項式困難の求解アルゴリズムは知られていない）である。加え，多くの離散最適化問題は効率的なアルゴリズムが知られていないＮＰ完全問題のクラスに属す。ＮＰ完全問題の正確な定義はこれまでのテキスト中にある。概略的に言えば，ＮＰ完全問題は数値計算上困難となる。任意の数値アルゴリズムは，最悪ケースにおいて大域最適解を正確に求めるため指数関数的な計算時間を要求する。
【０００５】
離散最適化問題解法の１つのポピュラーなアプローチは，反復改善局所探索アルゴリズムのクラスを使うことである[1]。これらは以下のように特徴付けられる。初期実行可能解からスタートし，その近傍内の改善解を探索する。改善解が存在すれば，初期解としての新しい解からスタートする探索過程を繰り返す。そうでなければ，局所探索過程を終了する。局所探索アルゴリズムは普通，局所最適解に捕捉され，そこから脱出できない。事実，離散最適化問題を解くための大多数の既存の最適化技術は通常，大域最適解ではなく，局所最適解を提供する。
【０００６】
反復改善局所探索アルゴリズムの欠点は，局所最適解から脱出するための探索過程を許すいくつかのメカニズムを導入することにより，改善解を見つけるためデザインされた多くのより洗練された局所探索アルゴリズム開発の動機付けとなってきた。基礎となる'脱出'メカニズムは，局所最適解からの脱出を可能とするためコスト悪化となる近傍を許容する任意の探索戦略を使う。これらの洗練された局所探索アルゴリズムはシミュレーテッド・アニーリング，遺伝的アルゴリズム，タブ・サーチ，ニューラル・ネットワークである。
【０００７】
しかしながら，多くの研究において，これらの洗練された局所探索アルゴリズムは，とりわけ強力な計算能力が要求され，普通，大域最適解を見つけることができないことが知られている。加えて，本発明において，いくつかの効果的な方法が，大域最適解探索過程における次の２つの重要かつチャレンジな問題提示のため開発される。
(i)どのように効果的に局所最適解から移動（脱出）し，別の局所最適解に移動するか，そして，
(ii)どのように既知である局所最適解への再探索を防ぐか。
【０００８】
過去において，重要な努力がこれら２つの問題を述べるために払われてきた。しかし，大きな成功はなかった。問題(i)は解くことは難しく，既存の方法はすべてこの困難に直面する。探索中の計算効率に関連する，問題(ii)も解くことが難しく，同じく既存の多くの方法がこの困難に直面する。問題(ii)は，大域最適解を探索する多くの既存の方法の性能を低下させる共通問題である。同じ局所最適解の複数探索，この操作は，全く大域最適解の位置に関する新しい情報を得ることができず計算時間の無駄である。計算時間の観点から，高効率を維持するため同じ局所最適解の再探索を防ぐことは重要である。
【発明の開示】
【０００９】
一般最適化問題の大域最適解を見つける作業は，多くの工学と科学分野にとって重要である。本発明は，決定論的に初期点からスタートした１つの局所最適解探索ステップ，全ての局所最適解探索まで既知の局所最適解からスタートした別の局所最適解探索ステップ，全ての局所最適解から大域最適解探索ステップを含む一般最適化問題の大域最適解を求める動的方法を示す。
【００１０】
全てでなければ複数局所最適解の探索とその中から最良解を選択する一般最適化問題解法の効果的なアプローチを提案する。
本発明において，一般最適化問題の全局所最適解を決定論的に見つける新しいシステマティックな方法論を開発する。いくつかのタイプの最適化問題を解くため以下の動的方法論が本発明において開発される。
・     目的関数が閉形式表現もしくはブラックボックス表現（すなわち，目的関数は解空間内の全ての点に対し計算可能であるが，閉形式表現でない）である無制約連続最適化問題を解くための動的方法論。
・     目的関数が閉形式表現もしくはブラックボックス表現の無制約離散最適化問題を解くための動的方法論
・     目的関数が閉形式表現の有制約離散最適化問題を解くための動的方法論
・     ブラックボックス目的関数を有する有制約離散最適化問題を解くための動的方法論
問題(i)について述べるため，本発明において，ＤＤＰ探索法との組み合わせにおいて，局所最適解からスタートし，その解から脱出し効果的かつ決定論的に別の局所最適解探索のシステマテッィクな手順の性能を有すＤＤＰベース数値法を開発する。問題(ii)について述べるため，本発明において，既知の局所最適解への再探索防止のためアンチ再探索法を開発する。アンチ再探索法の理論的基礎は，本発明において開発された動的分解点に基づく。
【００１１】
本発明において，これら問題(i)(ii)を克服するため開発された効果的な方法は，一般離散最適化問題の全局所最適解探索のための，２つの動的方法論により構成される。これら２つの動的方法論の１つの特徴は，これら動的方法論が局所最適解探索において，計算効率を達成するため，任意の既存の局所探索アルゴリズムと組み合わせることができ，全局所最適解探索の大域性能を維持することができることである。
【００１２】
開発された動的方法は，任意の現在の最適化法と容易に組み合わせることができる。これはユーザーにとって，本発明は大きなメリットである，なぜなら，それらは局所最適解探索において，非常に効率的にカスタマイズされた最適化法を破棄する必要がないからである。本方法は，効果的に局所最適解を見つけるためにカスタマイズされた方法を使用し，カスタマイズされた方法で１つの局所最適解から別の最適解へ脱出することを行う。
【００１３】
本発明中で開発される動的方法はコンピュータパッケージにプログラミングされ，局所最適解の完全集合を見つけるため効果的な既存のコンピュータパッケージと組み合わせることができる。本発明は，グラフィカルユーザーインターフェースとデータベースを含む，既存のコンピュータパッケージの環境を修正せずに，既存のコンピュータパーケージとインターフェースするプログラミングを行うことができる。特に，本発明は，結果を提供するコンピュータパッケージ内のユーザー向けに新しい学習カーブを課さない。既存のコンピュータパッケージ再利用の知的財産の性質は，本発明を非常に魅力的なものとする。
【発明を実施するための最良の形態】
【００１４】
一般最適化問題
本発明において，これまで同様，非線形連続最適化問題と非線形離散最適化問題に分けられる一般非線形最適化問題を考える。これらは更に以下の４つのクラスに分けられる。
・目的関数が閉形式表現もしくはブラックボックス表現の無制約連続最適化問題のクラス
・目的関数が閉形式表現もしくはブラックボックス表現の有制約連続最適化問題のクラス
・目的関数が閉形式表現もしくはブラックボックス表現の無制約離散最適化問題のクラス
・目的関数が閉形式表現もしくはブラックボックス表現の有制約離散最適化問題のクラス
非線形最適化問題の全クラスの全局所最適解と大域最適解探索の動的方法を開発した。
【００１５】
次に非線形最適問題の各クラスについて述べる。
無制約連続最適化問題
一般無制約連続最適化問題の形式は：
【００１６】
【数１】
2005527034.tif 000003
である。ここで，目的関数
2005527034.tif 000004
は閉形式表現もしくはブラックボックス表現である。関数
2005527034.tif 000005
は下に有界のため，それの大域最少（最適）解が存在し，局所最少（最適）解の数は有限である。ブラックボックス目的関数の表現はできない。代わりに，状態ベクトル
2005527034.tif 000006
から対応する目的関数値
2005527034.tif 000007
を返す外部サブルーチンとして参照される計算のみ可能である。
有制約連続最適化問題
一般有制約連続最適化問題の形式は：
【００１７】
【数２】
2005527034.tif 000008
【００１８】
である。ここで，目的関数
2005527034.tif 000009
は閉形式表現もしくはブラックボックス表現である。制約方程式
2005527034.tif 000010
で表現される不等式を満たす状態方程式の集合は実行可能領域と呼ばれる。関数
2005527034.tif 000011
は実行可能領域全体において下に有界のため，それの大域最少（最適）解が存在し，局所最少（最適）解の数は有限である。
無制約離散最適化問題
一般無制約離散最適化問題の形式は：
【００１９】
【数３】
2005527034.tif 000012
【００２０】
である。ここで，目的関数
2005527034.tif 000013
は閉形式表現もしくはブラックボックス表現である。関数
2005527034.tif 000014
は実行可能領域全体において下に有界のため，それの大域最少（最適）解が存在し，局所最少（最適）解の数は有限である。
有制約離散最適化問題
一般有制約離散最適化問題の形式は：
【００２１】
【数４】
2005527034.tif 000015
【００２２】
である。ここで，目的関数
2005527034.tif 000016
は閉形式表現もしくはブラックボックス表現である。関数
2005527034.tif 000017
は実行可能領域全体において下に有界のため，それの大域最少（最適）解が存在し，局所最少（最適）解の数は有限である。制約集合
2005527034.tif 000018
は全ての実行可能解から構成されている。集合
2005527034.tif 000019
は解析表現を伴った制約方程式の集合，もしくは状態ベクトル
2005527034.tif 000020
を取る外部サブルーチンを参照し，制約の満足性を返す計算可能なブラックボックスモデルに特徴付けられる。状態空間
2005527034.tif 000021
は有限もしくは可算無限集合である。
明らかに，このクラスの離散最適化問題は次の問題を含む。
【００２３】
【数５】
2005527034.tif 000022
【００２４】
ここで，目的関数
2005527034.tif 000023
は閉形式表現もしくはブラックボックス表現である。関数
2005527034.tif 000024
は実行可能領域全体において下に有界のため，それの大域最少（最適）解が存在し，局所最少（最適）解の数は有限である。制約関数ベクトル
2005527034.tif 000025
は閉形式表現である。状態空間
2005527034.tif 000026
は有限もしくは可算無限集合である。
以下のセクションで示される，(4-1)(4-3)(4-5)で記述される最適化問題を解くための動的法を本発明で開発した。
【００２５】
５．無制約連続最適化問題解法の動的方法
本セクションでは無制約最適化問題(4-1)を解くための動的方法を示す。
無制約連続最適化問題(4-1)解法のため，全局所最適解探索をガイドするための以下の関連した非線形動的システムの任意の軌道を利用した動的方法を開発する。
【００２６】
【数６】
2005527034.tif 000027
【００２７】
ここで、
2005527034.tif 000028
【００２８】
であり，ベクトル場
2005527034.tif 000029
は解の存在性と一意性を満たす。
【００２９】
最適化問題(4-1)の全局所最適解を特定するため実行される任意の軌道をもつ非線形動的システムの以下の十分条件を提案する。
(LC1)非線形動的システム(5-1)の全ての軌道は収束し，平衡点の１つに収束し，
(LC2)システム(5-1)の全安定平衡点は最適化問題(4-1)の局所最適解であり，逆もまた同様。
(LC3)最適化問題(4-1)の目的関数は非線形動的システム(5-1)の全軌道に沿って減少する。
【００３０】
次に，解析的閉形式目的関数もしくはブラックボックス目的関数を有する任意の無制約連続最適化問題(4-1)が与えられ，(5-1)の形式において，(LC1)〜(LC3)を満足する非線形動的システムを構築することができる，ことを示す。
【００３１】
非線形動的システムを見つけるためのガイドラインを提供するため，以下の２つの定理を始めに開発する。
以下の２つの条件を持たせば，関数
2005527034.tif 000030
は(5-1)のエネルギー関数である。(i)(5-1)の任意のシステム軌道に沿った
2005527034.tif 000031
の微分は非正，すなわち，
2005527034.tif 000032
である。(ii)
2005527034.tif 000033
が(5-1)の平衡点でないならば，
2005527034.tif 000034
に沿った集合
2005527034.tif 000035
は
2005527034.tif 000036
において測度0である。
定理5-1：動的システム(5-1)がエネルギー関数を持てば，条件(LC1)を満たす。
定理5-2：無制約連続最適化問題(4-1)の目的関数が非線形動的システム(5-1)のエネルギー関数であれば，条件(LC2)と(LC3)を満たす。
【００３２】
解析的閉形式目的関数
2005527034.tif 000037
を有した最適化問題(4-1)を示すため，条件(LC1)〜(LC3)を満たす非線形動的システムの一例を以下に示す。
【００３３】
【数７】
2005527034.tif 000038
【００３４】
ここで，
2005527034.tif 000039
は目的関数
2005527034.tif 000040
の勾配ベクトルである。一般的に述べると，解析的目的関数を持つ問題(4-1)の全局所最適解を計算するために実行される任意の動的軌道を有する，条件(LC1)〜(LC3)を満たす方程式(4-5)で記述される他の非線形動的システムがある。これらの非線形ダイナミカルシステムを以下の一般形とする。
【００３５】
【数８】
2005527034.tif 000041
【００３６】
ブラックボックス目的関数
2005527034.tif 000042
を有する最適化問題(4-1)に対し，条件(LC1)〜(LC3)を満足する非線形動的システムを構築する作業は難しい。この困難を解決するためのいくつかの方法を開発することができる。それらの１つは，以下に述べるが，ブラックボックス関数の分割差をベースとする。
【００３７】
【数９】
2005527034.tif 000043
【００３８】
ここで，
2005527034.tif 000044
の
2005527034.tif 000045
番目の成分に関する
2005527034.tif 000046
の微分は１方向の偏差により近似される。
2005527034.tif 000047
は
2005527034.tif 000048
番目のカーテジアンベイシスベクトル，
2005527034.tif 000049
は十分小さなスカラーである。別の非線形動的システムは以下のブラックボックス目的関数の中心偏差をベースに構築される。
【００３９】
【数１０】
2005527034.tif 000050
【００４０】
ここで，
2005527034.tif 000051
の
2005527034.tif 000052
番目成分に関する
2005527034.tif 000053
の導関数は，上の中心偏差により近似される。
2005527034.tif 000054
は
2005527034.tif 000055
番目のカーテジアンベイシスベクトル，
2005527034.tif 000056
は十分小さなスカラーである。
ブラックボックス目的関数を有する無制約連続最適化問題(4-1)を解くための条件(LC1)〜(LC3)を満たす，上述の(5-4)もしくは(5-5)の記述に加え，他の非線形動的システムも存在するであろう。これらの非線形動的システムを以下の一般形とする。
【００４１】
【数１１】
2005527034.tif 000057
【００４２】
明快な説明のため，解析的閉形式目的関数に関連した非線形動的システム(5-3)とブラックボックス目的関数に関連した非線形動的システム(5-6)の両者を以下の一般形にする。
【００４３】
【数１２】
2005527034.tif 000058
【００４４】
非線形動的システム(5-7)に関するいくつかの基本的な定義と事実は[2][4]に示される。
2005527034.tif 000059
で
2005527034.tif 000060
からスタートした(5-7)の解は軌道と呼ばれ，
2005527034.tif 000061
により表現される。
2005527034.tif 000062
であれば，状態ベクトル
2005527034.tif 000063
はシステム(5-7)の平衡点と呼ばれる。
2005527034.tif 000064
における
2005527034.tif 000065
のヤコビ行列のいずれの固有値もゼロの実部を持たない時，(5-7)の平衡点
2005527034.tif 000066
は双曲型と言う。双曲型平衡点ヤコビアンの
2005527034.tif 000067
個の固有値が正の実部を持てば，タイプ
2005527034.tif 000068
の平衡点と呼ぶ。双曲型平衡点に対し，対応するヤコビアンの全固有値の実部が負であれば，（漸近的に）安定平衡点，対応するヤコビアンの固有値の実部が正であれば不安定平衡点であることが示される。タイプ双曲型平衡点
2005527034.tif 000069
に対し，それの安定および不安定多様体
2005527034.tif 000070
は以下に定義される。
【００４５】
【数１３】
2005527034.tif 000071
【００４６】
ここで，
2005527034.tif 000072
と
2005527034.tif 000073
の次元はそれぞれ
2005527034.tif 000074
と
2005527034.tif 000075
である。
2005527034.tif 000076
内からスタートした(5-7)の全ての軌道が全ての
2005527034.tif 000077
において
2005527034.tif 000078
内に残れば，
2005527034.tif 000079
の集合
2005527034.tif 000080
は(5-7)の不変集合と呼ばれる。システムの全軌道が平衡点の１つに収束すれば，動的システムは完全安定と呼ばれる。
安定平衡点
2005527034.tif 000081
のスタビリティーリージョン（吸引域）は，軌道が全て収束する全ての点の集合であり以下に定義される。
【００４７】
【数１４】
2005527034.tif 000082
【００４８】
安定平衡点
2005527034.tif 000083
の準スタビリティーリージョンは以下に定義される。
【００４９】
【数１５】
2005527034.tif 000084
【００５０】
ここで，
2005527034.tif 000085
はスタビリティーリージョン
2005527034.tif 000086
の閉包，
2005527034.tif 000087
は
2005527034.tif 000088
の内点である。幾何学的観点から
2005527034.tif 000089
と
2005527034.tif 000090
は開集合，不変集合，パス結合集合，更にこれらは
2005527034.tif 000091
に微分同相である。
【００５１】
上述の２つの定理と以下の定理[3]は，条件(LC1)から(LC3)を満足する関連した非線形動的システム(5-7)を利用することにより，無制約連続最適化問題(4-1)を解くため，本発明において開発された動的方法の理論的原理を示す。
定理5-3：     条件(LC1)を満足する(5-7)により述べられる非線形動的システムを考える。
2005527034.tif 000092
を
2005527034.tif 000093
の準スタビリティーリージョン，
2005527034.tif 000094
を動的分解点とする。
2005527034.tif 000095
上の平衡点の安定多様体と不安定多様体が横断性条件を満たせば，次のような(5-1)の別のただ１つの安定平衡点
2005527034.tif 000096
が存在する。
【００５２】
(1)
2005527034.tif 000097
は
2005527034.tif 000098
に関する動的分解点である，かつ
(2)
2005527034.tif 000099
かつ
2005527034.tif 000100
である。
ここで，動的分解点は非線形動的システム(5-7)の準スタビリティーバウンダリー上のタイプ１平衡点であり，
2005527034.tif 000101
は動的分解点
2005527034.tif 000102
の不安定多様体である。
【００５３】
５．１  ハイブリッド局所探索法
局所最適解を確実に見つけるために，軌道ベース法と任意の効果的な局所探索法の結合による，ハイブリッド局所探索法を開発する。ハイブリッド局所探索法は本発明で開発された動的方法と組み合わされるであろう。
【００５４】
初期点からスタートする無制約連続最適化問題(4-1)のための，確実に局所最適解を得るためのハイブリッド局所探索法を以下に示す。
仮定：初期点
2005527034.tif 000103
が与えられる。
目的：無制約連続最適化問題(4-1)の局所最適解を確実に計算する。
ステップ１．  初期点
2005527034.tif 000104
からスタートし，効果的な局所探索アルゴリズムを無制約連続最適化問題(4-1)に適用する。
ステップ２．  局所探索法アルゴリズムが局所最適解に収束すれば，ストップする。そうでなければ，次のステップに進む。
ステップ３．  初期点
2005527034.tif 000105
からスタートし最終点を得るため数ステップ，関連する非線形動的システム(5-7)を積分する。初期点として最終点をセットし，ステップ１へ進む。
【００５５】
５．２  出口点（ＥＰ）の計算方法
無制約連続最適化問題(4-1)の局所最適解
2005527034.tif 000106
（すなわち，関連した非線形動的システム(5-7)の安定平衡点(s.e.p.)），そしてs.e.p.からスタートする予め定義された探索軌道が与えられる時，最適化問題(4-1)に関連した非線形動的システム(5-7)の出口点計算の方法を開発する。これを以下に示す。
仮定： 局所最適解
2005527034.tif 000107
，予め定義された探索経路と関連した非線形動的システム(5-7)を与える。
目的： 予め定義された探索経路と動的システム(5-7)のs.e.p.に関する出口点(EP)を見つける。
既知の局所最適解
2005527034.tif 000108
からスタートし，予め定義された探索経路に沿った最適化問題(4-1)の目的関数のはじめの局所最大値である，述べられた出口点を計算するため，予め定義された探索経路にそって動く。
出口点計算のための別の方法：       
2005527034.tif 000109
からスタートとした探索経路に沿って移動し，時間ステップ毎に探索経路と非線形動的システム(5-7)のベクトル場の偏差の内積を計算する。内積の符号が正から負へ変わった時，インターバル
2005527034.tif 000110
と呼ぶが，時刻
2005527034.tif 000111
における探索経路の点，もしくは時刻
2005527034.tif 000112
における探索経路の点が出口点を近似することに使うことが出来る。
【００５６】
５．３  動的分解点（ＤＤＰ）の計算方法
無制約連続最適化問題(4-1)の局所最適解
（すなわち，関連した非線形動的システム(5-7)の安定平衡点(s.e.p.)）そして，s.e.p.からスタートする予め定義された探索軌道が与えられる時，(5-7)のs.e.p.でもある局所最適解
2005527034.tif 000113
と予め定義された探索経路に関する関連する非線形動的システム(5-7)のＤＤＰを計算するための方法，ここで動的分解点（ＤＤＰ）計算のための方法とよぶ，を開発することを以下に示す。
仮定： 最適化問題(4-1)の局所最適解
2005527034.tif 000114
，予め定義された探索経路，そして関連した非線形動的システム(5-7)を与える。
目的： 予め定義された探索経路と局所最適解に関連する動的分解点（ＤＤＰ）を見つける。
【００５７】
ステップ１．  既知の最適解
2005527034.tif 000115
からスタートし，システム(5-7)の
2005527034.tif 000116
の準スタビリティーリージョンの出口点を計算するため，予め定義された探索経路
2005527034.tif 000117
に沿って動く。出口点を
2005527034.tif 000118
とする。
ステップ２．  
2005527034.tif 000119
からスタートし，以下のステップにより最少距離点（ＭＤＰ）を計算する。
(i)関連した非線形動的システム(5-7)を数ステップ積分する。最終点を現在の出口点とする。
(ii)現在の出口点と局所最適解
2005527034.tif 000120
をつなぐ線を引き，先に述べた現出口点と
2005527034.tif 000121
から始まるすでに引かれた線上の目的関数のはじめの局所最大点である修正出口点を入れ替え，この修正出口点を出口点
2005527034.tif 000122
に割り当てる。
(iii)ステップ(i)と(ii)を，ステップ(ii)で得られた先に述べられた現出口点ベクトル場(5-7)のノルムが閾値より小さくなる，すなわち
2005527034.tif 000123
まで繰り返す。そして，述べられた点は最少距離点（ＭＤＰ）
2005527034.tif 000124
である。
ステップ３．初期推定値としての述べられたＭＤＰ
2005527034.tif 000125
を用い，システム(5-7)の述べられたベクトル場
2005527034.tif 000126
の非線形代数方程式の集合を解く。解は
2005527034.tif 000127
と述べられた探索経路
2005527034.tif 000128
に関するＤＤＰ
2005527034.tif 000129
である。
【００５８】
５．４  別の局所最適解を見つけるためのＥＰベース法
最適化問題(4-1)のための，本発明は既知の局所最適解からスタートする局所最適解探索の出口点ベース（ＥＰベース）法を開発する。
仮定：連続最適化問題(4-1)の局所最適解
2005527034.tif 000130
を与える。
目的：連続最適化問題(4-1)の新しい局所最適解を見つける。
ステップ１．  既知の局所最適解
2005527034.tif 000131
からスタートし，ＥＰ
2005527034.tif 000132
を計算するため出口点（ＥＰ）計算の方法を非線形動的システム(5-7)に適用する。
ステップ２．  
2005527034.tif 000133
をセットする。ここで，εは小さな数である。
ステップ３．  
2005527034.tif 000134
から出発し，効果的な（ハイブリッド）局所探索法が過渡探索を上回るインターフェース点
2005527034.tif 000135
に到達するまで，対応したシステム軌道を得るための非線形ダイナミカルシステム(5-7)を積分することにより過渡探索を導く。
ステップ４．  インターフェース点
2005527034.tif 000136
からスタートし，ステップ３で選択された（ハイブリッド）局所探索法を隣接した局所最適解を見つけるため適用する。
【００５９】
５．５  別の局所最適解探索のＤＤＰベース法
最適化問題(4-1)に対し，本発明は既知の局所解からスタートし，局所最適解を見つけるためのＤＤＰベース法を開発する。
仮定：連続最適化問題(4-1)の局所最適解
2005527034.tif 000137
を与える。
目的：連続最適化問題(4-1)の新しい局所最適解を見つける。
ステップ１．  既知の局所最適解
2005527034.tif 000138
からスタートし，分解点を計算するための方法をＤＤＰ
2005527034.tif 000139
を計算するためシステム(5-7)に適用する。
ステップ２．  
2005527034.tif 000140
をセットする。ここで，εは小さな数である。
ステップ３．  
2005527034.tif 000141
から出発し，効果的な（ハイブリッド）局所探索法が過渡探索を上回るインターフェース点
2005527034.tif 000142
に到達するまで，対応したシステム軌道を得るための動的システム(5-7)を積分することにより過渡探索を導く。
ステップ４．  インターフェース点
2005527034.tif 000143
からスタートし，ステップ３で選択された（ハイブリッド）局所探索法を隣接した局所最適解を見つけるため適用する。
【００６０】
５．６  全ティア１局所最適解探索の動的方法
方法を示す前に，はじめに最適化問題(4-1)の連続解空間中（すなわち，関連した非線形動的システム(5-7)の状態空間）の既知の局所最適解に関するティア１局所最適解（すなわち，安定平衡点）とティアＮ局所最適解（すなわち，安定平衡点）の定義を以下に示す。
ティア１局所最適解： 関連した非線形動的システム(5-7)の
2005527034.tif 000144
のスタビリティーリージョンの閉包と
2005527034.tif 000145
のスタビリティーリージョンの閉包が互いに交差すれば，最適化問題(4-1)の局所最適解
2005527034.tif 000146
は既知の局所最適解
2005527034.tif 000147
のティア１局所最適と言われる。
ティアＮ局所最適解： 
2005527034.tif 000148
が次の２つの条件を満たせば，最適化問題(4-1)の局所最適解
2005527034.tif 000149
は既知の局所最適解
2005527034.tif 000150
のティアＮ（Ｎ＞１）局所最適解と言われる。
(i)    
2005527034.tif 000151
は
2005527034.tif 000152
のティア（Ｎ−２）もしくはティア（Ｎ−１） 局所最適解ではない。
(ii)   
2005527034.tif 000153
は
2005527034.tif 000154
の１つのティア（Ｎ−１） 局所最適解のティア１局所最適解である
2005527034.tif 000155
のティア０局所最適解は
2005527034.tif 000156
自身であることは明らかである。
2005527034.tif 000157
最適化問題(4-2),(4-3),(4-4)のティア１とティアＮ局所最適解は同様に定義される。
最適化問題(4-1)に対し，本発明は全てのティア１最適解を見つけるための方法の２つのグループを開発する。始めのグループはＥＰベース法で，２つめのグループはＤＤＰベースである。
【００６１】
ＥＰベース法
仮定：連続最適化問題(4-1)の局所最適解
2005527034.tif 000158
を与える。
目的：連続最適化問題(4-1)の
2005527034.tif 000159
の全ティア１局所最適解を見つける。
ステップ１．  ティア１局所最適解の集合
2005527034.tif 000160
を初期化し、
2005527034.tif 000161
での探索経路
2005527034.tif 000162
の集合を定義する。
2005527034.tif 000163
とセットする。
ステップ２．
2005527034.tif 000164
からスタートする全ての探索経路
2005527034.tif 000165
に対し，対応する局所最適解を計算する。
(i)    別の局所最適解を見つけるため，ＥＰベース法をシステム(5-7)に適用する。局所最適解が見つければ，
2005527034.tif 000166
とし次のステップへ進む。そうでなければ，ステップ(iii)へ進む。
(ii)   
2005527034.tif 000167
が既に見つけられていないか，すなわち
2005527034.tif 000168
であるか確認する。見つけられていなければ，
2005527034.tif 000169
をセットする。
・  i=i+1とセットする。
・  i>mとなるまでステップ(i)から(iii)を繰り返す。
ステップ３．  
2005527034.tif 000170
のティア１局所最適解の集合
2005527034.tif 000171
を出力する。
【００６２】
ＤＤＰベース法
仮定：連続最適化問題(4-1)の局所最適解
2005527034.tif 000172
を与える。
目的：連続最適化問題(4-1)の
2005527034.tif 000173
の全ティア１局所最適解を見つける。
ステップ１．  動的分解点の集合
2005527034.tif 000174
とティア１局所最適解の集合
2005527034.tif 000175
を初期化する。
ステップ２．  
2005527034.tif 000176
, i=1,2,…,mj
での探索経路
2005527034.tif 000177
の集合を定義する。。i=1とセットする。
ステップ３．  
2005527034.tif 000178
からスタートする全ての探索経路
2005527034.tif 000179
に対し，次のステップを用いて対応する局所最適解を計算する。
(i)    対応したＤＤＰを見つけるため，動的分解点（ＤＤＰ）を計算するための方法をシステム(5-7)に適用する。ＤＤＰが見つければ，次のステップへ進む。そうでなければ，ステップ(vi)へ進む。
(ii)   見つけられたＤＤＰを
2005527034.tif 000180
とし，集合
2005527034.tif 000181
に属するか，すなわち，
2005527034.tif 000182
であるかチェックする。もしそうであればステップ(vi)へ，そうでなければ
2005527034.tif 000183
とセットし，次のステップへ進む。
(iii)  
2005527034.tif 000184
をセットする。ここで，εは小さな数である。
(iv)   
2005527034.tif 000185
から出発し，効果的なハイブリッド局所探索法が過渡探索を上回るインターフェース点
2005527034.tif 000186
に到達するまで，対応したシステム軌道を得るための動的システム(5-7)を積分することにより過渡探索を導く。
・  インターフェース点
2005527034.tif 000187
からスタートし，ステップ(iv)で選択されたハイブリッド局所探索法を，
2005527034.tif 000188
に関連した局所最適解
2005527034.tif 000189
を見つけるため適用する。そして
2005527034.tif 000190
をセットする。
(vi)   i=i+1をセットする。
(v)    i>mjとなるまでステップ(i)から(vi)を繰り返す。
ステップ４．  
2005527034.tif 000191
のティア１局所最適解の集合
2005527034.tif 000192
を出力する。
【００６３】
５．７  全局所最適解探索の方法
最適化問題(4-1)に対し，本発明は全ての局所最適解を見つける２つの動的方法を開発する。はじめの方法はＥＰベース法で，一方，２つめの方法はＤＤＰベース法である。
【００６４】
ＥＰベース法
仮定：連続最適化問題(4-1)の初期点
2005527034.tif 000193
を与える。
目的：(i)連続最適化問題(4-1)の全ての局所最適解を見つける。
(ii)連続最適化問題(4-1)の大域最適解を見つける。
ステップ１．  
2005527034.tif 000194
からスタートし，局所最適解
2005527034.tif 000195
を見つけるため効果的な（ハイブリッド）探索法を適用する。
ステップ２．  j=0をセットする。局所最適解の集合
2005527034.tif 000196
とティアｊ局所最適解の集合
2005527034.tif 000197
を初期化する。
ステップ３．  ティア（ｊ＋１）局所最適解の集合
2005527034.tif 000198
を初期化する。
ステップ４．  
2005527034.tif 000199
中の各局所最適解
2005527034.tif 000200
に対し，全ティア１局所最適解を見つける。
(i)    
2005527034.tif 000201
での探索経路
2005527034.tif 000202
の集合を定義し、i=1にセットする。
(ii)   
2005527034.tif 000203
からスタートする全探索経路
2005527034.tif 000204
に対する別の局所最適解を見つけるためＥＰベース法を適用する。もし局所最適解が見つかれば，それを
2005527034.tif 000205
とし，次のステップへ進む。そうでなければ，ステップ(iv)へ進む。
(iii)  
2005527034.tif 000206
が既に見つかったか，すなわち
2005527034.tif 000207
であるかチェックする。もしそれが新しい局所最適解であれば，
2005527034.tif 000208
と
2005527034.tif 000209
をセットする。
(iv)   i=i+1とセットする。
(v)    i>mjとなるまで，ステップ(ii)から(iv)まで繰り返す。
ステップ５．  全ての新しく計算された局所最適解の集合
2005527034.tif 000210
が空であれば，ステップ６へ続く。そうでなければ，j=j+1とセットし，ステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000211
を出力し，
2005527034.tif 000212
の集合から集合
2005527034.tif 000213
の対応した目的関数値の比較と最も小さな値を持つものを選択することにより最良の最適解を特定する。そしてそれを大域最適解として出力する。
【００６５】
ＤＤＰベース法
仮定：初期点
2005527034.tif 000214
を与える。
目的：(i)連続最適化問題(4-1)の全ての局所最適解を見つける。
(ii)連続最適化問題(4-1)の大域最適解を見つける。
ステップ１．  
2005527034.tif 000215
からスタートし，局所最適解
2005527034.tif 000216
を見つけるための効果的なハイブリッド探索法を適用する。
ステップ２．  j=0をセットする。局所最適解の集合
2005527034.tif 000217
，ティアｊ局所最適解の集合
2005527034.tif 000218
，そして，見つけた動的分解点の集合
2005527034.tif 000219
を初期化する。
ステップ３．  ティア（ｊ＋１）局所最適解の集合
2005527034.tif 000220
を初期化する。
ステップ４．  
2005527034.tif 000221
中の局所最適解
2005527034.tif 000222
に対し，全ティア１局所最適解を見つける。
(i)    
2005527034.tif 000223
での探索経路
2005527034.tif 000224
の集合を定義し、i=1にセットする。
(ii)   
2005527034.tif 000225
からスタートする全探索経路
2005527034.tif 000226
に対する、対応する動的分解点（ＤＤＰ）を見つけるため，非線形システム(5-7)へ効果的な方法を適用する。ＤＤＰが見つかれば次のステップへ進み，そうでなければ，ステップ(viii)へ進む。
(iii)  見つけられたＤＤＰを
2005527034.tif 000227
とし，それが集合
2005527034.tif 000228
に属するか、すなわち
2005527034.tif 000229
であるかをチェックする。もし属せば，ステップ(viii)へ進み，そうでなければ，
2005527034.tif 000230
をセットし、次のステップへ進む。
(iv)   
2005527034.tif 000231
をセットする。ここでεは小さな数である。
(v)    
2005527034.tif 000232
からスタートし，効果的なハイブリッド局所探索法が過渡探索を上回るインターフェース点
2005527034.tif 000233
に上記過渡探索が到達するまで，非線形動的システム(5-7)を積分することにより上記過渡探索を導き、対応したシステム軌道を得る。
(vi)   インターフェース点
2005527034.tif 000234
からスタートし，ステップ(v)で選択された効果的なハイブリッド局所探索法を、
2005527034.tif 000235
で示される対応した局所最適解を見つけるため適用する。
(vii)  
2005527034.tif 000236
がすでに見つけられているか，すなわち
2005527034.tif 000237
であるかチェックする。もしそれが新しい局所最適解であれば，
2005527034.tif 000238
【００６６】
をセットする。
(viii) i=i+1をセットする。
(ix)   i>mjkとなるまでステップ(ii)から(viii)を繰り返す。
ステップ５．  全ての新しく計算された局所最適解の集合
2005527034.tif 000239
が空であれば，ステップ６へ続く。そうでなければ，j=j+1とセットし，ステップ3へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000240
を出力し，
2005527034.tif 000241
の集合から、集合
2005527034.tif 000242
の対応した目的関数値の比較と最も小さな値を持つものを選択することにより最良の最適解を特定する。そしてそれを大域最適解として出力する。
【００６７】
６．無制約離散最適化問題解法の動的方法
本節では，無制約離散最適化問題(4-3)を解くための動的方法を示す。
与えられた例(4-3)の大域最適解を見つける作業は非常に難しい。しかし，近傍に改善解がないという意味で，最善な局所最適解探索は通常可能である。この目的のため，特定できる近傍が必要である。近傍関数
2005527034.tif 000243
は，各解
2005527034.tif 000244
に対し、ある意味において
2005527034.tif 000245
近傍の解の集合
2005527034.tif 000246
に対し定義する写像である。集合
2005527034.tif 000247
は解
2005527034.tif 000248
の近傍と呼ばれる。全ての
2005527034.tif 000249
に対し
2005527034.tif 000250
であれば，
2005527034.tif 000251
は近傍
2005527034.tif 000252
に関する局所最適解（もしくは文章中で
2005527034.tif 000253
と理解される時はいつでも，単に局所最適解）という。
【００６８】
(4-3)の形をした多くの離散最適化問題はＮＰ困難である。一般にＮＰ困難問題は多項式境界計算時間内に最適に解くことができないと言われている。(4-3)の形をした離散最適化問題を解くため３つのアプローチが可能である。はじめの１つは多大な計算努力を要し，最適解を保証する列挙法である。別の方法は最適解に近い最適解探索のための多項式時間を有する近似アルゴリズムを使う。残りのアプローチは解の質もしくは計算時間の保証がない，ヒューリスティック技術，局所探索もしくは局所修正とよばれる，反復修正技術のいくつかのタイプを用いる。
【００６９】
局所探索は通常，多くの離散最適化問題を解くための選択のアプローチである。問題のサイズもしくは問題構造洞察の欠如のような因子は，通常，実離散最適化問題への列挙法の適用を禁止する。一方，多項式時間近似アルゴリズムは，性能の限界にかかわらず，不満足な解を与えるだろう。しかしながら，局所探索はロバストなアプローチを，合理的な時間内に，合理的なもしくは高品質であろう解を得るために，実問題に与える。局所探索アルゴリズムの基本的なバージョンは，任意の初期解からスタートし，コスト関数の（最小化のケースにおいて）より低い値の解のための近傍を探索する反復修正である。このような解が見つかれば，現在の解を交換し，探索を続ける。そうでなければ，現在の解は局所最適解であり，局所探索を終了する。
【００７０】
次に離散最適化問題(4-3)のための反復修正とよばれる局所探索アルゴリズムの基本的なバージョンを示す。
【００７１】
反復局所修正（局所探索）アルゴリズム
離散最適化問題(4-3)に対し，局所探索アルゴリズムは現在の解から進み，次のステップにより
2005527034.tif 000254
の周りの適当な近傍
2005527034.tif 000255
において，より上位の解を探すことにより
2005527034.tif 000256
を修正しようとする。
ステップ１．  初期化：初期点
2005527034.tif 000257
を選び，反復カウンタをk=1とする。
ステップ２．  修正：局所修正集合
2005527034.tif 000258
を考慮する。ここで，
2005527034.tif 000259
【００７２】
は
2005527034.tif 000260
まわりの近傍である。集合が空であれば終了し，
2005527034.tif 000261
が近傍
2005527034.tif 000262
の局所最小値であり，そうでなければ，
2005527034.tif 000263
として集合の１つを選び，k=k+1と増加させ，このステップを繰り返す。
局所探索アルゴリズムに関連した２つの問題がある。
(i)近傍
2005527034.tif 000264
の定義。
(ii)集合
2005527034.tif 000265
から
2005527034.tif 000266
を選択するメカニズム。
【００７３】
高品質の局所最適解を得るための効果的な近傍関数を見つける作業は，局所探索アルゴリズムの大きなチャンレンジである。効果的な近傍関数を見つける一般的な方法は現在ない。同じ問題に対してさえ，いくつかの有効な近傍関数があり，近傍の異なった定義は同じ局所探索アルゴリズムから異なった結果を導く。良い近傍関数のデザインはしばしば，研究問題の離散構造の優位となり，標準的に問題に依存する。問題(i)に言及すると，明らかに，適当な離散近傍は，現在解のいくつかの離散変種を含むに十分大きく，実用計算内に調査されるに十分小さい。表記上の簡単化のため，全ての変数は0-1制約と仮定する。
・     単位近傍：与えられた解
2005527034.tif 000267
に対し，
2005527034.tif 000268
の単位近傍は一度に
2005527034.tif 000269
の補完成分を形成により与えられる。すなわち，
【００７４】
【数１６】
2005527034.tif 000270
【００７５】
・     
2005527034.tif 000271
変化近傍：
2005527034.tif 000272
変化近傍は
2005527034.tif 000273
解成分に至る補完を許すことにより単位近傍を生成する。特に，
【００７６】
【数１７】
2005527034.tif 000274
【００７７】
・     ペア関連相互交換近傍：ペア関連相互交換近傍は２つの２進成分を一度に交換する，しかし補完においてである。
【００７８】
【数１８】
2005527034.tif 000275
【００７９】
・     
2005527034.tif 000276
相互交換近傍：
2005527034.tif 000277
相互交換近傍は解の
2005527034.tif 000278
値まで一度に交換する。しかし補完においてである。
【００８０】
【数１９】
2005527034.tif 000279
【００８１】
多様性のため，近傍関数は探索過程において切り替えることができる。
本発明において，以下，近傍の３つの定義も使う。
即近傍：
2005527034.tif 000280
と
2005527034.tif 000281
の差が
2005527034.tif 000282
のように表される場合のみ，点
2005527034.tif 000283
は即近傍内にあると言われる。ここで，ただし
2005527034.tif 000284
のみが１で，他はゼロである。従って，点
2005527034.tif 000285
とその即近傍
2005527034.tif 000286
の差は１である。
一方向拡張近傍（ＯＷＥＮ）：
2005527034.tif 000287
と
2005527034.tif 000288
の差，すなわち
2005527034.tif 000289
もしくは
2005527034.tif 000290
が
2005527034.tif 000291
のように表される場合のみ，点
2005527034.tif 000292
は一方向拡張近傍内にあると言われる。ここで，
2005527034.tif 000293
は０もしくは１である。
フル近傍：
2005527034.tif 000294
と
2005527034.tif 000295
の差，すなわち
2005527034.tif 000296
もしくは
2005527034.tif 000297
が
2005527034.tif 000298
のように表される場合のみ，点
2005527034.tif 000299
はフル近傍内にあると言われる。ここで，
2005527034.tif 000300
は０，１もしくは−１である。
【００８２】
点が即近傍に関する最小目的関数を持てば，その点は離散空間S内の即近傍に関する局所最適解である。点が一方向拡張近傍に関する最小目的関数を持てば，その点は離散空間S内の一方向拡張近傍に関する局所最適解である。点がフル近傍に関する最小目的関数を持てば，その点は離散空間S内のフル近傍に関する局所最適解である。次の事実は上の定義の結果である。
【００８３】
事実１：    点
2005527034.tif 000301
が一方向拡張近傍に関する局所最適解であれば，その点は即近傍の局所最適解である。
事実２：    点
2005527034.tif 000302
がフル近傍に関する局所最適解であれば，その点は即近傍の局所最適解と一方向拡張近傍の局所最適解である。
事実３：    無制離散最適化問題(4-3)に対し，
2005527034.tif 000303
の大域最適解はフル近傍に関する局所最適解である。
離散最適化問題(4-3)に対し，習慣により近傍は即近傍と呼ばれる。局所最適解は即近傍に関する局所最適解と呼ばれる。
局所探索アルゴリズムに関連する問題(ii)解決のため，
2005527034.tif 000304
を定義するための（すなわち，局所探索のステップ２の選択ルール）２つの一般的な反復修正局所探索アルゴリズムがある。
【００８４】
最良近傍探索法
最良近傍探索法は
2005527034.tif 000305
としての目的関数内に最急降下方向に近傍内に点を常に選択する。この方法は局所最適解を得る決定論的方法である。
より良い近傍探索法
2005527034.tif 000306
としての最急降下方向を伴う近傍内の点を選択する変わりに，より良い近傍探索法は
2005527034.tif 000307
としての目的関数内の降下方向を移動する近傍内の始めの点をとる。明らかにより良い近傍探索法は速い。しかしながら，近傍内の順列点の依存は検討される。この局所探索法はただ1つの結果に行きつかないであろう。特に，
2005527034.tif 000308
が局所最適解から遠い時。この局所探索法は確率的性質であることは明らかである。
【００８５】
ここ３０年以上，多くの局所探索アルゴリズムは開発され，離散最適化問題の多くに適用されてきた。これらのアルゴリズムの多くは特定的であり，あるタイプの離散最適化問題に適合される。さらに，それら方法の多くは局所最適解の探索のみに有効であり，大域最適解探索には有効でない。これらの探索プロセスの間，これらのアルゴリズムは通常，局所最適解にトラップされ，別の局所最適解への移動はできない。この欠点を改善し，しかし，近傍探索のパラダイム（方法論）を維持するため，いくつかの修正が提案されてきたが大きな成功例はない。局所探索の単純な拡張は異なったスタート解を用い，局所探索アルゴリズムを多数回実行し，最終解として最良な解をキープする。このマルチ・スタートアプローチに関する大きな成果は報告されていない。
【００８６】
反復修正局所探索アルゴリズムの欠点は，局所最適解から脱出するため探索プロセスを許すいくつかのメカニズムを導入することにより，より良い解を見つけるため設計された多くのより洗練された局所探索アルゴリズムの開発を動機つけた。基礎となる'脱出'メカニズムは局所最適解からの脱出を可能とするため，コスト悪化近傍を許容する適当な探索戦略を使う。シミュレーテッド・アニ−リング，遺伝的アルゴリズム，タブ・サーチ，ニューラル・ネットワークなどのいくつかの洗練された局所探索アルゴリズムがある。
【００８７】
しかしながら，これらの洗練された局所探索アルゴリズムは，他の問題において，徹底的な計算努力を要求し，大域的な最適解をみつけることができないことが，多くの研究の中に見つけられた。
【００８８】
本発明において，一般離散最適化問題の全ての局所最適解を見つけるための，決定論的な新しいシステマティックな方法を開発する。加え，無制約離散最適化問題(4-3)を解くための２つの動的方法が，本発明において，開発される。
・閉形式目的関数を有する無制約離散最適化問題解法の動的方法
・ブラックボックス目的関数を有する無制約離散最適化問題解法の動的方法
本発明において，２つの異なったアプローチを，すなわち，離散ベース動的アプローチと連続ベース動的アプローチを，ベースとしたいくつかの動的方法を開発する。加え，いくつかの効果的な方法が，大域的な最適解のための探索における次の２つの重要かつチャレンジな問題を記述するため，本発明にて，開発される。
(i)どのように効果的に，局所最適解から移動（脱出）し，他の局所最適解へ移動するか
(ii)どのようにすでに探索した局所最適解への再探索を防ぐか
【００８９】
６．１  離散ベース動的アプローチ
本節では，無制約離散最適化問題(4-3)を解くための離散ベース動的アプローチを開発する。
無制約離散最適化問題(4-3)を解くため，自律離散方程式の集合により記述される次の関連した非線形離散動的システムを考慮する。
【００９０】
【数２０】
2005527034.tif 000309
【００９１】
ここで，
2005527034.tif 000310
は離散状態空間である。方程式(6-5)は写像もしくは反復として知られている。このような写像は
2005527034.tif 000311
が
2005527034.tif 000312
の項で陽的形式で与えられるため陽的であると呼ばれる。
2005527034.tif 000313
からスタートする(6-5)の解はシステム軌道と呼ばれる。
2005527034.tif 000314
であれば，点
2005527034.tif 000315
は離散動的システム(6-5)の平衡点とよばれる。もしシステム軌道が平衡点に十分近い初期点
2005527034.tif 000316
の選択により，平衡点の任意の近傍内に残れば平衡点は安定である。
【００９２】
全局所最適解の位置を特定するために実行される任意の軌道が非線形離散動的システム次の十分条件を提案する。
(LD1)- 非線形動的システム(6-5)の全ての軌道が収束し，平衡点の１つに収束する。そして，
(LD2)- 離散最適化問題の目的関数は離散動的システムの全ての軌道に沿って減少する。
(LD3)- 離散最適化問題(4-3)の全ての局所最適解は(6-5)の安定平衡点であり，その逆も成立する。
離散最適化問題(4-3)の全ての局所最適解は関連した離散動的システム(6-5)の任意の動的軌道を経由してシステマティックに計算される。これらの局所最適解から大域最適解は容易に得られる。
【００９３】
６．１．１  ハイブリッド局所探索法
初期点からスタートする(4-3)で記述される離散最適化問題の局所最適解を計算するための離散ベースハイブリッド局所探索法を以下に示す。
仮定：初期値
2005527034.tif 000317
を与える。
目的：確実に局所最適解を計算する。
ステップ１．  初期点
2005527034.tif 000318
から開始する効果的な反復修正局所探索アルゴリズムを離散最適化問題(4-3)に適用する。
ステップ２．  局所探索アルゴリズムが局所最適解へ収束すれば，停止。そうでなければ，次のステップへ進む。
ステップ３．  最終点を得るため探索過程を数ステップ継続し
2005527034.tif 000319
から開始する最良近傍探索法を使用する。最終点を初期値としステップ１へ進む。
【００９４】
６．１．２  出口点計算方法
局所最適解
2005527034.tif 000320
から開始する探索経路の出口点を計算する方法を示す。
2005527034.tif 000321
を経由する探索経路
2005527034.tif 000322
は
2005527034.tif 000323
を伴う変数tでパラメータ付けられたカーブであり，全ての時間tに対する探索空間（すなわち，解空間）内にある。
【００９５】
既知の局所最適解から開始する最適化問題(4-3)に関連する離散動的システムの出口点を計算する方法，出口点計算のための離散ベース法と名づけられるが，を以下に示す。
仮定： 局所最適解
2005527034.tif 000324
，予め定義された探索経路，関連した離散動的システム(6-5)を仮定する。
目的： 予め定義された探索経路に関する出口点(EP)とシステム(6-5)の安定平衡点
2005527034.tif 000325
を見つける。
既知の局所最適解
2005527034.tif 000326
から開始し，予め定義された探索経路に沿って最適化問題(4-3)の目的関数の始めの局所最大値である述べられた出口点を検出するため，予め定義された探索経路に沿って動く。
【００９６】
６．１．３  ＤＤＰ計算のための離散ベース法
最適化問題(4-3)の局所最適解
2005527034.tif 000327
が与えられ，システム(6-5)の安定平衡点
2005527034.tif 000328
と次の予め定義された探索経路に関連した動的分解点(ＤＤＰ)計算のための離散ベース動的方法を開発する。
仮定：離散最適化問題(4-3)の局所最適解
2005527034.tif 000329
と予め定義された探索経路を与える。
目的：離散ダイナミカルシステム(6-5)の動的分解点(ＤＤＰ)を見つける。
ステップ１．  既知の局所最適解
2005527034.tif 000330
から開始し，出口点を計算するため，予め定義された探索経路に沿って動く。出口点は
2005527034.tif 000331
とする。
ステップ２．  
2005527034.tif 000332
から開始し，最良近傍探索法反復を１（前方）新しい点
2005527034.tif 000333
に適用する。
ステップ３．  直線修正手順とＤＤＰ計算を実施する。
(i)    
2005527034.tif 000334
と
2005527034.tif 000335
の直線を形成する。
(ii)   ベクトル
2005527034.tif 000336
と
2005527034.tif 000337
の表現が可能であれば，(ii)(a)を実施。そうでなければ，他を実施。
(a)    ２つのベクトル
2005527034.tif 000338
と
2005527034.tif 000339
の間の角度
2005527034.tif 000340
を計算する。
2005527034.tif 000341
が０度もしくは１８０度に近ければ，
2005527034.tif 000342
はＤＤＰであり，過程を停止する。そうでなければ，次のステップへ進む。
（ステップ(a)の別の方法）現在の
2005527034.tif 000343
をアップデートされた探索経路上に乗せるため探索経路をアップデートする。３点
2005527034.tif 000344
がアップデートされた探索経路上にあるかチェックする。そうであれば，
2005527034.tif 000345
はＤＤＰであり過程を停止する。そうでなければ，次のステップへ進む。
(iii)  
2005527034.tif 000346
を
2005527034.tif 000347
から開始する直線に沿った目的関数の始めの局所最大値である点
2005527034.tif 000348
に修正する。
2005527034.tif 000349
が
2005527034.tif 000350
に非常に近ければ，
2005527034.tif 000351
はＤＤＰであり過程を停止する。そうでなければ，次のステップへ進む。
ステップ４．  
2005527034.tif 000352
を出口点，すなわち，
2005527034.tif 000353
【００９７】
とし，ステップ２へ進む。
【００９８】
６．１．４  他の局所最適解探索のためのＥＰベース法
最適化問題(4-3)の局所最適解
2005527034.tif 000354
が与えられ，既知の局所最適解から開始する新しい局所最適解を見つけるための以下の離散ベース出口点ベース法を開発する。
仮定：最適化問題(4-3)の局所最適解
2005527034.tif 000355
と予め定義された探索経路を与える。
目的：最適化問題(4-3)の新しい局所最適解を見つける。
ステップ１．  
2005527034.tif 000356
から開始し予め定義された探索経路に沿って動き，出口点(ＥＰ)計算のための離散ベース法を非線形動的システム(6-5)に適用する。ＥＰ，
2005527034.tif 000357
をみつければ，次のステップへ進む。そうでなければ，過程を停止する。
ステップ２．  既知の出口点
2005527034.tif 000358
から開始し，予め定義された探索経路に沿って，
2005527034.tif 000359
から一段階，新しい点
2005527034.tif 000360
へ移動する。（もしくは，表現が可能であれば，
2005527034.tif 000361
を使用する。ここで，εは小さな数である。）
ステップ３．  
2005527034.tif 000362
から開始する最良近傍探索法を，効果的な離散ベース（ハイブリッド）局所探索法が最良近傍探索法より性能が優れているインターフェース点
2005527034.tif 000363
を得るため適用する。
ステップ４．  インターフェース点
2005527034.tif 000364
から開始し，効果的なハイブリッド局所探索法，ステップ３で選択された，を近傍の局所最適解を見つけるため適用する。
【００９９】
６．１．５  別の局所最適解探索のためのＤＤＰベース法
最適化問題(4-3)のため，本発明は既知の解から開始する局所最適解探索のためのＤＤＰベース法開発する。このＤＤＰベース法は，決定論的であり，以下に示す。
仮定：離散最適化問題(4-3)の局所最適解
2005527034.tif 000365
と予め定義された探索経路を与える。
目的：予め定義された探索経路に関する最適化問題(4-3)の新しい局所最適解を見つける。
ステップ１．  
2005527034.tif 000366
から開始し予め定義された探索経路に沿って動き，動的分解点（ＤＤＰ）計算のための方法を適用する。ＤＤＰが見つからない場合は過程を停止する。そうでなければ，次のステップへ進む。
ステップ２．  既知のＤＤＰから開始し，最後の出口点
2005527034.tif 000367
の修正に使用されたアップデートされた探索経路に沿って
2005527034.tif 000368
から一段階，数反復回数，点
2005527034.tif 000369
へ動く。（もしくは表現が可能であれば，
2005527034.tif 000370
を使う，ここでεは小さな数）
ステップ３．  最良近傍探索法を
2005527034.tif 000371
から開始する関連した離散非線形動的システム(6-5)へ，効果的なハイブリッド局所探索法が最良近傍探索法より性能が優れているインターフェース点
2005527034.tif 000372
を得るため適用する。
ステップ４．  インターフェース点
2005527034.tif 000373
から開始し，効果的なハイブリッド局所探索法，ステップ３で選択された，を近傍の局所最適解を見つけるため適用する。
【０１００】
６．１．６  全ティア１局所最適解を見つける動的離散ベース法
最適化問題(4-3)に対し，既知の局所最適解から開始する，全ティア１局所最適解を見つける次の動的方法を開発する。
仮定：最適化問題(4-3)の局所最適解
2005527034.tif 000374
を与える。
目的：
2005527034.tif 000375
の全ティア１局所最適解を見つける。
ステップ１．  ティア１局所最適解の集合
2005527034.tif 000376
を初期化し，
2005527034.tif 000377
の探索経路の集合
2005527034.tif 000378
を定義する。i=1にセットする。
ステップ２．  
2005527034.tif 000379
から開始し，それぞれの探索経路
2005527034.tif 000380
に沿って動き，離散ベースＥＰベース法（もしくはＤＤＰベース法）を最適化問題(4-3)の局所最適解（すなわち，離散最適化問題(6-5)の安定平衡点）を見つけるため適用する。局所最適解が見つかれば，
2005527034.tif 000381
とし次のステップへ進む。そうでなければ，ステップ４へ進む。
ステップ３．  
2005527034.tif 000382
が既に見つかっているか，すなわち
2005527034.tif 000383
，であるかチェックする。見つかっていなければ，
2005527034.tif 000384
をセットする。
ステップ４．  i=i+1とセットする。
ステップ５．  i>mとなるまでステップ２からステップ４を繰り返す。
ステップ６．  
2005527034.tif 000385
のティア１局所最適解の集合
2005527034.tif 000386
を出力する。
【０１０１】
６．１．７  全局所最適解を見つける動的離散ベース法
与えられた初期点から開始する，離散最適化問題(4-3)の全ての局所最適解を見つける動的離散ベース法を以下に開発する。
仮定：初期点
2005527034.tif 000387
を与える。
目的：(i)離散最適化問題(4-3)の全局所最適解を見つける。
(ii)離散最適化問題(4-3)の大域最適解を見つける。
ステップ１．  
2005527034.tif 000388
から開始し，効果的な（ハイブリッド）探索法を局所最適解
2005527034.tif 000389
を見つけるために適用する。
ステップ２．  j=0をセットする。局所最適解の集合
2005527034.tif 000390
，ティアｊの局所最適解の集合
2005527034.tif 000391
を初期化する。
ステップ３．  ティア（ｊ＋１）の局所最適解の集合
2005527034.tif 000392
を初期化する。
ステップ４．  
2005527034.tif 000393
内の各局所最適解
2005527034.tif 000394
に対し，それのティア１局所最適解を見つける。
(i)    
2005527034.tif 000395
の探索経路
2005527034.tif 000396
の集合を定義する。i=1をセットする。
(ii)   
2005527034.tif 000397
から開始し，それぞれの探索経路
2005527034.tif 000398
に沿って動き，ＥＰベース法（もしくはＤＤＰベース法）を最適化問題(4-3)の局所最適解（すなわち，離散最適化問題(6-5)の安定平衡点）を見つけるため適用する。局所最適解が見つかれば，
2005527034.tif 000399
とし次のステップへ進む。そうでなければ，ステップ(iv)へ進む。
(iii)  
2005527034.tif 000400
が既に見つかったか，すなわち
2005527034.tif 000401
であるか確認する。見つかっていなければ，
2005527034.tif 000402
をセットする。
(iv)   i=i+1をセットする。
(v)    i>mjとなるまでステップ(ii)からステップ(iv)を繰り返す。
ステップ５．  全ての新しく計算された局所最適解の集合
2005527034.tif 000403
が空であれば，ステップ６を継続する。そうでなければ，j=j+1をセットし，ステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000404
を出力し，集合
2005527034.tif 000405
内の対応する目的関数値の比較により集合
2005527034.tif 000406
から大域最適解を特定し，最小値を有するものを選択する。これを探索した大域最適解として出力する。
【０１０２】
６．２．連続ベース動的アプローチ
本発明の具体化において，解析的かつ閉形式の目的関数を有する無制約離散最適化問題(4-3)を解くための連続ベース動的アプローチを使用した動的方法を開発する。動的方法の基本的なアイディアは等価な最適化問題を，はじめに連続状態空間内で解き，必要であれば次に離散状態空間内で解くことである。ブラックボックス形式の最適化問題(4-3)に対する連続ベースアプローチの適用可能性は条件付であり，以下の節で提示される。
【０１０３】
等価アプローチ
無制約離散最適化問題(4-3)をユークリッド空間内で定義された次の等価連続最適化問題への変換を見つけることを提案する。
【０１０４】
【数２１】
2005527034.tif 000407
【０１０５】
ここで
2005527034.tif 000408
はユークリッド空間
2005527034.tif 000409
で定義された連続関数，nはオリジナル状態空間Sの自由度の数である。変換は次のガイドラインを満たすことを提案する。
(G1)オリジナル最適化問題(4-3)と等価最適化問題(6-6)は同じ大域最適解を有する。（すなわち，
2005527034.tif 000410
が
2005527034.tif 000411
の大域最適解の場合のみ，
2005527034.tif 000412
は
2005527034.tif 000413
の大域最適解である。）
(G2)オリジナル最適化問題(4-3)と等価最適化問題(6-6)は，可能な限り多くの同じ局所最適解を有する。
【０１０６】
等価アプローチにおいて，等価非線形最適化問題(6-6)の大域最適解を経由して(4-3)の大域最適解を見つける。従って，(6-6)の最適化問題の大域最適解と全ての局所最適解を見つけるための開発技術は離散最適化問題(4-3)を解くことに適用可能である。
はじめに上述の２つのガイドラインを満たす変換を構築する技術を以下で開発する。
【０１０７】
変調器追加による変換
等価目的関数
2005527034.tif 000414
【０１０８】
は以下のように構築される。
【０１０９】
【数２２】
2005527034.tif 000415
【０１１０】
ここで係数
2005527034.tif 000416
，そしてLはオリジナル目的関数
2005527034.tif 000417
のリプシュッツ定数である。
変換技術は離散最適化問題(4-3)を連続最適化問題(6-7)への変換手段である。変換は
2005527034.tif 000418
が微分可能であれば状態空間全体において微分できるメリットがある。計算手順は容易であり，変換の理論的解析が可能である。
2005527034.tif 000419
は連続関数，かつ
2005527034.tif 000420
【０１１１】
はオリジナル問題(4-3)と同じ大域最適解を有することが示される。しかしながら，変換はオリジナル問題には属さない新しい局所最適解を導入する可能性がある。このデメリットは変換問題(6-7)の局所最適解を計算し，大域最適解の探索において相当余分な計算負荷の原因となる。加えて，この変換は解析可能で閉形式目的関数を有する離散最適化問題(4-3)のクラスのみに適用可能である。
本発明の具体化において，上で提案したガイドライン(G1)と(G2)が成立する別の新しい変換を開発する。
【０１１２】
区分線形変換
オリジナル問題(4-3)が与えられ，本発明は次の変換を開発する。
【０１１３】
【数２３】
2005527034.tif 000421
【０１１４】
ここで，dist(x,y)はxとyの距離である。多くのケースでは，ユークリッド距離が使用される。
2005527034.tif 000422
であり,
2005527034.tif 000423
であり，
2005527034.tif 000424
は
2005527034.tif 000425
と同じもしくはこれ以上の最少整数を表し，
2005527034.tif 000426
であり,
2005527034.tif 000427
であり，
2005527034.tif 000428
は
2005527034.tif 000429
と同じもしくはこれ以下の最少整数を表す。
この変換は以下に述べるいくつかの望ましい性質を有する。
性質１：      
2005527034.tif 000430
は，ほとんどどこでも連続である。
補題： 点
2005527034.tif 000431
とその一方向拡張近傍点
2005527034.tif 000432
を与える。
2005527034.tif 000433
と２点
2005527034.tif 000434
，
により記述される単位開ボックスにより形成される結合領域を定義する。
2005527034.tif 000435
と
2005527034.tif 000436
のいずれかは結合領域内において変換された目的関数
2005527034.tif 000437
の最大点もしくは最少点である。
性質２：      
2005527034.tif 000438
の局所最適解はオリジナル問題(4-3)の一方向拡張近傍(OWEN)に関する局所最適解と同一である。
性質３：      
2005527034.tif 000439
はオリジナル最適化問題(4-3)と同一の大域最適解を有す。
【０１１５】
上で導出された３つの性質は，開発された変換がガイドライン(G1)と(G2)を満たすことを主張している。性質２は変換された問題はオリジナル問題より多くの局所最適解を有さないことを述べている。事実，変換問題の局所最適解は即近傍の変わりに一方向拡張近傍に関連したオリジナル問題の局所最適解である。変換された問題は一般にオリジナル問題(4-3)より少ない局所最適解を有する。これは，浅い局所最適解（大域最適解以外の局所最適解の意味）をスキップすることにより，大域最適解の探索で要求される計算時間を低減することができる望ましい性質である。この変換はＤＤＰベース法で離散問題を効果的解くために適用することに影響を与える。性質３は変換問題とオリジナル問題が同じ大域最適解を有することを述べている。この変換は解析的で陽形式目的関数を有する最適化問題(4-3)に適用する。また，この変換は，状態空間内において任意の2点間の距離が十分に定義される，ブラックボックス目的関数を有する最適化問題(4-3)に適用する。
【０１１６】
拡張アプローチ
目下，変換による連続ベース動的アプローチに焦点をあてた。最適化問題(4-3)の離散解空間の直接拡張を同じ形式を持つ目的関数の連続解空間に実施することにより別の連続ベースアプローチが開発される。拡張された連続最適化問題とよばれる結果としての問題は，以下となる。
【０１１７】
【数２４】
2005527034.tif 000440
【０１１８】
ここで，目的関数
2005527034.tif 000441
は閉形式表現を有する。nはオリジナル解空間Sの自由度の数である。オリジナル問題(4-3)の最適解と拡張された最適化問題(6-9)の最適解は異なるが，お互いそれほど違いはないことは明らかである。
【０１１９】
第１ステージでは，拡張最適化問題(6-9)のような，近似最適化問題の解法と，第２ステージでは，初期条件として第１ステージにて得られた結果を用いてオリジナル最適化問題(4-3)の解法を通し，オリジナル最適化問題(4-3)を解くことができる。この２つのステージのアプローチから得られる解はオリジナル最適化問題(4-3)の局所最適解である。
【０１２０】
目的関数の変換の導入とともに，等価アプローチは離散最適化問題(4-3)をオリジナル問題(4-3)と同じ解空間を有する(6-6)の形式に変換する。同じ目的関数を有する拡張解空間（すなわち，連続解空間）の導入とともに，拡張アプローチは離散最適化問題(4-3)を(6-9)の形式に変換する。加え，説明の明快のため，拡張連続最適化問題(6-9)はもちろん，等価連続最適化問題(6-6)を次の一般形にする。
【０１２１】
【数２５】
2005527034.tif 000442
【０１２２】
ここで，目的関数
2005527034.tif 000443
は閉形式表現を有する。nはオリジナル解空間Sの自由度の数である。解空間は連続となる。
無制約連続最適化問題に属す変換された最適化問題(6-10)は(4-1)で記述される。５節の条件(LC1)-(LC3)を満たす最適化問題(6-10)に関連した非線形動的システムは構築され，次の一般形となる。
【０１２３】
【数２６】
2005527034.tif 000444
【０１２４】
一般形式(6-10)で表現される，等価最適化問題(6-6)もしくは拡張最適化問題(6-9)を解くための連続アプローチにより離散最適化問題(4-3)の体系的に全ての局所最適解を計算する動的方法を開発する。
【０１２５】
６．２．１  ハイブリッド局所探索法
初期点から開始し連続解空間内の無制約離散最適化問題(4-3)のための局所最適解を得るハイブリッド局所探索法を次に示す。
仮定：初期点
2005527034.tif 000445
を与える。
目的：確実に無制約離散問題(4-3)の局所最適解を見つける。
ステップ１．  初期点
2005527034.tif 000446
から開始し，効果的な局所探索アルゴリズムを無制約離散問題(4-3)に適用する。
ステップ２．  局所探索アルゴリズムが局所最適解へ収束すれば，ステップ４へ進む。そうでなければ，初期点
2005527034.tif 000447
として最終点をセットし，次のステップへ進む。
ステップ３．  上記の初期点
2005527034.tif 000448
から開始し，非線形動的システム(6-11)を数回，最終点を得るため，積分する。初期点として最終点をセットし，ステップ１へ進む。
ステップ４．  （拡張アプローチのため）計算された連続局所最適解はm，つまり２，最近傍距離
2005527034.tif 000449
まで，端数を切り捨てる。２つの選択肢が可能である。局所最適解としての最小値を有するポイントを選択し，過程を停止する。もしくは，ステップ５への初期点としてそれらを使う。
ステップ５．  （拡張アプローチのため）より良い近傍局所探索を，m局所最適解
2005527034.tif 000450
を得るため，それぞれ各初期点へ適用する。オリジナル問題(4-3)の局所最適解としての最小値を有するポイントを出力する
【０１２６】
６．２．２  出口点計算のための連続ベース法
既知の局所最適解から開始する最適化問題(4-3)に関連する連続動的システム(6-11)の出口点計算のための連続ベース法，つまり出口点計算のための方法，を次に示す。
仮定： 離散最適化問題(4-3)の局所最適解
2005527034.tif 000451
，予め定義された探索経路，関連した非線形連続動的システム(6-11)を与える。
目的： ダイナミカルシステム(5-7)の予め定義された探索経路と安定平衡点
2005527034.tif 000452
に関連したダイナミカルシステム(6-11)の出口点を見つける。
既知の最適解
2005527034.tif 000453
から開始し，予め定義された探索経路に沿う連続目的関数(6-10)の最初の局所最大値である，上述した出口点を検出するため，予め定義された探索経路に沿って動く。
出口点計算のための別の方法：
2005527034.tif 000454
から開始する探索経路に沿って動く。そして，各時間ステップで，探索経路の微分と非線形動的システム(6-11)のベクトル場の内積を計算する。内積の符号が正から負へ変わるとき，つまり，間隔
2005527034.tif 000455
で，時間
2005527034.tif 000456
での探索経路の点もしくは，時間
2005527034.tif 000457
での探索経路の点が近似された出口点として使用できる。
【０１２７】
６．２．３  ＤＤＰ計算の方法
最適化問題(4-3)の局所最適解
2005527034.tif 000458
が与えられ，システム(6-11)の安定平衡点
2005527034.tif 000459
と予め定義された探索経路に関連する関連した非線形動的システム(6-11)のＤＤＰ計算の連続ベース法を以下に開発する。
ステップ１．  既知の局所最適解
2005527034.tif 000460
から開始し，システム(6-11)の
2005527034.tif 000461
の準スタビリティーリージョンの出口点を計算するため，予め定義された探索経路
2005527034.tif 000462
に沿って動く。出口点を
2005527034.tif 000463
とする。
ステップ２．  
2005527034.tif 000464
から開始し，次のステップにより最短距離点（ＭＤＰ）を計算する。
(i).   関連する非線形システム(6-11)を数ステップ積分し，最終点を現在出口点とする。
(ii).  現在出口点と局所最適解
2005527034.tif 000465
を結ぶ線を描き，
2005527034.tif 000466
から開始し，述べられた現在出口点を，(6-10)で記述される連続目的関数の直線に沿ったはじめの局所最大点である修正出口点に置きかえ，この修正された出口点を記述された出口点
2005527034.tif 000467
に割り当てる。
(iii). ステップ(ii)で得られ，すでに述べられた現在出口点におけるベクトル場(6-10)のノルムが閾値より小さくなる，すなわち
2005527034.tif 000468
，まで，ステップ(i)から(ii)を繰り返す。次に，述べられた点は最短距離点（ＭＤＰ）
2005527034.tif 000469
と表せられる。
ステップ３．  初期推定値として述べられたＭＤＰ
2005527034.tif 000470
を用い，解が関連するダイナミカルシステム(6-11)の
2005527034.tif 000471
と述べられた探索経路
2005527034.tif 000472
に関するＤＤＰ
2005527034.tif 000473
であるシステム(6-11)の述べられたベクトル場
2005527034.tif 000474
の非線形代数方程式の集合を解く。
【０１２８】
６．２．４  別の局所最適解を見つけるＥＰベース法
最適化問題(4-3)に対し，本発明は既知の局所最適解から開始し，局所最適解を見つける出口点ベース（ＥＰベース）法を開発する。
仮定：離散最適化問題(4-3)の局所最適解
2005527034.tif 000475
を与える。
目的：離散最適化問題(4-3)の新しい局所最適解を見つける。
ステップ１．  既知の最適解
2005527034.tif 000476
から開始し，出口点（ＥＰ）を計算する方法を非線形動的システム(6-11)へＥＰ
2005527034.tif 000477
を計算するため適用する。
ステップ２．  
2005527034.tif 000478
をセットする。ここでεは小さな数である。
ステップ３．  
2005527034.tif 000479
から開始し，効果的な（ハイブリッド）局所探索法が過渡的な探索の性能を上回る，インターフェース点
2005527034.tif 000480
に到達するまで，一致するシステム軌道を得るため，非線形ダイナミックシステム(6-11)を積分することにより過渡的な探索を導く。
（ステップ３の代替）
2005527034.tif 000481
から遠い方向の中であるが，
2005527034.tif 000482
方向に近い中で，
2005527034.tif 000483
の端数を切り捨て，新しい点
2005527034.tif 000484
とする。
2005527034.tif 000485
から開始し，最良近傍探索法を，効果的な（ハイブリッド）局所探索法が最良近傍探索の性能を上回るインターフェース点
2005527034.tif 000486
得るため適用する。
ステップ４．  インターフェース点
2005527034.tif 000487
から開始し，（ハイブリッド）局所探索法を，ステップ３で選択された，問題(4-3)へ近傍局所最適解を見つけるため適用する。
【０１２９】
６．２．５  別の局所最適解を見つけるＤＤＰベース法
最適化問題(4-3)のため，本発明は既知の最適解から開始する局所最適解を見つけるＤＤＰベース法を開発する。
仮定：最適化問題(4-3)の局所最適解
2005527034.tif 000488
を与える。
目的：最適化問題(4-3)の新しい局所最適解を見つける。
ステップ１．  既知の最適解
2005527034.tif 000489
から開始し，ダイナミック分解点（ＤＤＰ）を計算する方法をシステム(6-11)へＤＤＰ
2005527034.tif 000490
を見つけるため適用する。
ステップ２．  
2005527034.tif 000491
をセットする。ここでεは小さな数である。
ステップ３．  
2005527034.tif 000492
から開始し，効果的な（ハイブリッド）局所探索法が過渡探索の性能を上回る，インターフェース点
2005527034.tif 000493
に到達するまで，一致するシステム軌道を得るため，ダイナミックシステム(6-11)を積分することにより過渡探索を導く。
（ステップ３の代替）
2005527034.tif 000494
から遠い方向の中であるが，
2005527034.tif 000495
方向に近い中で，
2005527034.tif 000496
の端数を切り捨て，新しい点
2005527034.tif 000497
とする。
2005527034.tif 000498
から開始し，最良近傍探索法を，効果的な（ハイブリッド）局所探索法が最良近傍探索の性能を上回るインターフェース点
2005527034.tif 000499
得るため適用する。
ステップ４．  インターフェース点
2005527034.tif 000500
から開始し，（ハイブリッド）局所探索法を，ステップ３で選択された，問題(4-3)へ局所最適解を見つけるため適用する。
【０１３０】
６．２．６  全ティア１局所最適解探索の動的方法
離散最適化問題(4-3)のため，本発明は，全ティア１局所最適解を見つける連続ベース法の２つのグループを開発する。はじめのグループは連続ＥＰベース，一方，２つめのグループは連続ＤＤＰベースである。
【０１３１】
連続ＥＰベース法
仮定：離散最適化問題(4-3)の局所最適解
2005527034.tif 000501
を与える。
目的：離散最適化問題(4-3)の
2005527034.tif 000502
の全ティア１局所最適解を見つける。
ステップ１．  ティア１局所最適解の集合
2005527034.tif 000503
を初期化し，
2005527034.tif 000504
に対する探索経路の集合
2005527034.tif 000505
を定義する。i=1にセットする。
ステップ２．  
2005527034.tif 000506
からスタートする各探索経路
2005527034.tif 000507
に対し，対応する局所最適解を計算する。
(i)    ＥＰベース法をシステム（６−１１）へ別の局所最適解を見つけるため適用する。局所最適解が見つかれば，それを
2005527034.tif 000508
とし，次のステップへ進む。そうでなければ，ステップ(iii)へ進む。
(ii)   
2005527034.tif 000509
が既に見つかったか，すなわち
2005527034.tif 000510
であるか，チェックする。見つかっていなければ，
2005527034.tif 000511
をセットする。
(iii)  i=i+1をセットする。
(iv)   i>mとなるまでステップ(i)から(iii)を繰り返す。
ステップ３．  
2005527034.tif 000512
のティア1局所最適解の集合
2005527034.tif 000513
を出力する。
【０１３２】
連続ＤＤＰベース法
仮定：離散最適化問題(4-3)の局所最適解
2005527034.tif 000514
を与える。
目的：離散最適化問題(4-3)の
2005527034.tif 000515
の全ティア１局所最適解を見つける。
ステップ１．  ダイナミカル分解点の集合
2005527034.tif 000516
を初期化し，ティア1局所最適解の集合
2005527034.tif 000517
をセットする。
ステップ２．  
2005527034.tif 000518
に対する探索経路の集合
2005527034.tif 000519
を定義する。i=1にセットする。
ステップ３．  
2005527034.tif 000520
を初期値とする各探索経路
2005527034.tif 000521
に対し，対応する局所最適解を次のステップで計算する。
【０１３３】
(i).   動的分解点（ＤＤＰ）を計算する方法をシステム(6-11)へ対応するＤＤＰを見つけるため適用する。ＤＤＰが見つかれば，次のステップへ進む。そうでなければ，ステップ(vi)へ進む。
(ii).  見つけたＤＤＰを
2005527034.tif 000522
とし，集合
2005527034.tif 000523
に属するか，すなわち
2005527034.tif 000524
であるかチェックする。属せば，ステップ(vi)へ進む。そうでなければ，
2005527034.tif 000525
をセットし，ステップ(iii)へ進む。
(iii). 
2005527034.tif 000526
をセットする。ここでεは小さな数である。
(iv).  
2005527034.tif 000527
から開始し，効果的なハイブリッド局所探索法が過渡的な探索の性能を上回る，インターフェース点
2005527034.tif 000528
に到達するまで，対応するシステム軌道を得るため，ダイナミックシステム(6-11)を積分することにより過渡的な探索を導く。
（ステップ(iv)の代替）
2005527034.tif 000529
から遠い方向であるが，
2005527034.tif 000530
方向に近い，
2005527034.tif 000531
の端数を切り捨て，離散点
2005527034.tif 000532
とする。問題(4-3)向けにデザインされた最良近傍探索法を，効果的なハイブリッド局所探索法が最良近傍探索の性能を上回るインターフェース点
2005527034.tif 000533
得るため適用する。
(v).   インターフェース点
2005527034.tif 000534
から開始し，ステップ３で選択された効果的なハイブリッド局所探索法を適用して、
2005527034.tif 000535
に関する，
2005527034.tif 000536
と記述される対応した局所最適解を見つける。そして
2005527034.tif 000537
をセットする。
(vi).  i=i+1をセットする。
(v)    i>mとなるまでステップ(i)から(vi)を繰り返す。
ステップ４．  
2005527034.tif 000538
のティア1局所最適解の集合
2005527034.tif 000539
を出力する。
【０１３４】
６．２．７  全局所最適解探索の方法
離散最適化問題(4-3)に対し，本発明は，全局所最適解を見つける２つの動的方法を開発する。はじめの方法は連続ＥＰベース法，一方２つめの方法は連続ＤＤＰベース法である。
【０１３５】
連続ＥＰベース法
仮定：初期点
2005527034.tif 000540
を与える。
目的： (i）離散最適化問題(4-3)の全ての局所最適解を見つける。
(ii)離散最適化問題(4-3)の大域最適解を見つける。
ステップ１．  初期点
2005527034.tif 000541
から，効果的な（ハイブリッド）探索法を離散最適化問題(4-3)に局所最適解
2005527034.tif 000542
を見つけるため適用する。
ステップ２．  j＝0をセットする。局所最適解の集合
2005527034.tif 000543
と，ティアｊ局所最適解の集合
2005527034.tif 000544
を初期化する。
ステップ３．  ティア（ｊ+１）局所最適解の集合
2005527034.tif 000545
を初期化する。
ステップ４．  
2005527034.tif 000546
内の各局所最適解
2005527034.tif 000547
に対し，それらの全ティア１局所最適解を見つける。
(i)    
2005527034.tif 000548
に対し，探索経路
2005527034.tif 000549
の集合を定義する。i=1をセットする。
(ii)   初期値
2005527034.tif 000550
の各探索経路
2005527034.tif 000551
に対し，ＥＰベース法を適用して別の局所最適解を見つける。局所最適解が見つかれば，
2005527034.tif 000552
とし次へ進む。そうでなければ，ステップ(iv)へ進む。
(iii)  
2005527034.tif 000553
が既に見つかったか，すなわち，
2005527034.tif 000554
であるかチェックする。見つかっていなければ，
2005527034.tif 000555
と
2005527034.tif 000556
【０１３６】
をセットする。
(iv)   i=i+1とセットする。
(v)    
2005527034.tif 000557
となるまでステップ(ii)から(iv)を繰り返す。
ステップ５．  新しく計算された局所最適解の集合
2005527034.tif 000558
が空であれば，ステップ６へ進む。そうでなければ，j＝j＋1をセットしステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000559
を出力し，集合
2005527034.tif 000560
の対応する目的関数の比較と最小値を持つものの選択により
2005527034.tif 000561
の集合から大域最適解を特定する。それを大域最適解として出力する。
【０１３７】
ＤＤＰベース法
仮定：初期点
2005527034.tif 000562
を与える。
目的： (i)離散最適化問題(4-3)の全ての局所最適解を見つける。
(ii)離散最適化問題(4-3)の大域最適解を見つける。
ステップ１．  初期点
2005527034.tif 000563
から効果的なハイブリッド探索法を離散最適化問題(4-3)に局所最適解
2005527034.tif 000564
を見つけるため適用する。
ステップ２．  j＝0をセットする。局所最適解の集合
2005527034.tif 000565
と，ティアｊ局所最適解の集合
2005527034.tif 000566
と，見つけた動的分解点の集合
2005527034.tif 000567
とを初期化する。
ステップ３．  ティア（ｊ+１）局所最適解の集合
2005527034.tif 000568
を初期化する。
ステップ４．  
2005527034.tif 000569
内の各局所最適解
2005527034.tif 000570
に対し，それらの全てのティア１局所最適解を以下の手順にて見つける。
(i).   
2005527034.tif 000571
に対し，探索経路
2005527034.tif 000572
の集合を定義する。i=1をセットする。
(ii).  
2005527034.tif 000573
からスタートする各探索経路
2005527034.tif 000574
に対し，効果的な方法を対応した動的分解点（ＤＤＰ）をみつけるため，システム（6-11）へ適用する。ＤＤＰが見つかれば，次へ進む。そうでなければ，ステップ(viii)へ進む。
(iii). 見つけたＤＤＰを
2005527034.tif 000575
とし，集合
2005527034.tif 000576
に属するか，すなわち
2005527034.tif 000577
であるかチェックする。属せば，ステップ(viii)へ進む。そうでなければ，集合
2005527034.tif 000578
をセットする。そしてステップ(iii)へ進む。
(iv).  
2005527034.tif 000579
をセットする。ここでεは小さな数である。
(v).   
2005527034.tif 000580
からスタートし，インターフェース点
2005527034.tif 000581
に到達するまで，非線形動的システム（６−１１）を積分することにより過渡探索を導いて、対応したシステム軌道を得る。インターフェース点は，効果的なハイブリッド局所最適探索法が過渡探索を上回る点である。
（ステップvの代替）点
2005527034.tif 000582
を
2005527034.tif 000583
に近いが，
2005527034.tif 000584
から離れた点で丸め、これを離散点
2005527034.tif 000585
とする。そして、問題（４−３）向けにデザインされた最良近傍探索法を適用して、効果的なハイブリッド局所探索法が最良近傍探索の性能を上回る点であるインターフェース点
2005527034.tif 000586
を得る。
(vi)   インターフェース点
2005527034.tif 000587
からスタートし，ステップ(v)で選択された効果的なハイブリッド局所探索法を，対応した局所最適解
2005527034.tif 000588
を見つけるための離散最適化問題（４−３）に適用する。
(vii)  
2005527034.tif 000589
が既に見つかったか，すなわち
2005527034.tif 000590
であるかチェックする。見つかっていなければ，
2005527034.tif 000591
と
2005527034.tif 000592
をセットする。
(viii) i=i+1とセットする。
(ix)   i>mとなるまでステップ(ii)から(viii)を繰り返す。
ステップ５．  新しく計算された局所最適解の集合
2005527034.tif 000593
が空であれば，ステップ６へ進む。そうでなければ，j＝j＋1をセットしステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000594
を出力し，集合
2005527034.tif 000595
の対応する目的関数の比較と最小値を持つものの選択により
2005527034.tif 000596
の集合から大域最適解を特定する。それを大域最適解として出力する。
【０１３８】
７．有制約離散最適化問題解法の動的方法
本節にて，有制約離散最適化問題(4-4)解法の動的方法を示す。
有制約離散最適化問題(4-4)解法の困難さは，目的関数
2005527034.tif 000597
，解空間
2005527034.tif 000598
，実行可能集合
2005527034.tif 000599
の構造に依存する。特に，
2005527034.tif 000600
内の要素，
2005527034.tif 000601
のサイズを記述する困難さと
2005527034.tif 000602
の要素を系統的に列挙する困難さに依存する。(4-4)で定義された離散最適化問題に対し，局所探索アルゴリズムは，現在の解
2005527034.tif 000603
から進み，次のステップを用い，
2005527034.tif 000604
まわりの任意の近傍
2005527034.tif 000605
内の上質の解を探索することにより
2005527034.tif 000606
を修正する。
ステップ１．  初期化：初期点
2005527034.tif 000607
を選択し，反復カウンタをk=1とする。
ステップ２．  修正：局所修正集合
2005527034.tif 000608
を考える。ここで，
2005527034.tif 000609
は
2005527034.tif 000610
まわりの近傍である。集合が空であれば，終了し，
2005527034.tif 000611
を近傍
2005527034.tif 000612
に関する局所最適解とする。空でなければ，
2005527034.tif 000613
としていくつかの集合を選び，k=k+1と増加させ，本ステップを繰り返す。
局所探索アルゴリズムに関し，３つの問題がある。
(i)    近傍
2005527034.tif 000614
の定義。
(ii)   集合
2005527034.tif 000615
から
2005527034.tif 000616
を選択する方法。
(iii)  ステップ１を開始するため，どのように実行可能解を得るか？
はじめの２つの問題は無制約離散最適化問題（４−３）に似ている。制約を扱うため，最良近接探索法が，
2005527034.tif 000617
として，可能近接集合（制約を満たす近傍）から，目的関数の最大降下となる１つのみを選ぶ有制約最良近接探索法として修正される。同様に，より良い近接局所探索法が，目的関数内で降下方向を導く，はじめの実行可能近傍（制約を満たす近傍）を
2005527034.tif 000618
としてのみ選択する，有制約のより良い近接局所探索法として修正される。従って，制約最良近傍探索もしくは制約のより良い近傍探索を適用することにより，
2005527034.tif 000619
を得る。
問題(iii)を述べるため，全ての実行可能解が既知でない時，実行可能点を得るため，次のアプローチを適用する。
ステップ１．  初期化：初期点
2005527034.tif 000620
を選択し，
2005527034.tif 000621
であるかをチェックする。そうであれば，停止，そして局所探索を開始するための実行可能解を見つけた。そうでなければ，反復カウンタをk=1とする。
ステップ２．  可能性修正：次の非実行性修正集合
2005527034.tif 000622
について考える。ここで、関数
2005527034.tif 000623
は解
2005527034.tif 000624
の非実行性を計る。集合が空であれば，停止，そして，実行可能解が見つけられないことを示すため警告メッセージを出力する。
2005527034.tif 000625
が存在して
2005527034.tif 000626
であれば，停止し，
2005527034.tif 000627
が実行可能解となる。そうでなければ，
2005527034.tif 000628
としていくつかの集合を選択し，k=k+1と増加させ，このステップを繰り返す。
【０１３９】
有制約解空間アプローチ
有制約離散最適化問題（４−４）を解くため，３つのステージで構成された，次の有制約解空間アプローチをベースとした動的方法を開発する。
ステージ１：  結合された実行要素内の局所最適解を計算する。
ステージ２：  結合された実行要素内の全ての局所最適解を見つける。
ステージ３：  別の結合された実行要素を見つける。見つけられなければ，過程を停止。そうでなければ，ステージ２へ進む。
【０１４０】
本アプローチを，全ての局所最適解探索は解空間の実行可能要素内のみであるため，有制約解空間アプローチとよぶ。
本節では，目的関数
2005527034.tif 000629
は閉形式表現もしくはブラックボックス表現，制約関数ベクトル
2005527034.tif 000630
は閉形式表現である，方程式（４−５）を満足する有制約離散最適問題を解くための離散ベース動的方法を開発する。離散ベース動的方法のステージ２において，各実行可能要素内にある全ての局所最適解を見つける離散ベースアプローチを開発する。動的方法のステージ３において，全ての結合された実行可能要素を見つける連続ベースアプローチを開発する。
一般性を失うことなく，次の等式制約付きの最適化問題を考える。
【０１４１】
【数２７】
2005527034.tif 000631
【０１４２】
いくつかの一般条件下において，次の実行可能集合，実行可能要素とよばれる，が示される。
【０１４３】
【数２８】
2005527034.tif 000632
【０１４４】
は滑らかの多様体である。一般に，実行可能集合
2005527034.tif 000633
はいくつかの隔離された（パス−結合）実行可能要素を伴い，非常に複雑である。別の言葉では，実行可能集合
2005527034.tif 000634
はいくつかの隔離された実行要素の集合として示される。
【０１４５】
【数２９】
2005527034.tif 000635
【０１４６】
ここで各
2005527034.tif 000636
は有制約最適化問題(7-1)の複数の局所最適解を含む，パス連結実行可能要素である。
各実行可能要素内にある全ての局所最適解を見つける離散ベースアプローチを開発する。無制約離散最適化問題(4-3)を解くための，本発明において開発される離散ベースアプローチと同様に，次の関連した非線形離散動的システムを考える。
【０１４７】
【数３０】
2005527034.tif 000637
【０１４８】
2005527034.tif 000638
の時，(7-3)の解空間は離散である。離散動的システムは，６節で述べられている３つの条件(LD1)-(LD3)を満足する。離散動的システム(7-3)に関連した任意の動的軌道を介する実行可能要素内の，離散最適化問題(4-5)の全ての局所最適解をシステマティックに計算する動的方法を開発する。
【０１４９】
７．１  実行可能点を見つける方法
本発明において，次の一般形式により記述される非線形動的システムのいくつかの軌道をベースとした(7-2)の全ての実行可能可能要素をシステマティックに見つける作業をするため，ここで参考とする，同時係属出願，「シリアル番号０９／８４９，２１３，出願２００１年５月４日，タイトル"一般非線形プログラミング問題の大域最適解を得るための動的方法"，発明者シャオ・ドン・チャン博士」で記述される動的軌道ベース法を使用する。
【０１５０】
【数３１】
2005527034.tif 000639
【０１５１】
このような作業を実行するための非線形動的システムを構築するため，次のガイドラインを提案する。
(g1)   (7-4)のすべてのシステム軌道は平衡多様体の１つに収束し，
(g2)   集合が(7-4)の安定平衡多様体の場合のみ，集合は制約方程式(7-2)の集合の（パス結合）の実行可能要素である。
(7-3)のすべての実行可能要素を特定するための，条件(g1)と(g2)を満たす非線形動的システムの１つの例題を以下に示す。
【０１５２】
【数３２】
2005527034.tif 000640
【０１５３】
２つの方法は実行可能点を見つけるため開発された。はじめの１つは，軌道ベース法，２つめの方法はハイブリッド局所探索法である。
【０１５４】
実行可能点を見つけるための軌道ベース方法
非実行可能点から開始する(7-2)の実行可能要素を特定するためのアルゴリズムを次に示す。
仮定：非制約である初期点
2005527034.tif 000641
を与える。
目的：制約方程式(7-3)の集合を満たす実行可能点を見つける。
2005527034.tif 000642
から開始する動的システム(7-4)を積分する。(7-2)の実行可能点である，安定多様体内にある点へ軌道は収束する。
【０１５５】
実行可能点を見つけるハイブリッド法
次に，制約方程式(7-3)の実行可能点を見つけるための，軌道ベース法の大域収束性と局所探索方法のスピードを組み合わせた，ハイブリッド法を示す。
仮定：非実行可能解である初期点
2005527034.tif 000643
を与える。
目的：制約方程式(7-3)の集合を満たす実行可能解を見つける。
ステップ１．  
2005527034.tif 000644
から開始する効果的な反復修正局所探索アルゴリズムを適用する。局所探索アルゴリズムが実行可能点へ収束すると，停止する。そうでなければ，次のステップへ進む。
ステップ２．  
2005527034.tif 000645
から開始し，数ステップ，動的システム(7-4)を積分する。軌道が実行可能点へ収束すれば，停止。そうでなければ，最終点を初期点とし，つまり
2005527034.tif 000646
とし，ステップ１へ進む。
【０１５６】
７．２  局所探索法
非実行可能可能点からスタートする離散最適化問題(4-5)の局所最適解を得るためのラグランジベース法を開発する。
不等式制約から等式制約へ変換するためのスラック変数yの導入により，以下となる。
【０１５７】
【数３３】
2005527034.tif 000647
【０１５８】
ラグラジアン関数は以下のように構築される。
【０１５９】
【数３４】
2005527034.tif 000648
【０１６０】
2005527034.tif 000649
がラグランジ関数(7-7)の鞍点を構成すれば，
2005527034.tif 000650
は離散最適化問題(4-5)の局所最適解である。本ケースにおいて，グラジエントオペレータ
2005527034.tif 000651
を以下に示す。
定義.離散グラジエントオペレータ
2005527034.tif 000652
を以下に定義する。
2005527034.tif 000653
。ここで，
2005527034.tif 000654
，すなわち，最大でも１つの
2005527034.tif 000655
は非ゼロであり，
2005527034.tif 000656
を満たす。更に，
2005527034.tif 000657
より１つの変数の最大１違いがある，任意の
2005527034.tif 000658
に対し，
2005527034.tif 000659
を定義し，
2005527034.tif 000660
である。
従って，
2005527034.tif 000661
は常に，目的関数が降下し，
2005527034.tif 000662
が
2005527034.tif 000663
を，
2005527034.tif 000664
内の最低値を有する１つの近傍
2005527034.tif 000665
へ動かす方向を示す。このような
2005527034.tif 000666
が存在しない場合，
2005527034.tif 000667
である。
本定義により，離散グラジエントオペレータ
2005527034.tif 000668
は以下のように表現される。
【０１６１】
【数３５】
2005527034.tif 000669
【０１６２】
2005527034.tif 000670
がより良い近傍方向を示せば，
2005527034.tif 000671
は唯一ではない。欲張り探索方向（最良近傍探索方向）もしくは，
2005527034.tif 000672
の方向としてのグラジエント降下方向を使う。
離散ラグランジェベースアップデートルールを形成する。
【０１６３】
【数３６】
2005527034.tif 000673
【０１６４】
2005527034.tif 000674
を以下に定義する。
【０１６５】
【数３７】
2005527034.tif 000675
【０１６６】
ここで，
2005527034.tif 000676
は，探索プロセスを以前の遭遇した違反から離す力を決定する非正修正ファクタである。
2005527034.tif 000677
は集合，例えば，１である。
スラック変数yは以下に定義される。
【０１６７】
【数３８】
2005527034.tif 000678
【０１６８】
次に有制約離散最適化問題(4-4)の局所最適解を見つけるための離散ラグランジェベース法を示す。
仮定：非実行可能解の初期点
2005527034.tif 000679
を与える。
目的：有制約離散最適化問題(4-4)の局所最適解を見つける。
ステップ１．  いくつかの制約を禁止する，与えられた初期値
2005527034.tif 000680
から開始する。
ステップ２．  次のステップにより局所最適解を見つける。
(i)    k=1をセットする。
(ii)   方程式(7-10)から
2005527034.tif 000681
を計算する。
2005527034.tif 000682
が実行可能要素であれば，有制約のより良い近傍方向と
2005527034.tif 000683
を計算する方程式(7-8)を使う。そうでなければ，
2005527034.tif 000684
を計算するオリジナル解空間内のより良い近傍方向を使う。
(iii)  
2005527034.tif 000685
と
2005527034.tif 000686
の両者が十分小さい場合，探索は収束し，現在点
2005527034.tif 000687
は局所最適解である。そうでなければ，
2005527034.tif 000688
と
2005527034.tif 000689
をアップデートし，次のステップへ進む。
(iv)   k=k+1をセットする。
(v)    予め定義された繰り返しの数だけ，ステップ(ii)から(iv)を繰り返す。
【０１６９】
７．３  ハイブリッド有制約局所探索方法
実行可能初期点からスタートする，有制約離散最適化問題(4−5)の局所最適解を得るためのハイブリッド有制約局所探索法を以下に示す。
仮定：実行可能要素内の実行初期点
2005527034.tif 000690
を与える。
目的：実行可能要素内の局所最適解を見つける。
ステップ１．  実行初期点
2005527034.tif 000691
から開始し，初期点から有制約離散最適化問題(4−5)を解くための効果的な反復修正局所探索アルゴリズムを適用する。
ステップ２．  局所探索アルゴリズムは局所最適解に収束すれば，終了する。そうでなければ，最終点を初期点，すなわち
2005527034.tif 000692
としてセットし，次のステップへ進む。
ステップ３．  最終点を得，数ステップ探索過程を継続するため，
2005527034.tif 000693
から開始する，有制約最良近傍局所探索法もしくは有制約のより良い近傍局所探索法を使用する。最終点を初期点としてセットし，ステップ１へ進む。
【０１７０】
７．４ 実行可能出口点を計算する方法
ここで，実行可能出口点（すなわち全ての制約を満たす出口点）を計算する離散ベース法と呼ばれる，既知の局所最適解からスタートする探索経路に沿った，有制約離散最適化問題(4-5)に関連する離散動的システム(7-3)の実行可能出口点を計算する方法を以下に示す。
仮定：局所最適解
2005527034.tif 000694
と予め定義された探索経路を与える。
目的：対応した出口点（ＥＰ）を見つける。
既知の局所最適解
2005527034.tif 000695
からスタートし，予め定義された探索経路に沿った目的関数(4-5)の始めの局所最大値である，上述された出口点を検出するため予め定義された探索経路に沿って移動する。過程中，制約禁止状態をチェックする。制約が禁止状態であれば，探索過程を終了する。
【０１７１】
７．５  実行可能ＤＤＰ計算のための方法
有制約離散最適化問題(4-5)のための，以下に示す，局所最適解と予め定義された探索経路に関連する実行可能動的分解点（ＤＤＰ）を計算する動的方法を開発する。
仮定： 最適化問題(4-5)の局所最適解
2005527034.tif 000696
，予め定義された探索経路，関連した離散動的システム(7-3)を与える。
目的： 対応した実行可能動的分解点（ＤＤＰ）を見つける。
ステップ１．  既知の局所最適解
2005527034.tif 000697
からスタートし，離散動的システム(7-3)の対応した実行可能出口点（すなわち，全ての制約を満たす出口点）を見つけるため，予め定義された探索経路に沿って移動する。出口点を
2005527034.tif 000698
とする。
ステップ２．  
2005527034.tif 000699
からスタートし，
2005527034.tif 000700
を１（前方）反復新しい点
2005527034.tif 000701
へ移動させるため有制約最良近傍探索法を適用する。
ステップ３．  直線修正手順とＤＤＰ計算を実行する。
(i)    
2005527034.tif 000702
と
2005527034.tif 000703
を直線で結ぶ。
(ii)   ベクトル
2005527034.tif 000704
と
2005527034.tif 000705
が利用可能であれば，ステップ(ii)(a)を実行する。そうでなければ，他を実行する。
(a)    ２つのベクトル
2005527034.tif 000706
と
2005527034.tif 000707
の角度
2005527034.tif 000708
を計算する。
2005527034.tif 000709
が０度もしくは１８０度に近ければ，
2005527034.tif 000710
はＤＤＰで，過程を終了する。そうでなければ，ステップ(iii)へ進む。
（ステップ(a)の代替）探索経路を現在
2005527034.tif 000711
がアップデートされた探索経路上にあるようにアップデートする。アップデート探索経路上に３点
2005527034.tif 000712
があるかチェックする。そうであれば，
2005527034.tif 000713
がＤＤＰであり過程を終了する。そうでなければ，次のステップへ進む。
(iii)  
2005527034.tif 000714
を，
2005527034.tif 000715
からスタートする直線にそって，最適化問題(4-5)の目的関数の始めの局所最大点である
2005527034.tif 000716
へ修正する。
2005527034.tif 000717
が
2005527034.tif 000718
と同じであれば，
2005527034.tif 000719
はＤＤＰで過程を終了する。そうでなければ，次のステップへ進む。
ステップ４．  
2005527034.tif 000720
を出口点として使う。すなわち，
2005527034.tif 000721
に割り当てステップ２へ進む。
【０１７２】
７．６．別の局所最適解を見つけるＥＰベース法
有制約離散最適化問題(4-5)に対し，既知の局所最適解から新しい局所最適解を見つける出口点ベース法を開発する。
仮定：有制約離散最適化問題(4-5)の局所最適解
2005527034.tif 000722
と予め定義された探索経路を与える。
目的：対応する新しい（ティア１）局所最適解を見つける。
ステップ１．  
2005527034.tif 000723
から予め定義された探索経路に沿って移動し，対応した実行可能出口点（ＥＰ）
2005527034.tif 000724
を計算するため，離散ベース法を関連した非線形動的システム(7-3)に適用する。実行可能ＥＰが見つけられなければ，過程を停止し，次のステップへ進む。
ステップ２．  見つけられた出口点
2005527034.tif 000725
から，予め定義された探索経路に沿って，
2005527034.tif 000726
から新しい点へ一段階移動する。新しい点を
2005527034.tif 000727
（もしくは
2005527034.tif 000728
を、その表現が利用可能であれば、使う。ここで，
2005527034.tif 000729
は小さな数）とする。
ステップ３．  最適化問題(4-5)を解くための効果的な（ハイブリッド）局所探索法が有制約最良近傍探索法より良い解が得られる，インターフェース点
2005527034.tif 000730
に到達するまで，対応したシステム軌道を得るため，
2005527034.tif 000731
からスタートする有制約最良近傍探索法を適用する。
ステップ４．  インターフェース点
2005527034.tif 000732
からスタートし，対応した近接した局所最適解を見つけるため，ステップ３で選択された，効果的なハイブリッド局所探索法を適用する。
【０１７３】
７．７  別の局所最適解を見つけるためのＤＤＰベース法
有制約離散最適化問題(4-5)のための，既知の局所最適解
2005527034.tif 000733
からスタートする局所最適解を解くためのＤＤＰベース法を以下に開発する。
仮定：有制約離散最適化問題(4-5)の局所最適解
2005527034.tif 000734
と予め定義された探索経路を与える。
目的：対応した新しい（ティア１）局所最適解を見つける。
ステップ１．  
2005527034.tif 000735
からスタートする予め定義された探索経路に沿って移動し，対応した実行可能動的分解点（ＤＤＰ）
2005527034.tif 000736
を計算するため非線形動的システム(7-3)に関連する離散ベース法を適用する。ＤＤＰが見つけることができなければ，過程を終了する。そうでなければ，次のステップへ進む。
ステップ２．  見つけられた実行可能ＤＤＰ
2005527034.tif 000737
からスタートし，一段ずつ，最後の出口点
2005527034.tif 000738
を
2005527034.tif 000739
から
2005527034.tif 000740
へ調整するために使うアップデートされた探索経路にそって移動する（もしくは，
2005527034.tif 000741
の表現を利用可能であれば、それを使う。ここで
2005527034.tif 000742
は小さな数）。
ステップ３．  有制約最良近傍探索法を、それに関係する、
2005527034.tif 000743
からスタートする離散非線形動的システム(7-3)に適用して、効果的なハイブリッド局所探索法が有制約最良近傍探索法より良い解が得られるインターフェース点
2005527034.tif 000744
に到達するまで，対応したシステム軌道を得る。
ステップ４．  インターフェース点
2005527034.tif 000745
からスタートし，対応した近接した局所最適解を見つけるため，ステップ３で選択された効果的なハイブリッド局所探索法を適用する。
【０１７４】
７．８．実行可能要素内の全てのティア１局所最適解を探索する方法
既知の局所最適解からスタートする，有制約離散最適化問題の，実行可能要素内にある，全てのティア１局所最適解を見つける１つの動的離散ベース法を以下で開発する。
仮定：有制約離散最適化問題(4-3)の局所最適解
2005527034.tif 000746
を与える。
目的：実行可能要素内にある
2005527034.tif 000747
の全てのティア１局所最適解を見つける。
ステップ１．  ティア１局所最適解の集合
2005527034.tif 000748
を初期化し，
2005527034.tif 000749
での探索経路の集合
2005527034.tif 000750
を定義する。。i=1をセットする。
ステップ２．  
2005527034.tif 000751
からスタートする各探索経路
2005527034.tif 000752
に対し，離散ベースＥＰベース法（もしくはＤＤＰベース法）を、関連する動的システム(7-3)へ別の局所最適解を見つけるため適用する。局所最適解があれば，それを
2005527034.tif 000753
とし，次のステップへ進む。そうでなければ，ステップ４へ進む。
ステップ３．  
2005527034.tif 000754
が既に見つけられたか，すなわち
2005527034.tif 000755
であるかチェックする。見つかっていなければ，
2005527034.tif 000756
をセットする。
ステップ４．  i=i+1をセットする。
ステップ５．  i>mとなるまでステップ２から４を繰り返す。
【０１７５】
７．９．実行可能要素内の全ての局所最適解を見つける方法
与えられた初期点からスタートし，有制約離散最適化問題(4-5)の，実行可能要素内にある，全ての局所最適解を見つける，離散ベース動的方法を以下で開発する。
仮定：有制約離散最適化問題(4-3)の局所最適解
2005527034.tif 000757
を与える。
目的：
2005527034.tif 000758
を含む実行可能要素内の全ての局所最適解を見つける。
ステップ１．  
2005527034.tif 000759
からスタートし，局所最適解
2005527034.tif 000760
を見つけるため，効果的な（ハイブリッド）探索法を適用する。
ステップ２．  j=0をセットする。局所最適解の集合
2005527034.tif 000761
とティアj局所最適解の集合
2005527034.tif 000762
を初期化する。
ステップ３．  ティア(j+1)局所最適解の集合
2005527034.tif 000763
を初期化する。
ステップ４．  
2005527034.tif 000764
内の各局所最適解に対し，すなわち
2005527034.tif 000765
に対し，全てのティア１局所最適解を見つける。
(i)    
2005527034.tif 000766
に対する探索経路の集合
2005527034.tif 000767
を定義する。i=1をセットする。
(ii)   
2005527034.tif 000768
からスタートする各探索経路
2005527034.tif 000769
に対し，ＥＰベース法（もしくはＤＤＰベース法）を、関連する離散動的システム(7-3)へ，別の局所最適解を見つけるため適用する。局所最適解があれば，それを
2005527034.tif 000770
とし，次のステップへ進む。そうでなければ，ステップ(iv)へ進む。
(iii)  
2005527034.tif 000771
が既に見つかったか，すなわち
2005527034.tif 000772
であるかチェックする。見つかってなければ，
2005527034.tif 000773
と
2005527034.tif 000774
をセットする。
(iv)   i=i+1をセットする。
(v)    
2005527034.tif 000775
となるまでステップ(ii)から(iv)を繰り返す。
ステップ５．  全ての新しい計算された局所最適解の集合
2005527034.tif 000776
が空であれば，ステップ６を続け，そうでなければ，j=j+1をセットし，ステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000777
を出力し，集合
2005527034.tif 000778
の対応する目的関数値の比較により大域最適解を特定し，最小値を有する１つを選択する。これを既知の大域最適解として出力し，実行可能要素内の，全ての局所最適解の集合
2005527034.tif 000779
を出力する。
【０１７６】
７．１０．隣接した実行可能要素を見つける方法
既知の実行可能要素からスタートし，隣接し隔離された実行可能要素を見つける，動的方法を以下で開発する。
仮定： 実行可能初期点
2005527034.tif 000780
を与える。
目的： 有制約離散最適化問題(4-5)の隣接実行可能要素内にある新しい実行可能要素を見つける。
ステップ１．  
2005527034.tif 000781
からスタートし，軌道（逆時間モードで）を得るため，システム(7-4)を逆時間に積分し，必要であれば，(7-4)の不安定多様体内の点を見つける，局所探索法にスイッチする。ここで
2005527034.tif 000782
は小さな数である。点があれば，
2005527034.tif 000783
とし次のステップへ進む。そうでなければ，過程を終了する。
ステップ２．  
2005527034.tif 000784
をセットする。ここで
2005527034.tif 000785
は小さな数である。
ステップ３．  
2005527034.tif 000786
からスタートし，軌道を得るためシステム(7-4)を正方向に積分する，もしくは，隔離された実行可能要素内にある実行可能点を見つけるため，効果的なハイブリッド局所探索法を適用する。これを
2005527034.tif 000787
とする。
【０１７７】
７．１１．全ての局所最適解を見つける方法
与えられた初期点からスタートし、有制約離散最適化問題(4-5)の全ての局所最適解を見つける動的離散ベース法を以下で開発する。全ての局所最適解が見つかれば，大域最適解は，従って，得られる。そうでなければ，全ての見つけられた局所最適解の最良解が得られる。
仮定：初期点
2005527034.tif 000788
を与える。
目的：(i)有制約離散最適化問題(4-5)の全ての局所最適解を見つける。
(ii)有制約離散最適化問題(4-5)の大域最適解を見つける。
ステップ１．  
2005527034.tif 000789
からスタートし，局所最適解
2005527034.tif 000790
を見つけるため，効果的な局所探索法を適用する。
ステップ２．  j=0をセットする。そして，局所最適解の集合
2005527034.tif 000791
とティア０実行可能要素の集合
2005527034.tif 000792
を初期化する。
ステップ３．  ティア(j+1)実行可能要素の集合
2005527034.tif 000793
を初期化する。
ステップ４．  
2005527034.tif 000794
内の各実行可能点
2005527034.tif 000795
に対し，
2005527034.tif 000796
を含む実行可能要素内の局所最適解と，全ての隣接要素を次のステップにより見つける。
(i)    
2005527034.tif 000797
からスタートし，
2005527034.tif 000798
を含む最適化問題(4-5)の実行可能要素内の全ての局所最適解を見つけるための動的方法適用する。
(ii)   
2005527034.tif 000799
に対する探索経路の集合
2005527034.tif 000800
を定義する。
(iii)  各探索経路
2005527034.tif 000801
に対し，次のステップを実行することにより，隣接実行可能要素を見つける。
(a)    i=1をセットする。
(b)    隣接実行可能要素内にある点
2005527034.tif 000802
を見つけるため，隣接実行可能要素を見つけるための方法を適用する。
(c)    
2005527034.tif 000803
からスタートし，局所最適解
2005527034.tif 000804
を見つけるため効果的な（ハイブリッド）局所探索法を適用する。
2005527034.tif 000805
が既に見つけられたか，すなわち
2005527034.tif 000806
であるか，チェックする。見つかっていなければ，
2005527034.tif 000807
と
2005527034.tif 000808
をセットする。
(d)    i=i+1をセットする。
(e)    i>kとなるまでステップ(b)から(d)を繰り返す。
ステップ５．  全ての新しく計算された実行点の集合
2005527034.tif 000809
が空であれば，ステップ６を継続する。そうでなければ，j=j+1をセットし，ステップ３へ進む。
ステップ６．  局所最適解の集合
2005527034.tif 000810
を出力し，集合
2005527034.tif 000811
の対応する目的関数値の比較により大域最適解を特定し，最小値を有する１つを選択する。これを既知の大域最適解として出力する。
【０１７８】
８．例：ＶＬＳＩ分割問題
ＶＬＳＩシステムはその複雑性によりいくつかのレベルに分割される。（１）システムが，各サブシステムが１つのプリント基板（printed-circuit board：ＰＣＢ）に関し独立的に，デザイン，組み立てさせるサブシステムの集合に分割される，システムレベル分割。（２）ＰＣＢがＶＬＳＩチップに分割される時のボードレベル分割。（３）チップがより小さなサブ回路に分割されるチップレベル分割。各レベルにおいて，分割の制約条件と目的関数は異なる。本例題はチップレベル分割に関し示す。本結果は修正により他の分割レベルへ拡張可能である。
【０１７９】
分割問題はグラフ理論用語にて，より自然に表現される。分割問題を表現するハイパーグラフ
2005527034.tif 000812
は以下のように構築できる。
2005527034.tif 000813
を頂点の集合，
2005527034.tif 000814
をハイパーエッジの集合とする。各頂点は要素を表す。これらの頂点に対応した要素といつでも頂点を結合するハイパーエッジがある。従って，各ハイパーエッジは，頂点集合の部分集合，すなわち
2005527034.tif 000815
である。言いかえると，各ネットはハイパーエッジの集合により表現される。各要素の領域は
2005527034.tif 000816
と表現される。分割問題は
2005527034.tif 000817
を
2005527034.tif 000818
に分割する。ここで，
2005527034.tif 000819
分割はまたカットとして参照される。分割のコストは，カットを横断するハイパーエッジの数である，カットサイズと呼ばれる。
2005527034.tif 000820
を分割
2005527034.tif 000821
と分割
2005527034.tif 000822
間のカットサイズとする。各分割
2005527034.tif 000823
はエリア
2005527034.tif 000824
とターミナルカウント
2005527034.tif 000825
を有する。分割
2005527034.tif 000826
が占める，最大最小エリアは，それぞれ，
2005527034.tif 000827
と
2005527034.tif 000828
と記す。分割
2005527034.tif 000829
が持つこと出来るターミナルの最大数を
2005527034.tif 000830
と記す。
2005527034.tif 000831
をハイパーパスとする。
2005527034.tif 000832
を回数とする。
2005527034.tif 000833
はカットである。
【０１８０】
チップレベル分割における問題の制約条件と目的関数は以下に述べられる。
・     目的関数１はパーティション間の結合を最小化する。結合の低下は遅れを低下させるのみでなく，独立のデザインと製造に対し，それを容易にするパーティション間のインターフェースを低下させる。多くの結合は，配置とルーチンアルゴリズムの作業を複雑にするのみでなく，デザイン領域を増加させる。結合の最小化の目的は以下に記述される。
【０１８１】
【数３９】
2005527034.tif 000834
【０１８２】
・     目的関数２は分割における遅れを最小化する。回路分割は，パスにおいて，遅れを大いに増加させるパーティション間を多数行く，クリティカルパスの原因となる。この問題を述べるため，目的関数を以下に与える。
【０１８３】
【数４０】
2005527034.tif 000835
【０１８４】
・     制約条件１は現在閾値
2005527034.tif 000836
を越えないよう，ターミナルの数を維持することである。この制約条件は以下となる。
【０１８５】
【数４１】
2005527034.tif 000837
【０１８６】
・     制約条件２は現在の限界内に各パーティションの領域を維持すること。チップ分割レベルにおいて，この制約条件は，全てのパーティションが相対的に比較するように，各パーティションのサイズを維持することである。他は，例えば，相互分割問題は１つのパーティションが空，残りのパーティションが問題の全ての要素を含む，結果となる。この制約条件は，物理的な境界がセットされる分割の残りのレベルほど重要でない。領域限界のための制約条件は以下に示す。
【０１８７】
【数４２】
2005527034.tif 000838
【０１８８】
分割問題は閉形式の目的関数が可能でないカテゴリーに属す。パーティションの２つのインスタンス間の連続空間を満たす距離が定義されないことが起こる。従って，解アルゴリズム離散バージョンのみ開発されることができる。
【０１８９】
分割問題を解くため，離散ベースＤＤＰベース法を開発するため，６節において本発明の実施例を適用した。開発方法を実施し，いくつかのベンチマーク問題にて評価した。表４に示されるテスト結果は，４５−５５％領域バランス基準と実セルサイズのもと，異なる初期点から５０回の最小カットセットを用い得られた。また，標準ＦＭ法を用いたシミュレーション結果を比較のため示した。
【０１９０】
ＤＤＰベース法を従来ＦＭ法と組み合わせることにより，解の質は，表４に示されるように，非常に改善された。改善は，大規模回路は大きな改善，小規模回路は小さな改善である，９．５％から２６８％のレンジである。全体として，ＤＤＰベース法は，ＦＭ法より非常に良い。いくつかのケースにおいて，ＤＤＰベース法は，現在の最先端，複数レベル分割アプローチを凌ぐ。最近の作業は，ハイブリッド局所探索法と同様，複数レベルパーティションアプローチの組み合わせにより，また，ＤＤＰベース法は，複数レベルパーティションアプローチの結果以上の重要な改善に到達することができる。
【０１９１】
ＤＤＰベース法の他の改善は，解の逸脱がＦＭ法の同じ指標と比較し，十分小さいことである。この改善は，ＤＤＰベース法が良い解を得るためＦＭ法より，非常に短い計算時間であることを意味する。
【０１９２】
【表１】
2005527034.tif 000839
【０１９３】
参考資料：
１．   "組み合わせ最適化の局所探索", E.アーツ，J.K.レンストラ編集，ウィリ，１９９７
２．   H.D.チャン，L.フェキ−アフメッド，"非線形動的システムの準安定領域：理論"，IEEE 回路とシステムI：基本理論と適用，CAS-43号，８月，１９９６，６２７−６３５ページ。
３．   シャオ・ドン・チャン，チア・チ・チュ，"非線形プログラム問題の複数局所最適解を得るための系統的な探索法"，IEEE 回路とシステムI：基本理論と適用，43号，２号，２月，１９９６，９９−１０９ページ。
４．   H.D.チャン，M.ヒルシュ，F.F.ウ−，"非線形非自律系動的システムの安定領域"，IEEE 自動制御，AC-33号，１月，１９８８，１６−２７ページ。
【図面の簡単な説明】
【０１９４】
【図１】図１は連続空間において既知の局所最適解から局所最適解探索のＤＤＰベース法の図を表す。
【図２】図２は連続空間において既知の局所最適解から局所最適解探索のＥＰベース法の図を表す。
【図３】図３は離散空間において既知の局所最適解から局所最適解探索のＤＤＰベース法の図を表す。
【図４】図４は離散空間において既知の局所最適解から局所最適解探索のＥＰベース法の図を表す。
【図５】図５は全局所最適解探索の図を表す。
【図１】
2005527034.tif 000863
【図２】
2005527034.tif 000864
【図３】
2005527034.tif 000865
【図４】
2005527034.tif 000866
【図５】
2005527034.tif 000867
【国際調査報告】
2005527034.tif 000868
2005527034.tif 000869