Kenneth Cheng數學建模

數學趣題

攀越看不見的山：適應度地景上的啟發式方法

由爬山法、模擬退火、隨機重啟與鄰域設計，理解啟發式演算法如何在崎嶇適應度地景中移動。

2025年12月7日 · 約 2 分鐘閱讀

上一篇文章接受了「足夠好」的解；這篇續文深入探討啟發式方法如何在崎嶇的適應度地景上移動。地景中的每個座標代表一個解，高度則是目標函數值。

f(x,y) = sin x cos y + 0.1xy 的等高線示意 函數 $f(x,y)=\sin x\cos y+0.1xy$ 的兩個盆地與一個鞍點。

一條方程中的地景

假設目標是一座帶波動的山：

f(x)=−(x−2)2+35sin⁡(5x).f(x)=-(x-2)^2+\tfrac35\sin(5x).

它在 x≈2x\approx2 附近有一個高峰，其他位置有較小凸起。如果由 x0=−1x_0=-1 開始，每步只貪婪地向上，很可能停在小峰而不是全局最高點。

基本爬山法

局部搜尋反覆計算

xk+1=xk+η∇f(xk),x_{k+1}=x_k+\eta\nabla f(x_k),

其中 η\eta 是步長。一維時 ∇f=f′(x)\nabla f=f'(x)；對以上函數，

f′(x)=−2(x−2)+3cos⁡(5x).f'(x)=-2(x-2)+3\cos(5x).

取 η=0.05\eta=0.05，由 x0=−1x_0=-1 運行 80 步，很可能落在 x≈−0.6x\approx-0.6 的局部峰，而非 x≈2x\approx2。貪婪上升很快，但目光短淺。

import math

def f(x):
    return -(x-2)**2 + 0.6 * math.sin(5*x)

def fp(x):
    return -2*(x-2) + 3*math.cos(5*x)

x = -1.0
eta = 0.05
for _ in range(80):
    x += eta * fp(x)
print(round(x, 3), round(f(x), 3))

模擬退火：加入溫度以逃離陷阱

退火會以某個機率接受向下移動：

P(accept)=exp⁡ ⁣(−ΔET),ΔE=f(x)−f(x′),P(\text{accept})=\exp\!\left(-\frac{\Delta E}{T}\right), \quad \Delta E=f(x)-f(x'),

其中 TT 是「溫度」。早期溫度高，演算法偏向探索；其後冷卻，逐步轉向利用。常見幾何冷卻為

Tk=T0αk,α∈(0,1).T_k=T_0\alpha^k,\quad \alpha\in(0,1).

例如，候選移動損失 ΔE=0.8\Delta E=0.8，當 T=1T=1，接受機率為 exp⁡(−0.8)≈0.45\exp(-0.8)\approx0.45；當 T=0.1T=0.1，則降至 exp⁡(−8)≈0.0003\exp(-8)\approx0.0003。高溫讓路徑早期跨過山谷，冷卻則令後期解穩定下來。

隨機重啟：便宜的保險

若一次爬山找到全局峰的機率為 pp，nn 次獨立重啟的成功率是 1−(1−p)n1-(1-p)^n。即使 p=0.2p=0.2，三次重啟亦可把成功率提高至約 0.490.49。當梯度不存在或表面崎嶇，隨機重啟配合短局部搜尋是一種穩健啟發式。

鄰域設計很重要

組合問題中的「鄰居」定義一步可以改變甚麼。旅行商問題可交換兩個城市、反轉一段路線或作 2-opt／3-opt 重接；排程問題可交換時段或把一項工作移到新位置。較豐富的鄰域減少受困風險，亦提高每步成本：大幅移動探索較好，便宜移動則可更快迭代。

二維小山脈

考慮

f(x,y)=sin⁡xcos⁡y+0.1xy,f(x,y)=\sin x\cos y+0.1xy,

其梯度為

∇f=[cos⁡xcos⁡y+0.1y−sin⁡xsin⁡y+0.1x].\nabla f= \begin{bmatrix} \cos x\cos y+0.1y\\ -\sin x\sin y+0.1x \end{bmatrix}.

函數包含山脊與鞍點。由 (2,2)(2,2) 作純上升可能困在山脊；加入退火或偶發 Gaussian 步長雜訊，路徑便可能越過鞍點進入更高盆地。

何時使用哪種方法

當 ff 平滑且評估便宜，可用梯度或座標上升。加入動量 vk+1=βvk+η∇f(xk)v_{k+1}=\beta v_k+\eta\nabla f(x_k) 可加快沿山脊移動。地景崎嶇時採用退火或隨機爬山；組合陷阱主導時使用重啟與較大鄰域。同時保留目前最佳解 x∗x^*，可避免探索期間遺失好解。

結語

啟發式方法活在探索與利用之間。數學提供接受機率、冷卻速率、重啟次數與鄰域大小等槓桿。在崎嶇地景上，勝出的往往不是紙面上最聰明的演算法，而是最懂得把有限計算預算花在重要位置的方法。