基于自適應變異方法的差分進化算法

劉勇 于穎銳 李滿倉 張斌 王冬勇 王星博

摘 ? 要：在工程實際應用中，常需對高維復雜的優化問題進行求解。差分進化算法是目前智能優化算法中性能最優的算法之一，可在很多工程問題中得到應用。傳統的差分進化算法存在收斂速度慢、易陷入局部最優解等問題。本文對差分進化算法的變異方法進行研究，提出一種根據種群進化代數自適應的變異方法。數值結果顯示，本文提出的自適應變異方法可有效避免種群早熟和局部最優解的問題。

關鍵詞：優化算法 ?差分進化算法 ?自適應

中圖分類號：O224 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）07（c）-0136-03

在科學、工程、經濟、前言研究等領域，對很多科學分析、系統控制、經濟模型、人工智能等問題都需要進行優化問題的求解。求最優化問題的方法稱為最優化方法，傳統的最優化方法包括單純形法、最速下降法、共軛梯度法等，具有計算效率高、可靠性強、理論比較成熟等優點，但是通常要求待求解問題有精確的數學模型，對問題的依賴較強，并且大多不具備全局最優化的特點。而工程實際問題中，常遇到高維度、非線性、多峰值，甚至目標函數不連續、不可微的問題，傳統方法求解困難。20世紀80年代以來，以模擬退火算法、遺傳算法等算法為代表的智能優化算法得到廣泛的研究和應用，其中差分進化算法以其特有的有點，成為最優異的智能優化算法之一[1-2]。

差分進化算法是根據父代個體間的差分矢量進行變異、交叉和選擇操作，與其他進化算法一樣容易限入局部最優，存在早熟收斂現象。本文從其算法中變異的本質出發，提出一種根據種群進化代數自適應變化的變異因子，其作用是：在種群進化前期，種群變異主要通過隨機父代進行擾動，種群多樣性高，全局搜索能力越強;在進化后期，種群變異集中在優秀個體附近，提高收斂速度。

1 ?差分進化算法及自適應變異方法研究

1.1 差分進化算法及其影響因素分析

在差分進化算法中，一般稱維度與目標函數決策變量數相同的單個向量為個體，由NP個個體構成的集合稱為種群，NP稱為種群規模。差分進化算法在算法執行過程中，保持種群規模不變，通過進化的方式改善種群中個體的質量，在可行域中搜索最優解。

典型的算法操作包括變異、修復、交叉和選擇。變異操作釆用變異策略來生成變異個體，一般通過對上一代（父代）的差分操作，生成下一代（子代）的個體;修復操作的目的是使新生成的個體處于可行域內，保證生成的變異個體的可行性;交叉操作通過父代個體和子代個體的交叉策略來產生新的嘗試個體;選擇操作根據嘗試個體和父代個體的評價函數來決定進入一下代種群的優秀個體。算法通過以上操作進行迭代計算，保證在每次迭代中淘汰劣質個體，保留優良個體，使得種群整體上向全局最優解區域靠近，優秀個體逼近全局最優解。具體的步驟包括：

（1）種群初始化。

首先在變量取值范圍內隨機生成初始種群，作為迭代初值，如式（1）所示：

從算法過程可以看到，有兩個關鍵的參數：變異因子和交叉概率。文獻[3]對交叉概率因子進行了研究，提出了自適應的交叉概率，取得良好的效果。而變異因子是決定父代個體變異程度的重要參數，一般變異因子取值在0～1之間。進行變異操作存在兩方面問題，一方面，增加種群多樣性，可加強全局搜索能力;另一方面，如果有效利用優秀個體信息，集中在優秀個體鄰域附近搜索，可提升搜索效率，加強問題求解的收斂性。交叉操作是保持種群多樣性的關鍵，交叉概率決定了嘗試個體中變異個體所占比例，Cr取值一般為0到1。Cr越大，變異向量貢獻越多，有利于局部搜索，加快收斂;Cr越小，初始向量貢獻越大，有利于保持種群的多樣性和全局搜索。

1.2 自適應變異方法

本文針對變異操作，考慮到進化初期需要增加種群多樣性，可加強全局搜索能力;在進化后期，劣質個體逐漸被淘汰，優秀個體逐漸顯現，如果集中在優秀個體鄰域附近搜索，可提升搜索效率，加強問題求解的收斂性。為平衡這兩個問題，本文根據進化進程的不同，提出一種自適應變異因子，如式（6）所示：

FG隨進化代數的變化曲線如圖1所示。可以看到，在進化初期FG較大，作為基向量的隨機向量所占權重較大，此時全局搜索性能更高，能夠廣泛搜索最優個體;在進化后期FG較小，最優個體所占權重較大，此時集中在優秀個體鄰域附近搜索，加強問題求解的收斂性。

2 ?計算結果分析

本文選取了4個經典測試函數[4]對本文提出的自適應變異因子進行測試。這4個函數的信息如表1所示，表中理論最優解f（a）=b表示變量取a時，函數達到最小值b，其中粗體表示向量。

將計算結果與差分進化算法中傳統經典的DE/rand/1/bin和DE/best/1/bin進行比較，參考結果來源于文獻[1]。為使得比較的公平性，本文采用該參考文獻給出的計算條件，將種群規模設為100，最大函數評價次數設為50萬次。統計30次獨立運行的結果，以排除隨機效應帶來的影響，比較結果如表2所示。可以發現，本文提出的方法相對于傳統差分進化方法，對測試問題具有更高的精度和性能。

為了測試本文方法的魯棒性，將預設精度設置為10-6，最大函數評價次數設為50萬次，如果在限定次數內達到預設精度，則認為程序成功求解。獨立運行30次，統計函數平均評價次數及成功率，如表3所示。可以發現，本文的方法不論在函數評價次數上，還是成功率上，都較傳統方法優秀。

3 ?結語

本文針對差分進化算法的變異操作，提出了一種根據進化代數的自適應變異方法。在種群進化前期，可增大種群變異，加強全局搜索能力;在種群進化后期，可限制在優秀個體附近搜索，加強局部搜索能力和問題的收斂性。數值結果表明，本文提出的自適應變異方法，符合理論預期，比傳統的差分進化算法具有更優異的效果。

參考文獻

[1] 肖婧.差分進化算法的改進及應用研究[D].哈爾濱工程大學，2011.

[2] 董明剛.基于差分進化的優化算法及應用研究[D].浙江大學，2012.

[3] 鄧澤喜，曹敦虔，劉曉冀，等.一種新的差分進化算法[J]. 計算機工程與應用，2008，24（44）：40-42.

[4] Suganthan PN， Hansen N， Liang JJ， et al. Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization[D].School of EEE， Nanyang Technological University， 2005.