模擬退火原理與實作

核心概念

模擬退火 (Simulated Annealing) 靈感來自金屬冶煉：

高溫：原子劇烈運動，可以跳到任何狀態（探索）
降溫：原子逐漸穩定（收斂）
低溫：原子在最低能量狀態附近震盪（利用）

\begin{aligned} P(\text{接受更差的解}) = e^{-\Delta E / T} \end{aligned}

$\Delta E$：新解與舊解的差距
$T$：當前溫度
高溫時容易接受差解 → 跳出局部最佳
低溫時只接受好解 → 收斂到最佳

TSP 實作

import random, math

def simulated_annealing(cities, initial_temp=1000, cooling_rate=0.995, stop_temp=0.01):
    """
    cities: [(x, y), ...] 城市座標
    """
    n = len(cities)
    
    def distance(i, j):
        return math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    
    def total_dist(route):
        return sum(distance(route[i], route[(i+1)%n]) for i in range(n))
    
    # 初始解：隨機排列
    current = list(range(n))
    random.shuffle(current)
    current_dist = total_dist(current)
    
    best = current[:]
    best_dist = current_dist
    
    temp = initial_temp
    while temp > stop_temp:
        # 產生新解：交換兩個城市
        i, j = random.sample(range(n), 2)
        new = current[:]
        new[i], new[j] = new[j], new[i]
        new_dist = total_dist(new)
        
        delta = new_dist - current_dist
        if delta < 0 or random.random() < math.exp(-delta / temp):
            current = new
            current_dist = new_dist
            if current_dist < best_dist:
                best = current[:]
                best_dist = current_dist
        
        temp *= cooling_rate
    
    return best, best_dist

Vibe Prompt

🔥 詠唱：「請幫我用模擬退火解決 TSP，並用 Matplotlib 動畫顯示路線如何逐步最佳化。」

深入理解：模擬退火的關鍵參數

初始溫度 $T_0$

太高：接受太多差解 → 浪費時間隨機亂跳
太低：太早陷入局部最佳
經驗法則：$T_0$ 應讓初始接受率約 80%（接受差解的機率）

冷卻率 $\alpha$

$\alpha = 0.999$：降溫慢，搜尋徹底但慢
$\alpha = 0.99$：降溫快，適合時間有限的場景
$\alpha = 0.8$：降溫極快，近似貪婪演算法

停止條件

溫度低於閾值（最常見）
連續 $N$ 次迭代沒有改善
達到最大迭代次數

SA vs GA 比較

| 特性 | SA | GA | |------|:--:|:--:| | 記憶體使用 | 低（只記一個解） | 高（記一群解） | | 平行化 | 困難 | 容易 | | 連續空間 | 容易 | 需特殊編碼 | | 離散空間（TSP） | 容易 | 需特殊交叉運算 | | 收斂速度 | 快（簡單問題） | 慢（但更全面） |

實戰：參數靈敏度分析

import matplotlib.pyplot as plt

# 測試不同冷卻率的影響
cooling_rates = [0.99, 0.995, 0.999]
results = {}

for cr in cooling_rates:
    best_route, best_dist = simulated_annealing(cities, cooling_rate=cr)
    results[cr] = best_dist
    print(f"α={cr}: 最佳距離={best_dist:.2f}")

plt.bar([str(cr) for cr in cooling_rates], list(results.values()))
plt.xlabel('冷卻率 α')
plt.ylabel('最佳路徑距離')
plt.title('冷卻率對 SA 效能的影響')
plt.show()

關鍵要點

✅ SA 靈感來自冶金退火：高溫探索，低溫收斂
✅ $P = e^{-\Delta E/T}$ 是高溫時接受差解的機率公式
✅ SA 保證收斂到全局最佳（如果降溫夠慢）
✅ 四元素：初始溫度、冷卻率、停止條件、鄰居產生方式
✅ SA 適合離散最佳化（TSP、排程），實作簡單但調整需經驗

模擬退火的關鍵：溫度和冷卻速度

模擬退火（SA）的核心機制是以一定機率接受較差的解——溫度高時接受機率大（探索），溫度低時接受機率小（收斂）。這個「爬山又下山」的能力讓 SA 可以逃脫局部最佳解。

溫度的影響

| 溫度階段 | 行為 | 比喻 | |:--------|:----|:----| | 高溫（T >> 0） | 幾乎接受所有新解 | 金屬液態，分子亂跑 | | 中溫 | 偶爾接受較差解 | 金屬半固態，逐漸定型 | | 低溫（T ≈ 0） | 只接受更好的解 | 金屬固態，不再變化 |

為什麼要學模擬退火？

因為它簡單、通用、效果好。不須要對問題有深入了解就能用——給你一個黑箱函數，SA 可以在不修改演算法的情況下找到夠好的解。這在實務上非常實用：當你不知道該用哪種最佳化方法時，SA 是第一個該試的。

冷卻排程的選擇

| 冷卻方式 | 公式 | 特性 | |:--------|:----|:----| | 指數冷卻 | T = T₀ × α^k | 最常用，α 通常 0.95-0.99 | | 線性冷卻 | T = T₀ - k × ΔT | 降太快，不推薦 | | 自適應冷卻 | 根據歷史表現調整 | 效果好但複雜 |

下一章預告：基因演算法

SA 一次只 maintain 一個解。基因演算法 maintain 一群解（族群），透過交配和突變來演化——適合多模態最佳化問題。