高效秩-μ更新自動協方差矩陣自適應演化策略

楊勝飛 茍 剛

(貴州大學計算機科學與技術學院 貴州 貴陽 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和秩-μ更新更高效的方法，使算法在高維度下運行更快。