韓束丹，田雨波，李 睿，丁偉桐

(江蘇科技大學(xué) 電子信息學(xué)院， 鎮(zhèn)江 212100)

協(xié)方差自適應(yīng)進(jìn)化策略(covariance matrix adaptation-evolution strategy,CMA-ES)[1]，是演化啟發(fā)式算法的一種，主要用于解決高維復(fù)雜問題，被認(rèn)為近百年來最為成功的連續(xù)黑盒優(yōu)化方法之一[2].該算法通過擾動其協(xié)方差和步長來學(xué)習(xí)適應(yīng)度函數(shù)的核心特征，從而引導(dǎo)累積步長向全局最優(yōu)點(diǎn)移動[3]，且在不可分離的高維病態(tài)問題上表現(xiàn)良好且具有空間不變特性[4].在其較多的內(nèi)部參數(shù)賦予了算法處理復(fù)雜問題能力的同時，如果這些參數(shù)值選擇不恰當(dāng)，CMA-ES算法就易出現(xiàn)陷入局部最優(yōu)、收斂速度慢等問題.為了提高CMA-ES算法的性能，眾多學(xué)者進(jìn)行相關(guān)的研究與改進(jìn).文獻(xiàn)[5]提出Cholesky因式分解，將算法的時間復(fù)雜度由Θ(n3)降為Θ(n2)；文獻(xiàn)[6]提出將協(xié)方差矩陣對角化的方法，將時間復(fù)雜度和空間復(fù)雜度降為線性，大大縮短了算法的時間復(fù)雜度；文獻(xiàn)[7]解決了引入Cholesky因式分解導(dǎo)致的計算演化路徑復(fù)雜度過高的問題，顯著提高CMA-ES算法在解決非低維度問題上的效率；文獻(xiàn)[8]提出一種帶有限記憶的協(xié)方差矩陣適應(yīng)進(jìn)化策略，提高了CMA-ES算法在處理不可分離的高維病態(tài)問題上優(yōu)化速度和處理性能.文中提出了一種帶有隨機(jī)因子的協(xié)方差自適應(yīng)進(jìn)化策略(random-factor CMA-ES，RFCMA-ES)，通過在全局步長更新時加上具有隨機(jī)因子的差值項，避免陷入局部最優(yōu)，能更好地保持進(jìn)化群體的多樣性，從而提高算法全局尋優(yōu)的能力，并采用6種不同的標(biāo)準(zhǔn)測試函數(shù)進(jìn)行數(shù)值仿真，實(shí)驗(yàn)結(jié)果驗(yàn)證了RFCMA-ES算法在搜索能力、收斂速度方面相比于原始算法有了很大提高.

1 CMA-ES算法及其改進(jìn)

1.1 CMA-ES算法

在CMA-ES算法中，初始種群規(guī)模λ較為關(guān)鍵，λ值選取過小，算法評價數(shù)據(jù)較少，全局搜索能力弱，易陷入局部最優(yōu)；λ值選取過大，會引入冗余量，影響算法尋優(yōu)速率.為了使λ值相對合理，一般使其與問題參數(shù)的維數(shù)N掛鉤，通常取種群粒子數(shù)為：

λ≥4+3lnN

(1)

λ值確定之后，便可調(diào)用獨(dú)立于優(yōu)化算法的適應(yīng)度函數(shù)計算種群中λ個粒子的適應(yīng)度值，并將其按升序重新排序，選取其中前μ個粒子構(gòu)成初始種群的子孫種群.

更新后問題參量的各維度期望值:

(2)

Cg決定Bg和Dg，式(3)為Cg奇異值分解：

Cg=BgDg(BgDg)T=Bg(Dg)2(Bg)T

(3)

表1 CMA-ES內(nèi)部參數(shù)計算公式

1秩更新量C1g+1定義為:

C1g+1=c1pcg+1(pcg+1)T

(4)

μ秩更新量定義為:

(5)

其中,ωi和cμ的具體意義和計算公式見表1．

總的協(xié)方差矩陣Cg+1更新公式為:

(6)

上述的協(xié)方差矩陣是去除各維度量鋼差異之后的歸一化值,最終高斯分布的協(xié)方差還會受到方差步長σ的影響．σ值的大小表示了搜索區(qū)域粒子各維度參數(shù)值調(diào)整的幅度,全局步長σg+1的更新公式為:

(7)

式中：dσ為尼阻系數(shù),dσ≈1；cσ的具體意義和計算公式見表1,E‖N(0,I)‖表示N維多元正態(tài)分布,具體表達(dá)式為:

(8)

(9)

1.2 RFCMA-ES算法

1.2.1 基本原理

文獻(xiàn)[9]根據(jù)Rechenberg的“MSC”概念上提出了協(xié)方差算法的多路徑累積步長方法來擴(kuò)充目標(biāo)策略控制參數(shù)的自適應(yīng)模型,即在調(diào)制策略參數(shù)基礎(chǔ)上,增加與之相匹配的變異因子變化形成了“CMA-ES”．“MSC”中變異因子是算法在種群尋優(yōu)更新路徑上產(chǎn)生變異的根本原因,但是,通過增加變異強(qiáng)度不能同時解決提高變化速率與選擇差異性性能[10]．鑒此,在“MSC”概念、累積步長思想和原始全局步長σg+1更新公式的機(jī)理研究上提出帶有隨機(jī)因子新的全局步長更新方程:

(10)

1.2.2 算法流程

Step1: 根據(jù)所求解問題各個維度變量的取值空間,確定種群粒子的初始分布空間.

Step2: 利用高斯分布在初始種群空間中隨機(jī)選擇λ個種群粒子,種群粒子每個維度的協(xié)方差矩陣來表示各個粒子的高斯分布幅度.

Step3: 被選中λ個種群粒子構(gòu)成母系種群,根據(jù)適應(yīng)度函數(shù)計算其適應(yīng)度值,并判斷種群中是否存在滿足停止條件的粒子；如滿足條件則轉(zhuǎn)Step6,不滿足則轉(zhuǎn)Step4．

Step4: 在λ個母系種群中選出μ個相對最優(yōu)的粒子構(gòu)成子代種群,由子代種群的分布結(jié)合相應(yīng)的權(quán)重,根據(jù)式(2)得出新的期望值、根據(jù)式(6)得出新的協(xié)方差及根據(jù)式(10)更新全局搜索步長,從而獲得新的滿足高斯分布的樣本空間．

Step5: 重復(fù)Step2到Step4的步驟,直到得到滿足判定停止條件的適應(yīng)度值．

Step6: 停止算法運(yùn)行．

2 實(shí)驗(yàn)結(jié)果與分析

文中通過6個多維多峰測試函數(shù)對CMA-ES與RFCMA-ES性能進(jìn)行全方面對比評價,分為3個部分:① 通過對6個標(biāo)準(zhǔn)測試函數(shù)尋最小值過程對改進(jìn)算法收斂性性能進(jìn)行評價;② 將每個測試函數(shù)獨(dú)立實(shí)驗(yàn)200次對改進(jìn)算法穩(wěn)定性性能進(jìn)行評價;③ 設(shè)置相同測試函數(shù)的停止標(biāo)準(zhǔn),對改進(jìn)算法收斂速度進(jìn)行評價．

2.1 算法收斂性評價

選用標(biāo)準(zhǔn)6個多峰多維度測試函數(shù)Ackley(在解空間中存在大量局部極小值點(diǎn))、Rastrigin(在解空間內(nèi)存在大量的正弦凸起極小值點(diǎn))、Shubert、Shekel、Styblinski-Tang、Powell對優(yōu)化算法收斂性能進(jìn)行評價,其測試函數(shù)表達(dá)式、變量輸入維度、變量輸入范圍、優(yōu)化算法適應(yīng)度尋優(yōu)次數(shù)如表2．

圖1為兩種優(yōu)化算法尋優(yōu)迭代圖．

從圖1(a)可以看出,經(jīng)過7代迭代后,RFCMA-ES算法的收斂性優(yōu)于CMA-ES算法;圖1(b,c)中,在F2、F3整個迭代尋優(yōu)過程中,RFCMA-ES算法性能始終優(yōu)于CMA-ES算法；圖(d～f)中,在算法迭代前期,RFCMA-ES算法與CMA-ES算收斂性時高時低,但是最終趨勢為RFCMA-ES算法收斂性優(yōu)于CMA-ES算法,即RFCMA-ES相較于原始算法更具有全局尋優(yōu)能力,不易陷入局部最優(yōu)．

表2 標(biāo)準(zhǔn)測試函數(shù)相關(guān)參數(shù)設(shè)定

圖1 優(yōu)化迭代曲線Fig.1 Iteration curve of optimization

2.2 算法穩(wěn)定性評價

RFCMA-ES收斂性能優(yōu)于CMA-ES算法,但優(yōu)化算法的尋優(yōu)結(jié)果具有一定偶然性，因此，將6個標(biāo)準(zhǔn)測試函數(shù)分別進(jìn)行200次獨(dú)立仿真實(shí)驗(yàn),分別記錄CMA-ES算法與RFCMA-ES算法的平均最小值、均值和方差值,如表3,具體利用200次重復(fù)實(shí)驗(yàn)結(jié)果的平均方差來驗(yàn)證RFCMA-ES算法較CMA-ES算法在尋優(yōu)穩(wěn)定性上是否有一定的提升．從表3可以看出,RFCMA-ES算法最終尋優(yōu)結(jié)果的均值、最小值和方差值均小于或等于CMA-ES算法,尤其針對像F1,F6這樣的在解空間中存在大量局部極小值的函數(shù),即RFCMA-ES算法的尋優(yōu)能力和穩(wěn)定性較原始算法有較大提高．

表3 標(biāo)準(zhǔn)測試函數(shù)重復(fù)200次的平均仿真結(jié)果

2.3 算法收斂速度評價

實(shí)驗(yàn)PC機(jī)處理器為Intel(R) Core(TM) i5-8265U CPU @1.6GHz, RAM為8GB．現(xiàn)在就設(shè)置相同停止條件下,對比兩種算法應(yīng)用于6種測試函數(shù)的200次平均尋優(yōu)時間．從表4給出尋優(yōu)時間可得,RFCMA-ES算法收斂速度較原始算法平均提高36.256%,即所提出的算法較原始算法在尋優(yōu)效率上有很大的提高．

表4 相同停止條件下標(biāo)準(zhǔn)測試函數(shù)重復(fù)200次的仿真結(jié)果

3 結(jié)論

(1) RFCMA-ES算法在原始CMA-ES算法全局步長的更新公式上融合了帶有隨機(jī)因子的差值項,該方法保證了種群個體在進(jìn)化迭代中彼此之間的差異性,一定程度上避免算法陷入局部最優(yōu),有效擴(kuò)大算法全局搜索范圍和提高其尋優(yōu)效率．

(2) 實(shí)驗(yàn)結(jié)果可證明,RFCMA-ES算法相比于原始CMA-ES算法具有更加優(yōu)越的性能,平均收斂速度提升36.256%,且有更強(qiáng)的全局搜索能力．

(3) RFCMA-ES在處理多維多峰問題表現(xiàn)出優(yōu)越性,將來進(jìn)一步探索該算法在新領(lǐng)域中的應(yīng)用,擴(kuò)展該算法的適用范圍,并且將該算法應(yīng)用到具體工業(yè)實(shí)際問題的解決中去．