焼きなまし法｜数理最適化

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：局所探索と近傍　|　関連：タブー探索

要点（BLUF）

焼きなまし法（SA）は局所探索に 「悪化も確率的に受理する」 を加え、局所最適を脱出する。
受理確率は メトロポリス基準 $\exp(-\Delta E / T)$ 。温度 $T$ が高いと悪化を受け入れやすい。
$T$ を徐々に下げる（冷却）と、序盤は広く探索・終盤は局所最適化。理論上、十分ゆっくり冷やせば大域最適に収束。

概念 ── 金属の焼きなましに学ぶ

金属を高温から ゆっくり冷やすと、原子が低エネルギー状態（規則正しい結晶）に落ち着く。急冷すると欠陥だらけの局所最適に固まる。この物理を最適化に借りたのが SA。「目的関数＝エネルギー」「解＝状態」「制御パラメータ＝温度」と読み替える。

山登り（局所探索と近傍）は改善する隣にしか動かないので局所最適で止まる。SA は 温度が高いうちは悪化する隣にも飛び移れるので、谷を登って別の谷へ抜けられる。

メトロポリス基準

近傍からランダムに候補解を選び、目的の変化 $\Delta E = f(\text{新}) - f(\text{現})$ に応じて受理する：

P(\text{受理}) = \begin{cases} 1 & \Delta E \le 0 \quad (\text{改善ならば必ず受理}) \\ \exp\!\left(-\dfrac{\Delta E}{T}\right) & \Delta E > 0 \quad (\text{悪化は確率的に受理}) \end{cases}

$T$ が 大きい： $\exp(-\Delta E/T)\approx1$ 、悪化もほぼ受理 → ほぼランダムウォーク（広域探索）。
$T$ が 小さい： $\exp(-\Delta E/T)\approx0$ 、悪化を拒否 → 山登りに近づく（局所最適化）。
悪化幅 $\Delta E$ が大きいほど受理しにくい（小さな悪化は許すが大きな悪化は稀）。

冷却スケジュール： $T$ を $T \leftarrow \alpha T$ （ $\alpha<1$ 、幾何冷却）などで徐々に下げる。

Pythonで脱出を確認

山登りが局所最適 $-7.05$ に捕まった初期点（局所探索と近傍の $x=-12$ ）から SA を走らせ、大域最適 $-1.45$ へ抜けられるか見る。

import numpy as np

xs = np.linspace(-15, 15, 601)
def f(x): return 0.1*x**2 + 2*np.sin(x)
fvals = f(xs)

def simulated_annealing(seed, T0=10.0, cooling=0.9995, steps=6000):
    rng = np.random.default_rng(seed)
    i = 60                  # 初期 x=-12 (山登りなら-7.05で停止する側)
    best_i = i
    T = T0
    for step in range(steps):
        j = i + rng.integers(-3, 4)          # 近傍へランダム移動
        if not (0 <= j < len(xs)):
            continue
        dE = fvals[j] - fvals[i]             # エネルギー変化
        if dE < 0 or rng.random() < np.exp(-dE / T):   # メトロポリス基準
            i = j
            if fvals[i] < fvals[best_i]:
                best_i = i
        T *= cooling                          # 冷却
    return best_i

print(f"参照(全探索)最小: x={xs[np.argmin(fvals)]:.3f}, f={fvals.min():.4f}")
r = simulated_annealing(seed=0)
print(f"焼きなまし(初期x=-12): x={xs[r]:+.3f}, f={fvals[r]:.4f}")

実行結果：

参照(全探索)最小: x=-1.450, f=-1.7752
焼きなまし(初期x=-12): x=-1.450, f=-1.7752

山登りなら $-7.05$ （ $f=3.58$ ）で止まる初期点から、SA は局所最適の壁を温度の力で乗り越え、大域最適 $x=-1.45$ （ $f=-1.78$ ）に到達。序盤の高温で広く動き回り、冷却とともに良い谷へ収束した。

数式の直観的意味

メトロポリス基準 $\exp(-\Delta E/T)$ は統計力学の ボルツマン分布そのもの。温度 $T$ での状態の確率は $\propto \exp(-f(x)/T)$ で、SA はこの分布からのサンプリング（マルコフ連鎖）を、 $T$ を下げながら行う。 $T\to0$ の極限でボルツマン分布は最小エネルギー状態に集中する ── だから「十分ゆっくり冷やせば大域最適に確率1で収束」という理論保証がある（対数冷却 $T_k = c/\log k$ ）。ただし理論的な冷却は遅すぎて実用にならず、現実は幾何冷却で「ほぼ最適」を狙う。温度は「悪化をどれだけ許すか」＝探索（exploration）と活用（exploitation）のつまみで、高温＝探索、低温＝活用。この調整がベイズ最適化や強化学習の温度パラメータにも通じる普遍的な考え。

⚠️ よくある誤解・落とし穴

冷却が速すぎると急冷（局所最適に固まる）、遅すぎると時間がかかる。スケジュール調整が肝。
理論保証の冷却は遅すぎて非実用的。実務は幾何冷却で「十分良い解」を狙う（厳密最適は保証されない）。
初期温度の決め方：序盤の受理率が $0.8$ 程度になるよう $T_0$ を設定するのが目安。
最良解は別に記録する：最後の解より、探索中に出会った最良解（incumbent）を返す。