遗传算法原理与Python代码实现详解

2025年12月16日 互联网

遗传算法原理与Python代码实现详解

遗传算法（Genetic Algorithm, GA）作为进化计算的典型代表，通过模拟自然选择与遗传机制解决复杂优化问题。其核心优势在于无需梯度信息、可处理非凸非线性问题，且具备全局搜索能力。本文将从算法原理、核心步骤、代码实现三个维度展开，结合Python案例解析其工程实践。

一、遗传算法核心原理

1.1 算法框架

遗传算法遵循”生存竞争-遗传变异-迭代优化”的循环逻辑，包含五大核心组件：

  • 编码方案：将问题解映射为染色体（如二进制串、实数向量）
  • 适应度函数：量化个体优劣的评估标准（如目标函数值）
  • 选择算子：决定哪些个体参与繁殖（轮盘赌、锦标赛等）
  • 交叉算子：模拟基因重组生成新个体（单点交叉、均匀交叉）
  • 变异算子：引入随机扰动防止早熟收敛（位翻转、高斯变异）

1.2 数学本质

算法通过马尔可夫链描述种群状态转移，其收敛性由以下条件保证：

  • 适应度函数非负且存在最大值
  • 选择概率与适应度正相关
  • 变异概率保持种群多样性

二、Python代码实现详解

2.1 基础框架搭建

  1. import numpy as np
  2. import random
  4. class GeneticAlgorithm:
  5.     def __init__(self, fitness_func, pop_size=50, 
  6.                  crossover_rate=0.8, mutation_rate=0.01, 
  7.                  max_generations=100):
  8.         self.fitness_func = fitness_func
  9.         self.pop_size = pop_size
  10.         self.crossover_rate = crossover_rate
  11.         self.mutation_rate = mutation_rate
  12.         self.max_generations = max_generations
  13.         self.population = []
  15.     def initialize_population(self, chrom_length):
  16.         """生成初始种群（二进制编码示例）"""
  17.         self.population = [
  18.             ''.join(random.choice('01') for _ in range(chrom_length))
  19.             for _ in range(self.pop_size)
  20.         ]

2.2 核心算子实现

选择算子（锦标赛选择）

  1. def tournament_selection(self, k=3):
  2.     """从种群中选择适应度较高的个体"""
  3.     selected = []
  4.     for _ in range(self.pop_size):
  5.         candidates = random.sample(self.population, k)
  6.         fitness = [self.fitness_func(ind) for ind in candidates]
  7.         selected.append(candidates[np.argmax(fitness)])
  8.     return selected

交叉算子（单点交叉）

  1. def crossover(self, parents):
  2.     """执行基因重组"""
  3.     offspring = []
  4.     for i in range(0, len(parents), 2):
  5.         if i+1 >= len(parents) or random.random() > self.crossover_rate:
  6.             offspring.extend(parents[i:i+2])
  7.             continue
  9.         parent1, parent2 = parents[i], parents[i+1]
  10.         crossover_point = random.randint(1, len(parent1)-1)
  11.         child1 = parent1[:crossover_point] + parent2[crossover_point:]
  12.         child2 = parent2[:crossover_point] + parent1[crossover_point:]
  13.         offspring.extend([child1, child2])
  14.     return offspring

变异算子（位翻转）

  1. def mutate(self, offspring):
  2.     """引入随机变异"""
  3.     mutated = []
  4.     for individual in offspring:
  5.         if random.random() < self.mutation_rate:
  6.             pos = random.randint(0, len(individual)-1)
  7.             individual = individual[:pos] + ('1' if individual[pos] == '0' else '0') + individual[pos+1:]
  8.         mutated.append(individual)
  9.     return mutated

2.3 完整运行流程

  1. def run(self, chrom_length):
  2.     """执行遗传算法主循环"""
  3.     self.initialize_population(chrom_length)
  5.     for generation in range(self.max_generations):
  6.         # 评估适应度
  7.         fitness_values = [self.fitness_func(ind) for ind in self.population]
  8.         best_fitness = max(fitness_values)
  9.         avg_fitness = np.mean(fitness_values)
  11.         # 选择、交叉、变异
  12.         selected = self.tournament_selection()
  13.         offspring = self.crossover(selected)
  14.         new_population = self.mutate(offspring)
  16.         self.population = new_population
  18.         # 输出统计信息（实际项目可改为日志记录）
  19.         if generation % 10 == 0:
  20.             print(f"Gen {generation}: Best={best_fitness:.2f}, Avg={avg_fitness:.2f}")

三、工程实践建议

3.1 参数调优策略

  • 种群规模：复杂问题建议50-200，简单问题20-50足够
  • 交叉概率：通常设置0.7-0.95，高概率加速收敛
  • 变异概率：建议0.001-0.1，低概率维持种群多样性
  • 停止条件：可结合最大代数、适应度阈值、收敛判定

3.2 性能优化技巧

  1. 并行化评估：使用多进程/多线程加速适应度计算
    ```python
    from multiprocessing import Pool

def parallel_evaluate(self, population):
with Pool() as pool:
return pool.map(self.fitness_func, population)

  2. 2. **精英保留策略**：确保最优个体直接进入下一代
  3. ```python
  4. def evolve(self):
  5.     # 评估当前种群
  6.     fitness = [self.fitness_func(ind) for ind in self.population]
  7.     best_idx = np.argmax(fitness)
  9.     # 常规进化流程...
  10.     new_population = self.mutate(offspring)
  12.     # 替换最差个体
  13.     worst_idx = np.argmin([self.fitness_func(ind) for ind in new_population])
  14.     new_population[worst_idx] = self.population[best_idx]
  16.     self.population = new_population
  1. 自适应参数：动态调整交叉/变异概率 
    1. def adaptive_mutation(self, generation):
    2.  # 随着代数增加降低变异率
    3.  base_rate = 0.01
    4.  decay_factor = 0.995
    5.  return base_rate * (decay_factor ** generation)

3.3 典型应用场景

  • 组合优化：旅行商问题、背包问题
  • 机器学习：神经网络架构搜索、超参数优化
  • 工程设计：天线布局、管道网络优化
  • 调度问题：生产排程、任务分配

四、完整案例演示

以求解函数f(x)=-x²+5x在[0,31]区间的最大值为例：

  1. def fitness_function(individual):
  2.     """二进制编码转十进制并计算适应度"""
  3.     x = int(individual, 2)
  4.     return -x**2 + 5*x  # 目标函数
  6. # 初始化算法
  7. ga = GeneticAlgorithm(fitness_func=fitness_function, 
  8.                      pop_size=30, 
  9.                      max_generations=50)
  11. # 染色体长度5位（2^5=32覆盖[0,31]区间）
  12. ga.run(chrom_length=5)
  14. # 输出最终结果
  15. final_fitness = [fitness_function(ind) for ind in ga.population]
  16. best_solution = ga.population[np.argmax(final_fitness)]
  17. print(f"\nBest Solution: {best_solution} (x={int(best_solution,2)}, fitness={max(final_fitness):.2f})")

五、注意事项与进阶方向

  1. 编码方案选择：

    • 二进制编码：简单但存在汉明悬崖问题
    • 实数编码：适合连续优化问题
    • 排列编码：适用于TSP等顺序问题

  2. 约束处理：

    • 惩罚函数法：将约束转化为适应度惩罚
    • 修复算子：将非法解修正为可行解

  3. 混合算法：

    • 结合局部搜索（如爬山算法）提升精度
    • 与模拟退火、粒子群等算法融合

  4. 可视化分析：

    • 适应度变化曲线
    • 种群多样性指标
    • 收敛速度分析

遗传算法作为启发式搜索的经典方法，其实现关键在于平衡探索与开发能力。通过合理设置参数、优化算子设计、结合问题特性定制编码方案，可显著提升算法在复杂优化问题中的表现。实际工程中，建议从简单版本开始验证，逐步迭代完善实现。

最新文章