温度と受理確率

焼きなまし法で唯一の調整対象が温度 $T$。悪化をどれだけ許すかを決める。

$$P(\text{受理})=\{\begin{array}{cc}1& \mathrm{\Delta }\le 0\\ \exp (-\mathrm{\Delta }/T)& \mathrm{\Delta }>0\end{array}$$

具体的な数字で見る#

$\mathrm{\Delta }=1$ の悪化に対する受理確率。

$T$	$\exp (-1/T)$
10	0.90
1	0.37
0.1	$4.5\times {10}^{-5}$
0.01	$3.7\times {10}^{-44}$

$T$ が 1 を割ると急速に受け入れなくなる。 つまり$T$ は目的関数の変化量と同じ尺度で読むべき量で、 $f$ のスケールが変われば適切な $T$ も変わる。

初期温度の決め方#

理屈から決めるのは難しいので、実測から逆算するのが定石。

1. 無作為な移動を何回か試し、悪化量 $\mathrm{\Delta }$ の平均を測る
2. 初期受理率を 0.8 程度にしたいなら $T_0=-\bar{\mathrm{\Delta }}/\ln 0.8$

初期受理率を目安にするのは、$f$ のスケールに依存しない指標だから。

受理率を監視する#

探索中の受理率は、温度が適切かを示す。

• 高すぎる（0.9 以上が続く） … ほぼランダムウォーク。冷やすべき
• 低すぎる（0.01 未満） … 動けていない。実質的に山登り法
• 0.2〜0.5 程度 … おおむね機能している

受理率を目標値に保つよう $T$ を自動調整する 適応的焼きなましも広く使われる。

参考文献#

• 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
• 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