梯度策略自適應(yīng)差分進(jìn)化算法

楊　俊,魏靜萱

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安　710071)

梯度策略自適應(yīng)差分進(jìn)化算法

楊俊,魏靜萱

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安710071)

摘要差分進(jìn)化算法是一種有效求解全局優(yōu)化問(wèn)題的方法,為進(jìn)一步提高求解精度,加快求解過(guò)程,文中提出一種梯度策略自適應(yīng)差分進(jìn)化算法。該算法是在差分進(jìn)化算法中加入梯度下降法,使其不僅有較好的全局搜索能力,且具有傳統(tǒng)優(yōu)化方法的快速局部搜索能力,因此具有較高搜索精度和較快的搜索過(guò)程。通過(guò)對(duì)CEC2005測(cè)試集中的1～14號(hào)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn),并與SaDE,NSDE以及CMAES等算法實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比,結(jié)果表明了該算法的有效性。

關(guān)鍵詞差分進(jìn)化算法;全局優(yōu)化;梯度下降法

Adaptive Differential Evolution Algorithm Based on Gradient Search Strategy

YANG Jun,WEI Jingxuan

(School of Computer Science and Technology,Xidian University,Xi’an 710071,China)

AbstractThe differential evolutionary algorithm is effective in solving global optimization.An improved adaptive differential evolution algorithm based on gradient search strategy is proposed to improve the accuracy of the solved solutions.The improved gradient search strategy is introduced into differential evolutionary algorithm to solve large scale optimization problems.The proposed algorithm is capable of both global and local search.The simulation results show that the proposed algorithm has better results compared to SaDE,NSDE and CMAES for benchmark functions 1~14 in CEC 2005.

Keywordsdifferential evolution algorithm;global optimization;gradient descent

現(xiàn)實(shí)中的許多工程問(wèn)題都可以通過(guò)轉(zhuǎn)化為全局優(yōu)化問(wèn)題[1],而全局優(yōu)化的目標(biāo)就是快速而準(zhǔn)確地求解出目標(biāo)函數(shù)在可行域內(nèi)的最優(yōu)值。求解方法一般分為兩類:第一類是傳統(tǒng)優(yōu)化算法,例如梯度下降法、牛頓法、共軛梯度法、單純形法等[2-3]。這一類的方法由于其利用了目標(biāo)函數(shù)導(dǎo)數(shù)等性質(zhì),因此收斂速度較快,但容易陷入局部最優(yōu),且適用的目標(biāo)函數(shù)范圍較小。第二類方法是差分進(jìn)化算法,其利用數(shù)學(xué)的方式模擬生物進(jìn)化,快速進(jìn)行一代一代的進(jìn)化,從而求得最優(yōu)值[4]。這類方法由于不利用目標(biāo)函數(shù)的性質(zhì),因此適應(yīng)范圍較廣,但卻具有一定的局限性,例如易陷入局部最優(yōu)且進(jìn)化后期速度較慢。為解決上述進(jìn)化算法的局限性,本文提出了一種改進(jìn)的全局優(yōu)化算法——梯度策略自適應(yīng)差分進(jìn)化算法(GSaDE)。該算法將差分進(jìn)化算法與梯度下降法進(jìn)行結(jié)合,使其不僅能夠擴(kuò)大搜索范圍,且能避免算法陷入局部最優(yōu),保證解的多樣性。

1自適應(yīng)策略差分進(jìn)化算法

自適策略應(yīng)差分進(jìn)化算法(Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization,SaDE)是在文獻(xiàn)[5~6]提出的,其主要思想是將效果較好的4個(gè)變異算子策略集中在一起組成一個(gè)策略池,并記錄各個(gè)策略的歷史進(jìn)化情況,大概率選擇最優(yōu)策略。

SaDE 策略池中的4個(gè)算子策略分別是

DE/rand/1/bin

(1)

DE/rand-to-best/2/bin

(2)

DE/rand/2/bin

(3)

DE/current-to-rand/1

Ui,G=Xi,G+K·(Xr1,G-Xi,G)+F(Xr2,G-Xr3,G)

(4)

其中,r1~r5是隨機(jī)數(shù),代表5個(gè)不同的隨機(jī)個(gè)體。F是一個(gè)均值為0.5,方差為0.3服從正態(tài)分布的隨機(jī)數(shù),K為[0,1]的隨機(jī)數(shù)。

SaDE的具體過(guò)程是在進(jìn)化初期,進(jìn)行LP代的學(xué)習(xí),學(xué)習(xí)規(guī)則是:每個(gè)策略算子k均以1/4的概率被選中,且利用兩個(gè)矩陣(成功矩陣nsk和失敗矩陣nfk)來(lái)存儲(chǔ)相關(guān)信息,供后續(xù)計(jì)算自適應(yīng)選擇。在進(jìn)化LP代后,算法利用式(1),計(jì)算每一代中每一個(gè)算子被選中的概率

(5)

其中

式中,k表示策略池中第k個(gè)策略;G表示當(dāng)前代數(shù);LP表示學(xué)習(xí)代數(shù);g=G-LP,nsk,g表示第g代策略k成功進(jìn)化的個(gè)體個(gè)數(shù);nfk,g表示第g代策略k失敗進(jìn)化的個(gè)體數(shù),為避免成功率為0的出現(xiàn),ε設(shè)為一個(gè)較小的正數(shù),本文中令ε=0.01。

對(duì)于策略算子池中,每一個(gè)算子中都有一個(gè)參數(shù)CR,用于控制算子種群變異率的大小。SaDE中也利用矩陣CRMemory1~CRMemory4自適應(yīng)的調(diào)整參數(shù)CR。具體方法如文獻(xiàn)[5]。

可以看出,SaDE算法采用自適應(yīng)的方式進(jìn)行學(xué)習(xí),但這樣做使得策略算子池中所擁有的策略成為了關(guān)鍵,一旦策略算子池中的策略均不能較好的求解當(dāng)前問(wèn)題,則算法的效果就變差,且SaDE算法中策略算子池中的策略均是隨機(jī)策略,其適用的目標(biāo)函數(shù)范圍雖廣,卻并未較好地利用目標(biāo)函數(shù)的性質(zhì)。

2梯度策略自適應(yīng)差分進(jìn)化算法

2.1　梯度搜索策略算子

為避免上述局限性,本文提出了梯度策略自適應(yīng)差分進(jìn)化算法,該算法是在原SaDE算法的基礎(chǔ)上引入了梯度搜索策略算子,其利用了目標(biāo)函數(shù)的性質(zhì),從而使算法具有較好的搜索能力和穩(wěn)定性。

在SaDE算法的步驟3對(duì)每一個(gè)個(gè)體概率性的選擇一個(gè)策略算子池中的策略進(jìn)行變異,其本身有4個(gè)策略,但均是隨機(jī)策略,本文在其中再加入一個(gè)策略算子——梯度搜索策略算子。梯度搜索策略算子利用梯度下降法的思想,對(duì)于函數(shù)F(X),若在點(diǎn)a處可微且有定義,則函數(shù)在a點(diǎn)沿著梯度相反的方向下降最快。首先求出函數(shù)在初始點(diǎn)a的梯度grad(p),隨后-grad(P)沿著方向,向前前進(jìn)一小步,從而得到進(jìn)化子代。

函數(shù)F(X)在P點(diǎn)的梯度為

(6)

由于目標(biāo)函數(shù)是任何可能的函數(shù),不一定可微,因此偏導(dǎo)數(shù)的求解不能直接利用求導(dǎo)公式求解,文獻(xiàn)[7]提出了利用導(dǎo)數(shù)的定義進(jìn)行求解。根據(jù)導(dǎo)數(shù)的定義,函數(shù)在某一點(diǎn)的導(dǎo)數(shù)等于函數(shù)上某一點(diǎn)函數(shù)值的變化量與自變量變化量比值。若定義P點(diǎn)坐標(biāo)為(x,y,…,z),因此函數(shù)F(X)在P點(diǎn)的x軸的偏導(dǎo)數(shù)為

(7)

其中,Δ稱為梯度步長(zhǎng),其值為較小的數(shù),在實(shí)驗(yàn)中Δ=0.2。同理可求得

(8)

將式(7)和式(8)帶入式(6)中便可求得函數(shù)F(X)在P點(diǎn)的梯度[7]。

值得注意的是,當(dāng)P點(diǎn)的梯度相當(dāng)大時(shí),即使Δp=-0.01×grad(P)時(shí)也很大,這與前進(jìn)一小步的要求不符。文中令grad(p)整體縮小E倍,記作grad(P)*,其中E表示grad(P)中的最大的數(shù)量級(jí),令Δp為區(qū)間(-μ×grad(P)*,0)之內(nèi)的一個(gè)隨機(jī)數(shù),其中μ稱為梯度隨機(jī)因子,0<μ<1,實(shí)驗(yàn)中μ=0.5。

2.2　算法偽代碼

GSaDE算法具體步驟:

步驟1隨機(jī)初始化種群;

步驟2計(jì)算初始種群適應(yīng)值;

步驟3WhileG

2.1/*計(jì)算策略1~5的選擇概率p1~p5*/

ifG<=LP/*LP表示學(xué)習(xí)代數(shù)*/

p1~p5均為0.2;

else

根據(jù)式(5)計(jì)算p1~p5;

end if

2.2/*計(jì)算策略1~5的參數(shù)CR和F*/

對(duì)于種群中每一個(gè)個(gè)體,F均為符合N(0.5,0.3)的隨機(jī)數(shù);

ifG<=LP

CRm1~CRm5均為0.5;

else

/*CRMemory1~5為存儲(chǔ)5種策略歷史CR值的矩陣*/

CRm1~CRm5=median(CRMemory1~5);

end if

對(duì)種群中的每個(gè)個(gè)體根據(jù)式CR=Normrnd(CRmk,0.1)計(jì)算其參數(shù)CR

2.3/*對(duì)每一個(gè)個(gè)體,依照選擇概率隨機(jī)選擇策略進(jìn)行變異,產(chǎn)生子代*/

若個(gè)體選擇的是策略1~4,則利用對(duì)應(yīng)的式(1)~式(4),產(chǎn)生子代;若個(gè)體選擇的是策略5,則利用梯度搜索策略求解子代,詳見(jiàn)利用梯度搜索策略求解P點(diǎn)子代Q步驟;

2.4選擇出成功進(jìn)化的子代與失敗進(jìn)化的父代組成新的一代種群;

2.5將本次的進(jìn)化情況記錄在成功和失敗矩陣ns,nf,將參數(shù)CR記錄在CRMemory1~5;

2.6G=G+1;

步驟4輸出當(dāng)前種群最優(yōu)解。

利用梯度搜索策略求解P點(diǎn)子代Q步驟:

步驟1將式(7)~式(10)帶入式(6)求解grad(p);

步驟2grad(P)*=grad(P)/E,其中E為grad(p)中的最大的數(shù)量級(jí);

步驟3Δp=(-μ×grad(P)*,0),梯度隨機(jī)因子μ=0.5;

步驟4Q=P+Δp。

3實(shí)驗(yàn)結(jié)果

為進(jìn)一步驗(yàn)證GSaDE的性能,文中選擇CEC2005基準(zhǔn)測(cè)試集1~14號(hào)測(cè)試函數(shù)進(jìn)行測(cè)試,這些函數(shù)大部分是經(jīng)典測(cè)試函數(shù)的旋轉(zhuǎn)、平移以及復(fù)合,能夠較好地測(cè)試算法的性能,這些函數(shù)可在文獻(xiàn)[8]中找到。文中在Matlab 2008a中進(jìn)行實(shí)驗(yàn),對(duì)所有的測(cè)試函數(shù)測(cè)試25次,求得25次實(shí)驗(yàn)的平均值。為了能反應(yīng)算法的有效性,文中將GSaDE與SaDE,鄰域控制差分演化算法(NSDE)以及協(xié)方差自適應(yīng)演化策略(CMAES)的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比,為保證公平起見(jiàn),所有的算法都將使用相同的適應(yīng)度評(píng)估次數(shù),即3.0×105,作為算法終止條件。SaDE和NSDE,CMAES的實(shí)驗(yàn)結(jié)果分別取自文獻(xiàn)[6,9]。

GSaDE參數(shù)如下:種群規(guī)模NP=100,維數(shù)D=30,學(xué)習(xí)代數(shù)LP=50,終止進(jìn)化代數(shù)GMAX=3 000代,MAX_FES=100×3 000,梯度步長(zhǎng)Δ=0.2,梯度隨機(jī)因子μ=0.5。實(shí)驗(yàn)結(jié)果如表1~表3所示。

從表1可看出,對(duì)測(cè)試函數(shù)1~5,GSaDE算法的效果要略好于其他3個(gè)算法。GSaDE、SaDE以及NSDE均準(zhǔn)確找到了函數(shù)1的全局最優(yōu)點(diǎn);GSaDE對(duì)于函數(shù)2的實(shí)驗(yàn)結(jié)果要明顯優(yōu)于其他的算法;對(duì)于測(cè)試函數(shù)3和5,GSaDE、SaDE以及NSDE的測(cè)試結(jié)果基本相當(dāng)。對(duì)于CMAES算法,其測(cè)試結(jié)果與其他算法的差異性較大,其在測(cè)試函數(shù)3和5上明顯優(yōu)于其他算法;這主要是因這兩類算法具有本質(zhì)的設(shè)計(jì)區(qū)別,對(duì)于問(wèn)題的搜索偏向明顯不同。

表1　CEC2005函數(shù)1~5實(shí)驗(yàn)結(jié)果

如表2和表3所示,GSaDE算法效果要更優(yōu)于其他算法。GSaDE在函數(shù)6、7、9上要明顯優(yōu)于SaDE和NSDE,并且準(zhǔn)確找到了函數(shù)9的全局最優(yōu)點(diǎn)。對(duì)于8、11、13函數(shù),GSaDE與SaDE和NSDE的實(shí)驗(yàn)結(jié)果基本相當(dāng)。而CMAES算法也只是在函數(shù)6、7上具有優(yōu)勢(shì)。

表2　CEC2005函數(shù)6~10實(shí)驗(yàn)結(jié)果

表3　CEC2005函數(shù)11~14實(shí)驗(yàn)結(jié)果

綜上分析,發(fā)現(xiàn)GSaDE算法在基準(zhǔn)測(cè)試集CEC2005上的整體性能要優(yōu)于其他的比較算法。對(duì)于具有不同特點(diǎn)的測(cè)試函數(shù)都能夠進(jìn)行高效率的求解,這表明GSaDE算法不受求解問(wèn)題的限制,具有較強(qiáng)的通用性。當(dāng)然GSaDE算法在求解CEC2005測(cè)試集中某些函數(shù),例如函數(shù)10、12也存在問(wèn)題,這是由于梯度下降策略算子的加入,使得GSaDE的局部搜索能力加強(qiáng),但在進(jìn)化后期的廣度搜索能力卻得到了削弱,因此可能無(wú)法跳出一些局部最優(yōu)點(diǎn)。

4結(jié)束語(yǔ)

本文在SaDE算法的基礎(chǔ)上對(duì)算子池進(jìn)行了優(yōu)化,在其中加入梯度下降策略算子,更好地利用了目標(biāo)函數(shù)的特點(diǎn),提升算法的全局搜索能力和適應(yīng)性,并將其命名為GSaDE。經(jīng)過(guò)對(duì)CEC2005測(cè)試集中的1~14號(hào)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)并與SaDE,NSDE以及CMAES等算法實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比,表明GSaDE算法搜索能力較強(qiáng),效率較高,對(duì)解決高維全局優(yōu)化問(wèn)題具有明顯優(yōu)勢(shì)。在后續(xù)工作中,文中將改進(jìn)本文算法,使之能更好地適用于復(fù)雜的多峰函數(shù)問(wèn)題。

參考文獻(xiàn)

[1]趙春暉.基于遺傳算法的寬帶加權(quán)子空間擬合測(cè)向算法[J].電子學(xué)報(bào),2004,32(9):1487-1490.

[2]李元科.工程最優(yōu)化設(shè)計(jì)[M].北京:清華大學(xué)出版社,2006.

[3]何堅(jiān)勇.最優(yōu)化方法[M].北京:清華大學(xué)出版社,2007.

[4]玄光男.遺傳算法與工程優(yōu)化[M].于歆杰,譯.北京:清華大學(xué)出版,2004.

[5]QinAK,SuganthanPN.Self-Adaptivedifferentialevolutionalgorithmfornumericaloptimization[C].Edinburgh,Scotland:ProcedingofIEEECongressEvolutionComputer,2005.

[6]QinAK,HuangVL,SuganthanPN.Differentialevolutionalgorithmwithstrategyadaptationforglobalnumericaloptimization[J].IEEETransactionsonEvolutionaryComputation,2009,13(2):398-417.

[7]王宇平,劉大蓮.基于平滑技術(shù)和一維搜索的全局優(yōu)化進(jìn)化算法及其收斂性[J].計(jì)算機(jī)學(xué)報(bào),2006,29(4):670-675.

[8]SuganthanPN,HansenN,LiangJJ,etal.Problemdefinitionsandevaluationcriteriaforthe[C].Hefei:CEC2005SpecialSessiononReal-ParameterOptimization,2005.

[9]楊振宇.基于自然計(jì)算的實(shí)值優(yōu)化算法與應(yīng)用研究[D].合肥:中國(guó)科技大學(xué),2010.

作者簡(jiǎn)介:魏靜萱(1981—),女,博士,副教授,碩士生導(dǎo)師。研究方向:智能計(jì)算。楊俊(1992—),男,碩士研究生。研究方向:智能計(jì)算。

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61203372)

收稿日期:2015- 05- 06

中圖分類號(hào)TP306.1

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)01-025-04

doi:10.16180/j.cnki.issn1007-7820.2016.01.007