局所探索

現在の解の近傍を調べ、良い解が見つかったら移ることを繰り返す枠組み。 local search。近傍の定義を変えるだけで、連続にも組合せにも使える。

構成要素#

1. 初期解 — 無作為、あるいは貪欲法で作る
2. 近傍 $𝒩(x)$ — そこから 1 手で行ける解の集合
3. 移動の規則 — 近傍のどれに移るか
4. 停止条件 — 改善が無くなったら止める

組合せ問題では近傍の設計が性能を決める。 巡回セールスマン問題の 2-opt なら 「経路の 2 辺を選んで繋ぎ替える」が 1 手。

移動の規則#

規則	内容
最良改善 (best improvement)	近傍を全部調べ、最も良いものへ移る
最初の改善 (first improvement)	改善が見つかった時点で移る。1 手が速い

近傍が大きいときは最初の改善の方が全体として速いことが多い。

必ず局所最適解で止まる#

近傍に改善が無くなったら止まる。それは 局所最適解であって、 大域最適解とは限らない。ここから抜け出す工夫が 焼きなまし法（悪化も確率的に受け入れる）や タブー探索（直前の手を禁じる）で、 どちらも局所探索を土台にしている。

参考文献#

• Emile Aarts, Jan Karel Lenstra (eds.). Local Search in Combinatorial Optimization. Princeton University Press, 2003. https://doi.org/10.2307/j.ctv346t9c
• Holger H. Hoos, Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. https://doi.org/10.1016/B978-1-55860-872-6.X5016-1