自適應(yīng)調(diào)整控制參數(shù)的差異演化算法

武志峰，黃厚寬

（1.天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津300222；2.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

0 引 言

差異演化 （differential evolution，DE）作為一種基于種群之間差異的演化算法，自1995年Storn和Price提出之后，就在數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)參數(shù)訓(xùn)練、濾波器設(shè)計(jì)、聚類(lèi)分析、機(jī)器人路徑規(guī)劃等領(lǐng)域得到了廣泛的應(yīng)用［1－9］。

差異演化特別適合于求解非凸、多峰、非線性的函數(shù)優(yōu)化問(wèn)題。但和其它演化算法一樣，差異演化算法控制參數(shù)的選擇也是一個(gè)難題，不同的參數(shù)對(duì)算法的性能會(huì)產(chǎn)生較大的影響。差異演化算法中有3個(gè)主要參數(shù)：種群規(guī)模NP，縮放因子F和交叉因子CR。在原始差異演化算法中，這3個(gè)參數(shù)是保持不變的。對(duì)如何確定算法較好的控制參數(shù)人們?nèi)匀恢跎伲?0］。對(duì)給定的具體優(yōu)化問(wèn)題，用戶(hù)依然需要通過(guò)手工設(shè)置進(jìn)行多次實(shí)驗(yàn)來(lái)確定最優(yōu)的控制參數(shù)［11］。為克服手工設(shè)置控制參數(shù)帶來(lái)的問(wèn)題，人們提出了許多差 異 演 化 算 法 的 控 制 參 數(shù) 自 適 應(yīng) 技 術(shù)［10，12－13］。文 獻(xiàn)［10］提出一種調(diào)整控制參數(shù)的算法 （FADE算法），利用模糊邏輯動(dòng)態(tài)調(diào)整縮放因子F和交叉因子CR。J.Brest等在文獻(xiàn) ［12］中提出一種新的自適應(yīng)算法 （jDE算法）。該方法對(duì)種群中的每個(gè)個(gè)體都采用各自不同的F和CR生成新個(gè)體，同時(shí)各F和CR也都隨著種群的進(jìn)化而進(jìn)化。SaDE算法是文獻(xiàn) ［13］提出的一種自適應(yīng)算法。它利用種群的學(xué)習(xí)經(jīng)歷自動(dòng)選擇學(xué)習(xí)策略并設(shè)置合適的控制參數(shù)。文獻(xiàn) ［14］提出一種基于PSO學(xué)習(xí)策略的自適應(yīng)差異演化算法。在眾多的自適應(yīng)算法中，自適應(yīng)技術(shù)一般主要應(yīng)用于F和CR這兩個(gè)參數(shù)。這主要是因?yàn)橄鄬?duì)于種群規(guī)模NP，差異演化算法的效率和魯棒性對(duì)縮放因子F和交叉因子CR更敏感［15］。

本文提出一種自適應(yīng)調(diào)整縮放因子F和交叉因子CR的方法，使得參數(shù)F和CR能夠自動(dòng)適應(yīng)不同的優(yōu)化問(wèn)題，從而解決手工設(shè)置控制參數(shù)的不便。同時(shí)利用交叉操作生成雙子代個(gè)體與父代個(gè)體競(jìng)爭(zhēng)形成新一代種群，從而加快了算法的收斂。對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明該算法無(wú)論在最優(yōu)解質(zhì)量和收斂速度上都優(yōu)于相關(guān)算法。

1 DE算法

差異演化是一種利用種群之間的差異推動(dòng)種群演化的算法。差異演化算法的整體結(jié)構(gòu)與遺傳算法類(lèi)似，但其個(gè)體編碼采用實(shí)數(shù)形式與遺傳算法的主要區(qū)別是其變異操作是基于個(gè)體間的差異向量進(jìn)行的。本質(zhì)上差異演化是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。

首先，在n維空間里隨機(jī)產(chǎn)生滿(mǎn)足約束條件的NP個(gè)染色體 （個(gè)體）構(gòu)成一代種群，其中NP為種群規(guī)模。第t代的第i個(gè)染色體可表示為Xi（t）＝ （xi1（t），xi2（t），xi3（t），...，xin（t））。然后對(duì)種群中的各個(gè)個(gè)體進(jìn)行變異生成變異向量hi。在差異演化算法中，常用的幾種變異方式如下

其中xp1，xp2，xp3，xp4，xp5是從種群中隨機(jī)選擇的個(gè)體，且 （i≠p1≠p2≠p3≠p4≠p5），F(xiàn)稱(chēng)為縮放因子，取值在［0，2］之間，一般小于1，通常取0.5。

生成變異向量hi后，為增加種群的多樣性，變異向量與原目標(biāo)向量進(jìn)行交叉操作生成試驗(yàn)向量vi

其中rndij是在 ［0，1］之間的隨機(jī)小數(shù)，CR為交叉概率，rand（i）為 ［1，n］之間的隨機(jī)整數(shù)，這種交叉策略可確保xi（t＋1）至少有一分量由xi（t）的相應(yīng)分量貢獻(xiàn)。

最后，計(jì)算試驗(yàn)向量的適應(yīng)度，并與目標(biāo)向量的適應(yīng)度進(jìn)行比較，擇優(yōu)生成下一代成員，如下式所示 （以求最小值為例）

與其它演化算法一樣，DE算法的搜索性能取也決于算法全局探索和局部開(kāi)發(fā)能力的平衡，而這在很大程度上依賴(lài)于算法的控制參數(shù)的選取，如種群規(guī)模、縮放因子和交叉因子等。

2 自適應(yīng)調(diào)整控制參數(shù)的DE算法 （SelfDE）

2.1 算法原理

對(duì)于基本DE算法而言，在種群的整個(gè)進(jìn)化過(guò)程中其所有個(gè)體對(duì)應(yīng)的縮放因子F和交叉因子CR都是固定不變的。這雖然可以減少算法需要設(shè)置的參數(shù)，但卻在一定程度上影響了算法的效率。因?yàn)閷?duì)不同的優(yōu)化問(wèn)題，其對(duì)應(yīng)的縮放因子F和交叉因子CR也可能不同。因而，自動(dòng)調(diào)整縮放因子F和交叉因子CR，以適應(yīng)不同的優(yōu)化問(wèn)題是非常必要的。文獻(xiàn) ［12］提出一種自動(dòng)調(diào)整參數(shù)的方法，通過(guò)調(diào)整概率實(shí)現(xiàn)對(duì)參數(shù)F和CR的自動(dòng)調(diào)整。但在該方法中，并未利用個(gè)體適應(yīng)度作為參數(shù)調(diào)整的決策依據(jù)，調(diào)整具有一定的盲目性。我們提出利用個(gè)體的適應(yīng)度作為參數(shù)調(diào)整的決策依據(jù)，并結(jié)合一定的調(diào)整概率對(duì)F和CR進(jìn)行自適應(yīng)調(diào)整。即針對(duì)種群中不同個(gè)體采用相互獨(dú)立的F和CR值，并使其在進(jìn)化過(guò)程中按如下公式自動(dòng)調(diào)整

其中，rnd1，rnd2，rnd3，rnd4是 ［0，1］之間的隨機(jī)數(shù)。f（vi（t）），f（xi（t））分別表示以Fi，t，CRi，t生成的新個(gè)體的適應(yīng)度值和當(dāng)前個(gè)體的適應(yīng)度值。τ1，τ2表示調(diào)整F和CR的概率。由上式可知，對(duì)于種群中的一個(gè)個(gè)體，當(dāng)用相應(yīng)的Fi，t和CRi，t生成的新個(gè)體的適應(yīng)度比其當(dāng)前適應(yīng)度更差，并且隨機(jī)數(shù)小于給定的調(diào)整概率時(shí)，重新調(diào)整新縮放因子和交叉因子，否則保持原來(lái)的F和CR值不變。這種調(diào)整策略一方面可以保證當(dāng)原F和CR的值有效 （即用該參數(shù)值生成的新個(gè)體適應(yīng)度優(yōu)于該個(gè)體當(dāng)前適應(yīng)度）時(shí)，保留原F和CR值到下一代不變；另一方面，如果原F和CR的值無(wú)效 （即用該參數(shù)生成的新個(gè)體適應(yīng)度劣于該個(gè)體當(dāng)前適應(yīng)度），則由調(diào)整概率決定是否對(duì)該個(gè)體對(duì)應(yīng)的F和CR進(jìn)行調(diào)整，從而在一定程度上有利于增加種群多樣性。對(duì)于調(diào)整概率的取值，在實(shí)驗(yàn)中我們?nèi)≈禐棣?＝τ2＝0.1。

另外，在基本DE算法中，只利用交叉操作生成的一個(gè)新個(gè)體與父代個(gè)體競(jìng)爭(zhēng)形成的下一代個(gè)體。但實(shí)際上和遺傳算法類(lèi)似，差異演化的交叉操作可以生成兩個(gè) （一對(duì)）新個(gè)體，每個(gè)個(gè)體都包含父代個(gè)體的部分基因，其交叉操作如下式所示。但在基本DE算法中只用一個(gè)新個(gè)體參與生成子代，這必然會(huì)丟失某些有效信息，從而導(dǎo)致算法陷入局部最優(yōu)或使其收斂速度變慢。為此，我們提出了雙子代競(jìng)爭(zhēng)模型［16］，即利用交叉操作生成兩個(gè)新個(gè)體vi，ui，然后由這兩個(gè)新個(gè)體與父代個(gè)體競(jìng)爭(zhēng)形成子代個(gè)體。同時(shí)，為了減少對(duì)個(gè)體適應(yīng)度的評(píng)估次數(shù)，和基本DE算法一樣，首先用新個(gè)體vi與父代個(gè)體競(jìng)爭(zhēng)，如果vi的適應(yīng)度值優(yōu)于父代個(gè)體則直接用其作為子代個(gè)體，另一個(gè)新個(gè)體就不必計(jì)算；否則再以新個(gè)體ui與父代個(gè)體競(jìng)爭(zhēng)

2.2 SelfDE算法

SelfDE算法描述如下：

步驟1 隨機(jī)初始化第1代種群；

步驟2 對(duì)種群中的每個(gè)個(gè)體i執(zhí)行如下操作：

（1）隨機(jī)選擇3個(gè)互不相同的個(gè)體；

（2）對(duì)個(gè)體i執(zhí)行 ‘rand/1’型變異操作生成變異向量hi；

（3）利用兩子代生成策略形成兩個(gè)試驗(yàn)向量vi，ui；

（4）對(duì)試驗(yàn)向量vi，ui與目標(biāo)向量xi執(zhí)行選擇操作生成下一代個(gè)體；

（5）按2.1節(jié)給出的公式動(dòng)態(tài)調(diào)整個(gè)體i對(duì)應(yīng)的F和CR值；

步驟3 若不滿(mǎn)足結(jié)束條件，轉(zhuǎn)步驟2；

步驟4 輸出結(jié)果。

3 實(shí)驗(yàn)仿真與分析

為全面驗(yàn)證SelfDE算法的性能，我們從最優(yōu)解質(zhì)量和收斂速度兩方面對(duì)其進(jìn)行測(cè)試，并與已有的幾種差異演化改進(jìn)算法分別進(jìn)行了比較。

3.1 SelfDE與jDE、FADE算法的比較

為檢驗(yàn)SelfDE算法的最優(yōu)解性能，選擇文獻(xiàn) ［14］中的9個(gè)常用函數(shù)對(duì)算法進(jìn)行測(cè)試，并與jDE算法［12］和FADE算法［10］的結(jié)果比較。測(cè)試函數(shù)如表1所示，其中n表示自變量維數(shù)，S表示自變量取值范圍，fmin表示函數(shù)的最優(yōu)解。函數(shù)F1－F7是高維問(wèn)題。其中F1，F(xiàn)2是單峰函數(shù)，F(xiàn)3是不連續(xù)函數(shù)，F(xiàn)4為帶噪聲的4次函數(shù)，F(xiàn)5－F7是多峰函數(shù)。F8，F(xiàn)9是有局部極小點(diǎn)的低維函數(shù)。實(shí)驗(yàn)中SelfDE算法的參數(shù)設(shè)置與文獻(xiàn) ［14］中的jDE算法設(shè)置相同：D＝50，NP＝10×D，最大迭代次數(shù)分別取F1，F(xiàn)3，F(xiàn)4，F(xiàn)6，F(xiàn)7為5000，F(xiàn)2為7000，F(xiàn)5為10000，F(xiàn)8為100，F(xiàn)9為50。

實(shí)驗(yàn)結(jié)果如表2所示，其中mean best為平均最優(yōu)解，std－dev為標(biāo)準(zhǔn)差。表2中SelfDE的結(jié)果都取100次獨(dú)立運(yùn)行的平均值，jDE和FADE算法的結(jié)果取自文獻(xiàn) ［14］。

從表2可見(jiàn)，對(duì)9個(gè)測(cè)試函數(shù)，SelfDE算法所獲得的最優(yōu)解值都明顯優(yōu)于jDE和FADE算法。同時(shí)，值得說(shuō)明的是在實(shí)驗(yàn)中，τ1，τ2的取值均為0.1。通過(guò)多次實(shí)驗(yàn)，我們發(fā)現(xiàn)τ1，τ2的取值對(duì)函數(shù)的最優(yōu)結(jié)果影響是不明顯的。

表1 測(cè)試函數(shù)F1－F9

表2 函數(shù)F1－F9的運(yùn)行結(jié)果

3.2 SelfDE與DDE、jDE、MPDE及DE算法的比較

為進(jìn)一步檢驗(yàn)SelfDE算法的收斂速度，對(duì)文獻(xiàn) ［17］中的5個(gè)常用測(cè)試函數(shù)，分別用DDE算法［18］、jDE算法［12］、MPDE算法［17］及基本DE算法對(duì)其進(jìn)行比較實(shí)驗(yàn)。這5個(gè)測(cè)試函數(shù)如表3所示。其中，F(xiàn)1，F(xiàn)2為單峰函數(shù)，只有一個(gè)極小值。F3，F(xiàn)4，F(xiàn)5為多峰函數(shù)，都有多個(gè)局部極小值，特別是F5在全局極小點(diǎn)附近有無(wú)限多的次全局極小點(diǎn)，一般算法很難得到最優(yōu)解。在實(shí)驗(yàn)中，除F5為2維變量外，其它4個(gè)函數(shù)都取30維變量進(jìn)行測(cè)試。

為使算法運(yùn)行結(jié)果可以相互比對(duì)，所有算法參數(shù)設(shè)置與文獻(xiàn) ［17］相同：

（1）對(duì)各函數(shù)統(tǒng)一設(shè)置種群規(guī)模NP＝100。

（2）對(duì) DE、DDE、MPDE設(shè)置F＝0.5，CR＝0.9。jDE和SelfDE算法F和CR自適應(yīng)調(diào)節(jié)。

（3）在MPDE算法中，根據(jù)文獻(xiàn) ［17］設(shè)置MP的值，對(duì)F1，F(xiàn)3，F(xiàn)4設(shè) MP＝0.1，對(duì)F2設(shè) MP＝0.05，F(xiàn)5設(shè)MP＝0.008。

實(shí)驗(yàn)結(jié)果如表4～表8所示，各算法的結(jié)果均為獨(dú)立運(yùn)行50次的平均值。

從表4～表8的實(shí)驗(yàn)結(jié)果可以看出，SelfDE算法對(duì)F1－F4這4個(gè)高維測(cè)試函數(shù)都取得了很好的效果，無(wú)論是搜索最優(yōu)解的成功率，所需迭代的次數(shù)，以及所運(yùn)行的時(shí)間都明顯優(yōu)于其它4種算法。對(duì)低維函數(shù)F5而言，其搜索空間遠(yuǎn)遠(yuǎn)小于高維函數(shù)，其它算法都可以很快找到最優(yōu)解，因而SelfDE算法并沒(méi)有特別的優(yōu)勢(shì)。但低維函數(shù)的搜索本身就不需要太多時(shí)間，因而SelfDE算法與其它算法的差距也是很小的。這一點(diǎn)從表8的實(shí)驗(yàn)結(jié)果中也可以看出來(lái)。

另外，從表4～表8的實(shí)驗(yàn)結(jié)果可知，MPDE算法的搜索效率僅次與SelfDE算法，是一種效率較高的算法，但對(duì)函數(shù)F4而言搜索到最優(yōu)解的成功率較低。jDE算法雖然與SelfDE算法一樣對(duì)所有5個(gè)測(cè)試函數(shù)最優(yōu)解的搜索成功率均為100%，但jDE算法的搜索效率 （所需運(yùn)行時(shí)間或迭代次數(shù)）遠(yuǎn)遠(yuǎn)大于SelfDE算法。因此，我們可以看到SelfDE算法在保證得到全局最優(yōu)解的基礎(chǔ)上，所需的迭代次數(shù)和搜索時(shí)間大大少于其它算法，尤其對(duì)于高維函數(shù)而言。

表3 測(cè)試函數(shù)F1－F5

表4 函數(shù)F1實(shí)驗(yàn)結(jié)果

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

表6 函數(shù)F3實(shí)驗(yàn)結(jié)果

表7 函數(shù)F4實(shí)驗(yàn)結(jié)果

表8 函數(shù)F5實(shí)驗(yàn)結(jié)果

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

控制參數(shù)選取是包括差異演化在內(nèi)的演化算法設(shè)計(jì)所要解決的一個(gè)重要問(wèn)題。合適的控制參數(shù)對(duì)演化算法的性能有著重要影響。但針對(duì)不同的優(yōu)化任務(wù)人工設(shè)置最佳的控制參數(shù)又是非常困難的，需要反復(fù)試驗(yàn)，計(jì)算量太大。本文提出一種自適應(yīng)調(diào)整控制參數(shù)的差異演化算法 （Self－DE），自動(dòng)調(diào)整DE算法中的縮放因子F和交叉因子CR，并利用交叉操作生成兩個(gè)新個(gè)體與父代個(gè)體競(jìng)爭(zhēng)形成下一代個(gè)體。不但減少了DE算法中需要人工選取的控制參數(shù)，而且加快了DE算法的收斂速度。

對(duì)測(cè)試函數(shù)的仿真實(shí)驗(yàn)表明，SelfDE算法在最優(yōu)解質(zhì)量上優(yōu)于文獻(xiàn) ［10］和文獻(xiàn) ［14］中提出的兩種自適應(yīng)選取控制參數(shù)算法：FADE算法和jDE算法。另外，對(duì)5個(gè)常用測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明，SelfDE算法在保證收斂性的同時(shí)，大大加快了算法的收斂速度。特別是對(duì)于高維函數(shù)來(lái)說(shuō)，相對(duì)于基本差異演化算法、動(dòng)態(tài)差異演化算法（DDE算法）、帶局部增強(qiáng)算法的差異演化算法 （MPDE算法）和jDE算法，該算法的性能有較大的提高。

［1］Price K，Storn R，Lampinen J.Differential evolution：A practical approach for global optimization ［M］.Berline：Springer－Verlag，2005.

［2］Alatas B，Akin E，Karci A.MODENAR：Multi－objective differential evolution algorithm for mining numeric association rules ［J］.Applied Soft Computing，2008，8 （1）：646－656.

［3］Das S，Abraham A，Konar A.Automatic clustering using an improved differential evolution algorithm ［J］.IEEE Transaction on Systems Man and Cybernetics：Part A，2008，38（1）：218－237.

［4］Feoktistov V.Differential evolution：In search of solutions［M］.Secaucus，NJ，USA：Springer－Verlag New York Inc，2006.

［5］Chakraborty U，Advances in differential evolution ［M］.Berlin：Springer－Verlag，2008.

［6］Onwubolu G C，Davendra D.Differential evolution：A handbook for global permutation－based combinatorial optimization［M］.Berlin：Springer－Verlag，2009.

［7］Storn R.Designing nonstandard filters with differential evolution ［J］.IEEE Signal Processing Magazine，2005，22 （1）：103－106

［8］Paterlini S，Krink T.Differential evolution and particle swarm optimization in partitional clustering ［J］.Computational Statistics ＆ Data Analysis，2006，50 （5）：1220－1247.

［9］FENG Qi，ZHOU Deyun.Time optimal path planning based on differential evolution algorithm ［J］.Computer Engineering and Applications，2005，41 （12）：74－75 （in Chinese）. ［馮琦，周德云.基于微分進(jìn)化算法的時(shí)間最優(yōu)路徑規(guī)劃 ［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41 （12）：74－75.］

［10］Liu J，Lampinen J.A fuzzy adaptive differential evolution algorithm ［J］.Soft Computing－A Fusion of Foundations，Methodologies and Applications，2005，9 （6）：448－462.

［11］Teo J.Exploring dynamic self－adaptive populations in differential evolution ［J］.Soft Computing－A Fusion of Foundations，Methodologies and Applications，2006，10 （8）：673－686.

［12］Brest J，Greiner S，Boskovic B，et al.Zumer self－adapting control parameters in differential evolution：A comparative study on numerical benchmark problems［C］.IEEE Transactions on Evolutionary Computation，2006，110 （6）646－657，ISSN：1089－778X.

［13］Qin A K，Suganthan P N.Self－adaptive differential evolution algorithm for numerical optimization ［C］.IEEE Congress on Evolutionary Computation.IEEE Press，2005：1785－1791.DOI：10.1109/CEC.2005.1554904.

［14］ZHAN Zhihui，ZHANG Jun.Self－adaptive differential evolution based on PSO learning strategy ［C］.Portland，America：Proc Genetic Evol Comput Conf，2010：39－46.

［15］Brest J，Boskovic B，Greiner S.Performance comparison of self－adaptive and adaptive differential evolution algorithms［J］.Soft Computing－A Fusion of Foundations，Methodologies and Applications，2007，11 （7）：617－629.

［16］WU Zhi－feng， HUANG Hou－kuan， ZHANG Ying. A differential evolution algorithm with double trial vectors basedon Boltzmann mechanism ［J］.Journal of Nanjing University（Natural Sciences），2008，44 （2）：195－203 （in Chinese）.［武志峰，黃厚寬，張瑩.基于Boltzmann機(jī)制的雙子代競(jìng)爭(zhēng)差異演化算法 ［J］.南京大學(xué)學(xué)報(bào) （自然科學(xué)版），2008，44（2）：195－203.］

［17］ZHAO Guang－quan，PENG Xi－yuan，SUN Ning.A modified differential evolution algorithm with local enhanced operator［J］.Acta Electronica Sinica，2007，35 （5）：849－853 （in Chinese）.［趙光權(quán)，彭喜元，孫寧.帶局部增強(qiáng)算子的微分進(jìn)化改進(jìn)算法 ［J］.電子學(xué)報(bào)，2007，35 （5）：849－853.］

［18］Qing Anyong.Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems ［J］.IEEE Transactions on Geoscience and Remote Sensing，2006，44 （1）：116－125.