协方差矩阵自适应进化策略（CMA-ES）

名称

协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy, CMA-ES）

分类

查看分类思维导图

CMA-ES 是一种随机优化算法，隶属于进化算法（Evolutionary Algorithms）范畴，而进化算法又是计算智能（Computational Intelligence）与生物启发计算（Biologically Inspired Computation）的子类。它与其他进化策略方法密切相关，例如 (1+1)-ES 和 $(\mu/\mu_w, \lambda)$-ES。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 进化策略
          • 协方差矩阵自适应进化策略（CMA-ES）

策略

协方差矩阵的自适应调整

CMA-ES 维持一个多元正态分布作为搜索分布，并通过迭代更新使其适应目标函数的地形结构。该分布的协方差矩阵表征了搜索分布的形状与方向，从而使 CMA-ES 能够高效探索搜索空间中具有潜力的区域。

基于排序的选择机制

在每一次迭代中，CMA-ES 从当前搜索分布中采样出一组候选解。随后，利用目标函数对这些候选解进行评估，并依据其排序结果选取其中表现最优的一部分解。该基于排序的选择机制强调解的相对优劣，而非其绝对适应度值，因此使得 CMA-ES 对目标函数的尺度变化和变换具有较强鲁棒性。

累积步长自适应

CMA-ES 采用一种称为累积步长自适应（cumulative step-size adaptation）的步长控制机制，根据成功变异的累积路径来调整搜索分布的整体尺度。该自适应机制使 CMA-ES 能够依据目标函数的局部特征自动调节步长，从而实现高效收敛。

过程

数据结构

• 均值向量（mean）：搜索分布的均值向量
• 协方差矩阵（covariance）：搜索分布的协方差矩阵
• 步长（stepSize）：搜索分布的全局步长
• 种群规模（populationSize）：每次迭代中采样的候选解数量
• 有效选择规模（muEffective）：用于更新搜索分布的有效选择解数量

参数

• 种群规模（populationSize）：每次迭代采样的种群规模（默认值：4 + floor(3 * log(dimensionality))）
• 选择比例（muRatio）：用于更新搜索分布的被选解比例（默认值：0.5）
• 累积因子（cumulationFactor）：步长自适应中累积路径的权重（默认值：(muEffective + 2) / (dimensionality + muEffective + 5)）
• 阻尼因子（dampFactor）：步长自适应的阻尼因子（默认值：1 + 2 * max(0, sqrt((muEffective - 1) / (dimensionality + 1)) - 1) + cumulationFactor）

初始化

1. 将 mean 初始化为搜索空间中的一个随机点
2. 将 covariance 初始化为单位矩阵
3. 根据搜索空间边界为 stepSize 设定一个合适的初值
4. 根据维度和 muRatio 计算 populationSize 与 muEffective
5. 根据 muEffective 和问题维度计算 cumulationFactor 与 dampFactor

主循环

1. 从均值为 mean、协方差为 covariance * (stepSize^2) 的多元正态分布中采样 populationSize 个候选解
2. 使用目标函数评估每个候选解的适应度
3. 根据排序结果选出最优的 muEffective 个解
4. 将 mean 更新为所选解的加权平均值
5. 根据所选解及成功变异的累积路径更新 covariance
6. 根据成功变异的累积路径和 dampFactor 更新 stepSize
7. 检查终止条件（如最大迭代次数、适应度阈值等）
8. 若未满足终止条件，则返回步骤 1

注意事项

优点

• 不变性良好：CMA-ES 对目标函数的保序变换，以及搜索空间的旋转和平移均具有不变性，因此鲁棒性较强，适用于广泛的优化问题。
• 自适应能力强：CMA-ES 能够根据目标函数的局部特性自动调整搜索分布的形状与尺度，从而减少人工调参的需求。
• 适用于病态和不可分问题：对于条件数较差或变量之间存在强耦合的非可分问题，CMA-ES 通常表现优异，而其他优化算法在此类问题上往往较易失效。

缺点

• 计算代价较高：CMA-ES 需要大量目标函数评估，因此在高维问题或目标函数计算代价较高的场景下可能成本较大。
• 理论收敛性保证有限：尽管 CMA-ES 在经验研究中表现优良，但其理论收敛性质尚不如部分其他优化算法那样完备。
• 对噪声敏感：当目标函数存在较强噪声时，基于排序的选择机制可能会受到误导，从而影响算法性能。

启发式建议

种群规模

• 对于低维问题（例如维度小于 10），可考虑使用大于默认值的种群规模，以增强探索能力。
• 对于高维问题（例如维度大于 100），可考虑使用小于默认值的种群规模，以降低计算开销。

初始步长

• 若已知搜索空间边界，可将初始步长设为各维搜索范围的约三分之一。
• 若未知搜索空间边界，可考虑使用较小的初始步长（如 0.1），并依赖步长自适应机制对其进行动态调整。

终止条件

• 可设置最大迭代次数或最大函数评估次数，以避免过度消耗计算资源。
• 可监测当前最优适应度值，若在一定迭代次数内没有显著改善，则终止算法。
• 当步长下降到某一阈值以下时，也可考虑终止，因为这通常表明搜索已收敛到某个局部最优附近。

重启策略

• 若 CMA-ES 收敛到次优解，可考虑从不同初始点重新启动算法，以探索搜索空间中的其他区域。
• 可采用多起点策略，即从多个不同初始条件运行 CMA-ES，并从中选取最优结果。

混合方法

• 可考虑将 CMA-ES 与局部搜索方法（如 Nelder-Mead 或 BFGS）结合，以在搜索后期进一步精炼解并加快收敛。
• 可将 CMA-ES 用作全局搜索方法以定位有前景的区域，再结合局部搜索方法高效逼近该区域内的精确最优解。