自然进化策略（NES）

名称

自然进化策略（Natural Evolution Strategy, NES）

分类

查看分类思维导图

自然进化策略是一种黑盒优化方法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。它与进化策略（Evolution Strategies, ES）以及协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy, CMA-ES）等方法密切相关。

• 计算智能
  • 进化计算
    • 进化算法
      • 进化策略
        • 协方差矩阵自适应进化策略（CMA-ES）
        • 自然进化策略（NES）

策略

自然进化策略受到自然进化原理的启发，在该框架下，候选解种群通过变异与选择的迭代过程不断得到改进。NES 的核心思想在于对变异算子的概率分布进行参数化，并依据优化问题的适应度地形对该分布进行自适应调整。

变异分布

在 NES 中，变异算子被定义为具有均值向量和协方差矩阵的多元高斯分布。其中，均值表示当前最优解所在的位置，而协方差矩阵则描述变量之间的依赖关系，并使算法能够对搜索空间进行自适应探索。

适应度排序

每个候选解的适应度通过优化问题的目标函数进行评估。随后，算法依据适应度值对种群中的个体进行排序，其中表现更优的个体获得更高的排序位置。

分布更新

变异分布的参数（即均值向量和协方差矩阵）根据种群的适应度排序结果进行更新。该更新规则基于自然梯度（natural gradient）推导而来。自然梯度是一种二阶优化方法，能够考虑参数空间的几何结构，因此有助于提高分布更新的效率与稳定性。

迭代过程

上述步骤不断重复，直至满足某一终止条件，例如达到最大迭代次数或获得足够满意的适应度值。算法最终返回在整个优化过程中找到的最优解。

过程

数据结构

• 种群：由若干候选解构成的集合，其中每个候选解表示为一个实值向量。
• 适应度：用于存储各候选解适应度值的数组。
• 均值：变异分布的均值向量。
• 协方差矩阵：表示变异分布协方差的对称正定矩阵。

参数

• 种群规模：每次迭代中候选解的数量。
• 学习率：控制分布更新幅度的步长参数。
• 初始均值：变异分布的初始均值向量。
• 初始协方差矩阵：变异分布的初始协方差矩阵。
• 终止准则：用于停止优化过程的条件，例如最大迭代次数或适应度阈值。

优化过程

1. 从初始变异分布中采样候选解，初始化种群。
2. 使用目标函数评估每个候选解的适应度。
3. 根据适应度值对种群进行排序。
4. 利用自然梯度和适应度排序结果更新变异分布的参数（均值和协方差矩阵）。
5. 从更新后的变异分布中采样新的种群。
6. 重复步骤 2-5，直至满足终止准则。
7. 返回优化过程中找到的最优解。

注意事项

优点

• 黑盒优化能力：NES 不需要目标函数的梯度信息，因此适用于梯度不可得或难以计算的优化问题。
• 自适应探索能力：协方差矩阵的自适应机制使 NES 能够依据适应度地形自动调整搜索行为，从而在高维空间中实现较高效的搜索。
• 良好的不变性：NES 对目标函数的保序变换具有不变性，同时对搜索空间的旋转和平移也具有不变性。

缺点

• 计算复杂度较高：NES 中协方差矩阵的更新涉及矩阵运算，在高维问题中尤其可能带来较高的计算开销。
• 参数敏感性较强：NES 的性能对超参数选择较为敏感，例如种群规模和学习率，通常需要较细致的调节。
• 易陷入局部最优：与其他进化算法类似，在存在大量次优解的多峰问题中，NES 也可能陷入局部最优。

启发式建议

种群规模

• 种群规模应足够大，以维持种群多样性并避免过早收敛，但也不宜过大，以免造成过高的计算负担。
• 一个常见经验是令种群规模与问题维度相关，例如设为 $4 + \lfloor 3 \log(N) \rfloor$，其中 $N$ 表示变量个数。

学习率

• 学习率控制分布更新的步长大小，并在全局探索与局部开发之间起平衡作用。
• 较小的学习率会使收敛速度变慢，但有助于更充分地探索搜索空间；较大的学习率则可能加快收敛，但也可能错过全局最优解。
• 学习率可以在优化过程中进行动态调整，例如初期取较大值以增强探索能力，后期逐步减小以实现精细搜索。

初始分布

• 变异分布的初始均值通常可设置为搜索空间中的随机点；若已有先验知识，也可设为具有领域意义的初始位置。
• 初始协方差矩阵通常可设为单位矩阵乘以一个缩放因子，该因子应反映变量预期尺度的大小。

终止准则

• 最大迭代次数应根据可用计算预算和问题复杂度合理设定。
• 当找到满足要求的解时，可利用适应度阈值提前停止优化过程。
• 还可以结合收敛速率、种群多样性，或一定迭代窗口内最优适应度变化情况等指标设置附加终止条件。

约束处理

• 若优化问题包含约束条件，可通过对不可行解施加惩罚、或采用修复机制将不可行解投影回可行域等方式进行处理。
• 另一种方法是设计只生成可行解的变异算子，例如结合领域知识，或采用重采样、边界处理等约束处理技术。