遗传算法实战用Python从零实现一个简易GA附完整代码最近几年我身边不少做数据分析和优化的朋友都开始把目光投向了一些“非传统”的算法。大家不再满足于梯度下降这类确定性方法而是对那些从自然界汲取灵感的算法比如遗传算法产生了浓厚的兴趣。原因很简单很多现实世界的问题比如复杂的排班调度、非凸的函数优化、甚至是神经网络的超参数搜索其搜索空间往往崎岖不平充满了局部最优的陷阱。这时候一种能够进行全局探索、不依赖梯度信息、并且自带并行潜力的算法就显得格外有吸引力。遗传算法正是这样一种工具。它模拟了生物进化中“物竞天择适者生存”的核心机制通过编码、选择、交叉和变异等操作让一群“候选解”在迭代中不断进化最终逼近问题的最优解。听起来很酷对吧但很多初学者在尝试理解它时常常被各种生物学术语和抽象流程劝退。理论看懂了但一打开代码编辑器却不知从何下手。这篇文章就是为你准备的。我们将彻底抛开那些复杂的公式推导直接进入实战。我会手把手地带你用最纯粹的Python从零开始构建一个完整的、可运行的遗传算法。我们将从一个具体的优化问题出发一步步实现编码、评估、选择、交叉和变异等所有核心组件。更重要的是我会分享在实际编码中遇到的“坑”以及调参时那些微妙的直觉。读完本文你不仅能获得一份可以直接运行的代码更能真正理解遗传算法是如何“思考”和“进化”的。无论你是正在学习优化算法的学生还是希望为项目工具箱增添新武器的开发者相信这次实战之旅都会让你有所收获。1. 问题定义与算法框架设计在动手写代码之前我们必须先明确要解决什么问题。遗传算法是一个通用框架它可以应用于函数优化、组合优化、参数寻优等众多领域。为了聚焦于算法本身我们选择一个经典且直观的示例寻找一个二进制串使其所有位的和最大。这听起来很简单但它完美地契合了遗传算法的演示需求——解空间明确所有可能的二进制串适应度函数清晰求和并且我们可以直观地理解“优秀个体”是什么样的。具体来说我们设定每个个体候选解是一个长度为10的二进制串例如[1, 0, 1, 1, 0, 1, 0, 0, 1, 1]。我们的目标是找到那个全为1的串[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]因为它的和最大为10。虽然这个问题用枚举法也能瞬间解决但请把它看作一个“麻雀”我们将通过解剖它来理解遗传算法这只“麻雀”的五脏六腑。一个完整的遗传算法流程通常包含以下几个核心步骤它们构成了我们代码的主循环初始化随机生成一个包含多个个体的初始种群。评估计算种群中每个个体的适应度Fitness。选择根据适应度以某种概率选择出用于繁殖下一代的“父母”。交叉将选中的“父母”两两配对交换部分基因产生“后代”。变异以一个小概率随机改变后代中某些基因的值。迭代用新生成的后代种群替代旧种群重复步骤2-5直到满足终止条件如达到最大迭代次数或找到最优解。基于这个流程我们可以先勾勒出代码的骨架。这里我们将使用面向对象的方式来组织代码这样结构会更清晰也便于后续扩展。class SimpleGA: def __init__(self, pop_size, gene_length, crossover_rate, mutation_rate, max_generations): 初始化遗传算法参数。 :param pop_size: 种群大小 :param gene_length: 个体基因长度二进制串长度 :param crossover_rate: 交叉概率 :param mutation_rate: 变异概率 :param max_generations: 最大进化代数 self.pop_size pop_size self.gene_length gene_length self.crossover_rate crossover_rate self.mutation_rate mutation_rate self.max_generations max_generations self.population None self.fitness_history [] # 用于记录每一代的最佳适应度方便后续可视化 def run(self): 主运行函数控制整个进化流程。 self.initialize_population() for generation in range(self.max_generations): fitness self.evaluate_population() # 记录当前代的最佳适应度 self.fitness_history.append(max(fitness)) # 可以在这里添加终止条件判断例如找到完美解 if max(fitness) self.gene_length: # 适应度等于基因长度即找到全1解 print(f在第 {generation} 代找到最优解) break selected_parents self.select(fitness) offspring self.crossover(selected_parents) offspring self.mutate(offspring) self.population offspring # 新一代取代旧一代 return self.population, self.fitness_history # 以下方法将在后续章节具体实现 def initialize_population(self): pass def evaluate_population(self): pass def select(self, fitness): pass def crossover(self, parents): pass def mutate(self, offspring): pass这个框架就像我们算法的蓝图。接下来我们将逐一填充每一个空白的方法让算法真正“活”起来。2. 核心组件实现从初始化到评估2.1 初始化种群初始种群是算法探索的起点。一个多样化的初始种群有助于算法探索解空间的不同区域避免过早陷入局部最优。在我们的问题中初始化非常简单为种群中的每一个个体随机生成一个指定长度的二进制列表。import random def initialize_population(self): 随机初始化种群。 每个个体是一个长度为 gene_length 的列表元素为 0 或 1。 self.population [] for _ in range(self.pop_size): individual [random.randint(0, 1) for _ in range(self.gene_length)] self.population.append(individual)这里使用了列表推导式来高效生成随机个体。random.randint(0, 1)会等概率地返回0或1。初始化后self.population就是一个包含pop_size个列表的列表。2.2 适应度评估适应度函数是遗传算法的“指挥棒”它决定了哪些个体更优秀从而更有可能被选中参与繁殖。对于我们的求和问题适应度函数就是个体二进制串所有元素的和。这个值越大个体越优秀。def evaluate_population(self): 评估种群中每个个体的适应度。 :return: 一个列表包含每个个体的适应度值。 fitness_values [] for individual in self.population: # 适应度 所有基因位之和 fitness sum(individual) fitness_values.append(fitness) return fitness_values注意适应度函数的设计是遗传算法应用中最关键、也最需要技巧的一步。它必须能够准确、高效地反映解的质量。对于更复杂的问题如旅行商问题TSP适应度函数可能是路径总长度的倒数因为我们的目标是最小化距离。为了更直观地感受种群的状态我们可以在评估后加入一个简单的统计功能输出当前代的最佳个体和平均适应度。这有助于我们在算法运行时进行监控。def evaluate_population(self): fitness_values [] for individual in self.population: fitness sum(individual) fitness_values.append(fitness) # 可选打印当前代统计信息 best_fitness max(fitness_values) avg_fitness sum(fitness_values) / len(fitness_values) best_idx fitness_values.index(best_fitness) # 在实际项目中可以考虑使用日志库而非print # print(f最佳适应度: {best_fitness}, 平均适应度: {avg_fitness:.2f}, 最佳个体: {self.population[best_idx]}) return fitness_values3. 遗传算子的实现选择、交叉与变异遗传算子是驱动种群进化的引擎它们模拟了自然选择、基因重组和基因突变的过程。3.1 选择算子轮盘赌选择选择算子的目的是从当前种群中筛选出适应度较高的个体作为父代。最经典的方法是轮盘赌选择。其核心思想是个体被选中的概率与其适应度成正比。适应度越高在“轮盘”上占的面积就越大被选中的几率也就越高。实现轮盘赌选择需要以下几步计算种群的总适应度。计算每个个体的选择概率个体适应度 / 总适应度。计算每个个体的累积概率。生成一个[0, 1)之间的随机数落在哪个个体的累积概率区间内就选择哪个个体。重复此过程直到选满与种群大小相同数量的父代。def select(self, fitness_values): 使用轮盘赌选择法选择父代。 :param fitness_values: 当前种群的适应度列表 :return: 被选中的父代个体列表 total_fitness sum(fitness_values) # 避免除零错误如果总适应度为0初始种群可能全为0则赋予每个个体相等的概率 if total_fitness 0: prob [1/len(fitness_values)] * len(fitness_values) else: prob [f/total_fitness for f in fitness_values] # 选择概率 # 计算累积概率 cum_prob [] cumulative 0 for p in prob: cumulative p cum_prob.append(cumulative) selected_parents [] for _ in range(self.pop_size): rand random.random() # 生成一个[0,1)的随机数 # 找到第一个累积概率大于随机数的索引 for i, cp in enumerate(cum_prob): if rand cp: selected_parents.append(self.population[i][:]) # 注意使用拷贝避免后续操作修改原个体 break return selected_parents提示代码中self.population[i][:]使用了列表切片进行拷贝这是非常重要的一步。如果不拷贝后续的交叉和变异操作会直接修改原始种群中的个体破坏算法的状态可能导致意想不到的错误。轮盘赌选择简单有效但它有一个潜在问题在进化早期若某个超级个体适应度远高于其他它可能会迅速占据主导导致种群多样性急剧下降早熟收敛。在进化后期当个体适应度相差无几时选择压力又会变小进化缓慢。因此在实际应用中锦标赛选择、排序选择等变体也常被使用。3.2 交叉算子单点交叉交叉算子模拟了生物有性生殖中的基因重组。它从父代中随机选取两个个体然后按一定概率交换它们的一部分基因从而产生新的后代。这里我们实现最基础的单点交叉。操作步骤如下将选中的父代两两配对如 parent1 和 parent2。生成一个[0, 1)的随机数若小于交叉概率crossover_rate则进行交叉否则子代直接复制父代。如果决定交叉则随机选择一个交叉点1 到gene_length-1之间。交换两个父代在交叉点之后的那部分基因。def crossover(self, parents): 对选中的父代进行单点交叉产生后代。 :param parents: 经过选择操作得到的父代列表 :return: 后代种群列表 offspring [] # 将父代两两配对 (0-1, 2-3, ...) for i in range(0, self.pop_size, 2): parent1 parents[i] parent2 parents[i1] if (i1) self.pop_size else parents[i] # 处理种群大小为奇数的情况 child1 parent1[:] # 子代初始为父代的拷贝 child2 parent2[:] # 判断是否进行交叉 if random.random() self.crossover_rate: # 随机选择交叉点不能是0或最后一位否则无意义 cross_point random.randint(1, self.gene_length - 2) # 交换交叉点之后的基因片段 child1[cross_point:], child2[cross_point:] child2[cross_point:], parent1[cross_point:] # 注意上面这行交换代码有个常见错误正确的应该是用 parent2 的片段。 # 正确写法 # child1 parent1[:cross_point] parent2[cross_point:] # child2 parent2[:cross_point] parent1[cross_point:] # 但为了保持代码结构清晰我们采用更易懂的逐段交换方式并修正错误 temp child1[cross_point:] child1[cross_point:] child2[cross_point:] child2[cross_point:] temp offspring.append(child1) offspring.append(child2) # 确保后代数量与种群大小一致当pop_size为奇数时上面的循环会少生成一个 return offspring[:self.pop_size]交叉是产生新个体的主要动力它结合了不同父代的优良特性。交叉概率通常设置得较高如0.6-0.9以促进基因混合。3.3 变异算子按位变异变异算子以很小的概率随机改变个体中的某些基因值。它为种群引入了新的遗传物质是维持种群多样性、帮助算法跳出局部最优的关键。我们实现最简单的按位变异。操作步骤遍历后代种群中的每一个个体对于个体中的每一个基因位生成一个[0,1)的随机数。如果这个数小于变异概率mutation_rate则将该基因位取反0变11变0。def mutate(self, offspring): 对后代种群进行按位变异。 :param offspring: 经过交叉产生的后代列表 :return: 变异后的后代列表 for individual in offspring: for i in range(self.gene_length): if random.random() self.mutation_rate: individual[i] 1 if individual[i] 0 else 0 # 位翻转 return offspring变异概率通常设置得非常低如0.001-0.05。过高的变异率会使算法退化为随机搜索破坏已有的优良基因而过低则可能无法有效探索新的区域。4. 算法组装、调参与可视化现在我们已经实现了所有核心组件。让我们将它们组装起来设置一组参数并运行这个完整的遗传算法。4.1 完整代码与首次运行将之前所有的方法定义整合到SimpleGA类中并添加一个主程序入口。# 将之前所有def函数作为SimpleGA类的方法整合在此处 # ... (initialize_population, evaluate_population, select, crossover, mutate, run) if __name__ __main__: # 设置算法参数 POP_SIZE 20 # 种群大小 GENE_LENGTH 10 # 个体长度 CROSSOVER_RATE 0.8 # 交叉概率 MUTATION_RATE 0.05 # 变异概率 MAX_GENS 50 # 最大进化代数 # 创建算法实例并运行 ga SimpleGA(POP_SIZE, GENE_LENGTH, CROSSOVER_RATE, MUTATION_RATE, MAX_GENS) final_population, fitness_history ga.run() # 输出最终结果 final_fitness ga.evaluate_population() best_idx final_fitness.index(max(final_fitness)) print(f进化结束。) print(f最佳个体: {final_population[best_idx]}) print(f最佳适应度: {max(final_fitness)})运行这段代码你可能会看到类似这样的输出在第 42 代找到最优解 进化结束。 最佳个体: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 最佳适应度: 10恭喜你的第一个遗传算法成功找到了全局最优解。但别高兴太早多运行几次你会发现结果并不总是这么完美。有时算法会“卡”在某个次优解比如和为9这就是陷入了局部最优。算法的表现很大程度上依赖于我们设定的参数。4.2 关键参数调优指南遗传算法的性能对参数设置非常敏感。没有一套放之四海而皆准的“黄金参数”但有一些经验法则和调优思路参数典型范围影响调优建议种群大小 (pop_size)20 - 200越大多样性越强全局搜索能力越好但每代计算成本越高。问题越复杂搜索空间越大种群规模应相应增大。可以从50-100开始尝试。交叉概率 (crossover_rate)0.6 - 0.9控制基因混合的强度。太高可能导致优良模式被破坏太低则进化缓慢。通常设置较高如0.8。可以视为算法的主要搜索驱动。变异概率 (mutation_rate)0.001 - 0.1维持种群多样性、跳出局部最优的关键。过高会变成随机搜索。设置较低如0.01或1/gene_length。如果发现早熟收敛可适当提高。最大代数 (max_generations)100 - 5000算法运行的上限。需要根据问题复杂度和收敛速度设定。结合其他终止条件如连续N代适应度无改善使用避免无意义运行。注意参数之间会相互影响。例如增大种群规模可能允许你使用稍低的变异率。最好的方法是针对你的具体问题进行参数扫描实验。记录不同参数组合下算法达到预定精度所需的平均代数或成功率从而找到较优的参数区域。4.3 进化过程可视化“看见”进化过程能极大地帮助我们理解算法行为和调试参数。我们可以用matplotlib库来绘制最佳适应度随代数变化的曲线。首先确保安装了matplotlibpip install matplotlib。 然后在算法主循环中我们已经记录了每一代的最佳适应度到fitness_history列表中。现在添加可视化代码import matplotlib.pyplot as plt if __name__ __main__: # ... 参数设置和算法运行代码同上 ... # 可视化进化过程 plt.figure(figsize(10, 6)) plt.plot(fitness_history, b-, linewidth2, labelBest Fitness) plt.xlabel(Generation) plt.ylabel(Fitness) plt.title(Genetic Algorithm Evolution Progress) plt.grid(True, alpha0.3) plt.legend() plt.show()运行后你会得到一张折线图。一张健康的进化曲线通常显示适应度随着代数增加而阶梯式上升最终趋于平稳收敛。如果曲线很早就变平可能是早熟收敛尝试增加变异率或种群大小。如果曲线上升非常缓慢可能是选择压力不足或交叉/变异操作不够有效。为了更全面地评估算法性能我们还可以在同一张图上绘制平均适应度。这能反映整个种群的进化水平而不仅仅是精英个体。你需要在run方法中同时记录平均适应度。5. 超越简单问题扩展到函数优化我们之前解决的二进制求和问题更像一个“玩具”。为了展示遗传算法的真正威力让我们将其应用于一个经典的连续函数优化问题寻找Rastrigin函数的最小值。Rastrigin函数是一个多峰函数在搜索空间内存在大量局部极小点对算法的全局搜索能力是很好的考验。其公式为f(x) A*n Σ_{i1}^{n} [x_i^2 - A*cos(2πx_i)]通常A10x_i ∈ [-5.12, 5.12]。为了用我们的二进制遗传算法解决连续优化问题我们需要引入两个新概念实数编码个体不再是一串0/1而是一个实数列表向量。解码对于二进制编码的GA需要将二进制串解码为实数值。我们先修改算法使其支持实数编码。这实际上更简单因为个体直接就是解向量。class RealCodedGA(SimpleGA): 用于实数优化问题的遗传算法继承自SimpleGA并重写部分方法。 def __init__(self, pop_size, gene_length, crossover_rate, mutation_rate, max_generations, bounds): :param bounds: 每个基因变量的取值范围例如 [(-5.12, 5.12), (-5.12, 5.12)] 对于二维问题。 super().__init__(pop_size, gene_length, crossover_rate, mutation_rate, max_generations) self.bounds bounds # 每个变量的上下界 def initialize_population(self): 在给定边界内随机初始化实数种群。 self.population [] for _ in range(self.pop_size): individual [] for (lower, upper) in self.bounds: individual.append(random.uniform(lower, upper)) self.population.append(individual) def evaluate_population(self): 计算Rastrigin函数值。由于是求最小值我们将函数值取负作为适应度越大越好。 fitness_values [] A 10 for individual in self.population: sum_val A * self.gene_length for xi in individual: sum_val xi**2 - A * math.cos(2 * math.pi * xi) # Rastrigin函数值越小越好我们取负值这样“适应度”越大代表解越好 fitness -sum_val fitness_values.append(fitness) return fitness_values # 选择算子可以复用父类的轮盘赌因为它只依赖适应度值。 # 但交叉和变异算子需要为实数编码重新设计。 def crossover(self, parents): 模拟二进制交叉Simulated Binary Crossover, SBX这是实数编码GA常用的交叉算子。 offspring [] eta_c 20 # 分布指数控制子代与父代的相似程度值越大子代越接近父代 for i in range(0, self.pop_size, 2): p1 parents[i] p2 parents[i1] if (i1) self.pop_size else parents[i] c1, c2 [], [] if random.random() self.crossover_rate: for j in range(self.gene_length): u random.random() if u 0.5: beta (2*u) ** (1/(eta_c1)) else: beta (1/(2*(1-u))) ** (1/(eta_c1)) c1_j 0.5 * ((1beta)*p1[j] (1-beta)*p2[j]) c2_j 0.5 * ((1-beta)*p1[j] (1beta)*p2[j]) # 边界处理 c1_j max(self.bounds[j][0], min(self.bounds[j][1], c1_j)) c2_j max(self.bounds[j][0], min(self.bounds[j][1], c2_j)) c1.append(c1_j) c2.append(c2_j) else: c1, c2 p1[:], p2[:] offspring.append(c1) offspring.append(c2) return offspring[:self.pop_size] def mutate(self, offspring): 多项式变异Polynomial Mutation。 eta_m 20 # 变异分布指数 for individual in offspring: for j in range(self.gene_length): if random.random() self.mutation_rate: y individual[j] y_low, y_up self.bounds[j] delta1 (y - y_low) / (y_up - y_low) delta2 (y_up - y) / (y_up - y_low) rand random.random() mut_pow 1.0 / (eta_m 1.0) if rand 0.5: xy 1.0 - delta1 val 2.0 * rand (1.0 - 2.0 * rand) * (xy ** (eta_m 1.0)) delta_q val ** mut_pow - 1.0 else: xy 1.0 - delta2 val 2.0 * (1.0 - rand) 2.0 * (rand - 0.5) * (xy ** (eta_m 1.0)) delta_q 1.0 - val ** mut_pow y y delta_q * (y_up - y_low) y max(y_low, min(y_up, y)) # 边界钳制 individual[j] y return offspring现在我们可以用这个新的RealCodedGA类来求解Rastrigin函数在二维空间上的最小值了。已知该函数的全局最小值在 (0,0) 处函数值为0。import math if __name__ __main__: # 参数设置二维Rastrigin函数 DIM 2 BOUNDS [(-5.12, 5.12) for _ in range(DIM)] ga RealCodedGA(pop_size50, gene_lengthDIM, crossover_rate0.9, mutation_rate0.1, max_generations200, boundsBOUNDS) final_pop, history ga.run() final_fitness ga.evaluate_population() best_idx final_fitness.index(max(final_fitness)) best_solution final_pop[best_idx] best_value -max(final_fitness) # 将适应度转换回原函数值 print(f找到的最佳解: {best_solution}) print(f对应的Rastrigin函数值: {best_value}) # 可视化进化过程 plt.plot(history, r-, labelBest Fitness (Negative Rastrigin)) plt.xlabel(Generation) plt.ylabel(Fitness (Higher is better)) plt.title(Real-Coded GA on Rastrigin Function) plt.legend() plt.grid(True) plt.show()运行这个代码你会看到算法如何逐步逼近全局最优解。通过调整参数如增大种群规模到100或降低变异率到0.05观察收敛速度和精度的变化你能更深刻地体会每个参数的作用。从简单的二进制求和到复杂的连续函数优化我们实现了一个功能完整的遗传算法框架。这个框架具有很强的可扩展性。你可以尝试更换选择算子实现锦标赛选择或排序选择。尝试不同的交叉/变异方式如均匀交叉、高斯变异。解决你自己的问题只需重新定义initialize_population,evaluate_population以及可能的编/解码函数。添加精英保留策略在每一代中直接保留适应度最高的几个个体到下一代防止优秀基因丢失。遗传算法不是一个“即插即用”的魔术盒而是一个需要根据问题精心设计和调优的探索工具。理解其每个组件背后的思想比记住代码更重要。希望这次从零开始的构建过程能为你打开一扇门让你在遇到那些传统优化方法束手无策的复杂问题时多一种强大而有趣的思路。