自适应协方差矩阵调整演化策略(CMA-ES)基础题
字数 2971 2025-12-02 13:51:47

自适应协方差矩阵调整演化策略(CMA-ES)基础题

题目描述
考虑一个二维非线性优化问题：
最小化目标函数 \(f(x_1, x_2) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)，
其中 \(x_1, x_2 \in \mathbb{R}\)。使用自适应协方差矩阵调整演化策略（CMA-ES）求解该问题，初始点设为 \(x^{(0)} = (0, 0)^T\)，初始步长 \(\sigma^{(0)} = 1\)，种群大小 \(\lambda = 4\)。

解题过程
CMA-ES是一种基于种群的随机优化算法，通过自适应调整搜索分布的协方差矩阵来逼近目标函数的局部结构。以下是详细步骤：

  1. 初始化参数

    • 设置初始分布均值 \(m^{(0)} = x^{(0)} = (0, 0)^T\)。
    • 初始协方差矩阵 \(C^{(0)} = I\)（单位矩阵）。
    • 初始步长 \(\sigma^{(0)} = 1\)。
    • 选择种群大小 \(\lambda = 4\)，父代数量 \(\mu = \lfloor \lambda/2 \rfloor = 2\)。
    • 设置权重 \(w_i = \frac{\ln(\mu+0.5) - \ln(i)}{\sum_{j=1}^{\mu} \ln(\mu+0.5) - \ln(j)}\)（用于重组），例如 \(w_1 \approx 0.85, w_2 \approx 0.15\)。
    • 初始化进化路径 \(p_\sigma^{(0)} = 0, p_c^{(0)} = 0\)。

  2. 生成新种群（第\(g\)代）

    • 对每个个体 \(k = 1, \dots, \lambda\)：
      • 采样随机向量 \(z_k \sim \mathcal{N}(0, I)\)（独立同分布的标准正态分布）。
      • 计算 \(y_k = \sigma^{(g)} \cdot B^{(g)} D^{(g)} z_k\)，其中 \(C^{(g)} = B^{(g)} (D^{(g)})^2 (B^{(g)})^T\) 是协方差矩阵的特征分解。
      • 生成个体 \(x_k = m^{(g)} + y_k\)。
    • 示例（简化）：
      假设 \(z_1 = (0.5, -0.3)^T, z_2 = (-0.2, 0.7)^T, z_3 = (0.1, 0.4)^T, z_4 = (-0.6, -0.1)^T\)。
      由于 \(C^{(0)} = I\)，有 \(B^{(0)} = I, D^{(0)} = I\)，因此 \(y_k = z_k\)。
      得到种群：
      \(x_1 = (0.5, -0.3)^T, x_2 = (-0.2, 0.7)^T, x_3 = (0.1, 0.4)^T, x_4 = (-0.6, -0.1)^T\)。

  3. 评估与排序

    • 计算每个个体的目标函数值：
      \(f(x_1) = (0.5-2)^4 + (0.5 - 2\cdot(-0.3))^2 \approx 5.06 + 1.21 = 6.27\)，
      \(f(x_2) \approx 38.94 + 5.76 = 44.70\)，
      \(f(x_3) \approx 28.74 + 2.89 = 31.63\)，
      \(f(x_4) \approx 45.70 + 0.16 = 45.86\)。
    • 按 \(f(x)\) 升序排序：\(x_1, x_3, x_2, x_4\)。
    • 选择前 \(\mu = 2\) 个最优个体 \(x_1, x_3\) 作为父代。

  4. 更新分布均值

    • 新均值 \(m^{(g+1)} = \sum_{i=1}^{\mu} w_i x_{i:\lambda}\)，其中 \(x_{i:\lambda}\) 是第 \(i\) 优个体。
    • 计算：\(m^{(1)} = 0.85 \cdot (0.5, -0.3)^T + 0.15 \cdot (0.1, 0.4)^T \approx (0.44, -0.21)^T\)。

  5. 更新进化路径和协方差矩阵

    • 步长控制路径 \(p_\sigma\)：
      \(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 \approx 0.3\) 为学习率，\(\mu_{\text{eff}} = 1/\sum w_i^2 \approx 1.25\)。
      初始 \(p_\sigma^{(0)} = 0\)，计算 \(p_\sigma^{(1)} \approx 0.77 \cdot (0.44, -0.21)^T \approx (0.34, -0.16)^T\)。
    • 协方差矩阵更新：
      • 路径 \(p_c^{(g+1)}\) 更新类似 \(p_\sigma\)，但权重不同。
      • 协方差矩阵 \(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:\lambda} y_{i:\lambda}^T\)，
        其中 \(c_1 \approx 0.01, c_\mu \approx 0.1\) 为学习率。
        第一次迭代中，\(C^{(1)}\) 接近单位矩阵但略有调整。

  6. 更新步长 \(\sigma\)

    • 根据 \(p_\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\) 为阻尼系数。若 \(\|p_\sigma\|\) 大于期望值（表示路径较长），则增大 \(\sigma\) 以加速搜索。

  7. 迭代与终止

    • 重复步骤2-6，直到步长 \(\sigma\) 足够小或达到最大代数。
    • 最终均值 \(m\) 会收敛到近优解 \((2, 1)^T\)（理论最优解为 \(f(2,1)=0\)）。

关键点

  • CMA-ES通过协方差矩阵自适应学习目标函数的等高线形状，使搜索方向沿梯度下降方向。
  • 进化路径记录连续代的移动方向，避免过早收敛。
  • 本题中，算法预计在10-20代内收敛到高精度解。
自适应协方差矩阵调整演化策略(CMA-ES)基础题 题目描述 考虑一个二维非线性优化问题： 最小化目标函数 \( f(x_ 1, x_ 2) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \)， 其中 \( x_ 1, x_ 2 \in \mathbb{R} \)。使用自适应协方差矩阵调整演化策略（CMA-ES）求解该问题，初始点设为 \( x^{(0)} = (0, 0)^T \)，初始步长 \( \sigma^{(0)} = 1 \)，种群大小 \( \lambda = 4 \)。 解题过程 CMA-ES是一种基于种群的随机优化算法，通过自适应调整搜索分布的协方差矩阵来逼近目标函数的局部结构。以下是详细步骤： 初始化参数 设置初始分布均值 \( m^{(0)} = x^{(0)} = (0, 0)^T \)。 初始协方差矩阵 \( C^{(0)} = I \)（单位矩阵）。 初始步长 \( \sigma^{(0)} = 1 \)。 选择种群大小 \( \lambda = 4 \)，父代数量 \( \mu = \lfloor \lambda/2 \rfloor = 2 \)。 设置权重 \( w_ i = \frac{\ln(\mu+0.5) - \ln(i)}{\sum_ {j=1}^{\mu} \ln(\mu+0.5) - \ln(j)} \)（用于重组），例如 \( w_ 1 \approx 0.85, w_ 2 \approx 0.15 \)。 初始化进化路径 \( p_ \sigma^{(0)} = 0, p_ c^{(0)} = 0 \)。 生成新种群（第\( g \)代） 对每个个体 \( k = 1, \dots, \lambda \)： 采样随机向量 \( z_ k \sim \mathcal{N}(0, I) \)（独立同分布的标准正态分布）。 计算 \( y_ k = \sigma^{(g)} \cdot B^{(g)} D^{(g)} z_ k \)，其中 \( C^{(g)} = B^{(g)} (D^{(g)})^2 (B^{(g)})^T \) 是协方差矩阵的特征分解。 生成个体 \( x_ k = m^{(g)} + y_ k \)。 示例（简化）： 假设 \( z_ 1 = (0.5, -0.3)^T, z_ 2 = (-0.2, 0.7)^T, z_ 3 = (0.1, 0.4)^T, z_ 4 = (-0.6, -0.1)^T \)。 由于 \( C^{(0)} = I \)，有 \( B^{(0)} = I, D^{(0)} = I \)，因此 \( y_ k = z_ k \)。 得到种群： \( x_ 1 = (0.5, -0.3)^T, x_ 2 = (-0.2, 0.7)^T, x_ 3 = (0.1, 0.4)^T, x_ 4 = (-0.6, -0.1)^T \)。 评估与排序 计算每个个体的目标函数值： \( f(x_ 1) = (0.5-2)^4 + (0.5 - 2\cdot(-0.3))^2 \approx 5.06 + 1.21 = 6.27 \)， \( f(x_ 2) \approx 38.94 + 5.76 = 44.70 \)， \( f(x_ 3) \approx 28.74 + 2.89 = 31.63 \)， \( f(x_ 4) \approx 45.70 + 0.16 = 45.86 \)。 按 \( f(x) \) 升序排序：\( x_ 1, x_ 3, x_ 2, x_ 4 \)。 选择前 \( \mu = 2 \) 个最优个体 \( x_ 1, x_ 3 \) 作为父代。 更新分布均值 新均值 \( m^{(g+1)} = \sum_ {i=1}^{\mu} w_ i x_ {i:\lambda} \)，其中 \( x_ {i:\lambda} \) 是第 \( i \) 优个体。 计算：\( m^{(1)} = 0.85 \cdot (0.5, -0.3)^T + 0.15 \cdot (0.1, 0.4)^T \approx (0.44, -0.21)^T \)。 更新进化路径和协方差矩阵 步长控制路径 \( p_ \sigma \) ： \( 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 \approx 0.3 \) 为学习率，\( \mu_ {\text{eff}} = 1/\sum w_ i^2 \approx 1.25 \)。 初始 \( p_ \sigma^{(0)} = 0 \)，计算 \( p_ \sigma^{(1)} \approx 0.77 \cdot (0.44, -0.21)^T \approx (0.34, -0.16)^T \)。 协方差矩阵更新 ： 路径 \( p_ c^{(g+1)} \) 更新类似 \( p_ \sigma \)，但权重不同。 协方差矩阵 \( 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:\lambda} y_ {i:\lambda}^T \)， 其中 \( c_ 1 \approx 0.01, c_ \mu \approx 0.1 \) 为学习率。 第一次迭代中，\( C^{(1)} \) 接近单位矩阵但略有调整。 更新步长 \( \sigma \) 根据 \( p_ \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 \) 为阻尼系数。若 \( \|p_ \sigma\| \) 大于期望值（表示路径较长），则增大 \( \sigma \) 以加速搜索。 迭代与终止 重复步骤2-6，直到步长 \( \sigma \) 足够小或达到最大代数。 最终均值 \( m \) 会收敛到近优解 \( (2, 1)^T \)（理论最优解为 \( f(2,1)=0 \)）。 关键点 CMA-ES通过协方差矩阵自适应学习目标函数的等高线形状，使搜索方向沿梯度下降方向。 进化路径记录连续代的移动方向，避免过早收敛。 本题中，算法预计在10-20代内收敛到高精度解。