作者：張晏瑞 / 中原大學智慧運算與大數據碩士學位學程助理教授
上一篇我們釐清了「量子退火機」與「量子啟發式演算法」這兩條面對最佳化難題的技術路徑，並承諾在「演算法流」這條路徑上動手實作。本篇將把概念落地成程式碼：從模擬退火（Simulated Annealing, SA）的物理直覺切入，拆解它的三個關鍵元件——能量函數、鄰域擾動、Metropolis 接受準則——並在不到 50 行的 Python 中，於Google Colab上實際求解一個 10 自旋的易辛模型。最後比較三種冷卻排程的效果，並指出 SA 的局限，作為通往下一篇「平行回火與模擬量子退火」的橋樑。
一、從金屬退火到電腦退火：借用大自然的智慧
回顧上一篇，我們把最佳化問題改寫成了易辛模型（Ising Model）的能量函數：
任務於是變成：讓這群「磁鐵」找到能量 H 最低的排列方式。
模擬退火（Simulated Annealing, SA）這個演算法的命名，直接借用了冶金學的物理過程：把一塊金屬加熱到高溫，讓內部原子劇烈震動、自由跳動；接著緩慢降溫，原子在過程中會「自然地」找到能量最低的排列，形成完美晶格。如果降溫太快，原子來不及調整位置就會留下缺陷——在最佳化的語言裡，這就是「卡在局部最佳解」。
Kirkpatrick 等人在 1983 年提出的關鍵洞見是：這個物理過程可以被翻譯成一段純粹的數學程序，在任何一台傳統電腦上執行。具體對應如下：
✓ 原子的位置 → 解空間中的某個候選解（一組 
）
✓ 熱震動 → 隨機擾動目前解
✓ 溫度 → 一個可控參數 
，主導「接受較差解」的機率
✓ 緩慢降溫 → 預設的冷卻排程（cooling schedule），從高溫逐漸降到接近 0
二、演算法的三大支柱
SA 的精巧之處在於：它只需要三樣元件，就能跳出傳統演算法陷入局部最佳解的困境。
1. 能量函數 E(s)
把任何問題——TSP 路徑長度、投資組合風險、最大切割問題的切邊數——寫成一個可計算的能量函數。給定一組決策 s，我們要能算出它對應的「成本」是多少。
2. 鄰域擾動（Neighborhood Move）
從目前解 s 出發，定義「鄰居解 s′」的產生方式。最常見的做法是隨機翻轉一個自旋（把某個 σᵢ 由 +1 翻成 −1，或反之）。這個小擾動，正模擬了金屬中原子的熱震動。
3. Metropolis 接受準則
這是 SA 的靈魂。當我們從 s 跳到 s′，能量變化 ΔE = E(s′) − E(s) 時，新解被接受的機率為：
P_accept = 1 若 ΔE ≤ 0
P_accept = exp(− ΔE / T) 若 ΔE > 0
這個公式的奧妙在於：當新解較好（能量下降），永遠接受；當新解較差（能量上升），仍然有機會被接受，接受機率取決於兩件事——變差程度 ΔE 越大，越不容易被接受；目前溫度 T 越高，越容易被接受。
換言之，高溫時 SA 在解空間大幅亂跳，像血氣方剛的青年到處探險；低溫時 SA 變得保守、只接受改善解，像謹慎的老人專注局部優化（如圖 1 所示）。這就是「先大膽探索、再小心收斂」的核心策略，也是傳統貪婪演算法做不到的。
Figure 1 Metropolis 接受機率示意圖。當 ΔE > 0 時，接受機率隨溫度 T 下降而急速衰減——高溫近似隨機漫步，低溫近似貪婪下降。
三、Python實作：求解一個 10 自旋 Ising 問題
接下來我們把整套邏輯翻譯成 Python，整段程式碼可直接複製到 Google Colab 上執行。
步驟 1：產生一個隨機 Ising 問題
步驟 2：撰寫 SA 主迴圈
步驟 3：執行與視覺化
執行後，能量曲線呈現鋸齒狀下降（如圖 2 所示）：高頻波動代表「探索」（接受了較差解），整體往下趨勢代表「收斂」。對 10 自旋的小問題，我們甚至可以用暴力法窮舉所有 2¹⁰ = 1024 種組態驗證 SA 的答案。對於更大的問題（例如 N = 100，組態數已達 1.27 × 10³⁰），暴力法完全不可行，但 SA 仍能在數秒內給出高品質解——這就是「啟發式」之所以實用的原因。
Figure 2 10 自旋 Ising 模型上的 SA 能量演化曲線。可見前期能量呈現鋸齒狀大幅波動（高溫探索），後期逐漸平緩收斂至最低能量。
四、冷卻排程的藝術
SA 看似簡單，但「怎麼降溫」決定了它的成敗。三種常見的冷卻排程是：
✓ 線性冷卻：Tₖ = T₀ − k·β
✓ 指數冷卻：Tₖ = T₀ · αᵏ（剛剛實作所用）
✓ 對數冷卻：Tₖ = T₀ / log(1+k)（理論上保證收斂到全域最佳，但慢到不實用）
把三種排程都跑一遍，將能量曲線疊在同一張圖上（如圖 3 所示），可直觀地看出：降太快會卡在局部最佳，降太慢則浪費運算資源。實務上「指數冷卻」是最常用的折衷——前期保留充足的探索空間，後期能快速收斂。
Figure 3 三種冷卻排程的能量演化比較。線性冷卻過早凍結於局部最佳，對數冷卻收斂緩慢，指數冷卻在實務上取得最佳平衡。
調參時的幾條經驗法則：
✓ T₀ 應設得足夠高，使初始接受機率約 80%–95%（高溫近乎隨機漫步）
✓ T_end 應接近 0，但不可為 0（避免分母錯誤）
✓ n_iter 至少應為 N × 100 ~ N × 1000，視問題崎嶇程度而定
五、SA的力量、極限，與下一站
模擬退火是個歷久不衰的演算法。它的優勢顯而易見：邏輯簡單、適用範圍廣、無需特殊硬體。也因此，它常被當作組合最佳化研究的「基準線（baseline）」——任何新方法都得先打贏 SA 才有意義。
但 SA 也有它的痛點：
1. 效率隨問題規模惡化：自旋數從 10 跳到 1000，所需迭代次數大幅成長。
2. 能量地景極崎嶇時仍會卡住：尤其是有許多深而窄的局部最小值時。
3. 冷卻排程需要繁瑣調參：不同問題的最佳 T₀、α 都不一樣。
為了克服這些限制，研究者發展出了更進階的演算法家族：
✓ 平行回火（Parallel Tempering, PT）：同時跑多個不同溫度的 SA 並交換狀態。
✓ 模擬量子退火（Simulated Quantum Annealing, SQA）：用 Path Integral Monte Carlo 模擬量子穿隧。
✓ 數位退火（Digital Annealer）：富士通在 ASIC 上實作的高速並行 SA 變體。
✓ 直接呼叫真實量子退火機（D-Wave QPU）：跳到硬體流路徑。
這些技術都站在 SA 的肩膀上往前推。在下一篇文章中，我們將深入探討平行回火與模擬量子退火這兩個「介於 SA 與真正量子退火之間」的量子啟發式技術，並比較它們在同一個Ising 問題上的表現。
敬請期待：《量子啟發式運算 #3：穿越溫度與量子的橋樑——平行回火與模擬量子退火》