非线性规划中的自适应协方差矩阵调整演化策略(CMA-ES)基础题
题目描述
考虑一个简单的无约束非线性规划问题：
最小化目标函数 \(f(x) = x_1^2 + 2x_2^2 - 0.3 \cos(3\pi x_1) - 0.4 \cos(4\pi x_2) + 0.7\)，其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。
该函数是Rastrigin函数的变体，具有多个局部极小值，但全局最小值在 \((0, 0)\) 处（函数值为 \(0\)）。要求使用CMA-ES算法求解该问题，初始点设为 \(x^{(0)} = (1.5, -1.5)\)，初始步长 \(\sigma^{(0)} = 0.5\)，种群大小 \(\lambda = 10\)。
解题过程
CMA-ES是一种随机优化算法，通过自适应调整搜索分布的协方差矩阵来逼近目标函数的形状。以下是详细步骤：
-
初始化参数
- 设置初始解 \(x^{(0)} = (1.5, -1.5)\)，初始步长 \(\sigma^{(0)} = 0.5\)，种群大小 \(\lambda = 10\)。
- 初始化协方差矩阵 \(C^{(0)} = I\)（单位矩阵），进化路径 \(p_\sigma^{(0)} = 0\)，\(p_c^{(0)} = 0\)。
- 设置算法参数：
- 权重 \(w_i\)（用于重组，通常取 \(w_i = \frac{\ln(\lambda+1) - \ln(i)}{\sum_{j=1}^\mu \ln(\lambda+1) - \ln(j)}\)，其中 \(\mu = \lfloor \lambda/2 \rfloor\)）；
- 学习率 \(c_\sigma\)、\(c_c\)、\(c_1\)、\(c_\mu\)（默认值参考CMA-ES文献）。
-
生成新种群
在第 \(g\) 代（\(g = 0, 1, 2, \dots\)）：- 从多元正态分布生成 \(\lambda\) 个候选解：
\[ x_k^{(g+1)} = x^{(g)} + \sigma^{(g)} \mathcal{N}(0, C^{(g)}), \quad k = 1, \dots, \lambda. \]
- 计算每个候选解的目标函数值 \(f(x_k^{(g+1)})\)。
- 选择与重组
- 将候选解按 \(f(x)\) 升序排序，选择前 \(\mu\) 个最优解。
- 更新均值（加权重组）：
\[ x^{(g+1)} = \sum_{i=1}^\mu w_i x_{i:\lambda}^{(g+1)}, \]
其中 $ x_{i:\lambda} $ 表示第 $ i $ 个最优解。
- 更新进化路径
- 更新步长控制路径 \(p_\sigma\)：
\[ p_\sigma^{(g+1)} = (1 - c_\sigma) p_\sigma^{(g)} + \sqrt{c_\sigma (2 - c_\sigma) \mu_\mathrm{eff}} \, (C^{(g)})^{-1/2} \frac{x^{(g+1)} - x^{(g)}}{\sigma^{(g)}}, \]
其中 $ \mu_\mathrm{eff} = \left( \sum_{i=1}^\mu w_i^2 \right)^{-1} $。
- 更新协方差矩阵路径 \(p_c\)：
\[ p_c^{(g+1)} = (1 - c_c) p_c^{(g)} + \sqrt{c_c (2 - c_c) \mu_\mathrm{eff}} \, \frac{x^{(g+1)} - x^{(g)}}{\sigma^{(g)}}. \]
- 调整协方差矩阵
- 更新协方差矩阵 \(C\)：
\[ C^{(g+1)} = (1 - c_1 - c_\mu) C^{(g)} + c_1 p_c^{(g+1)} (p_c^{(g+1)})^\top + c_\mu \sum_{i=1}^\mu w_i y_i^{(g+1)} (y_i^{(g+1)})^\top, \]
其中 $ y_i^{(g+1)} = (x_i^{(g+1)} - x^{(g)}) / \sigma^{(g)} $。
- 调整步长
- 更新步长 \(\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 \approx 1 $ 是阻尼系数。
- 迭代与终止
- 重复步骤2–6，直到满足终止条件（如 \(\sigma\) 小于阈值或达到最大迭代次数）。
- 最终解 \(x^{(g)}\) 会逼近全局最小值点 \((0, 0)\)。
关键点说明
- CMA-ES通过协方差矩阵调整搜索方向，使其适应目标函数的局部地形（如谷底方向）。
- 进化路径记录搜索方向的历史信息，避免过早收敛。
- 对于本例的多峰函数，CMA-ES能有效避免局部极小值，因自适应步长和协方差调整允许探索与开发的平衡。