基于协方差矩阵自适应进化策略的函数寻优算法

协方差矩阵自适应进化策略的函数寻优算法"/>

基于协方差矩阵自适应进化策略的函数寻优算法

文章目录

• 一、理论基础
• • 1、CMA-ES算法结构
  • • （1）产生新个体
    • （2）计算适应度
    • （3）参数更新
  • 2、CMA-ES算法流程图
• 二、仿真实验与结果分析
• 三、参考文献

一、理论基础

协方差矩阵自适应进化策略(Covariance matrix adaptive evolution strategy, CMA-ES)是Nikolaus Hansen等人提出的一种新的无约束优化算法，已成功应用于全局优化、多峰优化、多目标优化、大规模优化和结构工程等领域。

1、CMA-ES算法结构

（1）产生新个体

CMA-ES在每一代中从 N ( m t , σ t 2 , C t ) N(m_t,σ^2_t , C_t) N(mt​,σt2​,Ct​)产生 λ \lambda λ个个体。 x i = m t + σ t y i , y i ∼ N ( 0 , C t ) (1) x_i=m_t+\sigma_ty_i,\,\,y_i\sim N(0,C_t)\tag{1} xi​=mt​+σt​yi​,yi​∼N(0,Ct​)(1)其中： y i ∈ R n y_i\in\mathbb R^n yi​∈Rn是搜索方向。通常， y y y可以通过协方差矩阵 C C C的特征分解来求解： C t = B D 2 B T C_t = BD^2B^\text{T} Ct​=BD2BT，并可以通过标准正态分布获得 y i = B D z i , z i ∼ N ( 0 , I ) (2) y_i=BDz_i,\,\,z_i\sim N(0,I)\tag{2} yi​=BDzi​,zi​∼N(0,I)(2)

（2）计算适应度

计算每一个新个体的适应度 f ( x ) f(x) f(x)，并进行适应度排序。 f ( x 1 : λ ) ≤ f ( x 2 : λ ) ≤ ⋯ ≤ f ( x λ : λ ) (3) f(x_{1:\lambda})\leq f(x_{2:\lambda})\leq\cdots\leq f(x_{\lambda:\lambda})\tag{3} f(x1:λ​)≤f(x2:λ​)≤⋯≤f(xλ:λ​)(3)下标表示第 i i i个个体。
根据适应度排序，截取前 μ \mu μ个个体进行参数更新，一般采取 μ = [ λ / 2 ] \mu= [\lambda/2] μ=[λ/2]，也可采用其他的截取方式。

（3）参数更新

使用所选的个体分别更新分布参数 m t m_t mt​、 C t C_t Ct​和 σ t \sigma_t σt​。首先更新均值： m t + 1 = ∑ i = 1 μ ω i x i : λ = m t + ∑ i = 1 μ ω i ( x i : λ − m t ) (4) m_{t+1}=\sum_{i=1}^\mu\omega_ix_{i:\lambda}=m_t+\sum_{i=1}^\mu\omega_i(x_{i:\lambda}-m_t)\tag{4} mt+1​=i=1∑μ​ωi​xi:λ​=mt​+i=1∑μ​ωi​(xi:λ​−mt​)(4) ∑ i = 1 μ ω i = 1 , ω 1 > ω 2 > ⋯ > ω μ > 0 (5) \sum_{i=1}^\mu\omega_i=1,\,\,\omega_1>\omega_2>\cdots>\omega_\mu>0\tag{5} i=1∑μ​ωi​=1,ω1​>ω2​>⋯>ωμ​>0(5)其中： m m m为均值，下标 t t t表示代数。 m t m_t mt​是个体 x 1 : t , ⋯ , x λ : t x_{1:t},\cdots,x_{\lambda:t} x1:t​,⋯,xλ:t​的加权平均值。
然后更新协方差矩阵，在CMA–ES中，协方差矩阵的更新包括 r a n k − 1 rank-1 rank−1和 r a n k − μ rank-\mu rank−μ。其中 r a n k − 1 rank-1 rank−1使用历史搜索信息，即进化路径。进化路径和协方差矩阵更新公式表达如下： P t + 1 = ( 1 − c ) p t + c ( 2 − c ) μ ω m t + 1 − m t σ t (6) P_{t+1}=(1-c)p_t+\sqrt{c(2-c)}\sqrt{\mu_\omega}\frac{m_{t+1}-m_t}{\sigma_t}\tag{6} Pt+1​=(1−c)pt​+c(2−c) ​μω​ ​σt​mt+1​−mt​​(6) C t + 1 = ( 1 − c 1 − c μ ) C t + c 1 p t + 1 p t + 1 T + c μ ∑ i = 1 μ ω i ( x i : λ − m t σ t ) ( x i : λ − m t σ t ) T (7) C_{t+1}=(1-c_1-c_\mu)C_t+c_1p_{t+1}p_{t+1}^\text{T}+c_\mu\sum_{i=1}^\mu\omega_i(\frac{x_{i:\lambda}-m_t}{\sigma_t})(\frac{x_{i:\lambda}-m_t}{\sigma_t})^\text{T}\tag{7} Ct+1​=(1−c1​−cμ​)Ct​+c1​pt+1​pt+1T​+cμ​i=1∑μ​ωi​(σt​xi:λ​−mt​​)(σt​xi:λ​−mt​​)T(7)其中 c 1 c_1 c1​和 c μ c_\mu cμ​为学习率。
CMA-ES算法使用累积步长调整，这是目前最成功的步长调整方法 s t + 1 = ( 1 − c σ ) s t + c σ ( 2 − c σ ) ∗ μ ω B ∑ i = 1 μ ω i z i : λ (8) s_{t+1}=(1-c_\sigma)s_t+\sqrt{c_\sigma(2-c_\sigma)}*\sqrt{\mu_\omega}B\sum_{i=1}^\mu\omega_iz_{i:\lambda}\tag{8} st+1​=(1−cσ​)st​+cσ​(2−cσ​) ​∗μω​ ​Bi=1∑μ​ωi​zi:λ​(8) σ t + 1 = σ t exp ⁡ ( c σ d σ ) ( ∣ ∣ s t + 1 ∣ ∣ E ∣ ∣ N ( 0 , I ) ∣ ∣ − 1 ) (9) \sigma_{t+1}=\sigma_t\exp(\frac{c_\sigma}{d_\sigma})(\frac{||s_{t+1}||}{E||N(0,I)||}-1)\tag{9} σt+1​=σt​exp(dσ​cσ​​)(E∣∣N(0,I)∣∣∣∣st+1​∣∣​−1)(9)

2、CMA-ES算法流程图

CMA-ES算法流程图如图1所示。

二、仿真实验与结果分析

以常用23个测试函数中的F1、F2(单峰函数/30维)、F9、F10(多峰函数/30维)、F14、F16(固定维度多峰函数/2维、2维)为例，实验设置种群规模为30，最大迭代次数为500，结果显示如下：

The optimal solution of F1 is : 7.6331e-07  6.5382e-07  2.8723e-06 -4.7179e-07  3.7437e-07  1.7081e-06   3.095e-06  -1.275e-06  -1.026e-06 -4.1949e-07 -5.8322e-07 -2.0732e-06   9.276e-08 -3.1926e-07 -1.6728e-06 -5.0495e-07 -1.4635e-07  1.4751e-06   7.156e-07  1.2271e-06  1.5031e-06  4.9227e-07 -1.1893e-06  -1.389e-09 -1.4571e-06  1.2453e-06 -1.2003e-06 -1.8651e-06 -4.4423e-07 -1.1751e-06
The optimal value of F1 is : 5.1079e-11
The optimal solution of F2 is : 8.8693e-07 -2.9606e-07 -4.7071e-08  1.0623e-06  1.0488e-07  2.8328e-08 -6.5901e-07 -3.1026e-07 -4.2958e-07 -5.0094e-07 -4.3787e-09 -1.6705e-06  3.0599e-07  4.1635e-07   2.806e-07  2.4441e-07  1.0747e-07 -1.0263e-06 -8.2988e-10  2.6453e-07 -7.9435e-07  6.3773e-07  4.9094e-08  1.2486e-07 -8.0775e-07 -8.9065e-08 -4.2563e-07  5.6749e-07  5.2862e-07  3.7548e-07
The optimal value of F2 is : 1.3047e-05
The optimal solution of F9 is : -0.0086374   -0.058855    0.027513      1.1708    -0.20828  -0.0070212      1.7599    -0.18712    0.059083     -1.8062      1.0951     0.97228     0.62508     0.36905   -0.065808     0.92887     0.13802     -1.0921    -0.20214     0.77243    0.027441      0.2291   -0.069691   -0.034561   -0.020914     0.79657     0.19275     -1.1211     -1.1501    -0.57864
The optimal value of F9 is : 160.8455
The optimal solution of F10 is : -3.1394e-08    -6.8e-07  2.5963e-07  1.0074e-06  7.6258e-07  3.7138e-07  6.4596e-08 -1.2247e-06  7.6583e-08  3.3921e-07 -1.5054e-06 -6.9183e-07  9.5065e-07  9.5794e-07  1.1898e-07   3.417e-07  2.0075e-06  1.3426e-06 -8.2708e-07  8.6759e-07  9.8511e-07 -5.0805e-07  5.2689e-07 -1.2734e-08  1.3126e-06 -1.8244e-06 -1.1301e-06 -1.6583e-07  1.3236e-06 -4.3244e-07
The optimal value of F10 is : 3.6993e-06
The optimal solution of F14 is : -0.715619     -31.1252
The optimal value of F14 is : 3.5571
The optimal solution of F16 is : 0.089842    -0.71266
The optimal value of F16 is : -1.0316

实验结果表明：CMA-ES算法具有良好的优化性能。

代码下载链接：

三、参考文献

[1] HANSEN N. The CMA evolution strategy: a comparing review[M]. Towards a New Evolutionary Computation. Advances on Estimation of Distribution Algorithms. Berlin, Heidelberg: Springer, 2006, 192: 72-102.
[2] 杨紫晴, 姚加林, 伍国华, 等. 集成协方差矩阵自适应进化策略与差分进化的优化算法[J]. 控制理论与应用, 2021, 38(10): 1493-1502.
[3] 乔帅. 基于云模型的CMA-ES算法研究与应用[D]. 太原: 太原理工大学, 2015.