高效秩-μ更新自动协方差矩阵自适应演化策略

杨胜飞 苟 刚

(贵州大学计算机科学与技术学院 贵州 贵阳 550025)

0 引 言

协方差矩阵自适应演化策略(CMA-ES)是应用最多、性能最好的演化策略(ES)[1]之一，由Hansen和Ostermeier[2-3]提出，主要应用实值优化问题，使函数值达到最小值且搜索成本最低。CMA-ES易陷入局部最优，乔帅结合云推理改善陷入局部最优[4]，胡冠宇引入混沌算子使其具有良好全局搜索能力[5]。CMA-ES的一般思想是在目标方向中使用成功搜索步骤的信息更改协方差矩阵的突变分布，不成功方向的信息随时间而丢弃。CMA-ES发展不同的变体，如MA-ES[8]和使用不同的演化策略(μ+λ)[6]的精英CMA-ES[7],使用五分之一成功规则，可应用于求解多目标优化问题。对于CMA-ES的不同变体，普遍存在更新协方差矩阵(秩-1和秩-μ)时间复杂度高的问题，计算协方差矩阵的秩-1和秩-μ时间为Θ((μ+1)n3)。Igel提出协方差矩阵cholesky秩-1更新并应用于精英CMA-ES[9]和非精英CMA-ES[10]，使用cholesky因子更新协方差矩阵，在计算时不直接计算协方差矩阵，而是对其cholesky因子进行计算，使计算协方差矩阵的秩-1更新时间减少为Θ(n2)。在进行协方差矩阵cholesky因子秩-1更新时，需考虑逆cholesky因子，Li等[11]提出一种高效的秩-1更新协方差矩阵(Li-CMA-ES),使用辅助演化路径代替协方差矩阵cholesky因子秩-1更新的演化路径，取消逆cholesky因子的计算。Krause等提出三角cholesky因子更新协方差矩阵，保证cholesky因子是三角矩阵，应用于精英CMA-ES[12]和非精英CMA-ES[13]。由于CMA-ES在获得突变信息时，只获取成功的突变信息，而不成功的信息被动丢弃，在一定程度上使协方差矩阵的自适应减慢。文献[14]提出自动(active)协方差矩阵自适应演化策略(active-CMA-ES)，在协方差矩阵更新中同时使用成功和不成功的突变信息，使不成功方向的方差自动减少，加快策略集中于有用的方向。文献[15]将active和cholesky的秩-1更新应用于精英CMA-ES,验证算法在某些问题上速度提升至2倍, Krimpmann等[16]将其应用于多目标优化。

目前，CMA-ES的cholesky因子更新只实现秩-1更新，对于秩-μ没有实现，自动CMA-ES增加不成功突变信息，使协方差矩阵更新的时间比CMA-ES增加了Θ((λ-μ)n3)。针对该问题，本文实现cholesky因子秩-μ更新，并结合Li提出的高效秩-1更新应用active-CMA-ES形成chol-active-CMA-ES，并与标准CMA-ES、active-CMA-ES、Li-CMA-ES在一组基准测试函数中验证算法的性能和效率。

1 背景知识

1.1 active-CMA-ES

在标准CMA-ES中，只有成功后代候选解的信息使用，而不成功的信息则被动丢弃，在一定程度上减慢协方差矩阵自适应。Jastrebski提出active-CMA-ES，使用不成功突变的后代信息有助于加快演化策略的处理，active-CMA-ES由以下6个步骤组成：

步骤1协方差矩C阵特征分解为正交矩阵B和对角矩阵D的乘积，C、B、D，均为n×n矩阵：

C=BD(BD)T

(1)

步骤2在每代中后代个体(候选解)从多元正态分布N(m,C)中产生[17]，m为搜索分布的移动均值，zi为突变向量服从正态分布N(0,I):

xi=m+σBDzi

(2)

将目标函数值f(xi)按照升序对个体进行排序，个体下标k∈[1,2,…,λ]表示第k个最好的个体。

步骤3更新搜索分布的移动均值m为:

m=m+σBD〈Z〉

(3)

步骤4Z为父代个体μ最好的平均突变向量:

步骤5协方差矩阵和步长更新需要演化路径Pc和共轭演化路径Pσ:

(5)

(6)

式中：cc、cσ为Pc和Pσ更新的学习率。

步骤6自动更新协方差矩阵为:

(7)

步骤7更新突变强度为：

(8)

式中：dσ为阻尼参数，χn标准正态分布的期望值。

1.2 协方差矩阵cholesky因子秩-1更新

在CMA-ES中，协方差矩阵秩-1和秩-μ更新时间复杂度分别为Θ(n3)和Θ(μn3)，在每代中计算协方差矩阵的代价昂贵。Igel提出cholesky因子秩-1更新协方差矩阵，直接在每代中对协方差矩阵的cholesky因子进行计算，进行cholesky因子秩-1减少为Θ(n2)。Li-CMA-ES实现协方差矩阵高效cholesky因子秩-1更新，使用辅助演化路径替换秩-1更新的演化路径，具体步骤如下：

步骤1每个对称正定矩阵(协方差矩阵)都可分解为C=AAT，A为cholesky因子，zi～N(0,I)，每代中候选解的产生重新定义:

xi=m+σAzi∶N(m,σ2AAT)

(9)

步骤2演化路径和共轭演化路径更新为:

(10)

(11)

步骤3分布移动均值更新为:

(12)

步骤4突变强度更新为:

(13)

步骤5协方差矩阵秩-1和秩-μ更新，δ=1-c1-cμ

(14)

步骤6辅助演化路径υ应用于协方差矩阵cholesky因子秩-1更新，υ代替A-1Pc，α=1-c1,β=c1:

(15)

(16)

2 改进方法

2.1 协方差矩阵cholesky因子秩-μ更新

Suttorp将cholesky因子秩-1更新应用CMA-ES，减少协方差矩阵秩-1更新时间，但对于协方差矩阵cholesky因子秩-μ更新没有实现，本文实现协方差矩阵cholesky因子秩-μ更新，相较于原始的协方差矩阵秩-μ更新，时间减少为Θ(μn2)。

引理1设u∈Rn为任意向量，则矩阵I+uuT被因式分解为:

I+uuT=(I+ζuuT)(I+ζuuT)

(17)

定理1设A∈Rn×n,z∈Rn,α,β∈R+，由υ=Az,当z≠0时，协方差矩阵cholesky因子A为:

(18)

由式(17)，协方差矩阵秩-μ更新重新表示为：

(19)

式中：υ=Azi:λ，zi～N(0,I)，将式(19)迭代展开为：

(20)

由式(20)、引理1和定理1，协方差矩阵cholesky因子秩-μ更新在i=1,2,…,μ中依次迭代计算为：

(21)

式中：βi=βωi,α1=1-cμ,α2=α2=…=αμ=1。

2.2 chol-active-CMA-ES

表1 参数值

算法1active-chol-CMA-ES

初始化：m0,σ0,Pc,0=0,Pσ,0=0,A0=I

1: repeat

2: fori=1:λdo

3:xi:λ=m+σyi:λ

4: end for

8:α=1-c1-cμ

10: forj=1:μdo

12: end for

13: fork=(λ-μ+1):λdo

15: end for

18: until stopping criterion is met

3 实验结果与分析

将提出的算法chol-active-CMA-ES与标准CMA-ES、Li-CMA-ES、active-CMA-ES在一组基准测试函数(表2)上运行比较提出算法的性能，设置目标函数值达到为最优。每个算法在基准测试函数中独立运行100次，问题维度为[100，200，300]。在表3-表5中，FE表示目标函数值，A1为标准CMA-ES算法，A2为Li-CMA-ES算法，A3为active-CMA-ES算法，A4为chol-active-CMA-ES算法。

表2 测试函数

图1为各个算法在维度为100，迭代10 000次，运行目标函数值达到时所需的最少迭代次数。chol-active-CMA-ES算法在(a)至(f)函数达到指定目标函数值，在(c)至(f)函数中所需迭代数最少，都优于其他CMA-ES变体。在(h)至(i)函数chol-active-CMA-ES算法与其他CMA-ES变体都未在迭代10 000次达到目标函数值，算法在(h)和(i)中获得较小值(见表3 粗体)。表4为图1各个算法运行的步长大小，取平均值。

图1 各个算法运行目标函数值达到10-10时所需最少迭代次数(迭代10 000次，问题维度为100)

表3 算法运行结果(取平均值)

表4 步长大小(取平均值)

chol-active-CMA-ES算法与active-CMA-ES算法运行100 000次，维度为[100,200,300]，比较达到目标函数值时协方差矩阵更新的时间，见表5(更新比=原始更新/新更新)，其中～为算法迭代结束后未达到指定目标函数值，故不计算其更新时间。chol-active-CMA-ES算法中协方差矩阵更新时间比原始算法快(除了fSphere和fCigar)，在fSphere中，在n=100时比原始更新快约4.1倍，n=200时比原始更新快约2.5倍，n=300时比原始更新快约8.7倍。

表5 协方差矩阵更新时间比(取平均值)

4 结 语

本文实现cholesky因子秩-μ更新协方差矩阵，结合Li-CMA-ES形成chol-active-CMA-ES，在一组基准测试函数中与其他CMA-ES变体比较性能及效率。实现结果表明所提出算法优于其他CMA-ES变体，并随着问题维度和迭代次数的增加，算法运行结果更好，更新协方差矩阵的时间比active-CMA-ES快。在未来的研究工作中，主要探索协方差矩阵秩-1和秩-μ更新更高效的方法，使算法在高维度下运行更快。