焼きなまし法の改良

焼きなまし法の改良

執筆済 最適化焼きなまし

素の焼きなまし法は遅い。実務で使うには工夫が要る。

主な方向#

並列テンパリング (replica exchange)

異なる温度のレプリカを同時に走らせ、定期的に状態を交換する。 高温側が広く探索し、低温側が精密化する。 温度スケジュールを事前に決めなくてよいのが利点で、 物理シミュレーションから最適化まで広く使われる。

適応的な温度制御

受理率を目標値（0.2〜0.5 程度）に保つよう T を調整する。 温度が 目的関数のスケールに依存する問題を回避できる。

近傍の設計

温度以上に効くことが多い。良い近傍とは

  • 1 手で目的関数が大きく変わりすぎない（受理率が保てる）
  • 差分だけで評価できる（f を再計算しなくてよい）
  • 実行可能解の間を移動できる（制約を破らない）

TSP の 2-opt は この 3 つをすべて満たす好例。

量子版#

温度による揺らぎの代わりに量子ゆらぎを使うのが 量子アニーリング。 横磁場の強さを下げていくことで、 トンネル効果によって 細く高い障壁を通り抜けられる、という主張になっている。

これを古典計算機で模倣したのが シミュレーテッド量子アニーリングで、 経路積分表示を使うと実質的に並列テンパリングに近い形になる。

参考文献#