模擬退火原理與實作

核心概念

模擬退火 (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 動畫顯示路線如何逐步最佳化。」