遺傳演算法

核心步驟

選擇 (Selection)：適應度越高的個體越容易被選中
交叉 (Crossover)：兩個父代交換基因產生子代
突變 (Mutation)：隨機改變基因，維持多樣性

Vibe Prompt

「幫我用遺傳演算法解決 TSP（20 個城市）。種群 100，迭代 200 代，用 Matplotlib 動畫顯示最佳路線的演化過程。」

import random, math

def genetic_algorithm(cities, pop_size=100, generations=200, mutation_rate=0.01):
    n = len(cities)
    def dist(i, j):
        return math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    def fitness(route):
        return -sum(dist(route[i], route[(i+1)%n]) for i in range(n))
    
    # 初始化種群
    pop = [random.sample(range(n), n) for _ in range(pop_size)]
    
    for gen in range(generations):
        # 計算適應度
        scores = [(fitness(ind), ind) for ind in pop]
        scores.sort(reverse=True)
        pop = [ind for _, ind in scores]
        
        # 菁英保留
        next_pop = pop[:2]
        
        while len(next_pop) < pop_size:
            p1, p2 = random.choices(pop[:pop_size//2], k=2)
            # OX 交叉
            a, b = sorted(random.sample(range(n), 2))
            child = [-1] * n
            child[a:b] = p1[a:b]
            remaining = [x for x in p2 if x not in child]
            for i in range(n):
                if child[i] == -1:
                    child[i] = remaining.pop(0)
            # 突變
            if random.random() < mutation_rate:
                i, j = random.sample(range(n), 2)
                child[i], child[j] = child[j], child[i]
            next_pop.append(child)
        pop = next_pop
    
    return pop[0], -fitness(pop[0])

深入理解：遺傳演算法的三大核心運算元

1. 選擇 (Selection)

| 方法 | 描述 | 特點 | |------|------|------| | 輪盤選擇 | 依適應度比例決定機率 | 簡單但可能早熟收斂 | | 錦標賽選擇 | 隨機取 k 個取最佳 | 可控制選擇壓力 | | 秩級選擇 | 依排序分配機率 | 不受適應度尺度影響 | | 菁英保留 | 直接保留前幾名 | 保證不退化 |

def tournament_selection(pop, fitnesses, k=3):
    """錦標賽選擇"""
    selected = random.sample(list(zip(pop, fitnesses)), k)
    return max(selected, key=lambda x: x[1])[0]

2. 交叉 (Crossover)

| 方法 | 適合 | 描述 | |------|------|------| | 單點交叉 | 二進位編碼 | 一個切點交換後半段 | | 均勻交叉 | 二進位編碼 | 每個基因隨機選父代 | | OX (順序交叉) | TSP 排列編碼 | 保留順序關係 | | PMX (部分映射交叉) | TSP 排列編碼 | 保留位置關係 |

3. 突變 (Mutation)

交換突變 (Swap)：交換兩個基因—適合 TSP
反轉突變 (Inversion)：反轉一段序列—適合 TSP
高斯突變 (Gaussian)：加入常態雜訊—適合連續空間
位元翻轉 (Bit Flip)：0↔1—適合二進位編碼

實戰：收斂過程視覺化

import matplotlib.pyplot as plt

# 追蹤每一代的最佳與平均適應度
def ga_with_tracking(cities, pop_size=100, generations=200):
    # ...（同上 GA 實作，但記錄歷代最佳）
    best_history = []
    avg_history = []
    
    for gen in range(generations):
        # ... GA 流程...
        scores = [fitness(ind) for ind in pop]
        best_history.append(max(scores))
        avg_history.append(sum(scores)/len(scores))
    
    return pop[0], best_history, avg_history

_, best_hist, avg_hist = ga_with_tracking(cities)

plt.figure(figsize=(10, 5))
plt.plot(best_hist, label='最佳適應度', linewidth=2)
plt.plot(avg_hist, label='平均適應度', alpha=0.7)
plt.xlabel('世代')
plt.ylabel('適應度')
plt.title('GA 收斂過程')
plt.legend()
plt.grid(True)
plt.show()

print(f"初始最佳: {best_hist[0]:.2f}")
print(f"最終最佳: {best_hist[-1]:.2f}")
print(f"改善率: {(best_hist[-1]-best_hist[0])/abs(best_hist[0])*100:.1f}%")

GA 參數調整指南

| 參數 | 太小 | 太大 | 建議值 | |------|------|------|:------:| | 種群大小 | 多樣性不足 | 計算成本高 | 50-200 | | 突變率 | 早熟收斂 | 變隨機搜尋 | 0.01-0.1 | | 交叉率 | 收斂慢 | 破壞優秀基因 | 0.7-0.9 | | 菁英數 | 好解可能丟失 | 減少多樣性 | 2-5 |

關鍵要點

✅ GA 的核心是選擇→交叉→突變的迭代循環
✅ 編碼方式決定 GA 的效能（二進位、排列、實數）
✅ 選擇壓力需平衡：太少收斂慢，太多早熟收斂
✅ 突變率在 < 0.1 時效果最好，太高就變隨機搜尋
✅ GA 適合平行化，可以同時評估多個個體的適應度

基因演算法：達爾文進化論的啟發

基因演算法（GA）模擬物競天擇——適應力越強的個體越有機會繁殖，下一代繼承上一代的優良基因。

GA 的核心步驟

1. 初始化族群（隨機產生 N 個解）
2. 評估每個解的適應度（fitness）
3. 選擇：適應度越高的被選中繁殖的機率越大
4. 交配：兩個父代的染色體交換，產生子代
5. 突變：隨機改變子代的部分基因（避免太早收斂）
6. 重複 2-5 直到滿足終止條件

為什麼要用 GA？

| 優勢 | 說明 | |:----|:----| | 全域搜尋 | 族群同時探索多個區域，不容易卡在局部最佳 | | 無需梯度 | 不需要目標函數可微分——適合黑箱問題 | | 平行化 | 每個個體的評估可以完全平行執行 | | 離散問題 | 自然支援組合最佳化（TSP、排程） |

與模擬退火的比較

| 比較 | 模擬退火 | 基因演算法 | |:----|:--------|:----------| | 解的數量 | 1 個 | N 個（族群） | | 平行化 | 難 | 容易 | | 多模態探索 | 靠機率跳脫 | 族群自然探索 | | 收斂速度 | 快 | 慢但更全面 |

下一章預告：粒子群最佳化 PSO

基因演算法的交配和突變有點複雜。下一章的 PSO 更簡單——每個粒子只有位置和速度，透過追蹤個人最佳和群體最佳來演化。