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

楊勝飛 茍 剛

(貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 貴州 貴陽(yáng) 550025)

0 引 言

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

目前，CMA-ES的cholesky因子更新只實(shí)現(xiàn)秩-1更新，對(duì)于秩-μ沒(méi)有實(shí)現(xiàn)，自動(dòng)CMA-ES增加不成功突變信息，使協(xié)方差矩陣更新的時(shí)間比CMA-ES增加了Θ((λ-μ)n3)。針對(duì)該問(wèn)題，本文實(shí)現(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)測(cè)試函數(shù)中驗(yàn)證算法的性能和效率。

1 背景知識(shí)

1.1 active-CMA-ES

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

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

C=BD(BD)T

(1)

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

xi=m+σBDzi

(2)

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

步驟3更新搜索分布的移動(dòng)均值m為:

m=m+σBD〈Z〉

(3)

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

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

(5)

(6)

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

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

(7)

步驟7更新突變強(qiáng)度為：

(8)

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

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

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

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

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

(9)

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

(10)

(11)

步驟3分布移動(dòng)均值更新為:

(12)

步驟4突變強(qiáng)度更新為:

(13)

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

(14)

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

(15)

(16)

2 改進(jìn)方法

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

Suttorp將cholesky因子秩-1更新應(yīng)用CMA-ES，減少協(xié)方差矩陣秩-1更新時(shí)間，但對(duì)于協(xié)方差矩陣cholesky因子秩-μ更新沒(méi)有實(shí)現(xiàn)，本文實(shí)現(xiàn)協(xié)方差矩陣cholesky因子秩-μ更新，相較于原始的協(xié)方差矩陣秩-μ更新，時(shí)間減少為Θ(μ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時(shí)，協(xié)方差矩陣cholesky因子A為:

(18)

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

(19)

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

(20)

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

(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 實(shí)驗(yàn)結(jié)果與分析

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

表2 測(cè)試函數(shù)

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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