C++ 簡單遺傳算法完整實現：二進制編碼、輪盤選擇、單點交叉、位變異、代碼詳解

前言

遺傳算法 (GA) 是啟發式優化算法，模擬自然選擇與遺傳機制。本文提供一個**教學級完整實現**：5 位二進制編碼、適應度函數 f(x)=x³-60x²+900x+100、輪盤賭選擇、單點交叉 (pc=0.9)、位翻轉變異 (pm=0.05)、20 代演化，搜索定義域 [0,31] 的最大值。

核心參數

const int L = 5;           // 染色體長度 (2^5=32 覆蓋 0~31)
const int POP_SIZE = 8;    // 種群大小
const int MAX_GEN = 20;    // 最大代數
const double P_CROSS = 0.90;
const double P_MUT   = 0.05;

關鍵流程

1. 初始化：隨機生成 8 個 0~31 整數作為第 0 代。
2. 適應度計算：f(x) 值越大越優。
3. 輪盤賭選擇：按適應度比例構建累積概率分佈，隨機選中個體進入交配池。
4. 交叉：配對個體，以 pc 概率隨機選擇交叉點 (1~L-1)，交換高位片段。
5. 變異：每個基因位以 pm 概率翻轉 (0↔1)，使用 std::bitset<L> 便捷操作。
6. 迭代：重複 2-5 共 20 代，輸出最終種群。

核心代碼片段

適應度函數

int fitness(int x) { return x*x*x - 60*x*x + 900*x + 100; }

輪盤賭選擇

double sum = 0;
for (int v : pop) sum += fitness(v);
double[] cumProb = new double[POP_SIZE];
for (int i = 0; i < POP_SIZE; i++) {
    cumProb[i] = (i==0) ? fitness(pop[i])/sum : cumProb[i-1] + fitness(pop[i])/sum;
}
for (int i = 0; i < POP_SIZE; i++) {
    double r = rand() / (double)RAND_MAX;
    int selected = 0;
    while (selected < POP_SIZE && r > cumProb[selected]) selected++;
    matingPool[i] = pop[selected];
}

單點交叉

void crossover(int &a, int &b) {
    int point = rand() % L + 1; // 1..L
    bitset A(a), B(b), C, D;
    for (int i = 0; i < point; i++) { if (A[i]) C.set(i); if (B[i]) D.set(i); }
    for (int i = point; i < L; i++) { if (B[i]) C.set(i); if (A[i]) D.set(i); }
    a = (int)C.to_ulong(); b = (int)D.to_ulong();
}

位變異

for (int &ind : pop) {
    bitset b(ind);
    for (int i = 0; i < L; i++)
        if (rand()/(double)RAND_MAX < P_MUT) b.flip(i);
    ind = (int)b.to_ulong();
}

運行結果示例

初始種群: 12 5 23 18 2 29 7 14
繁殖代數: t=0 ... t=20
最終結果: 30 30 30 30 30 30 30 30  (收斂到 x=30, f(30)=1000 附近最大值)

教學重點總結

擴展方向

• 實數編碼 (浮點數直接運算)，避免二進制編碼精度損失。
• 錦標賽選擇、模擬二進制交叉 (SBX)、多項式變異 (NSGA-II 標準)。
• 多目標優化 (Pareto 前沿)、約束處理、並行島模型。

總結

這個 150 行左右的 C++ GA 完整演示了「編碼→適應度→選擇→交叉→變異→迭代」核心流程。通過 bitset 封裝位運算，代碼既清晰又高效。作為進階學習 NSGA-II、CMA-ES、差分進化等現代演化算法的基石極為合適。