状態近傍

ウィキペディア小見出し辞書

状態近傍

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 03:36 UTC 版)

「タブーサーチ」の記事における「状態近傍」の解説

焼きなまし法と同様にタブーサーチにおいて近傍の定義は非常に重要になってくる、特にタブーサーチの場合複数の近傍が存在していることが前提なので設定次第では探索が停滞したり、最適解に到達不可能になる可能性もある。 基本的には探索グラフで表した場合、ほぼ同様のエネルギー状態になるようにおくことが好まれる、巡回セールスマン問題の場合なら隣り合う都市を入れ換えるなどである。

状態近傍

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 07:49 UTC 版)

「焼きなまし法」の記事における「状態近傍」の解説

各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。たとえば、巡回セールスマン問題において、個々の状態は、一般に「ツアー」（訪問する都市の順列）と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。

状態近傍

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 07:49 UTC 版)

「焼きなまし法」の記事における「状態近傍」の解説

近傍の選択方法は、特に重要である。「探索グラフ」としてモデル化できる場合もある。状態を点とし、近傍となる点との間に線が引かれる。概して、初期状態からこのグラフ上の相対的に短いパスを通って「十分によい」状態となる可能性は極めて高く、そのようなパスを焼きなまし法の繰り返しで辿ることもほぼ間違いない。 実際には、s の近傍に s とほぼ同じエネルギーの状態群を置く様に探索グラフを作成し、この手法を適用する場合を考える。したがって、巡回セールスマン問題なら、経路上隣接する2つの都市の順序を入れ替えることで近傍を生成した方が、任意の都市を入れ替えた経路を生成するよりもエネルギーの変化が小さい。n-1 回、任意の都市を入れ替えることで最適解が見つかるとすれば、隣接都市の入れ替えでは n(n-1)/2 回の入れ替えを必要とする。しかし、任意の都市入れ替えを適用した場合、ほぼ確実にエネルギーの大幅な増加となるだろう。一方、隣接都市入れ替えではエネルギーの変化は小さい。