Skip to content
返回搜索结果

进化策略(CMA-ES)——协方差矩阵自适应

提出者
Nikolaus Hansen & Andreas Ostermeier
年份
2001
类型
Derivative-free continuous black-box optimizer

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

CMA-ES,即协方差矩阵自适应进化策略,是由Hansen和Ostermeier于2001年提出的一种现代的、不依赖梯度(derivative-free)的连续黑盒函数优化器。它维护一个从多元正态分布中抽取的候选解种群,并迭代地更新分布的均值、步长和完整的协方差矩阵,以引导搜索趋向参数空间中的更优区域。它已成为连续黑盒优化的事实标准,并广泛应用于神经架构搜索和强化学习策略优化。

方法背后的直觉

想象一下,您正在一片丘陵地带寻找最低点,但您无法看到地形——您只能探测各个位置并了解它们的高度。CMA-ES的工作方式就像一个引导式蜂群:它在一组当前最佳猜测周围投放一团探测点,测量每个探测点的优劣程度,然后重塑这团探测点以用于下一轮搜索。这团探测点并非一个简单的球体——它通过记住哪些方向带来了改进,来学习其正在下降的山谷的狭长、倾斜的形状。随着世代的更迭,这团探测点会收窄并倾斜,以与损失曲面的曲率对齐,从而使算法能够导航那些会让简单方法陷入困境的长而狭窄的山谷。

历史学

进化策略(Evolution strategies)在20世纪60年代和70年代被引入,作为受生物进化启发的基于种群的优化器家族。协方差矩阵自适应机制由Hansen和Ostermeier开发,并在他们2001年的《Evolutionary Computation》论文中得到全面描述,该论文表明,完全去随机化的自适应——从成功步骤的历史中学习搜索地形的二阶完整几何形状——在病态和不可分离问题上的表现远远优于早期的进化策略。Hansen在2016年的教程中整合了该算法及其理论特性,使CMA-ES成为连续黑盒优化基准测试的标准参考方法。

何时使用

当目标函数是连续的、可能非凸的、多峰的或有噪声的,并且梯度信息不可用或计算成本过高时,CMA-ES是适用的。理想的维度范围大约在10到1000个参数之间;低于10个维度时,更简单的方法通常就足够了,而高于1000个维度时,协方差矩阵的二次内存成本可能会变得难以承受。在统计意义上没有最小样本量要求——算法本身生成其评估点。CMA-ES非常适合超参数调优、神经架构搜索、强化学习策略优化以及模拟器仅提供黑盒输出的工程设计问题。

局限与注意事项

  • 在维度数量上的二次内存和每代计算成本限制了其应用范围,超过约1000个参数时,如果没有降维变体,则难以应用。
  • 在没有重启的情况下会收敛到局部最优解;对于高度多峰的地形,需要多次重启(IPOP-CMA-ES或BIPOP-CMA-ES)。
  • 不适用于离散或组合搜索空间——该方法本质上是为连续实值向量定义的。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 不需要梯度信息——适用于任何可调用的目标函数,包括有噪声的或基于仿真的函数。
  • 通过协方差自适应学习搜索地形的局部曲率,使其能够导航那些会击败具有固定搜索分布的无梯度方法所遇到的狭长和病态条件搜索空间。
  • 对于目标函数的保序变换和搜索空间的旋转具有不变性,使其在各种问题几何形状下都具有鲁棒性。
  • 非常适合中高维连续问题(10-1000个参数),只有一个可调超参数——初始步长。

应用

  • 机器学习模型的超参数调优,包括神经网络架构和强化学习代理。
  • 神经架构搜索——通过连续松弛优化离散编码的架构参数。
  • 当策略由连续向量参数化时,进行强化学习策略优化。
  • 工程设计优化,例如气动外形优化和结构参数拟合,其中仅可获得模拟器输出。
  • 科学模型校准——当似然函数不可微或计算成本高昂时,通过模拟模型拟合实验数据。

使用方式

使用方式

1

该算法以一个初始解向量和一个初始步长(sigma)作为种子。协方差矩阵初始为单位矩阵——一个完全球形的搜索云。种群大小设定为通常的4 + floor(3 * ln(维度))。

2

在每一代中,从由均值向量、步长和协方差矩阵定义的当前多元正态分布中采样一组候选解。由于该分布是多元正态的,采样结果既反映了当前的最佳估计,也反映了搜索空间的学习到的形状。

3

每个候选解都被传递给目标函数,并获得一个适应度分数。不需要梯度信息——只需要每个采样点的标量目标值。这使得CMA-ES适用于噪声大、不可微和基于仿真的目标。

4

均值被移向排名靠前的解。协方差矩阵和步长通过两个互补的自适应路径——秩一更新和秩mu更新——进行更新,使得在下一代中产生良好改进的方向更有可能出现。这是CMA-ES学习地形局部几何形状的核心机制。

5

算法重复采样-评估-更新的循环,直到满足停止标准:达到最大函数评估次数、均值或步长变化容差,或检测到协方差矩阵的退化。返回所有世代中找到的最佳解。

常见陷阱

  • 将初始步长设置得太小会将搜索困在狭窄的邻域内并阻止探索;太大会导致早期世代在远离最优值的地方浪费评估。一个常见的经验法则是设置sigma,使得最优值位于起始点的大约三倍sigma范围内。
  • 将CMA-ES应用于非常低维的问题(少于五个参数)通常是浪费的——更简单的网格搜索或Nelder-Mead方法就足够了,而CMA-ES的种群开销没有带来任何好处。
  • 仅在多峰地形上运行单个CMA-ES实例存在错过全局最优解的风险;当已知地形具有高度多峰性时,建议使用多起点或基于种群的重启策略(IPOP/BIPOP)。
  • 将返回的最佳解视为真正的全局最优解而不进行重启验证是一个常见的错误——当目标高度非凸时,务必通过多次独立运行来确认。

常见问题

CMA-ES与简单的遗传算法有何不同?

经典的遗传算法维护一个种群,并以固定的算子应用交叉和变异。CMA-ES则将种群建模为多元正态分布的样本,并根据哪些解是成功的,持续地自适应该分布——其均值、步长和完整的协方差矩阵。这使得CMA-ES能够学习损失地形的形状,并比具有固定算子的遗传算法更有效地导航相关、病态的空间。

CMA-ES能保证找到全局最优解吗?

不能。CMA-ES是一种局部搜索方法,意味着单次运行可能会收敛到局部最优解。对于多峰地形,建议进行多次独立重启——可能采用递增种群大小(IPOP-CMA-ES)——以提高搜索空间的覆盖率。

最重要的超参数是什么?

初始步长sigma是最具影响力的超参数。一个好的经验法则是将其设置得使得预期的最优值大致位于起始点的大约三倍sigma范围内。种群大小和最大评估次数是次要控制项;默认的种群大小公式(4 + floor(3 * ln(维度)))在实践中效果很好。

CMA-ES能处理有噪声的目标函数吗?

可以。由于CMA-ES仅使用种群的秩次信息——而非绝对函数值——它对噪声具有相对鲁棒性。对于高度有噪声的评估,增加种群大小或对每个候选解进行多次评估取平均值可以进一步提高鲁棒性。

相关方法

参考文献

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    打开 DOI 文献
    已复制。
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    打开出版物文献
    已复制。