自適應差分演化算法研究

摘要：差分演化算法的參數設置影響算法的優化性能和收斂速度。在對差分演化算法的控制參數：種群規模、縮放因子和交叉因子的取值進行詳細實驗基礎上，分析各參數對算法性能的影響，總結參數選取規律，提出一種改進的自適應差分演化算法，該算法在迭代的每一代中，種群規模在一定范圍內取值，縮放因子和交叉因子則在固定取值的基礎上，按一定概率在一定范圍內隨機取值，使參數選擇更寬松，增加算法的遍歷性，避免陷入局部最優，提高算法收斂到全局最優的可能性。在基準函數的測試上，驗證了新算法比傳統差分演化算法具有更高的優化性能，并且簡單容易實現。

關鍵詞：差分演化算法;數值優化;參數分析;算法改進

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1009-3044（2019）36-0095一03

差分演化算法（Differential Evolution.DE）是Storn和Price于1995年提出的一種簡單高效的隨機啟發式搜索算法[1]，該算法采用實數編碼，具有原理簡單、容易編程實現、參數少、收斂快速、魯棒性強等優點，有很強的全局優化能力和很高的優化效率。但與其他進化算法一樣，DE也具有容易陷入局部最優的缺點，并且算法性能對參數設置很敏感[2]。DE的可調參數雖然只有3個：種群規模NP，縮放因子F和交叉因子CR，但參數的設置對算法執行性能具有重大影響，選取不當會導致算法早熟停止進化。為了提高算法性能，研究者在參數控制與適應等方面提出了很多改進措施：文獻[3]針對F和CR的綜合作用進行測試分析并提出F=rand（.）的SDE版本;文獻[4]提出了一種基于模糊控制的白適應FADE，利用模糊邏輯控制器對F和CR進行自適應控制;文獻[5]提卅一種動態白適應群體規模的DE;文獻[6]提出了一種自適應策略DE，算法中F采用隨機正態分布產生，CR則通過演化過程中的反饋信息進行自適應調整;文獻[7]對多種不同參數選取與控制策略進行比較分析，并證明了這些策略都在不同程度上提高了算法的收斂速度和優化精度;文獻[8]對DE的3個參數展開實驗研究，給出參數選取規則;文獻[9]則提出了參數白適應學習策略。

本文在詳細分析各參數對算法優化性能的影響規律基礎上，提出種改進的自適應DE：算法在迭代的每一代中，NP在一定范圍內取值，F和CR則在固定取值的基礎上，按一定概率在某一范圍內隨機產生，通過隨機參數來增加算法的多樣性，避免陷入局部最優。

1差分演化算法原理

DE是一類基于群體的白適應全局優化算法，利用差分變異、交叉和選擇等算子對群體不斷進行演化，演化過程與遺傳算法類似，也包括種群的表示與初始化、變異與交叉和選擇操作。以經典DE策略之- DE/rand/bin為例對算法進行描述：

（1）種群表示與初始化：設求解問題的白變量有D維，種群規模為NP，則種群中第i個個體Xi表示為：xi={xi（1），xi（2），…，xi（D）}。初始化是在一定搜索空間內隨機生成NP個D維向量構成初始種群。

（2）差分變異：對種群中的任意個體X.按式（1）生成一個對應的變異個體：

K=Xi1+F×（Xr2- Xr3）

（1）

式中：Xr1、Xr2和Xr3是當前群體隨機選擇的3個不同個體，而且它們也與Xi不同;Vi是變異個體;Xr2-Xr3為差分向量;F∈[O，1+]為縮放因子，用于對差分向量進行縮放，控制搜索步長。

（3）交叉：采用離散雜交操作，把目標個體X.和變異個體V.通過式（2）進行離散雜交得到測試個體Ui：

式中：Rj（0，1）是一個在（0，1）范圍內的均勻隨機數;Jran是[1，D]的一個隨機整數，保證Ui中至少有一維來白Vi;CR∈[0，1]是交叉率，用來控制在哪些決策變量上采用變異值。

（4）選擇：對每個測試個體Ui，采用式（3）的一對一競標賽選擇方式：

式中：F（Xi）為個體Xi的適應值;xi是代替Vi而進入下一代的子個體。

經過差分變異、交叉和選擇操作，DE得到一個新的群體{xii=l，l，2，…，N}進入下一代，算法不斷迭代直至滿足終止條件退出。

2控制參數對算法性能的影響

DE算法控制參數有3個：群體規模NP，縮放因子F和交叉因子CR，這3個參數影響算法搜索精度和收斂速度。為了調查參數對算法性能的影響規律，本文使用4個典型的Benchmark函數作為實例（其中f1—f3是單峰函數，f4是多峰函數，所有函數全局最優值均為0），針對參數對算法性能的影響進行詳細實驗和分析：

2.1群體規模NP的影響

群體規模NP是群智能算法的一般性參數，其取值決定了算法的多樣性，在一定程度上影響著算法的優化效率和優化質量。為了測試NP對算法性能的影響，在設定F=0.5和CR=0.9的情況下，把種群規模從5取到125，步長為5，采用上述函數對NP取值進行調查，函數維數D=30，迭代次數為1500。各個測試函數獨立運行30次，取各次運行結果最優適應度值的平均值。測試結果如圖1所示。

由圖l可以看出：不論是單峰函數或多峰函數，在給定迭代次數（Gen=1500）的情況下，當NP在50附近時，算法取得的最優解精度最高，繼續增大NP，算法的優化性能不僅沒有改善反而出現下降。

這說明：種群規模太小，算法缺少多樣性，收斂速度快但容易陷入局部最優;較大NP能夠增加群體多樣性，收斂到全局最優的可能性就越大，但所需的計算量也相應增加，降低收斂速度。在迭代次數不變情況下，有時種群規模的增大，反而會使最優解的精度降低。

因此，DE運行時必須考慮算法多樣性和收斂速度的平衡，NP取值不能過大也不能過小。一般情況下，在給定最大迭代次數下，種群規模NP∈[30，60]時，算法能很好地保持種群多樣性和收斂速度的平衡。

2.2縮放因子F和交叉因子CR的影響

縮放因子F用于控制差分向量對變異個體Vi（t）的影響，其取值在很大程度上同時影響著進化過程的收斂性及收斂速度。交叉因子CR控制個體的各維對交叉的參與程度，起到平衡全局與局部搜索能力的作用。

為了測試縮放因子和交叉因子對算法性能的影響，設定函數維數D=30，種群規模NP=50，迭代次數為1500，采用上述實例對F和CR取值進行調查。對每個實例，縮放因子F由0.1遞增至1.0，步長為0.1;同時針對每個F值，交叉因子CR同樣由0.1遞增至1.0，步長也為0.1。各個函數運行30次，取各次運行結果的最優適應度值的平均值，比較各函數在不同F/CR取值組合的最優解變化情況，結果如圖2～圖5所示。

由圖2～圖5可以看出：

1）不論是單峰函數還是多峰函數，隨著F增加，算法性能先變好后變差。當F在[0.3，0.6]取值時，算法能夠取得較好的優化性能。

原因在于：F控制搜索步長，較小的F值產生的擾動較小，起到局部精細化搜索的作用，能夠加速算法收斂，但容易使算法早熟收斂;較大的F值使差分向量（Xr2-Xr3）對變異個體Vi（t）的影響較大，產生較大擾動，增加算法跳出局部最優解的可能性，但當F>0.9時，算法近似隨機搜索，降低收斂速度。因此，F取值不能過大也不能過小，一般建議設置在0.5左右。

2）單峰函數中，當CR ∈（0.5，0.9）時，算法優化性能較好;多峰函數中，當CR ∈（0.1，0.3）時，算法優化性能較好。特別地，當CR=0.9時算法取得的最優解精度較高。而當CR>0.9時，算法取得的最優解精度大幅下降。這就因為差分變異算子具有旋轉不變性，即通過變異操作得到的變異向量Vi具有不隨坐標軸旋轉而改變的性質，這一特點使DE在CR=0.9時較適應求解變量相關的優化問題。

原因在于：CR本質上是用以調整歷史信息和當前進化信息的權重，單峰函數中，較大的CR有利于保持種群多樣性，搜索新的空間，加速收斂。而多峰函數中，CR的增加意味著對多變量相關的處理能力加強，也意味著Vi對子代的貢獻增多。即個體間的非線性交互越少，越不容易形成自組織系統，因而對復雜問題的演化能力下降[10]。

3）圖2～圖5中，當F=0.5，CR=0.9時，算法都能取得較好的優化結果。因此，固定參數DE中，通常F取0.5，CR取0.9。3改進的自適應參數DE算法

通過算法參數測試得知，DE中的縮放因子F較好初始值為F=0.5，但當F∈（0.3，0.6）時算法的最優解仍能取得很高精度，甚至比F=0.5時更優;相對于F，交叉因子CR的取值比較自由，其較好的初始值是CR=0.9。但F和CR是相互影響的，對不同F（CR），最佳CR（F）取值不同。如果把F和CR設置為固定值或按某一規律變化，而不考慮具體優化模型和實現過程，容易使算法陷入局部最優。

為了提高DE的優化性能，減少人為設置參數對算法性能的影響，本文在固定參數DE的基礎上，提出一種改進的自適應參數DE算法：該算法群體大小NP設置為[30，60]中的一個固定值，在迭代的每一代中，縮放因子和交叉因子在固定取值的基礎上，按一定概率在一定范圍內隨機選取，通過讓縮放因子和交叉因子在更大范圍內的取值，提高算法的遍歷性，提高算法收斂到全局最優的可能性。每個個體的控制參數取值策略如下：

其中，rn，dreal[a，6]是在[a，h]區間產生的均勻隨機小數，y1和y2調節參數固定取值或隨機取值的概率，即個體的控制參數部分取固定值，部分在一定范圍內隨機選取，讓種群可以在更大范圍內進行搜索，提高了算法的全局優化能力，并且避免了設置參數時的反復測試以及因參數設置不當而產生的誤差。

將本文提出的自適應DE與固定參數DE（F=0.5、C R=0.9）的運算性能進行比較：空間維數D取30，NP=50，y1和y2取0.5，算法最大迭代次數為1500。各個函數隨機運行30次，取各次運行結果的平均值。兩種算法運算結果如表1所示。

由表1可以看出：

本文提出新算法除了在個別函數（f3）中優化效率沒有明顯提高之外，在大部分函數（f1、f2和f4）中都取得了比固定參數DE更好的結果，各個函數取得的平均適應度值和平均方差均低于固定參數DE所取得的結果，表明本文提出的新算法具有較高的優化精度，并且穩定性強。

自適應DE提高獲得全局最優的可能性的原因在于：

1）固定參數DE把進化過程看成一個均勻向上的過程，但對于復雜、非線性、多峰值的函數，個體的進化是非線性的，收斂速度可能先快后慢，也可能先慢后快。

2） DE本質上是一種全局隨機優化技術，對于不同優化問題，最佳的F和CR并非某一確定組合，而是在一定區域內波動。F和CR可以多種取值組合，傳統的固定參數（F=0.5，CR=0.9）只是其中一個樣本。白適應參數DE讓個體在一個更寬松的環境迭代，增加找到全局最優的可能性。

3）由于算法中的選擇操作采用了貪婪機制，優勝劣汰，阻止了比當前種群中最差解還差的解進入下一代，在進化后期種群將集中在一些極小值附近。自適應參數DE增加個體跳出局部極值的可能性，能夠使種群從當前極小值的區域跳躍到另一個比當前區域更好的極小值區域，最終收斂到全局最優。

4結束語

差分演化算法控制參數的設置對算法搜索性能和收斂速度影響很大，不合理的參數設置可能導致算法早熟收斂或算法停滯。傳統DE對縮放因子F和雜交概率CR設置很敏感，對不同的優化問題經常需要從問題本身出發設置、測試和調整參數，手動參數調整費時費力且效率低下。如何設置參數使算法既能避免早熟又能快速收斂，并且保持算法簡單通用的優點，一直是DE研究的核心問題。

本文在分析控制參數對算法性能影響的基礎上，提出一種白適應參數選擇的DE，群體規模NP在一定范圍內取固定值，個體控制參數在固定取值的基礎上，讓部分縮放因子F和雜交概率CR在一定范圍內隨機取值，通過增加參數的選取組合來提高算法收斂到全局最優的可能性。本文提出的新算法僅在參數選擇上做出改進，沒有復雜的調整策略和混合技術，算法流程與標準DE 一致，無須額外增加運算開銷和數據存儲空間，保持了DE算法實現簡單、通用性強的優點，有利于算法進一步的推廣和應用。

參考文獻：

[1]Storn R，Price K.Differential evolution -A Simple and effi-cient adaptive scheme for global optimization over ContinuousSpace[R]. University of California， Berkley： ICSI， 1995.

[2] Storn R，Price K.Differential Evolution -A Simple and Effi-cient Heuristic for Global Optimization over Continuous Spaces[J]. Joumal of Global Optimization （S0925-5001）， 1997， 11（4）：341-359.

[3]謝曉鋒，張文俊，張國瑞，等.差異演化的實驗研究[J].控制與決策，2004， 19（1）：49-52.

[4] LIU J，LAMPINEN J.A Fuzzy Adaptive Differential EvolutionAlgorithm[Jl. Soft Computing， 2005， 9（6）：448-462.

[5] TEO J. Exploring Dynamic Self-adaptive Populations in Differ-ential Evolution[J]. Soft Computing， 2006， 10（8）：673-686.

[6] QIN A K，HUANG V L，SUGANTHAN P N.Differential Evo-lution Algorithm with Strategy Adaptation for Glohal Numeri-cal Optimization[J]. IEEE Transactions on Evolutionary Com-putation， 2009， 13（2）：398-417.

[7]高岳林，劉軍民.差分進化算法的參數研究[J].黑龍江大學自然科學學報，2009， 26（1）：81-85.

[8]楊振宇，唐珂.差分進化算法參數控制與適應策略綜述[J].智能系統學報，2011， 6（5）：415-423.

[9] ZHAN Z H，ZHANG J.Self-adaptive Differential EvolutionBased on PSO Learning Strategy[C]// In Proc. Genetic Evol.Comput. Conf.， 2010： 39-46.

[10]袁俊剛，孫治國，曲文吉.差異演化算法的數值模擬研究[J].系統仿真學報，2007， 19（20）：4646-4648.

【通聯編輯：謝媛媛】

收稿日期：2019-10-29

作者簡介：黃少榮（197 6-），女，教授，碩士，研究方向為計算機應用與計算智能。