【要約】巡回セールスマン問題をいろいろな手法で解いてみる④：アニーリング法 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
- ・組合せ最適化問題における局所最適解への停滞。
- ・単純な山登り法では、一度局所的な解に陥ると脱出不能。
- ・解の探索範囲の広さと、最終的な収束性の両立が課題。
// Approach
物理的な焼きなましプロセスをシミュレートする。
1.メトロポリス基準に基づき、解が悪化する場合でも確率的に採用する。
2.採用確率は
math.exp(-diff / current_temperature) で決定。3.高温時は広範囲を探索し、低温時は山登り法的に収束させる。
4.
cooling_rate（例: 0.9999）を用いて、ループごとに温度を徐々に下げる。5.
swap_cities 関数により、2つの都市を入れ替える近傍解を生成。// Result
- ・100,000回のイテレーションにより、交差の少ない効率的なルートを算出。
- ・温度低下に伴い、解が安定した状態へ収束することを確認。
Senior Engineer Insight
>
局所最適解を回避できる点は強力だ。しかし、ハイパーパラメータへの依存が極めて高い。初期温度や冷却速度の設定が、精度と計算時間に直結する。実戦では、問題規模に応じたパラメータの自動最適化が必須だ。計算資源の効率的な利用には、冷却スケジュールの設計が鍵となる。