焼きなまし法

悪化する移動も、確率的に受け入れる局所探索。 Simulated Annealing、SA。金属を高温から徐々に冷やして 結晶構造を整える焼きなましが名前の由来。

Kirkpatrick らが 1983 年に組合せ最適化へ導入した。

手順#

1. 温度 $T$ を高く設定する
2. 現在解の近傍から候補 $x^{\prime }$ を作る
3. $\mathrm{\Delta }=f(x^{\prime })-f(x)$ を計算する
4. $\mathrm{\Delta }<0$（改善）なら必ず受け入れる
5. $\mathrm{\Delta }\ge 0$（悪化）でも確率 $\exp (-\mathrm{\Delta }/T)$ で受け入れる
6. $T$ を少し下げ、2 へ戻る

温度の役割#

$T$	受理確率	振る舞い
高い	悪化もほぼ受け入れる	ほぼランダムウォーク。広く探索
中くらい	小さい悪化は受け入れる	浅い局所解から抜けられる
低い	改善しか受け入れない	山登り法と同じ

つまり温度が探索と活用の 配分をひとつのパラメータで制御している。

理論保証と現実#

冷却が十分に遅ければ（$T_k\ge c/\log k$ 程度）、 確率 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
• Stuart Geman, Donald Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE TPAMI 6(6), 1984.（冷却スケジュールの収束定理） https://doi.org/10.1109/TPAMI.1984.4767596
• 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