武志峰，黃厚寬

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

0 引 言

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

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

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

1 DE算法

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

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

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

生成變異向量hi后，為增加種群的多樣性，變異向量與原目標向量進行交叉操作生成試驗向量vi

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

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

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

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

2.1 算法原理

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

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

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

2.2 SelfDE算法

SelfDE算法描述如下：

步驟1 隨機初始化第1代種群；

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

（1）隨機選擇3個互不相同的個體；

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

（3）利用兩子代生成策略形成兩個試驗向量vi，ui；

（4）對試驗向量vi，ui與目標向量xi執(zhí)行選擇操作生成下一代個體；

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

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

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

3 實驗仿真與分析

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

3.1 SelfDE與jDE、FADE算法的比較

為檢驗SelfDE算法的最優(yōu)解性能，選擇文獻 ［14］中的9個常用函數(shù)對算法進行測試，并與jDE算法［12］和FADE算法［10］的結(jié)果比較。測試函數(shù)如表1所示，其中n表示自變量維數(shù)，S表示自變量取值范圍，fmin表示函數(shù)的最優(yōu)解。函數(shù)F1－F7是高維問題。其中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是有局部極小點的低維函數(shù)。實驗中SelfDE算法的參數(shù)設(shè)置與文獻 ［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。

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

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

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

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

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

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

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

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

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

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

實驗結(jié)果如表4～表8所示，各算法的結(jié)果均為獨立運行50次的平均值。

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

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

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

表4 函數(shù)F1實驗結(jié)果

表5 函數(shù)F2實驗結(jié)果

表6 函數(shù)F3實驗結(jié)果

表7 函數(shù)F4實驗結(jié)果

表8 函數(shù)F5實驗結(jié)果

4 結(jié)束語

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

對測試函數(shù)的仿真實驗表明，SelfDE算法在最優(yōu)解質(zhì)量上優(yōu)于文獻 ［10］和文獻 ［14］中提出的兩種自適應(yīng)選取控制參數(shù)算法：FADE算法和jDE算法。另外，對5個常用測試函數(shù)的實驗結(jié)果表明，SelfDE算法在保證收斂性的同時，大大加快了算法的收斂速度。特別是對于高維函數(shù)來說，相對于基本差異演化算法、動態(tài)差異演化算法（DDE算法）、帶局部增強算法的差異演化算法 （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）. ［馮琦，周德云.基于微分進化算法的時間最優(yōu)路徑規(guī)劃 ［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］.南京大學學報 （自然科學版），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)，彭喜元，孫寧.帶局部增強算子的微分進化改進算法 ［J］.電子學報，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.