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

名称

$(\mu,\lambda)$-进化策略（$(\mu,\lambda)$-Evolution Strategy），简称 $(\mu,\lambda)$-ES，也可写作 (mu,lambda)-Evolution Strategy 或 (mu,lambda)-ES。

分类

查看分类思维导图

$(\mu,\lambda)$-进化策略是一种基于种群的随机优化算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。它与其他进化策略方法密切相关，例如 $(1+1)$-ES 和 $(\mu+\lambda)$-ES。

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

策略

基于种群的搜索

$(\mu,\lambda)$-进化策略维持一个由 $\mu$ 个候选解构成的种群，这些候选解称为父代。每一次迭代中，算法通过对父代施加变异操作生成 $\lambda$ 个新的候选解，这些新生成的候选解称为子代。变异算子通常通过向父代解中加入服从正态分布的随机扰动来实现。

选择机制

在生成子代之后，$(\mu,\lambda)$-ES 从这 $\lambda$ 个子代中选取表现最优的 $\mu$ 个解，作为下一代的父代种群。该选择机制称为逗号选择（comma-selection），因为在选择过程中只考虑当前生成的子代，而不保留上一代父代个体。

自适应变异

$(\mu,\lambda)$-ES 通常采用自适应变异机制，即在搜索过程中动态调整变异算子的参数，例如步长或协方差矩阵。这样可以使算法根据优化问题的特性自动调节搜索行为，从而提升搜索效率与适应性。

过程

数据结构：

• 种群（Population）：由 $\mu$ 个候选解构成的数组，每个候选解表示为一个实值向量。
• 适应度（Fitness）：长度为 $\mu$ 的适应度数组，对应种群中各候选解的适应度值。

参数：

• $\mu$：父代解的数量。
• $\lambda$：每次迭代生成的子代解数量。
• 最大迭代次数（maxIterations）：最大迭代次数。
• 变异步长（mutationStepSize）：变异算子的初始步长。

步骤：

1. 随机生成 $\mu$ 个候选解，初始化种群。
2. 评估种群中每个候选解的适应度。
3. 重复以下过程，直到满足终止条件（例如达到最大迭代次数）：
   1. 通过对父代施加变异生成 $\lambda$ 个子代解：
      1. 对于每一个子代：
         1. 从父代种群中均匀随机选择一个父代个体。
         2. 使用给定的变异步长向该父代解加入随机扰动，从而生成一个新解。
   2. 评估每个子代解的适应度。
   3. 从 $\lambda$ 个子代中选出最优的 $\mu$ 个解，构成新的父代种群。
   4. 根据子代解的成功率更新变异步长。
4. 返回搜索过程中找到的最优解。

注意事项

优点：

• 适用于求解连续优化问题。
• 对问题结构要求较少，适用范围较广。
• 能够在优化过程中自适应地调整搜索行为。

缺点：

• 算法性能依赖于种群规模 $\mu$ 和子代数量 $\lambda$ 的设置。
• 可能需要大量适应度评估才能收敛。
• 对于非凸问题，不能保证一定找到全局最优解。

启发式建议

种群规模（$\mu$）

• 可根据问题的维度和复杂度选择 $\mu$。较大的 $\mu$ 有助于维持种群多样性并更充分地探索搜索空间，但也会增加每次迭代的计算成本。
• 一个常见经验是将 $\mu$ 设置为与问题维度平方根成比例的数值。

子代数量（$\lambda$）

• 通常令 $\lambda$ 大于 $\mu$，以增强探索能力并保持种群多样性。一个常见经验比值为 $\lambda = 7\mu$。
• 增大 $\lambda$ 有助于提高找到更优解的概率，但同时也会增加每次迭代的计算开销。

变异步长

• 初始变异步长应根据决策变量的预期取值范围来设定。一个常见经验是将初始步长设为决策变量取值范围的大约 $1/10$。
• 在搜索过程中，可根据子代解的成功率自适应调整变异步长。当成功率较高时增大步长，而当成功率较低时减小步长。
• 也可考虑采用自适应机制，使每个候选解都携带自身的变异步长，并使其与解一同演化。

终止准则

• 可根据可用计算预算设定最大迭代次数或最大函数评估次数。
• 可监测搜索过程的进展，当最优适应度在连续若干次迭代中不再提升时终止算法（停滞检测）。
• 也可采用相对改进阈值作为终止条件，即当最优适应度的相对提升低于某一预设阈值时停止搜索。