TL;DR
大域的最適化問題に使える汎用の乱択アルゴリズム。金属の焼きなましにならい、「温度」を下げながら、悪くなる方向への移動もある確率で受け入れて探索する。
なぜ必要か
山登り法は改善する方向にしか動かないので、局所的な最適解に捕まりやすい。焼きなまし法は、温度が高い間は悪い状態への移動も受け入れるので、局所解から抜け出せる。
仕組み
Wikipedia によると、探索空間の各点を「状態」、最小化したい関数を「エネルギー」と見なす。今の状態の近傍から次の状態を選び、エネルギーが下がるなら必ず移り、上がるなら温度 T とエネルギーの差に応じた確率で移る。Kirkpatrick らの元の手法では、エネルギーが e から e′ に上がる移動を exp((e−e′)/T) の確率で受け入れる。
温度は高い値から始めて、少しずつ 0 に近づける。一般には毎ステップ一定の係数を掛けて指数的に下げる。温度が下がるほど移動は改善する方向に限られ、最後はエネルギーの低い状態に落ち着く。名前は金属を熱してからゆっくり冷やし、結晶の欠陥を減らす焼きなましに由来する。
例
巡回セールスマン問題では、都市を回る順番を状態とし、順番を 1 か所入れ替えたものを近傍とする。
注意点
冷却スケジュールを適切に調整すれば、大域的最適解を得る確率は 1 に近づく。ただし、そのためには解空間を十分に探索する時間が要る。どの問題にも最善というパラメータの選び方はなく、特に近傍の設計が結果を左右する。