自適應(yīng)協(xié)方差矩陣進(jìn)化策略算法

程沙沙

[摘 要] 自適應(yīng)協(xié)方差矩陣進(jìn)化策略（CMA-ES）算法是Nikolaus Hansen等人提出的一種新的進(jìn)化算法，通過模擬自然界生物進(jìn)化過程，達(dá)到尋優(yōu)目的。多個(gè)測試函數(shù)結(jié)果表明，該算法具有全局性能好、尋優(yōu)效率高的特點(diǎn)，為解決高計(jì)算代價(jià)復(fù)雜工程優(yōu)化問題的求解提供了新的途徑。

[關(guān)鍵詞] 優(yōu)化算法；自適應(yīng)協(xié)方差矩陣進(jìn)化策略算法；測試函數(shù)

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2014 . 12. 057

[中圖分類號] TP301.6 [文獻(xiàn)標(biāo)識碼] A [文章編號] 1673 - 0194（2014）12- 0091- 03

本文擬通過測試基準(zhǔn)函數(shù)來研究CMA-ES算法的全局性和高效性。

1 CMA-ES算法基本原理

CMA-ES算法通過動態(tài)的步長參數(shù)σ和動態(tài)的正定協(xié)方差矩陣C來引導(dǎo)種群的突變進(jìn)化方向，其基本方程如下：

xk（g+1）=m（g）+σ（g）N（0，C（g））（1）

式中，xk（g+1）∈Rn是g+1代中的第k個(gè)個(gè)體；m（g）是g代種群適應(yīng)度的平均值；σ（g）是g代種群進(jìn)化的步長；C（g）是第g代種群進(jìn)化的協(xié)方差矩陣。

具體實(shí)施步驟如下：

步驟1 啟動Matlab環(huán)境下的優(yōu)化程序，設(shè)置CMA-ES算法相關(guān)參數(shù)。

步驟2 從給定的或者隨機(jī)產(chǎn)生的一個(gè)初始搜索點(diǎn)出發(fā)，以該初始點(diǎn)為搜索中心，按照一定的概率密度隨機(jī)生成第一代種群（λ個(gè)），并評價(jià)該種群中所有個(gè)體的適應(yīng)度。

步驟3 根據(jù)適應(yīng)度大小選擇適應(yīng)度較好的μ個(gè)個(gè)體組成新的種群來更新進(jìn)化策略參數(shù)σ和C。利用進(jìn)化策略參數(shù)調(diào)整下一代種群的進(jìn)化方向，從而進(jìn)行突變生成下一代種群。

步驟4 對當(dāng)前種群所有個(gè)體進(jìn)行適應(yīng)度評價(jià)，根據(jù)適應(yīng)度大小選出最優(yōu)解，對當(dāng)前最優(yōu)解進(jìn)行收斂條件判斷。如滿足收斂條件則退出計(jì)算，當(dāng)前最優(yōu)解即為全局最優(yōu)解；否則，返回步驟3。

受篇幅限制，CMA-ES算法基本原理詳見文獻(xiàn)。

2 算法測試

評定算法的優(yōu)劣需要從算法的全局搜索能力和搜索效率兩個(gè)方面進(jìn)行研究。傳統(tǒng)的優(yōu)化算法尋優(yōu)效率高，但是與初始點(diǎn)的選擇很有關(guān)系，如果選擇不當(dāng)，很有可能找不到最優(yōu)解或陷入局部最優(yōu)。現(xiàn)代仿生類的優(yōu)化算法全局性能好，能找到全局最優(yōu)解，但是尋優(yōu)過程中需要大量的函數(shù)評價(jià)次數(shù)。

國內(nèi)外常采用的一些典型的測試基準(zhǔn)函數(shù)來判斷算法的優(yōu)劣。本文中采用的函數(shù)及其表達(dá)式見表1。表1中的函數(shù)特征：U表示Unimodal，M表示Multimodal；S表示Separable，N表示Non-Separable。

在測試環(huán)境中，計(jì)算機(jī)配置為intel 2.40GHz處理器和2G內(nèi)存，操作系統(tǒng)為Windows XP，計(jì)算軟件采用了Matlab 2008。

2.1 全局搜索能力測試

全局搜索能力是指函數(shù)能夠找到較高精度的最優(yōu)解的能力。隨著維數(shù)的增加，函數(shù)越不容易搜索到全局最優(yōu)解。因此從不同維數(shù)測試函數(shù)的全局搜索能力是很有必要的。

CMA-ES算法的參數(shù)設(shè)置如下：種群數(shù)λ=4+[3ln n]；搜索空間的下限為lb=[-4，4，…，-4]，搜索空間的上限為ub=[4，4，…，4]；函數(shù)Sphere、Schwefel、Cigar、Tablet、Elli的初始步長設(shè)定為1，函數(shù)Rosen的初始步長設(shè)定為0.1；維數(shù)分別取2、5、10、20、30；收斂條件設(shè)定函數(shù)精度為10-10。每種函數(shù)在每種維數(shù)下分別測試10次，取最好的結(jié)果，見表2。

從表2可知，CMA-ES算法具有很好的搜索性能，能夠達(dá)到比較高的精度。對不同復(fù)雜的函數(shù)，CMA-ES算法都能找到最優(yōu)解，證明了CMA-ES算法的全局性能好。

2.2 尋優(yōu)效率測試

函數(shù)的尋優(yōu)效率是指函數(shù)尋找到全局最優(yōu)解所需要的函數(shù)評價(jià)次數(shù)，提高尋優(yōu)效率也就是要降低函數(shù)評價(jià)次數(shù)。維數(shù)的不同也會對函數(shù)的尋優(yōu)效率有影響。本文以簡單的球形函數(shù)Sphere為例，對比遺傳算法（簡稱GA）和粒子群算法（簡稱PSO），來研究CMA-ES算法的尋優(yōu)效率。

CMA-ES算法的參數(shù)設(shè)置如下：種群數(shù)λ=4+[3ln n]，初始步長為0.5（ub-lb），初始搜索點(diǎn)為X=lb+0.3（ub-lb）；

GA算法的參數(shù)設(shè)置為：變異概率Pm=0.2，交叉概率Pc=0.8，初始搜索點(diǎn)與CMA-ES算法相同；

PSO算法參數(shù)設(shè)置：學(xué)習(xí)因子C1=C2=2.0，種群數(shù)分別取10、20、30。

3種算法取相同的搜索空間：下限為lb=[-4，-4，…，-4]，上限為ub=[4，4，…，4]；維數(shù)分別取2、4、6、8、10；收斂條件設(shè)定函數(shù)精度為10-3。每種函數(shù)在不同參數(shù)和維數(shù)下分別測試10次，取最好的結(jié)果，如圖1。

從圖1可知，隨著維數(shù)的增加，函數(shù)評價(jià)次數(shù)也相應(yīng)增加。同時(shí)，CMA-ES算法在各個(gè)維數(shù)上的函數(shù)評價(jià)次數(shù)明顯小于PSO算法和GA算法，在高維數(shù)上表現(xiàn)更為明顯。由此說明CMA-ES算法的尋優(yōu)效率高。

3 結(jié) 語

本文通過采用典型測試基準(zhǔn)函數(shù)對CMA-ES算法在全局搜索能力和尋優(yōu)效率兩個(gè)方面性能進(jìn)行研究。算例結(jié)果表明，CMA-ES算法具有全局性能好，尋優(yōu)效率高的特點(diǎn)。本文方法對于高維度復(fù)雜的工程優(yōu)化問題的適應(yīng)性問題需進(jìn)一步研究。

主要參考文獻(xiàn)

[1]楊維，李岐強(qiáng). 粒子群優(yōu)化算法綜述[J].中國工程科學(xué)，2004，6（5）： 87-94.

[2]武振興.桁架結(jié)構(gòu)優(yōu)化的進(jìn)化策略與高斯過程方法[D]. 南寧：廣西大學(xué)，2011.