何をする手法か?
焼きなまし法は、1983年にKirkpatrick、Gelatt、Vecchiによって導入された確率的局所探索メタヒューリスティックである。これは、金属学における物理的な焼きなましプロセス(材料を加熱し、ゆっくり冷却して低エネルギーの結晶状態にする)をモデル化し、この類推を用いて組み合わせ最適化問題および連続最適化問題における局所的最適解からの脱出を図る。
手法の背後にある直感
目隠しをした状態で起伏の多い地形の最も低い地点を見つけようとしていると想像してほしい。純粋に貪欲な探索は常に下り坂をたどり、最初に見つけた谷に閉じ込められてしまう。これは必ずしも最も深い谷ではないかもしれない。焼きなまし法は制御されたランダム性を導入する。初期段階では、「温度」が高いとき、アルゴリズムは時折上り坂をたどることを受け入れ、偶然により悪い解を受け入れる。冷却スケジュールに従って温度が低下するにつれて、アルゴリズムはますます選択的になり、解に収束する。この高い温度での悪い移動を受け入れる意欲が、局所的最適解への早期収束を防ぎ、地形をより徹底的に探索することを可能にするメカニズムである。
歴史学
焼きなまし法は、1983年のScience誌におけるKirkpatrick、Gelatt、Vecchiによる画期的な論文で導入された。この論文では、固体の熱的焼きなましと組み合わせ最適化との間に明確な類推が示された。同じ考えは、巡回セールスマン問題の文脈でCerny(1985)によって独立に提案された。van LaarhovenとAarts(1987)は、さまざまな冷却スケジュール下での収束特性を証明し、最初の厳密な理論的扱いを提供した。以来、この手法は最も広く研究され応用されているメタヒューリスティックの1つとなり、工学設計、オペレーションズリサーチ、VLSIレイアウト、機械学習ハイパーパラメータチューニングなど、さまざまな分野で使用されている。
使うべき場面
焼きなまし法は、目的関数が微分可能であるか、凸であるか、あるいは解析的に表現可能であるかに関係なく、解空間上に近傍構造を定義できるあらゆる問題に適用可能である。特に組み合わせ問題(スケジューリング、ルーティング、グラフ問題)や連続的なブラックボックス最適化に適している。学習データや正規性の仮定は不要である。冷却スケジュールと近傍構造は問題に合わせて調整する必要があり、約1,000回の反復未満の実行は、局所的最適解への早期収束のリスクがあり、その場合はより単純な決定論的局所探索が好ましい。
限界と注意点
- 解の質は冷却スケジュールに敏感であり、悪いスケジュールではランダム探索と同程度の結果しか得られない可能性がある。
- 近傍構造は各問題クラスごとに設計する必要があり、ドメイン知識が必要となる。
- 大域的最適解への収束には実際には非常に遅い冷却が必要であり、高品質の保証を得るには実行時間が長くなる。
- 勾配や構造情報を活用しないため、滑らかで微分可能な問題では勾配ベースの方法よりも性能が劣る。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 純粋なヒルクライミングとは異なり、悪い解を確率的に受け入れることで局所的最適解から脱出できる。
- 近傍構造が定義されている限り、組み合わせ、連続、混合など、事実上あらゆる種類の問題に適用できる。
- 勾配情報が不要で、目的関数の数学的構造に関係なく動作する。
- 十分な低速冷却下での大域的最適解への収束に関する理論的保証がある(Hajek 1988)。
- ハイパーパラメータが少ない:初期温度、冷却率、近傍構造。
応用
- 解空間が網羅的探索には大きすぎる組み合わせスケジューリングおよびタイムテーブル作成問題。
- 物流およびオペレーションズリサーチにおける巡回セールスマン問題および車両ルーティング問題。
- 電気工学におけるVLSI回路レイアウトおよびチップフロアプランニング。
- 計算生物学におけるタンパク質フォールディングおよび分子構造問題。
- 勾配情報が利用できない場合の機械学習モデルのハイパーパラメータ最適化。
- 工学および経営科学におけるリソース割り当ておよび割り当て問題。
使い方
使い方
アルゴリズムは、開始解(探索空間内の任意の実行可能点)と高い初期温度から始まる。開始解はランダムまたは問題固有のものであり、初期温度は通常、開始時にほぼすべての近傍解が受け入れられるほど高く設定される。
近傍解は、現在の解に小さなランダムな変更(「移動」)を適用することによって生成される。近傍構造は問題に合わせて調整する必要がある。スケジューリング問題では、移動は2つのタスクを交換することかもしれない。連続関数では、現在のパラメータベクトルに小さなランダムな摂動を加えることかもしれない。
新しい解と現在の解との間の目的値の差が計算される。新しい解がより良い場合は、常に受け入れられる。悪い場合は、劣化の大きさや現在の温度に応じて減衰する確率、通常はexp(−ΔE / T)で受け入れられる。この確率的な受け入れが、早期収束を防ぐ中心的なメカニズムである。
各反復後(または同じ温度で固定数の移動後)、冷却スケジュールに従って温度が低下する。一般的には、1よりわずかに小さいαを用いた幾何学的スケジュールT ← α·Tである。冷却スケジュールの選択は解の質に強く影響する。冷却が速すぎると探索が局所的最適解に閉じ込められ、冷却が遅すぎると計算時間が無駄になる。
アルゴリズムは、温度が最小しきい値を下回ったとき、最大反復回数に達したとき、または指定されたステップ数で解が改善されなかったときに停止する。実行全体で遭遇した最良の解(最終状態だけでなく)が結果として返される。
よくある落とし穴
- 反復回数が少なすぎる(約1,000回未満)と、冷却スケジュールが適切に機能せず、探索が局所的最適解に閉じ込められる。実行時間が大幅に制限されている場合は、タブー探索または決定論的局所探索を優先する。
- 初期温度を低すぎると、アルゴリズムはすぐに貪欲なヒルクライミングのように動作し、局所的最適解から脱出する能力を失う。
- 冷却率を過度に速く設定する(例:αが0.9未満)と早期収束を引き起こす。複数の初期解から再起動して最終解の質を確認する。
- ある問題タイプ用に設計された近傍移動を異なる問題に適用すると、移動が無効または無意味になる可能性がある。生成されたすべての近傍が有効な解であることを常に確認する。
- 実行中に見られた最良の解ではなく、最終状態のみを報告すると、中間ステップで見つかった真の最適解を見逃す可能性がある。
よくある質問
冷却スケジュールをどのように選択しますか?
αが0.90から0.99の間にある幾何学的スケジュールT ← α·Tが最も一般的である。実用的なアプローチは、開始時に約80%の移動が受け入れられるように初期温度を高く設定し、その後1%未満の上向き移動が受け入れられるまで温度を下げることである。最終的な解の質が低い場合は、冷却速度を遅くする(αを増やす)。実行時間が長すぎる場合は、速める。頑健性を評価するために、常に異なる開始解からアルゴリズムを複数回実行する。
焼きなまし法は、遺伝的アルゴリズムや粒子群最適化とどのように異なりますか?
焼きなまし法は単一の解を維持し、ランダムな摂動を通じて近傍を探索し、悪い解を確率的に受け入れる。遺伝的アルゴリズムと粒子群最適化は、解の集団を維持し、交差、突然変異、または群れの移動を使用して集団を進化させる。焼きなまし法は、自然な近傍構造を持つ問題の実装が一般的に簡単である一方、集団ベースの方法は高次元連続問題により効果的である可能性がある。
大域的最適解は保証されますか?
理論的にははい、温度が十分に遅く低下するという条件(対数冷却)の下では。実際には、そのような冷却は計算上実行不可能であるため、アルゴリズムはほぼ最適解を見つける。結果の質は、より遅い冷却とより多くの反復で向上するが、有限時間での保証はない。複数の再起動を実行し、見つかった最良の解を保持することが、信頼性を高める実用的な方法である。
タブー探索や遺伝的アルゴリズムを代わりに選択すべきなのはいつですか?
実行時間が短い場合に、最近の解の再訪問を避け、問題構造を効率的に利用できる、決定論的でメモリガイド型の探索が必要な場合は、タブー探索を選択する。問題が高次元で連続である場合、または最適化ランドスケープをマッピングするために多様な解の集団が必要な場合は、遺伝的アルゴリズムまたは粒子群最適化を選択する。焼きなまし法は、明確な近傍構造を持つ組み合わせ問題で、実装の単純さが重要な場合に強力なデフォルトとなる。
関連する手法
参考文献
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
DOI 文献を開くコピーしました。van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN:9789027725431コピーしました。