遺傳算法(Genetic Algorithm, GA)模擬自然選擇與遺傳機制,用於搜尋最佳化問題的近似解。標準流程:
最大化函數 f(x) = x³ - 60x² + 900x + 100,定義域 x ∈ [0, 31](5 位元二進制編碼)。
#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;
}
| 策略 | 原理 | 優點 | 缺點 |
|---|---|---|---|
| 輪盤賭 | 適應度比例 | 簡單 | 早期早熟、後期選擇壓力不足 |
| 錦標賽選擇 | 隨機抽 k 個取最佳 | 參數可控、平行化易 | 需調整 k 值 |
| 排序選擇 | 按排名分配機率 | 穩定、無量綱問題 | 需排序 O(n log n) |
| 精英保留 | 保留前 k 最佳直接進入下一代 | 保證單調收斂 | 可能過早收斂 |