1983-模擬退火#

案件摘要#

組合最佳化的老困境：局部搜尋（如 KL、簡單交換法）一掉進局部最優就爬不出來——像登山客在霧中困在小山頭，看不見遠處的主峰。1983 年，IBM Watson 的 Scott Kirkpatrick、Daniel Gelatt、Mario Vecchi 在《Science》發表模擬退火（Simulated Annealing）：借冶金退火的物理——先高溫讓原子亂跑、再緩慢降溫讓晶格整齊——允許演算法以機率 \(e^{-\Delta E / T}\) 接受變差的移動，溫度 \(T\) 逐步下降。這是「以隨機換全局」的演算法革命，1985 年 Timberwolf 把它用於晶片佈局並擊敗 min-cut，退火自此成為 EDA 與組合最佳化的通用武器。

前因 -- 為什麼會有這個案子#

局部最優的陷阱：佈局、繞線、分區都是 NP-hard 的坑谷地貌；貪心法掉進第一個谷底就停——解的品質隨問題規模惡化。
冶金退火的物理：加熱金屬讓原子獲得動能跳脫亞穩態，緩慢降溫結成完美晶格（能量最低）——這是統計力學的成熟理論（Boltzmann 分布、Metropolis 1953 的蒙地卡羅法）。
IBM 的現場：Kirkpatrick 在 IBM 研究電路佈局與晶片測試，苦於局部搜尋的坑谷；Vecchi 有統計力學背景——跨學科合流。
Metropolis 演算法（1953）：以 \(p = e^{-\Delta E / T}\) 接受/拒絕移動的蒙地卡羅採樣——機制已就緒，缺的是「降溫排程」的洞察。

線索與推理 -- 數學式、程式、理論#

核心：Boltzmann 接受機率#

狀態 \(x\) 有能量（成本） \(E(x)\) 。隨機選鄰居 \(x'\) ，若變差（ \(\Delta E = E(x') - E(x) > 0\) ），仍以機率接受：

\[ p = e^{-\Delta E / T} \]

高溫 \(T\) 大 ⇒ \(p \approx 1\) ：亂跑，跳脫局部最優；
低溫 \(T \to 0\) ⇒ \(p \to 0\) ：退化成貪心，精修解。

降溫排程： \(T_{k+1} = \alpha T_k\) （ \(\alpha \approx 0.85\text{-}0.98\) ），每溫度做足夠多次移動（馬可夫鏈長度）。

import random, math

def anneal(cost, x0, T0=1000, alpha=0.95, steps=10000):
    x, E, T = x0, cost(x0), T0
    best, best_E = x, E
    for i in range(steps):
        x2 = neighbor(x)                       # 隨機鄰居（如搬移/交換）
        dE = cost(x2) - E
        if dE < 0 or random.random() < math.exp(-dE / T):
            x, E = x2, E + dE
            if E < best_E: best, best_E = x, E
        if i % 200 == 0: T *= alpha            # 降溫
    return best

為什麼全局收斂：細緻平衡#

移動機率滿足細緻平衡（detailed balance）：

\[ \pi(x)\, p(x \to x') = \pi(x')\, p(x' \to x), \quad \pi(x) \propto e^{-E(x)/T} \]

穩態分布是 Gibbs/Boltzmann 分布——高溫時接近均勻（全域探索），低溫時集中在最低能量態。Geman-Geman（1984）證明：若降溫慢到 \(T_k \propto 1/\log k\) ，退火機率收斂到全局最優——只是這個排程實務上太慢，工程上用幾何降溫換取速度（放棄理論保證，換實戰表現）。

為什麼適合 EDA#

物理退火	電路佈局
原子	單元/巨集
能量	線長 + 重疊 + 擁塞懲罰
溫度	搬移距離與接受率
退火曲線	排程（遠→近、粗→細）

佈局的成本函數天然可分解為局部移動的影響（增量計算 \(O(\deg)\) ），鄰居結構清楚——退火的理想土壤。

結案 -- 後果與影響#

Timberwolf（1985）的實戰勝利：Sechen-Sangiovanni-Vincentelli 用退火佈局，線長比當時最強的 min-cut 商用工具省 15-35%——退火從理論變成產業武器。
組合最佳化的通用引擎：TSP、排程、圖分區、電路測試——退火成為 1980-90 年代所有 NP-hard 問題的「預設武器」，催生 tabu search、門檻接受等後繼。
與解析法的分道：退火品質高但慢（CPU 時小時級），解析佈局（Kraftwerk 1998、ePlace 2015）後來以速度反超——兩條路線在 DREAMPlace（2019）合流。
跨學科的典範：統計力學 → 演算法的移植，是 EDA「物理回歸」主線中最著名的一案（同期還有：Metropolis、Boltzmann 機器）。

關鍵人物與文獻#

Scott Kirkpatrick：IBM Watson，退火用於組合最佳化的提出者。
Metropolis, Teller, Rosenbluth 夫婦（1953）：蒙地卡羅接受機制的原創者。
文獻：
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, "Optimization by Simulated Annealing," Science 220, 671 (1983).
N. Metropolis et al., "Equation of State Calculations by Fast Computing Machines," J. Chem. Phys. 21, 1087 (1953).
V. Černý, "Thermodynamical Approach to the Traveling Salesman Problem," J. Opt. Theory Appl. 45, 41 (1985)（獨立同時提出）。