遗传算法原理与代码实现全解析

2025年12月17日 互联网

遗传算法原理与代码实现全解析

遗传算法作为模拟自然进化过程的优化技术，在组合优化、机器学习参数调优等领域展现出独特优势。本文将从算法原理、核心操作、代码实现三个维度展开详细解析，为开发者提供可落地的技术指南。

一、遗传算法核心原理

1.1 算法框架

遗传算法遵循”适者生存”原则，通过迭代进化寻找最优解。其标准流程包含五个核心环节：

  • 初始化种群：随机生成包含N个个体的初始解集
  • 适应度评估：计算每个个体的目标函数值
  • 选择操作：基于适应度选择优质个体
  • 遗传操作：执行交叉和变异产生新个体
  • 终止判断：达到最大迭代次数或收敛条件时停止

1.2 数学基础

算法本质是概率搜索过程，其收敛性由马尔可夫链理论保证。种群多样性维持与选择压力的平衡是关键设计要点，过早收敛会导致陷入局部最优。

二、核心操作实现详解

2.1 编码方案

二进制编码是最基础的方式，适用于离散优化问题。例如求解0-1背包问题时，每个个体可表示为长度等于物品数量的二进制串：

  1. def initialize_population(pop_size, chrom_length):
  2.     """初始化二进制编码种群"""
  3.     return np.random.randint(0, 2, size=(pop_size, chrom_length))

实数编码更适合连续优化问题，每个基因位直接表示决策变量值。对于函数极值问题，编码长度等于变量维度：

  1. def real_init(pop_size, dim, bounds):
  2.     """实数编码初始化"""
  3.     pop = np.zeros((pop_size, dim))
  4.     for i in range(dim):
  5.         pop[:,i] = np.random.uniform(bounds[i][0], bounds[i][1], pop_size)
  6.     return pop

2.2 选择操作实现

轮盘赌选择是经典方法，实现时需注意适应度值的归一化处理：

  1. def roulette_selection(population, fitness):
  2.     """轮盘赌选择"""
  3.     fitness = fitness - np.min(fitness) + 1e-6  # 避免负值
  4.     prob = fitness / np.sum(fitness)
  5.     indices = np.random.choice(len(population), size=len(population), p=prob)
  6.     return population[indices]

锦标赛选择通过随机竞争提升选择效率，参数k控制选择压力：

  1. def tournament_selection(population, fitness, k=3):
  2.     """锦标赛选择"""
  3.     selected = []
  4.     for _ in range(len(population)):
  5.         candidates = np.random.choice(len(population), k)
  6.         winner = candidates[np.argmax(fitness[candidates])]
  7.         selected.append(population[winner])
  8.     return np.array(selected)

2.3 交叉操作实现

单点交叉适用于二进制编码，交叉点随机选择：

  1. def single_point_crossover(parent1, parent2):
  2.     """单点交叉"""
  3.     point = np.random.randint(1, len(parent1))
  4.     child1 = np.concatenate([parent1[:point], parent2[point:]])
  5.     child2 = np.concatenate([parent2[:point], parent1[point:]])
  6.     return child1, child2

算术交叉处理实数编码时，通过线性组合生成后代：

  1. def arithmetic_crossover(parent1, parent2, alpha=0.5):
  2.     """算术交叉"""
  3.     child1 = alpha * parent1 + (1-alpha) * parent2
  4.     child2 = alpha * parent2 + (1-alpha) * parent1
  5.     return child1, child2

2.4 变异操作实现

位翻转变异是二进制编码的常用方式：

  1. def bit_flip_mutation(individual, mutation_rate):
  2.     """位翻转变异"""
  3.     for i in range(len(individual)):
  4.         if np.random.rand() < mutation_rate:
  5.             individual[i] = 1 - individual[i]  # 0变1，1变0
  6.     return individual

高斯变异适用于实数编码，在基因值附近进行扰动：

  1. def gaussian_mutation(individual, mutation_rate, bounds, sigma=0.1):
  2.     """高斯变异"""
  3.     for i in range(len(individual)):
  4.         if np.random.rand() < mutation_rate:
  5.             individual[i] += np.random.normal(0, sigma)
  6.             # 边界处理
  7.             individual[i] = np.clip(individual[i], bounds[i][0], bounds[i][1])
  8.     return individual

三、完整代码实现示例

以求解Rastrigin函数极小值为例，展示完整实现流程：

  1. import numpy as np
  3. def rastrigin(x):
  4.     """Rastrigin测试函数"""
  5.     return 10*len(x) + np.sum(x**2 - 10*np.cos(2*np.pi*x))
  7. def real_ga(dim, pop_size=50, max_gen=100, 
  8.             mutation_rate=0.1, lb=-5.12, ub=5.12):
  9.     """实数编码遗传算法"""
  10.     # 初始化
  11.     bounds = [(lb, ub)] * dim
  12.     population = np.zeros((pop_size, dim))
  13.     for i in range(dim):
  14.         population[:,i] = np.random.uniform(lb, ub, pop_size)
  16.     best_fitness = []
  17.     for gen in range(max_gen):
  18.         # 评估适应度
  19.         fitness = np.array([rastrigin(ind) for ind in population])
  20.         best_fitness.append(np.min(fitness))
  22.         # 选择
  23.         selected = tournament_selection(population, -fitness, k=3)
  25.         # 交叉
  26.         new_pop = []
  27.         for i in range(0, pop_size, 2):
  28.             if i+1 < pop_size:
  29.                 child1, child2 = arithmetic_crossover(
  30.                     selected[i], selected[i+1], alpha=0.7)
  31.                 new_pop.extend([child1, child2])
  33.         # 变异
  34.         mutated = []
  35.         for ind in new_pop[:pop_size]:  # 保持种群规模
  36.             mutated.append(gaussian_mutation(ind, mutation_rate, bounds))
  38.         population = np.array(mutated)
  40.         # 精英保留
  41.         best_idx = np.argmin(fitness)
  42.         if fitness[best_idx] < rastrigin(population[0]):
  43.             population[0] = population[best_idx]
  45.     return population[np.argmin([rastrigin(ind) for ind in population])]
  47. # 运行示例
  48. best_solution = real_ga(dim=2)
  49. print(f"最优解: {best_solution}, 函数值: {rastrigin(best_solution)}")

四、工程实践建议

  1. 参数调优策略：

    • 种群规模通常设为变量数的5-10倍
    • 变异率建议初始值0.1，根据收敛情况动态调整
    • 交叉概率控制在0.7-0.9之间

  2. 性能优化技巧：

    • 并行化适应度评估（使用多进程/多线程）
    • 采用精英保留策略防止优质解丢失
    • 引入自适应变异率机制

  3. 收敛判断方法：

    • 连续N代最优解变化小于阈值
    • 适应度标准差小于设定值
    • 达到最大迭代次数

  4. 混合算法改进：

    • 结合局部搜索（如爬山算法）提升精度
    • 与差分进化算法混合使用
    • 引入模拟退火思想避免早熟

五、典型应用场景

  1. 组合优化问题：TSP问题、车间调度、背包问题
  2. 机器学习调参：神经网络超参数优化、SVM参数选择
  3. 工程设计：天线阵列设计、机械结构优化
  4. 自动控制：PID参数整定、模糊控制规则优化

通过合理设计遗传算子和控制参数，该算法能有效处理复杂非线性优化问题。开发者可根据具体场景调整编码方案和操作策略，平衡探索与开发能力。

最新文章