自適應調整控制參數的差異演化算法

武志峰，黃厚寬

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

0 引 言

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

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

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

1 DE算法

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

首先，在n維空間里隨機產生滿足約束條件的NP個染色體 （個體）構成一代種群，其中NP為種群規模。第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稱為縮放因子，取值在［0，2］之間，一般小于1，通常取0.5。

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

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

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

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

2 自適應調整控制參數的DE算法 （SelfDE）

2.1 算法原理

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

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

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

2.2 SelfDE算法

SelfDE算法描述如下：

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

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

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

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

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

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

（5）按2.1節給出的公式動態調整個體i對應的F和CR值；

步驟3 若不滿足結束條件，轉步驟2；

步驟4 輸出結果。

3 實驗仿真與分析

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

3.1 SelfDE與jDE、FADE算法的比較

為檢驗SelfDE算法的最優解性能，選擇文獻 ［14］中的9個常用函數對算法進行測試，并與jDE算法［12］和FADE算法［10］的結果比較。測試函數如表1所示，其中n表示自變量維數，S表示自變量取值范圍，fmin表示函數的最優解。函數F1－F7是高維問題。其中F1，F2是單峰函數，F3是不連續函數，F4為帶噪聲的4次函數，F5－F7是多峰函數。F8，F9是有局部極小點的低維函數。實驗中SelfDE算法的參數設置與文獻 ［14］中的jDE算法設置相同：D＝50，NP＝10×D，最大迭代次數分別取F1，F3，F4，F6，F7為5000，F2為7000，F5為10000，F8為100，F9為50。

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

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

表1 測試函數F1－F9

表2 函數F1－F9的運行結果

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

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

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

（1）對各函數統一設置種群規模NP＝100。

（2）對 DE、DDE、MPDE設置F＝0.5，CR＝0.9。jDE和SelfDE算法F和CR自適應調節。

（3）在MPDE算法中，根據文獻 ［17］設置MP的值，對F1，F3，F4設 MP＝0.1，對F2設 MP＝0.05，F5設MP＝0.008。

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

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

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

表3 測試函數F1－F5

表4 函數F1實驗結果

表5 函數F2實驗結果

表6 函數F3實驗結果

表7 函數F4實驗結果

表8 函數F5實驗結果

4 結束語

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

對測試函數的仿真實驗表明，SelfDE算法在最優解質量上優于文獻 ［10］和文獻 ［14］中提出的兩種自適應選取控制參數算法：FADE算法和jDE算法。另外，對5個常用測試函數的實驗結果表明，SelfDE算法在保證收斂性的同時，大大加快了算法的收斂速度。特別是對于高維函數來說，相對于基本差異演化算法、動態差異演化算法（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）. ［馮琦，周德云.基于微分進化算法的時間最優路徑規劃 ［J］.計算機工程與應用，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）.［趙光權，彭喜元，孫寧.帶局部增強算子的微分進化改進算法 ［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.