區域搜尋與元啟發式（local search and metaheuristics）

想像你在夜裡被丟到一片霧濛濛的山脈某處，被告知要抵達最高峰，但你只能感覺到腳邊的地面。一個自然的計畫：永遠往上坡走，朝著比較高的鄰近位置，當每個鄰居都比較低時就停。那就是區域搜尋（爬山法）：從某個候選解開始，反覆移動到稍微更好的鄰居，並在一個區域最佳處停下。當找到真正的最佳解不可行時，這是攻打困難最佳化問題的通用辦法——你退而求「夠好、找得快」。

純爬山法的致命缺陷在霧山的畫面裡顯而易見：你會爬到「碰巧起步的那座小山」的頂——一個「區域」最佳——然後卡住，即使一座遠更高的峰（「全域」最佳）就在你拒絕走下的山谷對面。元啟發式（metaheuristics）是疊在區域搜尋之上、用來逃離這類陷阱的巧妙策略。模擬退火借鏡冷卻金屬：它有時會接受「更差」的移動，其機率一開始很高（早期允許狂野的探索性下坡步），並隨著一個「溫度」參數冷卻而隨時間縮小，使它起初能爬出山谷、之後安定下來。基因演算法保留一整群候選解，藉由混合優良親代的片段（交配）並隨機微調它們（突變）來「繁殖」新解，讓適者生存把族群導向更好的區域。其他例子包括禁忌搜尋（禁止最近造訪過的狀態以避免繞圈）與隨機重啟（試許多起點）。

這些方法之所以重要，是因為無數真實的最佳化問題——排程、電路佈局、車輛路由、神經網路架構、蛋白質摺疊——都是 NP 困難的，搜尋空間大到精確方法無能為力，卻又需要一個現在就能用的答案。元啟發式很有彈性，幾乎能套用到任何「你能定義鄰居與品質分數」的問題上，且常能快速找到極佳的解。誠實且極為重要的提醒：這些方法「沒有」保證——它們可能回傳一個糟糕的區域最佳，而你通常無法判斷離最佳有多遠；它們的表現嚴重取決於調參（溫度排程、突變率、鄰域設計）與運氣（隨機種子）；而且儘管有生物或物理的名字，它們是啟發式，不是證明——對於存在可證明保證的問題，近似演算法通常是更好、更誠實的選擇。