当前位置：首页 > java >正文

遗传算法简明指南：思路解析与C++实现

java 2025/7/27 18:35:07

摘要：遗传算法（Genetic Algorithm）是一种模拟生物进化过程的优化算法，适用于复杂搜索空间中的最优解查找。本文通过生活化比喻和C++伪代码，帮助开发者快速掌握算法核心思路。

一、算法核心思路

想象你正在培养一支超级战队：

初代成员：随机生成一批候选方案（种群初始化）
选拔精英：评估每个方案的优劣（适应度函数）
优胜劣汰：优选高质量方案进行"繁殖"（选择操作）
基因重组：组合优秀方案的特性（交叉操作）
基因突变：引入随机变化保持多样性（变异操作）
代际传承：保留每代最优方案（精英保留）

二、算法流程图

初始化种群 → 评估适应度 → 选择父代 → 交叉产生子代 → 变异 → 精英保留 → 循环迭代

三、关键步骤详解

1. 种群初始

struct Chromosome {vector<Gene> genes;  // 解决方案编码double fitness;      // 适应度评分
};vector<Chromosome> initializePopulation(int size) {vector<Chromosome> population;for(int i=0; i<size; ++i) {Chromosome c;random_generate(c.genes);  // 随机生成基因c.fitness = 0;population.push_back(c);}return population;
}

2. 适应度评估（需自定义）

void evaluateFitness(Chromosome& c) {// 根据业务需求实现评分逻辑// 评分越高表示解决方案越优c.fitness = ...; 
}

3. 锦标赛选择（父代选拔）

Chromosome tournamentSelect(const vector<Chromosome>& pop, int k) {vector<Chromosome> candidates;for(int i=0; i<k; ++i) {int idx = rand() % pop.size();candidates.push_back(pop[idx]);}return *max_element(candidates.begin(), candidates.end(), [](auto& a, auto& b){ return a.fitness < b.fitness; });
}

4. 基因重组（交叉操作）

pair<Chromosome, Chromosome> crossover(const Chromosome& p1, const Chromosome& p2) {Chromosome c1 = p1, c2 = p2;// 实施交叉策略（示例为单点交叉）int point = rand() % p1.genes.size();swap_ranges(c1.genes.begin()+point, c1.genes.end(), c2.genes.begin()+point);return {c1, c2};
}

5. 基因突变

void mutate(Chromosome& c, double rate) {for(auto& gene : c.genes) {if(rand()/RAND_MAX < rate) {gene = random_modification(gene); // 随机修改}}
}

6. 精英保留策略

void elitism(vector<Chromosome>& newPop, const vector<Chromosome>& oldPop,int eliteSize) 
{// 保留旧种群中前eliteSize个最优个体auto elites = oldPop;sort(elites.begin(), elites.end(), [](auto& a, auto& b){ return a.fitness > b.fitness; });// 替换新种群中较差的个体for(int i=0; i<eliteSize; ++i) {newPop[newPop.size()-1-i] = elites[i];}
}

四、完整算法框架

void geneticAlgorithm() {// 参数配置const int POP_SIZE = 100;const double MUTATION_RATE = 0.1;const int MAX_GENERATION = 1000;const int ELITE_SIZE = 5;// 初始化auto population = initializePopulation(POP_SIZE);for(int gen=0; gen<MAX_GENERATION; ++gen) {// 评估适应度for(auto& c : population) evaluateFitness(c);// 创建新种群vector<Chromosome> newPopulation;// 生成子代while(newPopulation.size() < POP_SIZE) {// 选择父代auto p1 = tournamentSelect(population, 3);auto p2 = tournamentSelect(population, 3);// 基因重组auto [c1, c2] = crossover(p1, p2);// 基因突变mutate(c1, MUTATION_RATE);mutate(c2, MUTATION_RATE);newPopulation.push_back(c1);if(newPopulation.size() < POP_SIZE) newPopulation.push_back(c2);}// 精英保留elitism(newPopulation, population, ELITE_SIZE);// 世代更替population = newPopulation;}
}

五、应用场景建议

组合优化问题：如旅行商问题、排班调度
参数调优：机器学习超参数优化
路径规划：机器人导航、物流配送
设计优化：工程结构设计、电路布局

六、参数调整指南

参数	典型范围	影响说明
种群大小	50-500	越大搜索空间越广，计算量越大
变异率	0.01-0.2	过高导致随机性过强
精英保留数量	1-5%种群大小	防止优质解丢失
最大迭代次数	100-10000	根据问题复杂度调整