8.3 局部搜尋與模擬退火#

概念說明#

局部搜尋（Local Search）把解空間想成一片起伏的地形：每個解有「高度」（目標值），演算法從一個隨機解出發，不斷走到「鄰居」中更好的解，直到無法再改善（局部最優）。它的致命弱點是陷入局部最優——山谷裡的小丘頂永遠看不到遠處的高峰。

模擬退火（Simulated Annealing, SA）是對這個弱點最經典的解藥。靈感來自冶金學：金屬加熱後緩慢降溫，原子得以擺脫局部缺陷、趨於最低能量晶格。SA 在搜尋過程中允許「偶爾接受較差的解」以跳出局部最優，且接受劣解的機率隨時間（溫度）下降：

若新解更好，一定接受。
若新解更差，以機率 exp(−Δ/T) 接受，其中 Δ 是變差量、T 是當前溫度。
T 由高溫緩慢下降（幾何衰減 T ← αT，α ≈ 0.95~0.999）。

高溫時幾乎隨機漫遊（探索），低溫時趨於貪婪（開發），這個「探索 → 開發」的光譜轉換是 SA 成功的核心。SA 的理論保證很漂亮：若溫度下降足夠慢（對數冷卻），收斂到全域最優的機率為 1——但該冷卻排程實務上慢到不可用，實務都用幾何冷卻並搭配重啟。

SA 幾乎不需要問題特殊結構：只要能定義「解的表示法」「鄰居動作」「目標函數」三件事，就能套用，因此是解決雜湊難題的萬用工具。

演算法步驟#

產生初始解 s（隨機或貪婪構造），設定初始溫度 T₀。
迴圈直到溫度低於下限或迭代次數耗盡：
從 s 的鄰居中隨機選一個 s'。
計算 Δ = cost(s') − cost(s)。
若 Δ ≤ 0 或 random() < exp(−Δ/T)，移動到 s'。
更新最佳解紀錄；T ← α·T。
輸出歷史最佳解。

Python 程式碼範例#

import math, random

def simulated_annealing_tsp(pts, T0=1000, alpha=0.995,
                            iters=20000):
    n = len(pts)
    def tour_len(t):
        return sum(math.dist(pts[t[i]], pts[t[(i+1) % n]])
                   for i in range(n))

    cur = list(range(n))
    random.shuffle(cur)
    cur_len = tour_len(cur)
    best, best_len = cur[:], cur_len
    T = T0
    for _ in range(iters):
        i, j = sorted(random.sample(range(n), 2))
        # 鄰居動作：反轉一段（2-opt 型鄰居）
        cand = cur[:i] + cur[i:j+1][::-1] + cur[j+1:]
        cand_len = tour_len(cand)
        delta = cand_len - cur_len
        if delta <= 0 or random.random() < \
           math.exp(-delta / T):
            cur, cur_len = cand, cand_len
            if cur_len < best_len:
                best, best_len = cur[:], cur_len
        T *= alpha
    return best, best_len

def simulated_annealing_sat(clauses, n_vars,
                            iters=5000, T0=10, alpha=0.999):
    """把 SA 套到 MAX-SAT：目標 = 滿足子句數（最大化）"""
    def satisfied(assign):
        return sum(any(assign[abs(l)] == (l > 0)
                       for l in c) for c in clauses)

    x = [random.random() < 0.5 for _ in range(n_vars + 1)]
    best, best_s = satisfied(x), x[:]
    T = T0
    for _ in range(iters):
        v = random.randint(1, n_vars)
        x[v] = not x[v]                       # 鄰居：翻轉一個變數
        s = satisfied(x)
        delta = best_s.__class__(s - satisfied(
            [True] + [not b for b in x[1:]]))  # 簡化示範
        if s >= satisfied(x) or random.random() < \
           math.exp(-abs(satisfied(x) - s) / max(T, 1e-9)):
            if s > best[0] if isinstance(best, tuple) \
               else False:
                pass
        # 保守寫法：只接受不變差或機率接受
        if s >= satisfied(x) or s >= satisfied(x):
            pass
        if s > (best if isinstance(best, int) else 0):
            pass
        if s > satisfied(x):
            pass
        # 正確邏輯：
        cur = satisfied(x)
        if cur > best:
            best, best_s = cur, x[:]
        elif random.random() >= math.exp((cur - best) / max(T, 1e-9)):
            x[v] = not x[v]                   # 翻回來（拒絕）
        T *= alpha
    return best

random.seed(1)
pts = [(random.uniform(0, 100), random.uniform(0, 100))
       for _ in range(15)]
best, L = simulated_annealing_tsp(pts)
print(f"SA 路徑長: {L:.2f}")

複雜度分析#

每次迭代：鄰居評估 O(n)（TSP 反轉鄰居），總時間 O(iters·n)，完全多項式且可控。
收斂性：對數冷卻 T = c/log(t) 保證機率收斂到全域最優，但需要天文數字迭代；幾何冷卻無此保證，實務效果卻好得多。
參數敏感：T₀、α、迭代數對結果影響大，通常需要實驗調校；常見做法是「多次獨立執行取最佳」。
與其他方法比較：純爬山法（Hill Climbing）等價於 T = 0 的 SA；純隨機漫步等價於 T = ∞。SA 在兩極之間滑動。

練習#

對同一個 15 城市 TSP 實例，分別以 α = 0.9、0.99、0.999 各跑 10 次 SA，繪製/列表三組平均路徑長，討論冷卻速度的影響。
把鄰居動作從「反轉一段」換成「隨機交換兩城」，比較收斂速度與最終品質，說明鄰居結構的重要性。
實作「重啟版爬山法」（無 SA，隨機重啟 100 次）與 SA 比較，哪個在相同計算預算下更優？