高效秩-μ更新自動協(xié)方差矩陣自適應(yīng)演化策略

楊勝飛 茍 剛

(貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院 貴州 貴陽 550025)

0 引 言

協(xié)方差矩陣自適應(yīng)演化策略(CMA-ES)是應(yīng)用最多、性能最好的演化策略(ES)[1]之一，由Hansen和Ostermeier[2-3]提出，主要應(yīng)用實值優(yōu)化問題，使函數(shù)值達到最小值且搜索成本最低。CMA-ES易陷入局部最優(yōu)，喬帥結(jié)合云推理改善陷入局部最優(yōu)[4]，胡冠宇引入混沌算子使其具有良好全局搜索能力[5]。CMA-ES的一般思想是在目標(biāo)方向中使用成功搜索步驟的信息更改協(xié)方差矩陣的突變分布，不成功方向的信息隨時間而丟棄。CMA-ES發(fā)展不同的變體，如MA-ES[8]和使用不同的演化策略(μ+λ)[6]的精英CMA-ES[7],使用五分之一成功規(guī)則，可應(yīng)用于求解多目標(biāo)優(yōu)化問題。對于CMA-ES的不同變體，普遍存在更新協(xié)方差矩陣(秩-1和秩-μ)時間復(fù)雜度高的問題，計算協(xié)方差矩陣的秩-1和秩-μ時間為Θ((μ+1)n3)。Igel提出協(xié)方差矩陣cholesky秩-1更新并應(yīng)用于精英CMA-ES[9]和非精英CMA-ES[10]，使用cholesky因子更新協(xié)方差矩陣，在計算時不直接計算協(xié)方差矩陣，而是對其cholesky因子進行計算，使計算協(xié)方差矩陣的秩-1更新時間減少為Θ(n2)。在進行協(xié)方差矩陣cholesky因子秩-1更新時，需考慮逆cholesky因子，Li等[11]提出一種高效的秩-1更新協(xié)方差矩陣(Li-CMA-ES),使用輔助演化路徑代替協(xié)方差矩陣cholesky因子秩-1更新的演化路徑，取消逆cholesky因子的計算。Krause等提出三角cholesky因子更新協(xié)方差矩陣，保證cholesky因子是三角矩陣，應(yīng)用于精英CMA-ES[12]和非精英CMA-ES[13]。由于CMA-ES在獲得突變信息時，只獲取成功的突變信息，而不成功的信息被動丟棄，在一定程度上使協(xié)方差矩陣的自適應(yīng)減慢。文獻[14]提出自動(active)協(xié)方差矩陣自適應(yīng)演化策略(active-CMA-ES)，在協(xié)方差矩陣更新中同時使用成功和不成功的突變信息，使不成功方向的方差自動減少，加快策略集中于有用的方向。文獻[15]將active和cholesky的秩-1更新應(yīng)用于精英CMA-ES,驗證算法在某些問題上速度提升至2倍, Krimpmann等[16]將其應(yīng)用于多目標(biāo)優(yōu)化。

目前，CMA-ES的cholesky因子更新只實現(xiàn)秩-1更新，對于秩-μ沒有實現(xiàn)，自動CMA-ES增加不成功突變信息，使協(xié)方差矩陣更新的時間比CMA-ES增加了Θ((λ-μ)n3)。針對該問題，本文實現(xiàn)cholesky因子秩-μ更新，并結(jié)合Li提出的高效秩-1更新應(yīng)用active-CMA-ES形成chol-active-CMA-ES，并與標(biāo)準(zhǔn)CMA-ES、active-CMA-ES、Li-CMA-ES在一組基準(zhǔn)測試函數(shù)中驗證算法的性能和效率。

1 背景知識

1.1 active-CMA-ES

在標(biāo)準(zhǔn)CMA-ES中，只有成功后代候選解的信息使用，而不成功的信息則被動丟棄，在一定程度上減慢協(xié)方差矩陣自適應(yīng)。Jastrebski提出active-CMA-ES，使用不成功突變的后代信息有助于加快演化策略的處理，active-CMA-ES由以下6個步驟組成：

步驟1協(xié)方差矩C陣特征分解為正交矩陣B和對角矩陣D的乘積，C、B、D，均為n×n矩陣：

C=BD(BD)T

(1)

步驟2在每代中后代個體(候選解)從多元正態(tài)分布N(m,C)中產(chǎn)生[17]，m為搜索分布的移動均值，zi為突變向量服從正態(tài)分布N(0,I):

xi=m+σBDzi

(2)

將目標(biāo)函數(shù)值f(xi)按照升序?qū)€體進行排序，個體下標(biāo)k∈[1,2,…,λ]表示第k個最好的個體。

步驟3更新搜索分布的移動均值m為:

m=m+σBD〈Z〉

(3)

步驟4Z為父代個體μ最好的平均突變向量:

步驟5協(xié)方差矩陣和步長更新需要演化路徑Pc和共軛演化路徑Pσ:

(5)

(6)

式中：cc、cσ為Pc和Pσ更新的學(xué)習(xí)率。

步驟6自動更新協(xié)方差矩陣為:

(7)

步驟7更新突變強度為：

(8)

式中：dσ為阻尼參數(shù)，χn標(biāo)準(zhǔn)正態(tài)分布的期望值。

1.2 協(xié)方差矩陣cholesky因子秩-1更新

在CMA-ES中，協(xié)方差矩陣秩-1和秩-μ更新時間復(fù)雜度分別為Θ(n3)和Θ(μn3)，在每代中計算協(xié)方差矩陣的代價昂貴。Igel提出cholesky因子秩-1更新協(xié)方差矩陣，直接在每代中對協(xié)方差矩陣的cholesky因子進行計算，進行cholesky因子秩-1減少為Θ(n2)。Li-CMA-ES實現(xiàn)協(xié)方差矩陣高效cholesky因子秩-1更新，使用輔助演化路徑替換秩-1更新的演化路徑，具體步驟如下：

步驟1每個對稱正定矩陣(協(xié)方差矩陣)都可分解為C=AAT，A為cholesky因子，zi～N(0,I)，每代中候選解的產(chǎn)生重新定義:

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

(9)

步驟2演化路徑和共軛演化路徑更新為:

(10)

(11)

步驟3分布移動均值更新為:

(12)

步驟4突變強度更新為:

(13)

步驟5協(xié)方差矩陣秩-1和秩-μ更新，δ=1-c1-cμ

(14)

步驟6輔助演化路徑υ應(yīng)用于協(xié)方差矩陣cholesky因子秩-1更新，υ代替A-1Pc，α=1-c1,β=c1:

(15)

(16)

2 改進方法

2.1 協(xié)方差矩陣cholesky因子秩-μ更新

Suttorp將cholesky因子秩-1更新應(yīng)用CMA-ES，減少協(xié)方差矩陣秩-1更新時間，但對于協(xié)方差矩陣cholesky因子秩-μ更新沒有實現(xiàn)，本文實現(xiàn)協(xié)方差矩陣cholesky因子秩-μ更新，相較于原始的協(xié)方差矩陣秩-μ更新，時間減少為Θ(μn2)。

引理1設(shè)u∈Rn為任意向量，則矩陣I+uuT被因式分解為:

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

(17)

定理1設(shè)A∈Rn×n,z∈Rn,α,β∈R+，由υ=Az,當(dāng)z≠0時，協(xié)方差矩陣cholesky因子A為:

(18)

由式(17)，協(xié)方差矩陣秩-μ更新重新表示為：

(19)

式中：υ=Azi:λ，zi～N(0,I)，將式(19)迭代展開為：

(20)

由式(20)、引理1和定理1，協(xié)方差矩陣cholesky因子秩-μ更新在i=1,2,…,μ中依次迭代計算為：

(21)

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

2.2 chol-active-CMA-ES

表1 參數(shù)值

算法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 實驗結(jié)果與分析

將提出的算法chol-active-CMA-ES與標(biāo)準(zhǔn)CMA-ES、Li-CMA-ES、active-CMA-ES在一組基準(zhǔn)測試函數(shù)(表2)上運行比較提出算法的性能，設(shè)置目標(biāo)函數(shù)值達到為最優(yōu)。每個算法在基準(zhǔn)測試函數(shù)中獨立運行100次，問題維度為[100，200，300]。在表3-表5中，F(xiàn)E表示目標(biāo)函數(shù)值，A1為標(biāo)準(zhǔn)CMA-ES算法，A2為Li-CMA-ES算法，A3為active-CMA-ES算法，A4為chol-active-CMA-ES算法。

表2 測試函數(shù)

圖1為各個算法在維度為100，迭代10 000次，運行目標(biāo)函數(shù)值達到時所需的最少迭代次數(shù)。chol-active-CMA-ES算法在(a)至(f)函數(shù)達到指定目標(biāo)函數(shù)值，在(c)至(f)函數(shù)中所需迭代數(shù)最少，都優(yōu)于其他CMA-ES變體。在(h)至(i)函數(shù)chol-active-CMA-ES算法與其他CMA-ES變體都未在迭代10 000次達到目標(biāo)函數(shù)值，算法在(h)和(i)中獲得較小值(見表3 粗體)。表4為圖1各個算法運行的步長大小，取平均值。

圖1 各個算法運行目標(biāo)函數(shù)值達到10-10時所需最少迭代次數(shù)(迭代10 000次，問題維度為100)

表3 算法運行結(jié)果(取平均值)

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

chol-active-CMA-ES算法與active-CMA-ES算法運行100 000次，維度為[100,200,300]，比較達到目標(biāo)函數(shù)值時協(xié)方差矩陣更新的時間，見表5(更新比=原始更新/新更新)，其中～為算法迭代結(jié)束后未達到指定目標(biāo)函數(shù)值，故不計算其更新時間。chol-active-CMA-ES算法中協(xié)方差矩陣更新時間比原始算法快(除了fSphere和fCigar)，在fSphere中，在n=100時比原始更新快約4.1倍，n=200時比原始更新快約2.5倍，n=300時比原始更新快約8.7倍。

表5 協(xié)方差矩陣更新時間比(取平均值)

4 結(jié) 語

本文實現(xiàn)cholesky因子秩-μ更新協(xié)方差矩陣，結(jié)合Li-CMA-ES形成chol-active-CMA-ES，在一組基準(zhǔn)測試函數(shù)中與其他CMA-ES變體比較性能及效率。實現(xiàn)結(jié)果表明所提出算法優(yōu)于其他CMA-ES變體，并隨著問題維度和迭代次數(shù)的增加，算法運行結(jié)果更好，更新協(xié)方差矩陣的時間比active-CMA-ES快。在未來的研究工作中，主要探索協(xié)方差矩陣秩-1和秩-μ更新更高效的方法，使算法在高維度下運行更快。