遗传算法 (GA) 实战：Python 实现 3 种交叉算子与 2 种变异策略对比

遗传算法实战：Python实现3种交叉算子与2种变异策略对比

引言：遗传算法的工程实践价值

在解决复杂优化问题时，传统方法往往陷入局部最优或计算复杂度爆炸的困境。遗传算法(GA)作为一种受自然选择启发的全局优化技术，通过模拟生物进化机制，在机器学习、工程设计和金融建模等领域展现出独特优势。与梯度下降等确定性方法不同，GA不依赖目标函数的可微性，能够处理离散、非凸和高维搜索空间。

本文将聚焦遗传算法最核心的进化算子——交叉与变异的工程实现。我们将用Python构建完整GA框架，实现3种主流交叉算子（单点、两点、均匀）和2种经典变异策略（位翻转、高斯变异），并在Rastrigin等测试函数上进行性能对比。不同于理论讲解，本文强调可复现的代码实践和算子选择的经验法则，帮助开发者根据问题特性选择适当算子组合。

# 基础遗传算法框架结构示意 class GeneticAlgorithm: def __init__(self, population_size, chromosome_length): self.population = self.initialize_population(population_size, chromosome_length) def initialize_population(self, size, length): return np.random.randint(0, 2, size=(size, length)) def evolve(self, crossover_method, mutation_method, elitism=True): # 选择->交叉->变异的完整流程 pass

1. 种群表示与初始化策略

1.1 染色体编码方案

遗传算法的第一步是将解空间映射到遗传空间。我们采用最通用的二进制编码，每个染色体是由0和1组成的序列：

def initialize_population(pop_size, chrom_length): """初始化二进制编码种群 Args: pop_size: 种群规模 chrom_length: 染色体长度 Returns: np.array: 形状为(pop_size, chrom_length)的随机二进制矩阵 """ return np.random.randint(0, 2, size=(pop_size, chrom_length))

对于连续优化问题，需设计解码函数将二进制串映射回实数值。例如，将20位二进制编码解码到[-5.12, 5.12]区间：

def binary_to_float(chromosome, min_val=-5.12, max_val=5.12): """二进制染色体解码为实数值 Args: chromosome: 二进制编码串 min_val: 区间下限 max_val: 区间上限 Returns: float: 解码后的实数值 """ int_val = int(''.join(map(str, chromosome)), 2) ratio = int_val / (2**len(chromosome) - 1) return min_val + ratio * (max_val - min_val)

1.2 适应度函数设计

适应度函数是GA的导航系统。以Rastrigin函数为例，其全局最小值在原点处：

$$ f(\mathbf{x}) = A n + \sum_{i=1}^n \left[x_i^2 - A \cos(2\pi x_i)\right], \quad A=10 $$

Python实现需注意避免循环计算，利用NumPy向量化：

def rastrigin(x): """计算Rastrigin函数值 Args: x: 输入向量(可处理矩阵输入) Returns: float/array: 适应度值 """ A = 10 return A * x.shape[-1] + np.sum(x**2 - A * np.cos(2 * np.pi * x), axis=-1)

提示：对于最小化问题，通常将目标函数取负或倒数转换为适应度值。同时应对适应度进行缩放处理，避免早期超级个体主导选择过程。

1.3 关键参数设置经验

下表总结了不同问题规模下的典型参数设置：

实际应用中建议通过网格搜索或贝叶斯优化确定最佳参数组合。

2. 选择机制实现

2.1 轮盘赌选择

轮盘赌选择按适应度比例分配选择概率，实现简单但可能导致过早收敛：

def roulette_wheel_selection(population, fitness): """轮盘赌选择 Args: population: 当前种群 fitness: 对应适应度值 Returns: selected_indices: 被选中的个体索引 """ prob = fitness / fitness.sum() return np.random.choice(len(population), size=len(population), p=prob)

2.2 锦标赛选择

锦标赛选择通过小规模竞争降低超级个体影响，更好地保持多样性：

def tournament_selection(population, fitness, tournament_size=3): """锦标赛选择 Args: population: 当前种群 fitness: 对应适应度值 tournament_size: 每轮锦标赛参与者数量 Returns: selected_indices: 被选中的个体索引 """ selected = [] for _ in range(len(population)): candidates = np.random.choice(len(population), tournament_size) winner = candidates[np.argmax(fitness[candidates])] selected.append(winner) return np.array(selected)

2.3 精英保留策略

强制保留当代最优个体到下一代，确保算法单调收敛：

def apply_elitism(population, new_population, fitness, elite_num=1): """精英保留 Args: population: 父代种群 new_population: 子代种群 fitness: 父代适应度 elite_num: 保留精英数量 Returns: elite_population: 融入精英后的新种群 """ elite_indices = np.argpartition(fitness, -elite_num)[-elite_num:] new_population[:elite_num] = population[elite_indices] return new_population

3. 交叉算子实现与对比

3.1 单点交叉(One-point Crossover)

单点交叉随机选择一个切点交换父代基因片段：

def one_point_crossover(parent1, parent2): """单点交叉 Args: parent1: 父代个体1 parent2: 父代个体2 Returns: child1, child2: 子代个体 """ point = np.random.randint(1, len(parent1)) child1 = np.concatenate([parent1[:point], parent2[point:]]) child2 = np.concatenate([parent2[:point], parent1[point:]]) return child1, child2

特点分析：

• 计算效率高，适合低维问题
• 破坏模式较少，适合短距模式重组
• 在TSP等有序问题中可能产生非法解

3.2 两点交叉(Two-point Crossover)

两点交叉选择两个切点交换中间片段：

def two_point_crossover(parent1, parent2): """两点交叉 Args: parent1: 父代个体1 parent2: 父代个体2 Returns: child1, child2: 子代个体 """ point1, point2 = sorted(np.random.choice(len(parent1), 2, replace=False)) child1 = np.concatenate([parent1[:point1], parent2[point1:point2], parent1[point2:]]) child2 = np.concatenate([parent2[:point1], parent1[point1:point2], parent2[point2:]]) return child1, child2

对比优势：

• 保留更多父代基因组合
• 适合中等长度模式重组
• 在函数优化中通常优于单点交叉

3.3 均匀交叉(Uniform Crossover)

均匀交叉按位随机选择父本基因：

def uniform_crossover(parent1, parent2, rate=0.5): """均匀交叉 Args: parent1: 父代个体1 parent2: 父代个体2 rate: 交换概率 Returns: child1, child2: 子代个体 """ mask = np.random.random(len(parent1)) < rate child1 = np.where(mask, parent1, parent2) child2 = np.where(mask, parent2, parent1) return child1, child2

适用场景：

• 高维优化问题
• 基因位间关联性弱的场景
• 需要最大程度保持多样性的情况

3.4 交叉算子性能对比实验

我们在Rastrigin函数上对比三种交叉算子的收敛速度：

# 测试框架示例 def test_crossover(crossover_func, n_runs=10): results = [] for _ in range(n_runs): ga = GeneticAlgorithm(crossover_method=crossover_func) best_fitness = ga.run() results.append(best_fitness) return np.mean(results), np.std(results) # 执行测试 one_point_mean, one_point_std = test_crossover(one_point_crossover) two_point_mean, two_point_std = test_crossover(two_point_crossover) uniform_mean, uniform_std = test_crossover(uniform_crossover)

典型结果对比（迭代100代后）：

实验表明均匀交叉在高维非线性问题上表现最优，但两点交叉在解空间结构明确时可能是更稳妥的选择。

4. 变异策略实现与分析

4.1 位翻转变异(Bit-flip Mutation)

最基础的变异操作，以概率pm翻转每个基因位：

def bit_flip_mutation(chromosome, pm=0.01): """位翻转变异 Args: chromosome: 输入染色体 pm: 变异概率 Returns: mutated: 变异后染色体 """ mask = np.random.random(len(chromosome)) < pm return np.where(mask, 1 - chromosome, chromosome)

参数设置经验：

• 二进制编码：pm通常取1/chromosome_length
• 初期可采用较高变异率，后期逐渐降低
• 与选择压力保持平衡，避免随机游走

4.2 高斯变异(Gaussian Mutation)

适用于实数编码，添加高斯随机扰动：

def gaussian_mutation(chromosome, pm=0.1, scale=0.1): """高斯变异 Args: chromosome: 实数编码染色体 pm: 变异概率 scale: 变异强度 Returns: mutated: 变异后染色体 """ mask = np.random.random(len(chromosome)) < pm noise = np.random.normal(0, scale, len(chromosome)) return chromosome + mask * noise

调优技巧：

• 自适应变异：根据种群多样性动态调整scale
• 相关性变异：对相关基因使用协方差矩阵
• 边界处理：对越界值进行反射或裁剪

4.3 变异策略对比实验

设计对比实验评估两种变异策略：

# 变异策略测试框架 def test_mutation(mutation_func, init_scale=0.2, n_runs=10): results = [] for _ in range(n_runs): ga = GeneticAlgorithm(mutation_method=mutation_func, mutation_params={'scale': init_scale}) history = ga.run(return_history=True) results.append(history['best_fitness']) return np.array(results) # 执行测试 bit_flip_results = test_mutation(bit_flip_mutation) gaussian_results = test_mutation(gaussian_mutation)

实验结果分析要点：

1. 初期多样性：高斯变异能更快跳出局部最优
2. 后期精度：位翻转在二进制编码中更稳定
3. 参数敏感性：高斯变异对scale参数更敏感

5. 完整算法实现与调优

5.1 算法主流程实现

整合各组件构建完整GA：

class GeneticAlgorithm: def __init__(self, obj_func, pop_size=100, chrom_length=20, crossover_method=two_point_crossover, mutation_method=gaussian_mutation, selection_method=tournament_selection, elitism=True): # 参数初始化 self.obj_func = obj_func self.pop_size = pop_size self.chrom_length = chrom_length self.population = self._initialize_population() self.crossover = crossover_method self.mutation = mutation_method self.selection = selection_method self.elitism = elitism def _initialize_population(self): return np.random.randint(0, 2, size=(self.pop_size, self.chrom_length)) def _evaluate(self): # 解码并计算适应度 decoded = np.array([binary_to_float(ind) for ind in self.population]) return self.obj_func(decoded) def evolve(self, generations=100): best_fitness = [] for gen in range(generations): fitness = self._evaluate() best_fitness.append(np.min(fitness)) # 选择 selected = self.selection(self.population, -fitness) # 最小化问题取负 # 交叉 offspring = [] for i in range(0, len(selected), 2): if i+1 >= len(selected): offspring.append(selected[i]) break child1, child2 = self.crossover(selected[i], selected[i+1]) offspring.extend([child1, child2]) # 变异 offspring = [self.mutation(ind) for ind in offspring] # 精英保留 if self.elitism: best_idx = np.argmin(fitness) offspring[0] = self.population[best_idx] self.population = np.array(offspring) return best_fitness

5.2 自适应参数调整

实现变异率自适应机制：

def adaptive_mutation(chromosome, pm_base=0.1, gen=None, max_gen=100): """自适应变异率 Args: chromosome: 输入染色体 pm_base: 基础变异率 gen: 当前代数 max_gen: 最大代数 Returns: mutated: 变异后染色体 """ if gen is not None: pm = pm_base * (1 - gen/max_gen) # 线性衰减 else: pm = pm_base return bit_flip_mutation(chromosome, pm)

5.3 并行化加速

利用multiprocessing实现适应度并行计算：

from multiprocessing import Pool def parallel_evaluate(population, obj_func, n_workers=4): """并行适应度评估 Args: population: 当前种群 obj_func: 目标函数 n_workers: 进程数 Returns: fitness: 适应度数组 """ with Pool(n_workers) as p: decoded = [binary_to_float(ind) for ind in population] return np.array(p.map(obj_func, decoded))

6. 应用案例：Rastrigin函数优化

6.1 实验设置

• 维度：10维
• 种群规模：200
• 最大代数：500
• 交叉概率：0.9
• 变异概率：0.01
• 精英数量：5

6.2 结果可视化

import matplotlib.pyplot as plt def plot_convergence(history): plt.figure(figsize=(10, 6)) plt.plot(history['best'], label='Best Fitness') plt.plot(history['avg'], label='Average Fitness') plt.xlabel('Generation') plt.ylabel('Fitness Value') plt.title('Convergence History') plt.legend() plt.grid(True) plt.show() # 运行算法并绘图 ga = GeneticAlgorithm(rastrigin, pop_size=200, chrom_length=50) history = ga.run(generations=500, return_history=True) plot_convergence(history)

6.3 性能指标分析

7. 工程实践建议

1. 算子选择经验法则：

   • 低维有序问题：两点交叉 + 位翻转
   • 高维非线性问题：均匀交叉 + 高斯变异
   • 动态环境问题：增加变异率 + 保持多样性

2. 参数调优流程：

   • 先确定大致参数范围（如pc∈[0.7,0.9]）
   • 固定其他参数，网格搜索关键参数
   • 最后微调组合验证

3. 常见问题排查：

   • 早熟收敛：增加变异率、采用锦标赛选择、引入移民策略
   • 停滞不前：调整选择压力、尝试不同交叉算子
   • 计算耗时：采用并行评估、减少种群规模、使用更高效的编码

4. 进阶优化方向：

   • 混合算法：结合局部搜索（如memetic算法）
   • 多目标优化：NSGA-II等Pareto前沿方法
   • 分布式实现：岛屿模型等并行遗传算法

# 混合遗传算法示例：加入局部搜索 def hybrid_ga(obj_func, pop_size=100, local_search_step=5): ga = GeneticAlgorithm(obj_func, pop_size) best_history = [] for gen in range(100): ga.evolve(1) if gen % local_search_step == 0: # 对最优个体进行局部搜索 best_idx = np.argmin(ga._evaluate()) ga.population[best_idx] = local_search(ga.population[best_idx]) best_history.append(np.min(ga._evaluate())) return best_history

遗传算法的魅力在于其灵活性和通用性。通过本文介绍的交叉与变异算子组合，开发者可以构建适应不同问题特性的进化优化方案。实际应用中，建议从简单配置开始，逐步引入复杂机制，并通过系统实验验证改进效果。