C# 數值計算實戰：模擬退火算法原理與參數選擇指南（上）

前言

組合優化問題廣泛存在於運籌學、VLSI 設計、圖像處理、生物資訊等領域。許多經典問題（TSP、圖著色、設備佈局）屬於 NP 完全問題，缺乏多項式時間精確算法。1983 年 Kirkpatrick 等人將金屬退火物理過程引入優化領域，提出模擬退火——一種能以概率跳出局部最優、趨近全域最優的啟發式算法。本文系統闡述其核心原理、Metropolis 準則、冷卻進度表參數選擇，為後續 C# 實戰篇奠基。

1. 物理隱喻：從退火到優化

金屬退火：高溫 → 緩慢降溫 → 晶體結構達到能量最低穩定態。若急速降溫（淬火）則陷入亞穩態（高能量局部極小值）。

對應優化：

2. 核心算法流程

1. 初始化：設定初始解 S、初始溫度 T₀、冷卻參數、終止條件
2. 外層循環（降溫）：T = α·T (α 接近 1，如 0.95)
3. 內層循環（馬可夫鏈）：在當前 T 下重複 L 次：
   1. 鄰域隨機產生新解 S'
   2. 計算能量差 ΔE = f(S') - f(S)
   3. Metropolis 接受準則：
      • ΔE < 0（更優）→ 無條件接受 S = S'
      • ΔE ≥ 0（劣解）→ 以概率 P = exp(-ΔE / T) 接受
   4. 更新歷史最優解
4. 滿足終止條件（T 足夠低、連續無改善、時間上限）則停止

3. Metropolis 準則深度解析

源自 1953 年統計力學論文。系統從能量 E₁ 變到 E₂ 的概率：

P = exp[-(E₂ - E₁) / kT] （k 為玻爾茲曼常數，優化中常併入 T 縮放）

• 高溫階段：T 大 → P ≈ 1 → 大幅接受劣解 → 全域探索
• 低溫階段：T 小 → P → 0 → 僅接受微小劣解 → 局部精細化
• T → 0：退化為貪婪算法，只接受優解

關鍵洞見：「以一定概率接受劣解」 是跳出局部最優的唯一機制。

4. 三大支柱：冷卻進度表、鄰域結構、接受準則

4.1 冷卻進度表參數選擇

4.2 鄰域結構與新解產生器

• 定義解空間的「鄰近」關係：交換、插入、反轉（TSP）、位翻轉（0/1 背包）等
• 步長控制：S' = S + step·random()，步長可隨 T 遞減
• 需保證遍歷性：從任意解出發，經有限步可達全空間

4.3 接受準則與隨機數產生器

標準 Metropolis：if (ΔE < 0 || random() < exp(-ΔE/T)) accept;

變體：Safer acceptance（避免溢位）、Lam 閾值法（預計算閾值加速）。隨機數品質直接影響算法統計特性，建議用 System.Random 或更高品質生成器。

5. 參數選擇實戰經驗則

1. T₀ 過小 → 陷入局部最優；T₀ 過大 → 浪費計算資源。實務上常用「預熱運行」自動校準。
2. α 接近 1（如 0.95~0.99）收斂較好但耗時長；問題規模大需更大 α。
3. L 太小 → 未達準平衡，解質量差；L 太大 → 邊際收益遞減。可採用自適應 L：接受數/嘗試數比率在目標區間（如 0.4~0.6）。
4. 終止條件：工程上常用「連續 N 次降溫最優解改善 < ε」或「總迭代次數上限」。

6. 小結與下篇預告

本文建立了模擬退火的理論框架：物理隱喻 → Metropolis 核心 → 三大支柱參數化。下篇將給出完整 C# 實現，求解 f(x,y) = 5sin(xy) + x² + y² 的全域最小值，展示參數調試、收斂曲線繪製、多次運行統計等工程細節。理解參數選擇的「為何」，比複製代碼的「如何」更關鍵——模擬退火是一門參數調校的藝術。

參考文獻

1. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
2. Press, W. H. et al. Numerical Recipes in C (Chapter 10.9).
3. 計算方法叢書《非數值並行算法》第一冊：模擬退火算法。