进化算法常见算子

1. 前言

本文主要介绍进化算法各阶段常用的算子，并通过具体示例帮助理解每种算子的工作原理和适用场景。

2. 进化算法的结构及其算子

2.1. 进化算法的结构

进化算法可大致分为以下几个部分：

• 表示：如何使用基因或染色体结构去表示一个解（如二进制串、实数向量、排列序列等）
• 种群：基于种群的算法，维护一组候选解
• 适应度函数：衡量解的质量，一般来讲，适应度越高越好
• 初始化：随机或者基于先验知识生成初始种群
• 父母选择机制：挑选适应性较好的个体用于繁衍后代
• 变异与交叉算子：
  • 交叉重组：组合两个或多个父母的基因产生子代
  • 变异：对个体的基因进行微调，引入新的遗传信息
• 幸存者选择机制：从父母和子代中选择合适的个体组成新一代种群
• 终止条件：循环上述过程，直到达到目标解或满足预设的终止条件（如最大代数、计算时间、适应度阈值）

2.2. 进化算法算子

2.2.1 算子综览

• 交叉重组：K点交叉、均匀交叉、算术交叉、模拟二进制交叉（SBX）等
• 变异：位翻转、高斯变异、多项式变异、交换变异等
• 选择：轮盘赌选择、锦标赛选择、截断选择、精英保留等
• 代际更新策略：完全替换、精英保留、稳态替换、父子混合选择等
• 特殊算子：多父母重组、反转变异、部分映射交叉（PMX）、顺序交叉（OX）等

2.2.2. 探索（Exploration）和利用（Exploitation）

• 探索（Exploration）：全局搜索，探索整个搜索空间以发现新的有前景区域。主要通过变异算子和较大的交叉步长实现。
• 利用（Exploitation）：局部搜索，在已知的良好区域进行精细搜索以逼近最优解。主要通过选择压力和局部交叉实现。

两者需要平衡：过度探索会导致收敛缓慢，过度利用则容易陷入局部最优。

2.2.3. 交叉重组算子

2.2.3.1. 离散编码的重组

适用于二进制编码、符号编码、排列编码等。

1. 单点交叉

   • 操作：随机选择一个交叉点，将两个父母在该点之后的部分交换。
   • 示例：

     父母1: 101|0011 → 子代1: 101|1100
     父母2: 010|1100 → 子代2: 010|0011

2. k点交叉

   • 操作：随机选择k个交叉点，将染色体分成k+1段，间隔交换这些段。
   • 示例（2点交叉）：

     父母1: 10|100|11 → 子代1: 10|011|11
     父母2: 01|011|00 → 子代2: 01|100|00

3. 均匀交叉

   • 操作：对于每个基因位，以概率p（通常p=0.5）从父母1取值，否则从父母2取值。
   • 示例（p=0.5）：

     父母1: 1 0 1 0 0 1 1
     父母2: 0 1 0 1 1 0 0
     掩码:   1 0 1 0 1 1 0  (1表示取父1，0表示取父2)
     子代:   1 1 1 1 0 1 0

2.2.3.2. 连续编码的重组

适用于实数参数优化问题。

1. 算术交叉

   • 操作：对父母向量进行加权平均。
   • 公式：
     设 $x_1$ 和 $x_2$ 为两个父母，$\alpha \in [0,1]$ 为权重：
     • 子代1：$x’ = \alpha x_1 + (1-\alpha) x_2$
     • 子代2：$x’’ = \alpha x_2 + (1-\alpha) x_1$
   • 示例（$\alpha=0.3$）：

     父母1: [2.0, 5.0]
     父母2: [8.0, 3.0]
     子代1: [0.3×2.0+0.7×8.0=6.2, 0.3×5.0+0.7×3.0=3.6]
     子代2: [0.3×8.0+0.7×2.0=3.8, 0.3×3.0+0.7×5.0=4.4]

2. 模拟二进制交叉（SBX）

   • 特点：模拟二进制编码的单点交叉特性，使子代分布在父母周围，分布指数可调。
   • 公式（简化）：
     生成随机数 $u \in [0,1]$，根据分布因子 $\eta$ 计算扩展因子 $\beta$，然后：
     $x’_1 = 0.5[(1+\beta)x_1 + (1-\beta)x_2]$
     $x’_2 = 0.5[(1-\beta)x_1 + (1+\beta)x_2]$

3. 启发式交叉

   • 操作：假设 $x_2$ 优于 $x_1$，则沿 $x_2$ 指向 $x_2 - x_1$ 的方向外推。
   • 公式：$x’ = x_2 + \alpha(x_2 - x_1)$，$\alpha \in [0,1]$

4. 单纯形交叉

   • 操作：选择一组父母（>2），找出最优 $x_b$ 和最差 $x_w$，计算除最差点外其他点的重心 $x_c$，用 $x_c$ 替换 $x_w$。

2.2.4. 变异算子

2.2.4.1. 离散编码的变异

1. 位翻转变异

   • 单点翻转：随机选择一个位，将0变1或1变0。
   • 示例：

     原个体: 1011001
     变异后: 1010001 (第4位翻转)

   • 多位翻转：按概率 $p_m$ 对每一位独立决定是否翻转，通常 $p_m = 1/d$（d为染色体长度）。

2. 交换变异

   • 操作：随机选择两个位置，交换其值。
   • 示例（适用于排列编码，如TSP）：

     原路径: A-B-C-D-E-F
     变异后: A-E-C-D-B-F (交换B和E)

3. 反转变异

   • 操作：随机选择一段子序列，将其顺序反转。
   • 示例：

     原路径: A-B-C-D-E-F-G
     反转段: C-D-E → E-D-C
     变异后: A-B-E-D-C-F-G

2.2.4.2. 连续编码的变异

1. 均匀变异

   • 操作：以概率 $p_m$ 将某维度的值替换为定义域内的随机值。
   • 公式：$x_i’ = U(L_i, U_i)$
   • 示例（定义域[0,10]）：

     原个体: [3.2, 5.7, 8.1]
     变异后: [3.2, 2.3, 8.1] (第2维随机变为2.3)

   • 注意：可能破坏优良解，通常用于早期探索。

2. 高斯变异

   • 操作：在原值基础上添加服从高斯分布的随机扰动。
   • 公式：$x_i’ = x_i + N(0, \sigma)$
   • 示例（$\sigma=0.5$）：

     原个体: [3.2, 5.7, 8.1]
     扰动:   [+0.3, -0.1, +0.4]
     变异后: [3.5, 5.6, 8.5]

   • 特点：小步长局部搜索，步长可自适应调整。

3. 多项式变异

   • 特点：模拟二进制变异，分布指数可调，能在边界附近产生更多变异。

2.2.5. 选择机制

选择压力（Selection Pressure） 是驱动种群向更优区域进化的核心动力。选择压力过大易早熟，过小则收敛缓慢。

2.2.5.1. 父辈选择机制

1. 轮盘赌选择（适应度比例选择）

   • 操作：个体被选中的概率与其适应度成正比。
   • 示例：设种群有3个个体，适应度为[5, 3, 2]，总适应度=10，则选中概率分别为[0.5, 0.3, 0.2]。
   • 问题：适应度不能为负；早期超级个体易主导种群；后期个体间适应度相近时选择压力消失。

2. 锦标赛选择

   • 操作：随机抽取k个个体，从中选出最优者。
   • 示例（k=3）：随机抽取3个个体，比较适应度，胜者入选。
   • 特点：无需全局适应度归一化，选择压力可通过锦标赛规模k调节（k越大压力越大）。

3. 排序选择

   • 操作：按适应度排序，根据排序位置分配选择概率。
   • 线性排序：设最优个体排序值为N，最差为1，则第i个体的选择概率为 $\frac{2s}{N(N+1)}(N-i+1)$，s为平均选择次数。

2.2.5.2. 幸存者选择机制

1. 精英保留策略

   • 操作：将当前种群中最优的几个个体直接复制到下一代，不参与交叉变异。
   • 作用：保证算法单调不退化，防止最优解丢失。

2. $(\mu+\lambda)$ 选择

   • 操作：从 $\mu$ 个父代和 $\lambda$ 个子代的并集中选出 $\mu$ 个最优个体。
   • 特点：保留父代中的优秀个体，收敛快，但可能早熟。

3. $(\mu,\lambda)$ 选择

   • 操作：只从 $\lambda$ 个子代中选出 $\mu$ 个最优个体（通常 $\lambda > \mu$），父代全部淘汰。
   • 特点：允许暂时变差，有助于跳出局部最优。

4. 基于年龄的选择

   • 操作：每个个体允许存活固定代数，到期后无论适应度如何都被淘汰。
   • 作用：保持种群活力，防止某些个体长期主导。

3. 算子选择的考量与建议

选择哪些算子以及如何设置参数，取决于问题的性质和优化目标：

3.1 问题特性与算子匹配

问题类型	推荐编码	常用交叉算子	常用变异算子
组合优化（如TSP）	排列编码	PMX, OX, 循环交叉	交换变异, 反转变异
函数优化（连续）	实数向量	SBX, 算术交叉	高斯变异, 多项式变异
特征选择	二进制编码	单点/均匀交叉	位翻转变异
调度问题	排列/实数	顺序交叉, 启发式交叉	插入变异, 扰动变异

3.2 参数设置建议

• 交叉概率 $p_c$：通常设为0.7-0.95。过高会破坏优良模式，过低则搜索效率低。
• 变异概率 $p_m$：二进制编码常取 $1/d$；连续编码常取0.01-0.1。自适应变异是更高级的策略。
• 种群大小：一般取20-100，复杂问题可更大。过小易早熟，过大会降低收敛速度。
• 选择压力调节：
  • 锦标赛规模：k=2-7，问题越复杂宜用小规模。
  • 精英数量：1-2个通常足够，过多会降低多样性。

3.3 常见组合模式

1. 遗传算法（GA）经典组合：锦标赛选择 + 单点/均匀交叉 + 位翻转变异 + 精英保留
2. 进化策略（ES）典型配置：$(\mu+\lambda)$ 或 $(\mu,\lambda)$ 选择 + 算术交叉/无交叉 + 自适应高斯变异
3. 差分进化（DE）：DE算子（基于向量差分的变异） + 二项式交叉 + 贪婪选择

4. 总结

进化算法的算子种类繁多，每种算子都有其适用场景和特性：

• 交叉算子负责从现有优良解中组合新解，主要贡献于利用能力。
• 变异算子负责引入新的遗传信息，主要贡献于探索能力。
• 选择机制调控进化方向，平衡探索与利用。

总的来说，进化算法的算子各种各样，但需要针对具体情况去进行选择。不适合具体情境的算子不但会对优化过程毫无作用，甚至可能破坏优秀解带来坏处。

• 本文作者： Kylin
• 本文链接： https://kylinnnnn.github.io/2026/02/15/进化算法常见算子/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！