把「物競天擇」寫成程式：不懂問題結構也能逼近好解的通用武器，本篇以 TSP 與背包實戰
你不知道最好的路線長什麼樣，但你會比較兩條路線誰好。那就這樣辦：養一群隨機路線，讓好的容易「生小孩」（混合兩條路線的片段），偶爾「突變」（隨機小改動），差的自然淘汰。幾百代之後，族群裡就長出很好的路線——這就是遺傳演算法，達爾文當工程師。
GA 是元啟發式（metaheuristic）：不保證最優、不保證近似比，但幾乎不挑問題——只要能編碼解、能打分數，就能跑。它是 NP-Hard 工具箱的最後一格：精確解太慢、近似演算法不存在或太差、問題結構混沌時的萬用鑰匙。
五個組件
編碼：解如何表示成「染色體」。TSP 用排列、背包用位元字串——編碼決定一切後續設計。
選擇：錦標賽選擇（隨機抓 \(k\) 個、取最好）簡單、好調、對適應度縮放不敏感，是實務首選。
交配：把兩個好解的「基因片段」重組。必須尊重編碼的合法性（見下節）。
突變：維持多樣性、逃離局部最優的保險絲。
菁英保留：每代把最好的幾個直接抄進下一代——保證最佳解單調不退步。
關鍵設計：TSP 的排列編碼
為什麼不能用普通交配
染色體是城市排列。單點交配把 \([0,3,1,2,4]\) 和 \([0,2,4,1,3]\) 前後段拼起來會得到 \([0,3,1,1,3]\)——城市重複又缺漏，根本不是合法路線。排列編碼需要專用算子。
順序交配 OX（Order Crossover）
從父 A 抄一段連續區間到子代同位置。
剩下的洞，按父 B 的出現順序把缺的城市依序填入。
\[\underbrace{A = [0,\framebox{3,1},2,4]}_{\text{抄中段}} + B = [0,2,4,1,3] \;\Rightarrow\; \text{子} = [0,\framebox{3,1},2,4] \text{（B 順序補 } 2,4\text{）}\]
子代保有 A 的一個連續片段與 B 的相對順序——兩個父母的「好基因」都有機會傳下去，且永遠是合法排列。
突變：交換與反轉
交換突變（隨機兩城互換）擾動小；反轉突變（隨機區間反轉）正是 2-opt 的動作——把局部搜尋的智慧藏進突變裡，是 TSP GA 的標準配方。
第二種編碼：背包的位元字串
背包解 = \(n\) 位 0/1（拿或不拿）。交配用單點切割、突變用位元翻轉——教科書原味 GA。多了一個問題：超重的非法個體怎麼辦？本篇採修復策略：反覆丟出「價值密度最低」的物品直到合法。（另兩種流派：罰分——適應度扣超重量的懲罰；或設計不會產生非法解的編碼。）
同一套引擎、換編碼與適應度就能解完全不同的問題——這就是 GA「泛用」的意思，也是它被工程師偏愛的原因。
調參的三個旋鈕
| 參數 | 太小 | 太大 |
|---|---|---|
| 族群大小 | 多樣性不足、早熟收斂 | 每代太貴、收斂慢 |
| 突變率 | 卡死在局部最優 | 退化成隨機亂搜 |
| 菁英數 | 好解可能絕種 | 過早壟斷、多樣性崩潰 |
本篇程式 Example 2、3 直接掃這些參數給你看：突變率 0 的族群明顯早熟（卡在 +0.8%），0.05–0.25 都健康；這個規模下族群 20 就夠——參數的「感覺」必須靠實驗建立，不要背數字。
完整 C++ 程式
包含：TSP GA（排列編碼、錦標賽、OX、交換+反轉突變、菁英）、Held–Karp 對照最優、族群/突變率參數掃描、背包 GA（位元編碼 + 修復）對照 DP。編譯：
g++ -std=c++17 -O2 -Wall -Wextra -o genetic_algorithm genetic_algorithm.cpp執行結果與解讀
=== Example 1: GA on 15-city TSP (watch it evolve) ===
gen 100 best = 316.32
...
GA best = 316.32
true OPT = 316.32 (Held-Karp)
gap = +0.00%
=== Example 2: does population size matter? ===
population 20 -> best 316.32 (gap +0.00%)
population 100 -> best 316.32 (gap +0.00%)
population 400 -> best 316.32 (gap +0.00%)
=== Example 3: mutation rate sweep ===
mutation 0.00 -> best 318.84 (gap +0.80%)
mutation 0.05 -> best 316.32 (gap +0.00%)
mutation 0.25 -> best 316.32 (gap +0.00%)
mutation 0.80 -> best 316.32 (gap +0.00%)
=== Example 4: GA on 0/1 knapsack (bit-string encoding) ===
n=30, W=500 | GA = 1345, DP optimal = 1345 (gap 0.00%)最有教學價值的是 Example 3 的突變率 0：只靠交配重組現有基因、沒有新變異注入，族群很快同質化，卡在離最優 0.8% 的地方再也出不來——這就是「早熟收斂」的長相。加上區區 5% 突變率就治好。另外注意：15 城的 TSP 對 GA 是小菜（Held–Karp 都能直接驗證），GA 的主場是 \(n\) 上百、精確解徹底絕望之後。
使用 GA 的三大紀律：(1) 先試簡單方法——貪心、局部搜尋常常又快又好（上一篇的 NN+2opt 在小實例直接命中最優，GA 反而繞遠路）；(2) 隨機種子要記錄，結果才可重現；(3) 多跑幾次取最好，單次 GA 的結果是隨機變數，報告平均與變異數才誠實。
實務應用
排程與時刻表：學校課表、護理師排班、機組排班——約束又多又雜、無乾淨結構，正是 GA 舒適圈。
工程設計最佳化：NASA ST5 任務的天線形狀由演化演算法設計（著名的「演化天線」），性能勝過人工設計。
神經網路：神經演化（NEAT、超參數搜尋）；強化學習的進化策略（ES）路線。
晶片布局：placement 與 routing 的元啟發式家族成員。
近親：模擬退火（單點 + 溫度）、禁忌搜尋（記憶體防繞圈）、蟻群（費洛蒙）——不同隱喻、同一精神：有偏好的隨機探索 + 保留好解。
練習題
手算一次 OX：\(A=[0,4,1,3,2]\)、\(B=[0,1,2,3,4]\)、抄 A 的位置 2–3，寫出子代。
把錦標賽 \(k\) 從 4 改成 2 與 12，觀察收斂速度與早熟的取捨（\(k\) 越大選擇壓力越強）。
實作輪盤選擇（依適應度比例抽樣），與錦標賽比較——注意 TSP 是最小化問題，適應度要先轉換。
給背包 GA 換成罰分策略（超重扣分），與修復策略比較最終品質與收斂代數。
挑戰：Memetic GA——每個子代出生後先跑幾步 2-opt 再放回族群（「拉馬克演化」），對 \(n=50\) 的 TSP 比較純 GA 的差距。
小結：NP 難題工具箱的全景
| 工具 | 保證 | 什麼時候拿出來 |
|---|---|---|
| 精確（DP/分支限界） | 最優 | \(n\) 小或參數 \(k\) 小（FPT） |
| 近似演算法 | 可證明的倍率 | 有已知近似（VC、SetCover、排程…） |
| 局部搜尋 | 局部最優 | 快、簡單、常常夠用 |
| GA 等元啟發式 | 無 | 結構混沌、約束雜、其他方法失靈 |
本系列 13 篇至此收官：從 3-SAT 的難度源頭，經過回溯、DP、位元壓縮、FPT、近似、貪心，到今天的演化——這就是人類面對 NP-Hard 的完整武器庫。沒有魔法，只有取捨：時間換品質、保證換速度、通用換效率。
延伸閱讀：Holland Adaptation in Natural and Artificial Systems（1975 開山）；Goldberg Genetic Algorithms in Search, Optimization and Machine Learning；Eiben & Smith Introduction to Evolutionary Computing；No Free Lunch 定理（Wolpert & Macready 1997——為什麼「萬用」必有代價）。