非线性规划中的自适应协方差矩阵调整演化策略(CMA-ES)基础题
题目描述
考虑一个二维非线性优化问题：
最小化目标函数 \(f(x_1, x_2) = (x_1 - 3)^2 + 2(x_2 + 1)^2 + 5\)，
其中变量 \(x_1, x_2 \in \mathbb{R}\)。该问题无约束，最优解为 \(x^* = (3, -1)\)，最优值 \(f(x^*) = 5\)。要求使用自适应协方差矩阵调整演化策略（CMA-ES）求解该问题，重点解释CMA-ES如何通过自适应调整搜索分布来逼近最优解。
解题过程
-
算法原理概述
CMA-ES是一种随机优化算法，核心思想是通过多元正态分布生成候选解，并动态调整该分布的均值（定位最优区域）和协方差矩阵（控制搜索方向与步长）。调整策略基于成功搜索路径的累积信息，使搜索方向逐渐对齐目标函数的等高线结构。 -
初始化参数
- 设置初始均值 \(m^{(0)} = (0, 0)\)（随机选择或根据先验知识）。
- 初始步长 \(\sigma^{(0)} = 1\)（全局缩放因子）。
- 初始协方差矩阵 \(C^{(0)} = I\)（单位矩阵，表示各向同性搜索）。
- 设置种群大小 \(\lambda = 10\)（每代生成解的个数），选择权重 \(w_i\)（用于加权更新，通常 \(\sum w_i = 1\)）。
-
迭代步骤（以第 \(g\) 代为例）
步骤1：生成候选解
从当前多元正态分布 \(\mathcal{N}(m^{(g)}, (\sigma^{(g)})^2 C^{(g)})\) 采样 \(\lambda\) 个解：
\[ x_i^{(g+1)} = m^{(g)} + \sigma^{(g)} y_i, \quad y_i \sim \mathcal{N}(0, C^{(g)}) \]
例如，第一代可能生成解 $ (1.2, -0.5) $、$ (-0.8, 0.3) $ 等。
步骤2：评估与排序
计算每个解的目标函数值 \(f(x_i)\)，按值从小到大排序，选择前 \(\mu\) 个较优解（如 \(\mu = 5\)）。
步骤3：更新均值 \(m\)
使用加权平均更新均值，偏向优质解：
\[ m^{(g+1)} = \sum_{i=1}^{\mu} w_i x_i^{(g+1)} \]
例如，若优质解集中在 $ (2.5, -0.8) $ 附近，新均值会向该方向移动。
步骤4：更新演化路径和协方差矩阵 \(C\)
- 累积路径更新：
记录均值移动方向的加权历史信息（演化路径 \(p_\sigma\) 和 \(p_c\)），用于调整步长和协方差。
\[ p_\sigma^{(g+1)} = (1 - c_\sigma) p_\sigma^{(g)} + \sqrt{c_\sigma (2 - c_\sigma) \mu_{\text{eff}}} \cdot \frac{m^{(g+1)} - m^{(g)}}{\sigma^{(g)}} \]
其中 $ c_\sigma $ 为学习率（如 0.3），$ \mu_{\text{eff}} $ 为权重有效值。
- **协方差矩阵更新**：
结合历史路径和当前优质解的信息：
\[ C^{(g+1)} = (1 - c_1 - c_\mu) C^{(g)} + c_1 p_c^{(g+1)} (p_c^{(g+1)})^T + c_\mu \sum_{i=1}^{\mu} w_i y_i y_i^T \]
其中 $ c_1 $ 和 $ c_\mu $ 控制学习速率。此步骤使协方差矩阵逐渐对齐目标函数的等高线（本例中为椭圆）。
步骤5：更新步长 \(\sigma\)
根据演化路径 \(p_\sigma\) 的长度调整步长：若路径较长（连续移动方向一致），则增大 \(\sigma\) 以加速搜索；若路径较短（方向振荡），则减小 \(\sigma\) 以精细搜索：
\[ \sigma^{(g+1)} = \sigma^{(g)} \exp\left( \frac{c_\sigma}{d_\sigma} \left( \frac{\| p_\sigma^{(g+1)} \|}{\mathbb{E} \| \mathcal{N}(0, I) \|} - 1 \right) \right) \]
其中 $ d_\sigma $ 为阻尼系数。
- 收敛判断
重复迭代直到满足终止条件（如步长 \(\sigma\) 小于阈值 \(10^{-6}\)，或均值变化可忽略）。本例中，均值 \(m\) 将收敛至 \((3, -1)\)，协方差矩阵 \(C\) 会近似为 \(\begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}\) 的缩放形式，反映目标函数在 \(x_1\) 和 \(x_2\) 方向的不同曲率。
关键点
CMA-ES通过自适应调整协方差矩阵，使搜索分布的形状（如椭圆方向）适应目标函数的局部几何结构，比各向同性搜索（如标准演化策略）更高效。本例中，算法会快速识别 \(x_2\) 方向需更大调整，从而加速收敛。