【优化算法】协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy，CMA-ES）

CMA-ES（Covariance Matrix Adaptation Evolution Strategy）算法是一种无导数、基于多元正态分布的迭代优化方法，通过自适应地调整搜索分布的均值、协方差矩阵和步长，能够高效地解决非线性、非凸的连续优化问题。

• 算法以最大似然和演化路径为两大核心思想，在每一代中生成 λ 个候选解，依据排序选取 μ 个优秀个体，并利用它们来更新搜索分布参数，实现二阶信息的隐式估计和迅速收敛。

1 算法解析

1.1 核心原理

• 最大似然原则：通过调整均值 $m$ 和协方差矩阵 $C$，使得先前成功（即具有较好目标值）的样本和搜索步长在新的分布下具有更高的采样概率，相当于对成功样本的增量式最优拟合。
• 演化路径（Evolution Paths）：算法维护两条路径——协方差更新路径 $p_c$ 和步长控制路径 $p_{\sigma }$。
  • 当连续步长朝同一方向时，路径长度变长，反映了搜索方向上的相关性；
  • 演化路径被用于加速协方差更新以及自适应步长调整，防止过早收敛并提升收敛速度。

1.2 算法核心步骤

1. 初始化：

   • 设定维度 $n$、初始均值 $m_0$、初始步长标准差 ${\sigma }_0$、种群规模 $\lambda$、精英数 $\mu$ 及权重 { w i } \{w_i\} {wi​}。
   • 初始协方差矩阵通常取单位矩阵 $C_0=I_n$。

2. 采样（Sampling）：

   $$x_k^{(t+1)}=m^{(t)}+{\sigma }^{(t)}\mathcal{N}(0,C^{(t)}),k=1,\dots ,\lambda$$

3. 排序与加权重组（Recombination）：按 $f(x)$ 从小到大排序，选取前 μ 个并按权重 $w_i$ 计算新的均值

   $$m^{(t+1)}=\sum _{i=1}^{\mu }{w}_i{x}_{i:\lambda }^{(t+1)}$$

4. 更新演化路径：

• 位置路径: $$p_c\leftarrow (1-c_c)p_c+\sqrt{c_c(2-c_c){\mu }_w}\frac{m^{(t+1)}-m^{(t)}}{{\sigma }^{(t)}}$$
• 步长路径：
  $$p_{\sigma }\leftarrow (1-c_{\sigma })p_{\sigma }+\sqrt{c_{\sigma }(2-c_{\sigma }){\mu }_w}{C}^{(t{)}^{-1/2}}\frac{m^{(t+1)}-m^{(t)}}{{\sigma }^{(t)}}$$

4. 协方差矩阵更新：
   $$C^{(t+1)}=(1-c_1-c_{\mu })C^{(t)}+c_1{p}_c{p}_c^T+c_{\mu }\sum _{i=1}^{\mu }{w}_i{y}_{i:\lambda }{y}_{i:\lambda }^T$$
   其中 $y_{i:\lambda }=(x_{i:\lambda }-m^{(t)})/{\sigma }^{(t)}$。

5. 步长控制（Step-Size Control）：

   $${\sigma }^{(t+1)}={\sigma }^{(t)}\exp \left(\frac{c_{\sigma }}{d_{\sigma }}\right(\frac{\Vert p_{\sigma }\Vert }{E[\Vert \mathcal{N}(0,I)\Vert ]}-1\left)\right)$$

   其中 $E[\Vert \mathcal{N}(0,I)\Vert ]$ 为期望长度。

2 参数说明

参数	含义	默认/约定
$n$	决策变量维度	—
$\lambda$	每代样本数（子代）	$\approx 4+3\ln n$
$\mu$	父代个体数（$\mu <\lambda$）	$\lfloor \lambda /2\rfloor$
$w_i$	父代重组权重，满足 $\sum w_i=1$，通常按对数划分	$w_i\propto \ln (\mu +1)-\ln (i)$
$m$	搜索分布的均值	初始化为问题起始点
$\sigma$	步长（全局标准差）	依问题设定，一般为可行域尺度
$C$	协方差矩阵	初始为单位矩阵
$c_c$, $c_{\sigma }$	演化路径的衰减因子	$c_c\approx \frac{4}{n+4}$, $c_{\sigma }\approx \frac{{\mu }_w+2}{n+{\mu }_w+5}$
$c_1$, $c_{\mu }$	协方差更新学习率	$c_1\approx \frac{2}{(n+1.3{)}^2+{\mu }_w}$, $c_{\mu }=\min (1-c_1,\frac{{\mu }_w-2+1/{\mu }_w}{(n+2{)}^2+{\mu }_w})$
$d_{\sigma }$	步长阻尼因子	$d_{\sigma }=1+c_{\sigma }+n^{-0.5}$

注：${\mu }_w={\sum }_{i=1}^{\mu }{w}_i^2$ 为有效父代大小。

3. 核心优势

1. 无梯度要求：
   不依赖目标函数的梯度信息，适用于黑箱优化问题（如非凸、多峰、不可导函数）。
2. 自适应搜索方向：
   通过协方差矩阵的动态调整，算法能够自动适应目标函数的几何特性（如旋转、缩放等）。
3. 鲁棒性：
   对噪声环境（如随机目标函数）具有较强的鲁棒性。

4 具体示例

以优化 n 维球函数

$$f(x)=\sum _{i=1}^n{x}_i^2$$

为例，取 $n=10$，初始均值 $m^0=(5,\dots ,5)$，初始步长 ${\sigma }^0=2$，则：

1. 初始化：
   $m=(5,5,\dots ,5),\sigma =2,C=I_{10}$。

2. 迭代示例（第一代）：

   • 采样 λ≈4+3ln10≈11 个样本，并计算对应的 f 值；
   • 按 f 排序后选 μ=5 个父代，计算加权均值；
   • 更新 $p_c$、$p_{\sigma }$、$C$ 和 $\sigma$；
   • 可观察到均值向原点移动，σ 逐渐缩小。

经过数十至数百代迭代后，均值 $m$ 会收敛至原点，且 $f(m)\to 0$。