焼きなまし・局所探索

現在の解を少しずつ変えながら良くしていく手法群。 局所探索を土台に、 局所最適解から抜け出す仕掛けを足したもの。

抜け出し方の違い#

手法	抜け出す仕掛け
焼きなまし法	悪化も確率的に受け入れる。確率は温度で制御
タブー探索	直前の手を禁じ、来た道を戻れなくする
反復局所探索	局所解に落ちたら大きく揺さぶって再開

集団を持たないので記憶量が小さく実装が短いのが利点。 組合せ最適化で特に使われる。

参考文献#

• 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
• Scott Kirkpatrick, C. Daniel Gelatt, Mario P. Vecchi. Optimization by Simulated Annealing. Science 220(4598), 1983. https://doi.org/10.1126/science.220.4598.671