Simulated Annealing

🔥 Vibe Prompt

"Solve TSP with 20 cities using SA. Compare final tour length vs greedy algorithm."

import math, random

cities = [(random.randint(0,100), random.randint(0,100)) for _ in range(20)]

def dist(a, b): return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
def tour_len(tour): return sum(dist(tour[i], tour[i+1]) for i in range(-1, len(tour)-1))

def simulated_annealing(cities, temp_start=1000, temp_end=0.01, cooling=0.995):
    tour = cities[:]
    random.shuffle(tour)
    best = tour[:]
    
    temp = temp_start
    while temp > temp_end:
        i, j = sorted(random.sample(range(len(tour)), 2))
        tour[i:j] = reversed(tour[i:j])
        delta = tour_len(tour) - tour_len(best)
        if delta < 0:
            best = tour[:]
        elif random.random() >= math.exp(-delta / temp):
            tour[i:j] = reversed(tour[i:j])  # Undo
        temp *= cooling
    return best

# Compare
greedy = cities[:]
random.shuffle(greedy)
sa_tour = simulated_annealing(cities)

print(f"Greedy: {tour_len(greedy):.0f}")
print(f"SA:     {tour_len(sa_tour):.0f}")
print(f"Improvement: {(1-tour_len(sa_tour)/tour_len(greedy))*100:.1f}%")

Applications

VLSI circuit layout
Job shop scheduling
Protein folding
Airport gate assignment

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

模擬退火的靈感來源：金屬冶煉

Simulated Annealing 的名字來自冶金學中的退火 (Annealing) 過程：

加熱：將金屬加熱到高溫，原子獲得能量後可以自由移動（進入高能量狀態）
保溫：維持高溫一段時間，讓原子有機會重新排列
緩慢冷卻：以非常緩慢的速度降溫，原子逐漸固定在能量最低的排列方式

如果降溫太快（淬火 Quenching），原子來不及找到最低能量排列，會卡在一個較高能量的狀態——金屬會變脆。

SA 完全對應了這個過程：

高溫：演算法可以自由跳到更差的解（探索）
緩慢降溫：逐漸減少接受差解的機率
低溫：收斂到局部最佳解

為什麼 SA 在 TSP 上這麼有效？

旅行推銷員問題 (TSP) 的搜尋空間是 (n-1)!/2——20 個城市就有約 6×10¹⁶ 種可能路徑。暴力搜尋不可能，貪婪演算法容易找到很差的路徑。

SA 用一種精巧的方式平衡了探索與利用：

| 溫度階段 | 行為 | 比喻 | |:--------:|------|------| | 高溫 (T=1000) | 幾乎接受任何新解（好壞都收） | 到處亂逛，了解地形 | | 中溫 (T=10) | 只接受稍微差一點的解 | 找到大概方向，開始往下走 | | 低溫 (T=0.1) | 幾乎只接受更好的解 | 精細調整，確保是最低點 | | 極低溫 (T<0.01) | 不接受任何差解 | 鎖定最佳解 |

什麼時候該用 SA？

| 場景 | 適合度 | 原因 | |:----:|:------:|------| | TSP 與路徑規劃 | ✅ 非常適合 | SA 對排列問題的鄰居搜尋很有效率 | | 連續函數最佳化 | ✅ 適合 | 搭配高斯擾動即可，但 PSO 通常更快 | | 晶片佈局設計 | ✅ 業界標準 | 晶片設計從 80 年代就開始用 SA | | 影像處理 | ✅ 可使用 | 影像分割、匹配等 | | 神經網路訓練 | ❌ 不適合 | Adam 等梯度方法快太多了 | | 需要保證最佳解 | ❌ 不適合 | SA 是機率性演算法，不保證最佳 |

下一章預告：從一個解到一群解

模擬退火一次只維護一個解，逐步降溫收斂。下一章的 遺傳演算法 (GA) 則採取完全不同的策略——維護一群解，讓它們透過選擇、交叉、突變來演化。

如果說 SA 是一個登山者摸索下山的路，那 GA 就是同時派出 100 個登山者，彼此分享資訊，最後一起找到山谷。不同的策略，適合不同的問題。