楊　俊,魏靜萱

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

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

楊俊,魏靜萱

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

摘要差分進(jìn)化算法是一種有效求解全局優(yōu)化問題的方法,為進(jìn)一步提高求解精度,加快求解過程,文中提出一種梯度策略自適應(yīng)差分進(jìn)化算法。該算法是在差分進(jìn)化算法中加入梯度下降法,使其不僅有較好的全局搜索能力,且具有傳統(tǒng)優(yōu)化方法的快速局部搜索能力,因此具有較高搜索精度和較快的搜索過程。通過對CEC2005測試集中的1～14號測試函數(shù)進(jìn)行仿真實驗,并與SaDE,NSDE以及CMAES等算法實驗結(jié)果進(jìn)行了對比,結(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)實中的許多工程問題都可以通過轉(zhuǎn)化為全局優(yōu)化問題[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個變異算子策略集中在一起組成一個策略池,并記錄各個策略的歷史進(jìn)化情況,大概率選擇最優(yōu)策略。

SaDE 策略池中的4個算子策略分別是

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個不同的隨機(jī)個體。F是一個均值為0.5,方差為0.3服從正態(tài)分布的隨機(jī)數(shù),K為[0,1]的隨機(jī)數(shù)。

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

(5)

其中

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

對于策略算子池中,每一個算子中都有一個參數(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)前問題,則算法的效果就變差,且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對每一個個體概率性的選擇一個策略算子池中的策略進(jìn)行變異,其本身有4個策略,但均是隨機(jī)策略,本文在其中再加入一個策略算子——梯度搜索策略算子。梯度搜索策略算子利用梯度下降法的思想,對于函數(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)

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

(8)

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

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

2.2　算法偽代碼

GSaDE算法具體步驟:

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

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

步驟3WhileG

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

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

p1~p5均為0.2;

else

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

end if

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

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

ifG<=LP

CRm1~CRm5均為0.5;

else

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

CRm1~CRm5=median(CRMemory1~5);

end if

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

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

若個體選擇的是策略1~4,則利用對應(yīng)的式(1)~式(4),產(chǎn)生子代;若個體選擇的是策略5,則利用梯度搜索策略求解子代,詳見利用梯度搜索策略求解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ù)量級;

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

步驟4Q=P+Δp。

3實驗結(jié)果

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

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

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

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

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

[3]何堅勇.最優(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ī)學(xué)報,2006,29(4):670-675.

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

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

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

基金項目:國家自然科學(xué)基金資助項目(61203372)

收稿日期:2015- 05- 06

中圖分類號TP306.1

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

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

doi:10.16180/j.cnki.issn1007-7820.2016.01.007