(μ+λ)-进化策略（(μ+λ)-ES）

名称

$(\mu+\lambda)$-进化策略（$(\mu+\lambda)$-Evolution Strategy），也可记作 (mu+lambda)-ES 或 $(\mu+\lambda)$-ES。

分类

查看分类思维导图

$(\mu+\lambda)$-进化策略是一种基于种群的随机优化算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。

• 计算智能
  • 进化计算
    • 进化算法
      • 进化策略
        • $(\mu+\lambda)$-进化策略

策略

$(\mu+\lambda)$-进化策略维持一个由 $\mu$ 个候选解构成的种群，这些候选解称为父代。在每一次迭代中，算法通过对父代施加变异操作生成 $\lambda$ 个新的候选解，这些新生成的候选解称为子代。变异算子通常通过向父代解中加入随机扰动来实现，从而使算法能够对搜索空间进行探索。扰动幅度由一组策略参数控制，这些参数通常会在优化过程中进行自适应调整，以平衡全局探索与局部开发。

在生成子代之后，$(\mu+\lambda)$-ES 从父代与子代构成的联合种群中选取表现最优的 $\mu$ 个个体，作为下一代种群。该选择机制保证了当前已发现的最优解能够被持续保留，因此属于一种精英保留策略，强调对搜索空间中潜在优良区域的进一步开发。

变异与选择过程不断迭代进行，直至满足预设的终止条件，例如达到最大迭代次数或找到满足要求的高质量解。$(\mu+\lambda)$-ES 以其处理连续优化问题的能力以及通过策略参数自适应来适应问题地形的特性而受到广泛关注。

过程

数据结构

• 种群：由 $\mu$ 个候选解构成的数组，每个候选解表示为一个实值向量。
• 策略参数：用于控制变异算子的一组参数，通常包括解向量各维度对应的变异强度（步长）。

参数

• $\mu$：种群中父代解的数量。
• $\lambda$：每次迭代生成的子代解数量。
• 终止准则：用于决定算法何时停止的条件，例如最大迭代次数或目标适应度值。

伪代码

1. 随机生成 $\mu$ 个候选解，初始化种群。
2. 为每个候选解初始化对应的策略参数。
3. 当未满足终止准则时，重复执行：
   1. 对于 $\lambda$ 个子代中的每一个，执行：
      1. 从当前种群中均匀随机选择一个父代解。
      2. 利用该父代对应的策略参数对其施加变异，生成一个新的子代。
   2. 评估每个子代解的适应度。
   3. 从父代与子代构成的联合种群中选出最优的 $\mu$ 个个体，形成新的种群。
   4. 根据被选个体的表现更新其策略参数。
4. 返回搜索过程中找到的最优解。

注意事项

优点

• 能够有效处理连续优化问题。
• 策略参数的自适应能力使算法能够较好地适应问题的地形特征。
• 精英保留选择机制保证了当前已发现的最优解不会丢失。

缺点

• 在高维搜索空间中，算法性能可能下降。
• 若无法维持种群多样性，算法可能会过早收敛。
• $\mu$ 和 $\lambda$ 的取值会显著影响算法性能，通常需要针对具体问题进行调节。

启发式建议

种群规模

• $\mu$ 与 $\lambda$ 的比例应根据具体问题特性进行设定。一个常见经验是取 $\mu \approx \lambda/7$。
• 较大的种群规模有助于增强探索能力，但也会提高计算成本。

变异强度

• 初始变异强度应依据问题变量的预期尺度进行设置。
• 在优化过程中，应动态调整变异强度，以维持探索与开发之间的平衡。

终止准则

• 最大迭代次数应根据可用计算资源和问题复杂度合理设置。
• 另一种可选的终止方式是监测固定迭代窗口内最优适应度值的改进速率。

策略参数自适应

• $1/5$ 成功法则是一种常见的变异强度调整启发式：若超过 20% 的子代是成功的（即其表现优于对应父代），则增大变异强度；否则减小变异强度。
• 也可以采用更高级的自适应机制，例如自适应演化或协方差矩阵自适应，以进一步提升算法性能。