Day 154-Q5 | Simulated Annealing（焼きなまし法）

問題

状態は整数 $x \in \{0,1,\dots,N-1\}$ で表され、各状態にはコスト $f(x)$ が定まっている。初期状態 $x_0$ から出発し、$K$ 回の焼きなましステップを行う。

ステップ $k$（$k=0,1,\dots,K-1$）では：

温度 $T_k = T_0 / 2^k$ を計算する
移動候補 $x' = x + d_k$ を提案する（$x' \notin [0,N-1]$ の場合はこのステップを何もせず棄却する）
$\Delta = f(x') - f(x)$ を計算する
$\Delta \le 0$、または（$\Delta > 0$ かつ乱数値 $r_k < \exp(-\Delta / T_k)$）ならば移動を受理し $x \leftarrow x'$ とする。それ以外は $x$ を維持する

すべてのステップ終了後、これまでに訪れたすべての状態（初期状態を含む）の中でコストが最小だったものの状態番号とコストを出力せよ。再現性のため、乱数値の列 $r_0,\dots,r_{K-1}$ は入力として明示的に与えられる。

入力形式

N
f_0 f_1 ... f_{N-1}
x_0
K
d_0 d_1 ... d_{K-1}
T_0
r_0 r_1 ... r_{K-1}

制約

$1 \le N \le 2 \times 10^5$

$0 \le f_i \le 10^9$

$d_k \in \{-1,+1\}$

$0 < T_0 \le 100$、$0 \le r_k < 1$

入出力例

入力例1

5
4 1 3 0 2
0
4
1 1 1 1
8
0.10 0.05 0.30 0.02

出力例1

3 0

概念図：局所最適からの脱出（エネルギー地形）

ヒント（段階的開示）

ヒント1（方向性）

$f=[4,1,3,0,2]$ で $x_0=0$ から改善方向にしか動かない山登り法を行うと、$x=0\to1$（改善）の後、$x=1$の隣は $x=0$（$f=4$）と $x=2$（$f=3$）でどちらも $f(1)=1$ より大きいためそこで身動きが取れなくなる（局所最適）。真の最小値は $x=3$（$f=0$）にあるのに到達できない。焼きなまし法がどうやってこの「谷」を越えるかを追う。

ヒント2（アプローチ）

$\Delta>0$（悪化する移動）でも、温度 $T_k$ が高いうちは $\exp(-\Delta/T_k)$ が1に近く、多少の悪化なら高確率で受理される。温度が下がるにつれてこの確率は急速に0へ近づく。「今の状態」と「これまでの最良状態（best-so-far）」を別々に管理するのが実装上の要点。

ヒント3（誘導）

best_x, best_f = x0, f[x0]
x = x0
for k in range(K):
    T = T0 / (2 ** k)
    nx = x + d[k]
    if not (0 <= nx < N):
        continue
    delta = f[nx] - f[x]
    if delta <= 0 or r[k] < math.exp(-delta / T):
        x = nx
        if f[x] < best_f:
            best_x, best_f = x, f[x]
print(best_x, best_f)

模範解答 (Python)

import sys
import math
input = sys.stdin.readline


def main():
    N = int(input())
    f = list(map(int, input().split()))
    x0 = int(input())
    K = int(input())
    d = list(map(int, input().split()))
    T0 = float(input())
    r = list(map(float, input().split()))

    x = x0
    best_x, best_f = x0, f[x0]

    for k in range(K):
        T = T0 / (2 ** k)
        nx = x + d[k]
        if not (0 <= nx < N):
            continue
        delta = f[nx] - f[x]
        if delta <= 0 or r[k] < math.exp(-delta / T):
            x = nx
            if f[x] < best_f:
                best_x, best_f = x, f[x]

    print(best_x, best_f)


main()

Step-by-Step 解説

1$k=0$（$T_0=8$）
$x=0,f(0)=4$。$d_0=+1$で$x'=1$、$\Delta=1-4=-3\le0$→無条件受理。$x=1,f(1)=1$。best更新: best=(1,1)。

2$k=1$（$T_1=4$）— 焼きなましの本領
$d_1=+1$で$x'=2$、$\Delta=3-1=2>0$（改悪）。受理確率 $\exp(-2/4)\approx0.6065$。乱数 $r_1=0.05<0.6065$ なので改悪を受理。$x=2,f(2)=3$。best据え置き。この「あえて悪化する」動きがHill Climbingでは不可能な脱出になっている。

3$k=2$（$T_2=2$）
$d_2=+1$で$x'=3$、$\Delta=0-3=-3\le0$→無条件受理。$x=3,f(3)=0$。best=(3,0)に更新（真の最小値に到達）。

4$k=3$（$T_3=1$）— 最良点からさらに離れる
$d_3=+1$で$x'=4$、$\Delta=2-0=2>0$。受理確率$\exp(-2)\approx0.1353$。$r_3=0.02<0.1353$なので受理され$x=4,f(4)=2$に移動。しかしbest_f=0は$2$より小さいためbestは更新されない。出力は最終状態$x=4$ではなくbest=(3,0)の3 0となり出力例と一致する。

よくあるミス

ミス	原因	正しい書き方
ループ終了後のxをそのまま答えとして出力する	「焼きなましは最後には収束するはず」という誤解	温度が下がりきる前でも改悪を受理する可能性が残るため、best_x, best_fを別変数で管理し続ける
Δ≤0の場合にも確率判定を通してしまう	受理条件の実装を1本化しすぎる	改善は無条件受理、悪化のみ確率判定、と条件分岐を明確に分ける
温度T_kを毎ステップ初期値のまま使う	スケジュール式T_k=T_0/2^kの適用を忘れる	各ステップでkに応じた温度を再計算する
範囲外への移動を例外にする・クランプする	境界処理の仕様を独自解釈する	範囲外なら何もせずそのステップを終える（仕様通り）
確率計算に整数除算//を使い確率が0か1に潰れる	Pythonの/と//の取り違え	温度計算・確率計算は必ず浮動小数点除算/を使う

次のステップ

発展: 温度スケジュールを $T_k=T_0/2^k$（指数冷却）から $T_k=T_0/(k+1)$（対数的に遅い冷却）に変えると、同じ乱数列・移動列でも受理される改悪の範囲が変わる。実際に手計算し直し、どちらがこの$f$配列の大域最小値により確実に到達するか比較せよ。
次回予告: フェーズ8+ ローテーション継続（新規テーマ選定）

自己評価

完全理解おおむね理解要復習

Day 154-Q5 — Simulated Annealing（焼きなまし法）

問題