萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C++ 遺傳算法完整實作:從編碼、選擇、交叉、變異到優化求解

遺傳算法核心流程

遺傳算法(Genetic Algorithm, GA)模擬自然選擇與遺傳機制,用於搜尋最佳化問題的近似解。標準流程:

  1. 初始化:隨機產生初始族群
  2. 適應度評估:計算每個個體的適應度
  3. 選擇:按適應度比例選擇父代(輪盤賭法)
  4. 交叉:按機率交換父代基因片段
  5. 變異:按低機率翻轉基因位
  6. 終止條件:達到最大世代數或收斂

問題定義

最大化函數 f(x) = x³ - 60x² + 900x + 100,定義域 x ∈ [0, 31](5 位元二進制編碼)。

完整 C++ 實作(現代 C++17 風格重構)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

constexpr int GENE_LENGTH = 5;           // 染色體長度(位元數)
constexpr int POP_SIZE = 8;              // 族群大小
constexpr int MAX_GENERATIONS = 20;      // 最大世代數
constexpr double CROSSOVER_RATE = 0.90;  // 交叉機率
constexpr double MUTATION_RATE = 0.05;   // 變異機率
constexpr int X_MIN = 0;
constexpr int X_MAX = 31;                // 2^5 - 1

// 適應度函數
int fitness(int x) {
    return x*x*x - 60*x*x + 900*x + 100;
}

// 解碼:二進制位元組 → 整數
int decode(const std::bitset& genes) {
    return static_cast(genes.to_ulong());
}

// 編碼:整數 → 二進制位元組
std::bitset encode(int x) {
    return std::bitset(x);
}

// 單點交叉
void crossover(std::bitset& a, std::bitset& b, std::mt19937& rng) {
    std::uniform_int_distribution dist(1, GENE_LENGTH - 1);
    int point = dist(rng); // 交叉點 1..4
    
    // 交換高位部分
    for (int i = point; i < GENE_LENGTH; ++i) {
        bool temp = a[i];
        a[i] = b[i];
        b[i] = temp;
    }
}

// 變異:翻轉單一位元
void mutate(std::bitset& individual, std::mt19937& rng) {
    std::uniform_real_distribution prob(0.0, 1.0);
    std::uniform_int_distribution pos(0, GENE_LENGTH - 1);
    
    for (int i = 0; i < GENE_LENGTH; ++i) {
        if (prob(rng) < MUTATION_RATE) {
            individual.flip(i);
        }
    }
}

// 輸出族群狀態
void printPopulation(const std::vector>& pop, int gen) {
    std::cout << "Generation " << gen << ": ";
    for (const auto& ind : pop) {
        std::cout << decode(ind) << '(' << ind.to_string() << ") ";
    }
    std::cout << '\n';
}

int main() {
    // 隨機引擎
    std::random_device rd;
    std::mt19937 rng(rd()); // 或固定種子 rng(6553) 以複現
    
    // 1. 初始化族群
    std::vector> population(POP_SIZE);
    std::uniform_int_distribution initDist(X_MIN, X_MAX);
    for (auto& ind : population) {
        ind = encode(initDist(rng));
    }
    
    std::cout << "初始族群: ";
    printPopulation(population, 0);
    
    // 2. 進化主迴圈
    for (int gen = 1; gen <= MAX_GENERATIONS; ++gen) {
        // 2.1 計算適應度
        std::vector fitnessValues(POP_SIZE);
        for (int i = 0; i < POP_SIZE; ++i) {
            fitnessValues[i] = fitness(decode(population[i]));
        }
        
        // 2.2 計算總適應度與累積機率(輪盤賭)
        int totalFitness = std::accumulate(fitnessValues.begin(), fitnessValues.end(), 0);
        std::vector cumulativeProb(POP_SIZE);
        double sum = 0.0;
        for (int i = 0; i < POP_SIZE; ++i) {
            sum += static_cast(fitnessValues[i]) / totalFitness;
            cumulativeProb[i] = sum;
        }
        
        // 2.3 選擇:建立新族群
        std::vector> newPopulation(POP_SIZE);
        std::uniform_real_distribution selectDist(0.0, 1.0);
        for (int i = 0; i < POP_SIZE; ++i) {
            double r = selectDist(rng);
            int idx = std::lower_bound(cumulativeProb.begin(), cumulativeProb.end(), r) - cumulativeProb.begin();
            idx = std::min(idx, POP_SIZE - 1); // 邊界保護
            newPopulation[i] = population[idx];
        }
        population = std::move(newPopulation);
        
        // 2.4 交叉:配對交換
        std::uniform_real_distribution crossDist(0.0, 1.0);
        for (int i = 0; i < POP_SIZE; i += 2) {
            if (i + 1 < POP_SIZE && crossDist(rng) < CROSSOVER_RATE) {
                crossover(population[i], population[i + 1], rng);
            }
        }
        
        // 2.5 變異
        for (auto& ind : population) {
            mutate(ind, rng);
        }
        
        // 2.6 輸出統計
        int bestIdx = std::max_element(fitnessValues.begin(), fitnessValues.end()) - fitnessValues.begin();
        std::cout << "Gen " << std::setw(2) << gen 
                  << " | Best x=" << decode(population[bestIdx]) 
                  << " f(x)=" << fitnessValues[bestIdx]
                  << " | Avg f=" << (totalFitness / (double)POP_SIZE) << '\n';
    }
    
    // 3. 最終結果
    std::cout << "\n最終族群: ";
    printPopulation(population, MAX_GENERATIONS);
    
    // 找出最優解
    auto bestIt = std::max_element(population.begin(), population.end(),
        [](const auto& a, const auto& b) {
            return fitness(decode(a)) < fitness(decode(b));
        });
    std::cout << "最優解: x = " << decode(*bestIt) 
              << ", f(x) = " << fitness(decode(*bestIt)) << '\n';
    
    return 0;
}

關鍵設計決策解析

1. 編碼策略

  • 二進制編碼:原文使用 5 位元直接對應 0-31,簡單直觀
  • 格雷碼:相鄰整數僅差 1 位,減少「錘子效應」(大變異導致大跳躍)
  • 實數編碼:直接操作浮點數,精度高、無編解碼開銷,現代 GA 主流

2. 選擇策略比較

3. 交叉與變異參數調整

  • CROSSOVER_RATE 通常 0.6~0.9,過高破壞優良結構,過低搜尋停滯
  • MUTATION_RATE 通常 0.001~0.1,維持多樣性、跳出局部最優
  • 自適應參數:根據族群多樣度動態調整

進階擴充方向

  • 多目標優化:NSGA-II、SPEA2(Pareto 前沿)
  • 約束處理:懲罰函數、可行性法則、修復算子
  • 混合整數/實數編碼:針對混合變數問題
  • 並行化:島嶼模型、主從模型、GPU 加速
  • 元啟發式混合:GA + 局部搜尋(Memetic Algorithm)、GA + 模擬退火

總結

遺傳算法是解決複雜最佳化問題的強大工具。理解編碼、選擇、交叉、變異四大核心算子的設計權衡,並結合問題領域知識調整參數,是成功應用 GA 的關鍵。現代 C++ 提供的 <random>、<algorithm>、std::bitset 等工具,讓實作更安全、可讀、高效。

copyright © 萬盛學電腦網 all rights reserved
策略原理優點缺點
輪盤賭適應度比例簡單早期早熟、後期選擇壓力不足
錦標賽選擇隨機抽 k 個取最佳參數可控、平行化易需調整 k 值
排序選擇按排名分配機率穩定、無量綱問題需排序 O(n log n)
精英保留保留前 k 最佳直接進入下一代保證單調收斂可能過早收斂