进化策略（ES）

名称

进化策略（Evolution Strategies, ES），也称演化策略。

分类

查看分类思维导图

进化策略是一类优化算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个重要分支。它与遗传算法（Genetic Algorithms）、进化规划（Evolutionary Programming）以及遗传编程（Genetic Programming）等其他进化算法密切相关。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
      • 进化规划
      • 进化策略
      • 遗传编程

策略

进化策略受到生物进化基本原理的启发，尤其借鉴了自然选择过程以及“适者生存”的思想。该算法维护一个候选解种群，其中每个候选解均由一个实值参数向量表示。这些候选解通常被称为个体（individuals）或子代（offspring）。

算法通过一系列遗传操作对候选解种群进行迭代更新，主要包括变异（mutation）和重组（recombination，也称交叉 crossover）。其中，变异用于向个体中引入随机扰动，而重组则通过组合多个父代的遗传信息来生成新的子代。

每个个体的适应度由目标函数进行评估，目标函数用于衡量候选解在给定优化问题中的质量或性能。算法的目标是在搜索过程中找到具有最高适应度值的个体，从而获得该问题的最优解或近似最优解。

选择机制用于决定当前种群中哪些个体能够存活并对下一代产生贡献。该过程通常偏向于选择适应度较高的个体，使其遗传信息能够传递到后续代中。

算法持续重复应用遗传操作、适应度评估与选择过程，直至满足某一终止条件。该终止条件可以是预设的最大代数、达到满意的适应度水平，或满足某种收敛阈值。

过程

1. 初始化种群：
   1. 确定种群规模 $\mu$ 和子代数量 $\lambda$。
   2. 创建一个由 $\mu$ 个个体组成的初始种群，每个个体由一个实值参数向量表示。
   3. 使用目标函数评估初始种群中每个个体的适应度。
2. 当未满足终止条件时，重复执行以下步骤：
   1. 重组：
      1. 根据适应度从当前种群中选择 $\rho$ 个父代个体。
      2. 对选出的父代应用重组算子（如中间重组、离散重组），生成 $\lambda$ 个新的子代。
   2. 变异：
      1. 对重组步骤生成的每个子代施加变异操作（如高斯变异），以引入随机变化。
      2. 根据所采用的变异策略（如 $1/5$ 成功法则、自适应机制）调整变异强度（步长）。
   3. 适应度评估：
      1. 使用目标函数评估每个子代的适应度。
   4. 选择：
      1. 根据适应度从父代与子代组成的联合种群中选择 $\mu$ 个个体。
      2. 被选中的个体构成下一代种群。
3. 返回优化过程中找到的最优个体作为问题的解。

数据结构与参数

• 种群（Population）：由个体构成的数组或列表，其中每个个体由一个实值参数向量表示。
• 适应度值（Fitness values）：用于存储种群中各个个体适应度值的数组或列表。
• 种群规模（$\mu$）：种群中个体的数量。
• 子代规模（$\lambda$）：每一代生成的子代数量。
• 重组规模（$\rho$）：参与重组的父代个体数量。
• 变异强度（步长）：控制施加于子代的变异幅度的参数。
• 终止条件：用于决定何时停止优化过程的条件（如最大代数、适应度阈值等）。

注意事项

优点

• 适用于以实值参数表示的连续优化问题。
• 能够较好地平衡搜索空间中的全局探索与局部开发。
• 对噪声具有一定鲁棒性，并能够处理不可微、非凸的目标函数。
• 具有较好的并行化潜力，便于高效利用计算资源。

缺点

• 可能需要大量适应度评估，从而带来较高的计算开销。
• 变异强度及其他策略参数的选取会显著影响算法性能。
• 若种群多样性无法得到有效维持，算法可能会过早收敛到次优解。

启发式建议

种群规模设置

• 较大的种群规模 $\mu$ 有助于增强对搜索空间的探索能力，但也可能增加计算成本。
• 子代规模 $\lambda$ 通常设置为大于种群规模 $\mu$，以促进多样性和搜索探索。
• 一个常见的设置是 $\lambda = 7\mu$，但该参数也可根据具体问题特性进行调整。

重组

• 中间重组是一种常见选择，其中子代参数由父代参数的加权平均计算得到。
• 也可以采用离散重组，即子代的每个参数随机选自某一个父代。
• 对于中间重组，重组规模 $\rho$ 常设为 2；而对于离散重组，则通常采用更大的取值。

变异

• 高斯变异是常用方法，即向子代参数加入服从高斯分布的随机扰动值。
• 变异强度（步长）应在优化过程中进行自适应调整，以平衡探索与开发。
• $1/5$ 成功法则是一种简单的自适应策略，其根据前几代变异成功率对变异强度进行调整。
• 自适应策略（如对数正态自适应）允许变异强度与候选解一起协同进化。

终止准则

• 可以设置最大代数或最大函数评估次数，以限制所消耗的计算资源。
• 可以设定适应度阈值，当某个个体的适应度达到该阈值以上时终止算法。
• 也可以采用收敛性判据，例如最优个体与最差个体之间的适应度差异，或适应度改进速率，以检测停滞现象并终止算法。