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

名称

$(\mu/\rho +, \lambda)$-进化策略（$(\mu/\rho +, \lambda)$-Evolution Strategy），也可写作 $(\mu/\rho + \lambda)$-ES。

分类

查看分类思维导图

$(\mu/\rho +, \lambda)$-进化策略是一种基于种群的随机优化算法，属于进化算法（Evolutionary Algorithms, EA）范畴，其设计思想来源于生物进化。它与其他进化策略方法密切相关，例如 $(1+1)$-ES、$(\mu+1)$-ES、$(\mu+\lambda)$-ES 和 $(\mu,\lambda)$-ES。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 进化策略
          • $(\mu/\rho +, \lambda)$-进化策略

策略

初始化与表示

$(\mu/\rho +, \lambda)$-ES 首先初始化一个由 $\mu$ 个个体组成的种群，其中每个个体表示优化问题的一个潜在解。这些个体通常表示为搜索空间中的实值向量。此外，每个个体还关联一组策略参数，用于控制搜索过程中变异的幅度与方向。

父代选择与重组

在每一代中，从大小为 $\mu$ 的种群中选择 $\rho$ 个父代个体。该选择通常以均匀随机方式进行，而不对适应度施加偏置。随后，对选中的父代执行重组操作，即将其遗传信息进行组合，以生成新的子代个体。常见的重组算子包括中间重组和离散重组，分别通过对父代向量分量求平均或随机选取分量的方式生成子代。

变异

完成重组后，对生成的 $\lambda$ 个子代个体施加变异操作。变异算子依据与个体关联的策略参数对每个子代的决策变量进行扰动。通常，变异通过向子代添加一个服从正态分布的随机向量来实现，而策略参数决定该分布的方差。经过变异后的子代构成搜索空间中的新候选解。

生存者选择

在生成并变异子代之后，需要通过生存者选择机制决定哪些个体进入下一代。在 $(\mu/\rho +, \lambda)$-ES 中，生存者选择通过将 $\mu$ 个父代个体与 $\lambda$ 个子代个体合并，再依据适应度从中选出最优的 $\mu$ 个个体来完成。这种机制称为“加号选择”（plus selection），因为其在生存选择时同时考虑父代与子代。

迭代与终止

父代选择、重组、变异和生存者选择这一过程不断重复，直到达到预设代数或满足某一终止条件。终止条件可以依据最大迭代代数、种群收敛情况或达到满意适应度水平等因素来设定。算法终止时，返回搜索过程中找到的最优个体作为优化结果。

过程

数据结构

• 个体：表示一个候选解，由实值决策变量向量及其关联的策略参数构成。
• 种群：由 $\mu$ 个个体组成的集合。

参数

• $\mu$：种群规模，即种群中的个体数量。
• $\rho$：参与重组的父代个体数量。
• $\lambda$：每一代生成的子代个体数量。
• 重组算子：用于组合父代遗传信息的算子（如中间重组或离散重组）。
• 变异算子：用于扰动子代个体决策变量的算子。
• 终止准则：决定算法何时停止的条件（如最大代数、收敛或适应度阈值）。

算法步骤

1. 随机初始化一个由 $\mu$ 个个体组成的种群，同时为每个个体设置决策变量和策略参数。
2. 评估种群中每个个体的适应度。
3. 当未满足终止准则时，重复执行步骤 4-8。
4. 以均匀随机方式从种群中选择 $\rho$ 个父代个体。
5. 对选中的父代施加重组算子，生成 $\lambda$ 个子代个体。
6. 对每个子代个体施加变异算子，根据其关联的策略参数扰动决策变量。
7. 评估每个子代个体的适应度。
8. 将 $\mu$ 个父代个体与 $\lambda$ 个子代个体合并，并依据适应度选取其中最优的 $\mu$ 个个体作为下一代种群。
9. 返回搜索过程中找到的最优个体作为优化结果。

注意事项

优点

• 在求解高维搜索空间中的连续优化问题时通常具有较好效果。
• 对噪声干扰和非凸适应度景观具有较强鲁棒性。
• 能够基于策略参数自动调整搜索步长。
• 由于其基于种群的特性，易于并行化，具有较好的可扩展性。

缺点

• 需要仔细调节种群规模 $\mu$、父代选择规模 $\rho$ 以及子代规模 $\lambda$ 等参数。
• 若种群多样性无法维持，算法可能出现过早收敛或停滞。
• 重组算子与变异算子的选择会显著影响算法性能。
• 与基于梯度的优化方法相比，其计算开销通常更高，尤其在大种群和高维问题中更为明显。

启发式建议

种群规模（$\mu$）

• 可将种群规模初始设置为问题维度的至少 10 倍。
• 对于更复杂或多峰的适应度景观，可适当增大种群规模。
• 在设定种群规模时，应综合考虑全局探索与局部开发之间的平衡。

父代选择规模（$\rho$）

• 父代选择规模通常应小于种群规模，即 $\rho < \mu$。
• 一个常见经验是将 $\rho$ 设置为种群规模的一定比例，例如 $\rho = \mu/2$ 或 $\rho = \mu/4$。
• 较大的 $\rho$ 有助于提高子代多样性，而较小的 $\rho$ 则更倾向于围绕潜在优良区域集中搜索。

子代规模（$\lambda$）

• 通常将子代规模设置为大于种群规模，即 $\lambda > \mu$，以增强探索能力。
• 一个常见经验是令 $\lambda$ 为种群规模的若干倍，例如 $\lambda = 7\mu$ 或 $\lambda = 10\mu$。
• 较大的 $\lambda$ 会增加计算成本，但通常有助于提升解的质量。

重组算子

• 对于决策变量之间存在较强依赖关系的问题，可优先考虑使用中间重组。
• 对于决策变量之间相关性较弱或近似独立的问题，可优先考虑使用离散重组。
• 可通过实验比较不同重组算子的表现，以确定更适合具体问题的方案。

变异算子

• 可根据搜索过程的进展动态调整变异步长，例如采用自适应策略或协方差矩阵自适应方法。
• 在搜索初期宜采用较大的变异步长以增强探索能力，而在搜索后期宜采用较小步长以精细化搜索结果。
• 还可结合领域知识或约束条件设计问题特定的变异算子。

终止准则

• 可依据可用计算资源和问题复杂度设定最大代数。
• 可监测种群收敛情况，当适应度改进在若干代内停滞时停止算法。
• 也可预先设定目标适应度值，当找到满意解时提前终止算法。