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

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

關(guān)鍵詞：優(yōu)化算法 ?差分進(jìn)化算法 ?自適應(yīng)

中圖分類號：O224 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）07（c）-0136-03

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

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

1 ?差分進(jìn)化算法及自適應(yīng)變異方法研究

1.1 差分進(jìn)化算法及其影響因素分析

在差分進(jìn)化算法中，一般稱維度與目標(biāo)函數(shù)決策變量數(shù)相同的單個向量為個體，由NP個個體構(gòu)成的集合稱為種群，NP稱為種群規(guī)模。差分進(jìn)化算法在算法執(zhí)行過程中，保持種群規(guī)模不變，通過進(jìn)化的方式改善種群中個體的質(zhì)量，在可行域中搜索最優(yōu)解。

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

（1）種群初始化。

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

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

1.2 自適應(yīng)變異方法

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

FG隨進(jìn)化代數(shù)的變化曲線如圖1所示?？梢钥吹?，在進(jìn)化初期FG較大，作為基向量的隨機(jī)向量所占權(quán)重較大，此時全局搜索性能更高，能夠廣泛搜索最優(yōu)個體;在進(jìn)化后期FG較小，最優(yōu)個體所占權(quán)重較大，此時集中在優(yōu)秀個體鄰域附近搜索，加強(qiáng)問題求解的收斂性。

2 ?計算結(jié)果分析

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

將計算結(jié)果與差分進(jìn)化算法中傳統(tǒng)經(jīng)典的DE/rand/1/bin和DE/best/1/bin進(jìn)行比較，參考結(jié)果來源于文獻(xiàn)[1]。為使得比較的公平性，本文采用該參考文獻(xiàn)給出的計算條件，將種群規(guī)模設(shè)為100，最大函數(shù)評價次數(shù)設(shè)為50萬次。統(tǒng)計30次獨(dú)立運(yùn)行的結(jié)果，以排除隨機(jī)效應(yīng)帶來的影響，比較結(jié)果如表2所示?？梢园l(fā)現(xiàn)，本文提出的方法相對于傳統(tǒng)差分進(jìn)化方法，對測試問題具有更高的精度和性能。

為了測試本文方法的魯棒性，將預(yù)設(shè)精度設(shè)置為10-6，最大函數(shù)評價次數(shù)設(shè)為50萬次，如果在限定次數(shù)內(nèi)達(dá)到預(yù)設(shè)精度，則認(rèn)為程序成功求解。獨(dú)立運(yùn)行30次，統(tǒng)計函數(shù)平均評價次數(shù)及成功率，如表3所示。可以發(fā)現(xiàn)，本文的方法不論在函數(shù)評價次數(shù)上，還是成功率上，都較傳統(tǒng)方法優(yōu)秀。

3 ?結(jié)語

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

參考文獻(xiàn)

[1] 肖婧.差分進(jìn)化算法的改進(jìn)及應(yīng)用研究[D].哈爾濱工程大學(xué)，2011.

[2] 董明剛.基于差分進(jìn)化的優(yōu)化算法及應(yīng)用研究[D].浙江大學(xué)，2012.

[3] 鄧澤喜，曹敦虔，劉曉冀，等.一種新的差分進(jìn)化算法[J]. 計算機(jī)工程與應(yīng)用，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.