【要約】巡回セールスマン問題をいろいろな手法で解いてみる④：アニーリング法 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
巡回セールスマン問題のような組合せ最適化問題では、単純な山登り法を用いると、局所的な最適解（ローカルオプティマ）に陥り、真の最適解を見逃すリスクがある。探索空間が膨大になるほど、この課題は深刻化し、効率的な解の探索が困難になる。
// Approach
物理的な冷却プロセスを模倣し、高温時には改悪を許容して広範囲を探索し、低温になるにつれて探索範囲を絞り込む手法を採用する。メトロポリス基準に基づき、コストが増加する場合でも温度に応じて確率的に遷移を許可することで、局所解からの脱出を実現する。
// Result
Pythonを用いた実装により、温度の低下とともに経路が最適化され、交差の少ない効率的なルートへ収束する様子を確認できる。ハイパーパラメータの調整が、解の精度と計算時間のトレードオフを制御する鍵となる。
Senior Engineer Insight
>
メタヒューリスティクスとしての有用性は高いが、実戦投入には「パラメータの感度」という課題が付きまとう。初期温度や冷却率の設定次第で、解の品質と計算時間が劇的に変動するため、決定論的な挙動が求められるシステムには不向きだ。物流や配送計画などのバッチ処理的な最適化には極めて強力な武器となるが、リアルタイム性が要求されるパス計算等に用いる場合は、計算時間のワーストケースを考慮した設計が不可欠である。