焼きなまし法【simulated annealing】シミュレーテッドアニーリング法

概要

探索は初期解から始まり、少し変化させた候補を繰り返し生成して評価する。評価が改善すればその解を採用し、悪化しても「温度」に応じた確率で受け入れる。この仕組みにより、狭い範囲の解に固定されることを避けられる。

温度はアルゴリズムの挙動を制御するパラメータの一つで、探索の進行に合わせて徐々に下げられる。初期は温度が高い状態で、悪化する解も積極的に受け入れて広範囲を探る。温度が下がるにつれて悪化する解を受け入れる確率も小さくなり、探索は有望な解の周辺へと絞られていく。

常に評価が上がる方向へしか進まない「山登り法」では、最初に見つけた小さな山の頂上から抜け出せなくなることがある。焼きなまし法は一時的に評価が下がる移動も許容することで、谷や峠を越えて、より高い山を発見できる可能性を高めている。この温度の下げ方は「冷却」と呼ばれ、急激に下げると局所最適解に陥りやすく、緩やかに下げすぎると計算に時間がかかるというトレードオフがある。

焼きなまし法は、巡回セールスマン問題やスケジューリング、集積回路の配線設計など、組み合わせの数が膨大で全探索が現実的でない問題に対してよく利用される。厳密な最適解を保証するものではないが、比較的少ない計算量で実用上十分な精度の解を得やすく、様々な分野で応用されている。確率的な手法であるため、同じ問題であっても実行の度に結果が異なる場合がある。初期解の選び方や候補の生成方法、冷却速度などの設定によって、探索の効率や解の品質が変わってくる。