冷却スケジュール

温度をどう下げるか。焼きなまし法の性能を実質的に決める部分。

代表的な形#

名前	式	性質
指数冷却	$T_k=T_0{\alpha }^k$（$\alpha =0.90\sim 0.99$）	最も広く使われる。実装が簡単
線形冷却	$T_k=T_0-\beta k$	終盤で 0 に達し、以降は山登り法
対数冷却	$T_k=c/\ln (k+1)$	理論保証があるが遅すぎる
適応冷却	受理率を見て調整	スケールに依存しない

理論と実用の乖離#

Geman と Geman は、$T_k\ge c/\ln (k+1)$ を満たす冷却なら 確率 1 で大域最適解に収束することを示した。

しかしこの速度は極端に遅い。$T$ を半分にするのに $k$ を二乗する必要があり、実用的な時間では終わらない。

そのため実務では指数冷却を使うが、その瞬間に理論保証は失われる。 焼きなまし法は「理論的に保証されたアルゴリズム」ではなく、 「理論に着想を得たヒューリスティック」として運用されている。 論文の主張を読むときはここを区別したい。

再加熱#

温度を単調に下げるだけでなく、停滞したら上げ直す運用もある （reheating、あるいは非単調冷却）。 CMA-ES の再始動や ABC の Scout Bee と同じく、 「行き詰まったら探索側へ戻す」という発想。

参考文献#

• 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
• Bruce Hajek. Cooling Schedules for Optimal Annealing. Mathematics of Operations Research 13(2), 1988. https://doi.org/10.1287/moor.13.2.311
• 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