經典算法研究：遺傳算法（GA）原理、流程與核心算子深度解析

遺傳算法是模擬達爾文自然選擇與孟德爾遺傳機制的啟發式優化算法，擅長處理高維、非線性、多峰值、不可導的複雜優化問題。本文系統梳理GA框架、編碼策略、適應度函數、選擇/交叉/變異三大算子、參數設置與收斂判斷。

一、 算法框架與偽代碼

GA()
t ← 0
P(t) ← 初始種群 (M個體)
while t ≤ T:
    評價 P(t) 中每個體適應度
    P'(t) ← 選擇操作(P(t))
    P''(t) ← 交叉操作(P'(t))
    P(t+1) ← 變異操作(P''(t))
    t ← t + 1
return 最優個體

二、 核心組成四要素

1. 編碼

• 二進制編碼：標準GA（SGA）採用，位串長度L，精度(b-a)/2ᴸ。
• 實數編碼：直接用浮點數，適合連續優化，精度無損，交叉變異更自然。
• 順序/樹/圖編碼：針對組合優化（TSP）、程序進化（GP）定制。

2. 適應度函數

將目標函數f(x)映射為非負適應度F(x)，驅動自然選擇。
常見轉換：F(x) = f(x) - f_min + ε（最小化問題）、F(x) = 1/(1+f(x))、線性歸一化/指數歸一化。
設計原則：保持選擇壓力適中，避免早熟或停滯。

3. 遺傳算子

選擇算子：輪盤賭法

個體選中概率pᵢ = Fᵢ / ΣFⱼ。
實現：計算累積概率分布，生成[0,1)隨機數，二分查找落入區間。
優點：期望保留比例選擇；缺點：早期超優個體霸佔種群（早熟），後期選擇壓力不足。
改進：鍦標選擇、排序選擇、錦標賽選擇（工程首選）。

交叉算子：單點/多點/均勻交叉

• 單點交叉：隨機選一點，交換尾部。P(保留模式) = 1 - δ/L（δ為模式定義長度）。
• 多點交叉：k個點，交替交換段，擾動性更強。
• 均勻交叉：每位獨立以0.5概率交換，最大擾動，適合實數編碼（算術交叉：x' = αx + (1-α)y）。

交叉概率p_c通常0.6~0.9。

變異算子：位翻轉/高斯擾動

• 二進制：每位以p_m（0.001~0.1）翻轉。
• 實數：x' = x + N(0,σ)或多項式變異。

作用：維持種群多樣性，跳出局部最優，補充交叉丟失的等位基因。

三、 運行參數設置經驗值

四、 收斂判斷與停止條件

• 達到最大進化代數T。
• 最優適應度連續k代改善<ε。
• 種群多樣性（平均漢明距離/方差）低於閾值。
• 找到已知理論最優解。

五、 GA 的優缺點與適用邊界

優點：全域搜索、並行性好、無需梯度、編碼靈活。
缺點：參數敏感、收斂慢、無嚴格最優保證、易早熟。
適用：參數優化、調度規劃、神經網絡結構搜索、特徵選擇、黑箱優化。
不適用：凸優化/可導問題（梯度下降更快）、強實時要求場景。

六、 智能優化算法家族對比

遺傳算法是啟發式優化的「瑞士軍刀」，理解其編碼-適應度-算子三位一體的設計邏輯，即可針對具體問題靈活定制高效求解器。