區域搜尋與元啟發式

當證明用完了，你還是需要一個答案

走到這座階梯的這個位置，你已經蒐集了一套強大的工具，也得到了一張清醒標出它邊界的地圖。有些問題是 NP 完全的，所以沒有已知的多項式演算法。近似演算法替其中一些問題給了你一個最壞情況的倍率——度量 TSP 的 2-近似是個模範生——但對許多問題而言，連一個好的近似比都難求，或者它承諾的常數太鬆而派不上用場。然而一個實作工程師不能回一句「這是 NP 困難的，所以我放棄。」一條送貨路線今天早上還是得畫出來。區域搜尋正是對這道缺口誠實而務實的回答。

這個念頭簡單到近乎孩子氣，而那正是它的魅力。別想著一口氣搜尋整個大到天文數字的組態空間。取而代之，手裡握住一個候選解。定義一個概念：哪些解是它的鄰居——你被允許做的、微小的局部改動。環顧鄰居，若其中有任何一個依你的成本量度更好，就走過去。重複。你正走在一片由解構成的地景上，永遠往下坡走（對最小化問題而言），一次一小步，直到沒有鄰居比你站的地方更好為止。

兩個設計決定界定了一個區域搜尋，其餘一切都從它們衍生。第一是鄰域：給定一個解，哪些別的解算作離它一步之遙？對旅行推銷員問題，經典的答案是 2-opt——一個鄰居就是你把當前路線裁掉兩條邊、再把那兩段路徑反向接回去所得到的任何路線。對布林可滿足性問題，一個鄰居就是你翻轉一個變數所得到的賦值。第二是目標函數：一個你試圖壓低的數字（路線長度、不被滿足的子句數）。把這兩者選好，你就有了一個演算法；選壞了，你就有了一個非常快速地找到平庸答案的方法。

地景，以及它為何困住你

把每一個可能的解想成一片廣袤地形上的一個點，它的目標值畫成高度。區域搜尋是一個只能看見每個方向一步、且永遠往下坡走的登山者。它真正能抵達的終點有個精確的名字：一個區域最佳解——一個沒有任何鄰居比它更好的解。麻煩出在區域這個詞。一個區域最佳解是某個山谷的谷底，但這片地形可能藏著許多深淺迥異的山谷，而我們這位近視的登山者沒有辦法知道自己找到的是最深的那個（真正的全域最佳解）、還是不過是個淺淺的小凹。

這正是你初次學到貪婪式推理會誤導人時遇上的那道裂縫。貪婪會失敗，恰恰是因為「看起來區域最佳」並不是全域最佳的證明，而區域與全域最佳解之間的落差，正是那次失敗披上幾何外衣的模樣。樸素的區域搜尋——常被稱為爬山法（往下走時，則是梯度下降的離散表親）——對此毫無防備。一旦每個鄰居都更糟，它就停住。它對「停下來」這件事很誠實，卻無法保證停下的地方接近最佳。

爬回出口：元啟發式工具箱

如果純粹的下坡步行會卡在第一個山谷裡，那麼顯而易見的補救就是偶爾允許一步上坡，好讓登山者爬出淺谷、去尋找更深的谷。一個元啟發式正是這件事：一套包裹在區域搜尋外面的、與問題無關的通用策略，由它決定何時以及如何逃離區域最佳解。元啟發式與區域搜尋這把大傘罩住了一整族這樣的逃脫策略，而它們有著一個可辨認的共同形狀——一開始大膽探索，然後逐漸安定下來。

這一族裡最乾淨的成員是模擬退火，借自一塊緩慢冷卻的金屬如何安定成低能量結晶的過程。每一步你提議一個隨機鄰居。若它更好，你總是接受。若它更糟、差了 d 那麼多，你仍以機率 exp(-d / T) 接受它，其中 T 是一個你隨時間調低的「溫度」。當 T 很高時，幾乎任何上坡的移動都被接受，於是搜尋自由地遊蕩、從淺谷裡彈出來。隨著 T 冷卻趨近零，上坡的移動變得微乎其微，方法便硬化成普通的爬山法，打磨它一路晃進的那座深谷。

s = random initial solution
for T = T_hot down to ~0 (cooling schedule):
    s' = a random neighbor of s
    d  = cost(s') - cost(s)
    if d < 0:            s = s'           # better: always move
    else with prob exp(-d / T): s = s'    # worse: sometimes move
return best s ever seen

模擬退火：永遠接受改善，並以一個隨溫度 T 冷卻而縮小的機率接受惡化。

其他成員則替換食譜裡的某一部分。禁忌搜尋 保留一份最近造訪過的解的短期記憶，並禁止回到它們，這就阻止了登山者立刻走回它剛逃出的那個山谷。基因演算法 保留一整個解的族群，靠重組好親代的片段來「繁衍」新解、偶爾突變——這是與交叉操作平行進行的區域搜尋。它們在機械結構上不同，卻共享同一個靈魂：一組區域移動、一個要壓低的目標函數，以及一份受控的意願——暫時走錯方向，為的是最終走得更對。

一幅實作圖像：可滿足性上的 WalkSAT

讓我們在所有 NP 完全問題中最基本的那個——布林可滿足性——上把這件事弄具體。我們有一個合取範式的公式（一個由許多子句組成的大 AND，每個子句是幾個文字的 OR），我們想要一個給變數的真假賦值，使每個子句都為真。區域搜尋的目標函數是不被滿足的子句數；我們想把它逼到零。一個賦值的鄰居，就是只翻轉恰好一個變數後的同一賦值。這片地形有 2^n 個點（每個賦值一個），所以列舉是無望的，但每個點只有 n 個鄰居。

從所有 n 個變數隨機賦予真或假的一個賦值出發。數出不被滿足的子句。
若每個子句都被滿足，你就完成了——輸出這個賦值。這是全域最佳解（目標值為 0）；沒有更低的地方可去。
否則隨機挑一個不被滿足的子句。其中每個變數，一旦翻轉，都會讓那個子句變真——所以在這裡翻一下就取得了局部進展。
以某個機率，翻轉該子句中會破壞最少其他子句的那個變數（貪婪的、下坡的移動）；否則從該子句隨機翻轉一個變數（帶雜訊的、可能上坡的移動，讓你能逃出陷阱）。這份貪婪與雜訊的混合，正是 WalkSAT 的核心。
回到第 2 步，直到某個翻轉次數的預算用盡。若預算用盡，就從一個全新的隨機賦值重新開始。

注意那份雜訊替你買到了什麼。純貪婪的翻轉——永遠減少不被滿足的數目——會卡死在第一個區域最佳解，那是一個任何單獨翻轉都讓情況變糟、卻仍有些子句不被滿足的賦值。隨機翻轉這個選項，是模擬退火「接受一個更糟的移動」那招的化身：它偶爾抬高目標函數，好讓搜尋離開陷阱。實務上這套組合解出了任何精確方法都碰不了的龐大可滿足性實例，這正是為什麼建立在這些念頭上的求解器，如今悄悄地驅動著晶片驗證與排程工具。

誠實的細則

現在來談提醒，因為這正是區域搜尋最常被過度吹捧的地方。最大的一條：一個元啟發式幾乎從不附帶證明。模擬退火有個著名的定理：在一個無限緩慢的冷卻排程下，它收斂到全域最佳解——但「無限緩慢」意味著比暴力法還慢，所以那個定理是一份寬慰，而非可用的保證。用任何實際的排程，你對解的品質沒有界限、對執行時間也沒有界限。這跟你信得過、在每個輸入上都落在 2 倍之內、有保證的 2-近似，恰好處於光譜的兩端。

那為什麼要信任一個沒有保證的方法？因為最壞情況與典型情況可能天差地遠，而區域搜尋就靠著這道落差過活。這正是下一篇用平滑分析講精確的同一個教訓：一個演算法在對手構造的輸入上可能理論上糟透了，在真正會出現的輸入上卻表現出色。線性規劃的單純形法是著名的例子——最壞情況下指數、實務上快如閃電——而區域搜尋的啟發式分享著那副性情。它們的憑據是經驗性的：它們在真實實例上被調校與測試，靠結果而非定理掙得地位。

退一步，看看這在階梯上的位置。先前的階段給了你能證明的演算法：一個正確的不變量、一個漸進緊界、一個有保證的近似比。這一階的前沿方法，拿這份確定性的一部分去換觸及範圍。區域搜尋是其中最務實的——它幾乎完全放棄了最壞情況的保證，只問一句「它在我真正面對的實例上管用嗎？」這不是從嚴謹的撤退；它是對另一個問題的嚴謹。知道何時可證明的方法搆得著、何時該降下來改用一個精心打造的啟發式，這本身就是一種精通的標誌。