(1+1)-进化策略（(1+1)-ES）

名称

$(1+1)$-进化策略（$(1+1)$-Evolution Strategy），也可写作 $(1+1)$-ES 或 $(1+1)$ Evolution Strategy。

分类

查看分类思维导图

$(1+1)$-进化策略是一种简单的、基于单个候选解的进化算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。

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

策略

$(1+1)$-进化策略是一种简单的、基于单解的优化算法，其思想来源于生物进化原理。该算法始终维护一个候选解，通常称为父代，并通过变异与选择过程迭代地对其进行改进。

变异

在每一次迭代中，算法通过对父代施加变异操作生成一个新的候选解，称为子代。变异算子通常通过向父代的决策变量加入随机扰动来实现，这些扰动一般服从均值为零、标准差给定的正态分布。

选择

在生成子代之后，算法比较子代与父代的适应度（即目标函数值）。若子代的适应度优于父代，则用子代替换父代，并将其作为下一次迭代中的新父代；若父代的适应度更优，则保留父代，并丢弃子代。

这种简单的选择机制保证算法始终朝着更优解的方向推进，而不会接受更差的解。变异与选择过程不断重复，直到达到预设的迭代次数，或满足某一终止准则为止。

过程

数据结构

• 父代解（parent）：当前候选解
• 子代解（offspring）：通过变异生成的新候选解
• 适应度函数（fitness(solution)）：用于评估给定解适应度（目标函数值）的函数

参数

• mu：变异所用正态分布的均值（通常设为 0）
• sigma：变异所用正态分布的标准差
• 最大迭代次数（max_iterations）：算法运行的最大迭代次数

伪代码

1. 随机生成一个候选解，初始化 parent
2. 对于 i = 1 到 max_iterations，重复执行：
   1. 通过对 parent 施加变异生成 offspring：
      1. 对于 parent 中的每个决策变量 x：
         1. offspring[x] = parent[x] + Normal(mu, sigma)
   2. 若 fitness(offspring) 优于 fitness(parent)：
      1. parent = offspring
3. 返回 parent 作为找到的最优解

注意事项

优点

• 简单性：$(1+1)$-进化策略结构极其简洁，变异与选择算子也较为直接，因此易于理解与实现。
• 参数较少：该算法仅包含少量需要调节的参数，主要是变异强度（标准差）和终止准则，因此相较于更复杂的算法，对参数设置不那么敏感。
• 局部搜索能力：$(1+1)$-ES 能够有效探索候选解附近的局部邻域，因此适合用于解的微调和局部优化。

缺点

• 探索能力有限：由于该算法仅维护单个解，并采用简单的变异算子，因此在跳出局部最优、有效探索搜索空间不同区域方面能力较弱。
• 收敛速度较慢：对于高维或复杂优化问题，该算法可能需要大量迭代才能收敛到较优解。
• 缺乏多样性：$(1+1)$-ES 不维护多样化种群，这限制了其适应多峰适应度景观以及寻找全局最优解的能力。

启发式建议

变异强度（Sigma）

• 在搜索初期可采用相对较大的 sigma 值，以增强探索能力；随着优化过程推进，再逐步减小 sigma，以加强局部开发与精细搜索。
• 可根据搜索进展自适应调整 sigma。若算法持续找到更优解，则可适当增大 sigma 以维持探索；若算法长时间难以获得改进，则可减小 sigma 以加强局部搜索。

终止准则

• 可将最大迭代次数与基于适应度改进速率的收敛判据结合使用。当在预设迭代窗口内未观察到显著改进时，可停止算法。
• 在设置终止准则时，应综合考虑计算预算与所需解质量。对于复杂问题或对解质量要求较高的场景，通常需要允许更多迭代。

初始化

• 应在可行搜索空间内随机初始化 parent，以提供一个具有随机性的起点。
• 若已掌握一定先验知识，也可利用启发式方法或已有的较优解初始化 parent，从而使搜索从更有前景的区域开始。

问题特定修改

• 可根据具体问题特征调整变异算子。例如，可针对不同决策变量的敏感性或重要性，为其设置不同的变异强度。
• 可引入问题相关的约束处理或修复机制，以确保生成的子代解始终满足可行性要求。

混合方法

• 可考虑将 $(1+1)$-ES 与其他局部搜索技术（如爬山法或模式搜索）结合，以增强其局部优化能力。
• 也可将 $(1+1)$-ES 作为更大规模种群型进化算法中的局部搜索算子，以实现全局探索与局部开发之间的平衡。