Genetic Algorithm

🔥 Vibe Prompt

"Evolve a bitstring to match '11111111...' (64 bits). Use tournament selection, 1-point crossover, mutation."

import random

def ga(target_len=64, pop_size=100, gens=100):
    target = [1] * target_len
    
    def fitness(ind): return sum(i == t for i, t in zip(ind, target))
    def create(): return [random.randint(0,1) for _ in range(target_len)]
    
    pop = [create() for _ in range(pop_size)]
    
    for gen in range(gens):
        scores = [(fitness(ind), ind) for ind in pop]
        scores.sort(reverse=True)
        
        if scores[0][0] == target_len:
            print(f"Perfect solution at gen {gen}!")
            break
        
        new_pop = [scores[0][1], scores[1][1]]  # Elitism
        
        while len(new_pop) < pop_size:
            parents = random.choices(pop, weights=[f + 1 for f, _ in scores], k=2)
            cross = random.randint(0, target_len)
            child = parents[0][:cross] + parents[1][cross:]
            if random.random() < 0.01:
                child[random.randint(0, target_len-1)] ^= 1
            new_pop.append(child)
        pop = new_pop
        
        if gen % 20 == 0:
            print(f"Gen {gen}: best fitness = {scores[0][0]}/{target_len}")

    return max(fitness(ind) for ind in pop)

result = ga()
print(f"Final fitness: {result}/64")

Applications

Neural architecture search
Financial trading strategies
Robot controller design
Feature selection

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

為什麼 GA 能這麼有效？三個關鍵機制

GA 的核心在於三個運算元（Operators）的協同作用：

| 運算元 | 作用 | 防止的問題 | |:------:|------|:----------:| | 選擇 (Selection) | 保留適應度高的個體 | 防止好解被丟棄 | | 交叉 (Crossover) | 組合兩個好解的優點 | 探索新的解空間區域 | | 突變 (Mutation) | 隨機改變部分基因 | 防止早熟收斂到局部最佳 |

單獨使用任何一個都不夠——選擇會讓族群失去多樣性，交叉只能在現有基因組合中打轉，突變如果太強就變隨機搜尋。三者的平衡才是 GA 的關鍵。

常見的選擇策略

| 策略 | 實作方式 | 特性 | |:----:|---------|------| | 輪盤選擇 (Roulette Wheel) | 適應度越高的個體被選中機率越高 | 可能讓超級個體主宰族群，失去多樣性 | | 錦標賽選擇 (Tournament) | 隨機抽 k 個，取最好的那個 | 可控制選擇壓力（k 越大壓力越大） | | 秩級選擇 (Rank-Based) | 依適應度排名分配機率，不看絕對值 | 不受適應度尺度影響，穩定性好 | | 菁英保留 (Elitism) | 直接保留前 n 名到下一代 | 保證最佳解不會消失 |

什麼時候該用 GA？

| 場景 | 適合度 | 原因 | |:----:|:------:|------| | 超參數調優 | ✅ 非常適合 | 超參數空間不連續、不可微，GA 不需梯度 | | 神經網路架構搜尋 | ✅ 業界標準 | Google 用 GA 找到了更好的 CNN 架構 | | 排程與路徑規劃 | ✅ 適合 | 但 SA 在 TSP 上通常更快 | | 遊戲 AI | ✅ 經典應用 | 訓練遊戲角色的行為策略 | | 連續函數最佳化 | ⚠️ 可以但非首選 | PSO 在這方面更快更簡單 | | 即時系統（需毫秒級回應） | ❌ 不適合 | GA 收斂慢，不適合線上即時決策 |

下一章預告：從演化到群體智慧

GA 從生物演化中獲得靈感——適者生存、基因重組、突變。下一章的 粒子群最佳化 (PSO) 則從另一個自然現象獲得靈感：鳥群覓食。

兩種都是「族群式」演算法，但運作方式截然不同。GA 透過選擇與重組來演化，PSO 則透過粒子在空間中移動並互相學習。當你遇到一個新的最佳化問題時，了解這兩者的差異能幫助你選對工具。

🎯 理解核心原理：掌握遺傳演算法 GA、動手實作、串聯所學、進階探索、專案實戰的完整知識體系
💻 動手實作：使用 Python/JavaScript 寫出可運行的實作程式碼
🔍 除錯與分析：遇到相關問題時能快速定位根本原因
🏗️ 整合應用：將本章所學整合到你的實際專案中

銜接下一章

本章深入探討了 遺傳演算法 GA 的核心概念與實作方法。下一章將在此基礎上，進一步探索更進階的應用場景——你將學會如何將本章的知識擴展到更複雜的真實世界問題中。

確保你已經完全理解本章的內容再前進，因為下一章會直接建立在這些基礎概念之上。