基于自適應(yīng)變異方法的差分進(jìn)化算法

劉勇 于穎銳 李滿(mǎn)倉(cāng) 張斌 王冬勇 王星博

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

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

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

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

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

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

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

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

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

（1）種群初始化。

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

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

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

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

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

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

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

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

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

3 ?結(jié)語(yǔ)

本文針對(duì)差分進(jìn)化算法的變異操作，提出了一種根據(jù)進(jìn)化代數(shù)的自適應(yīng)變異方法。在種群進(jìn)化前期，可增大種群變異，加強(qiáng)全局搜索能力;在種群進(jìn)化后期，可限制在優(yōu)秀個(gè)體附近搜索，加強(qiáng)局部搜索能力和問(wèn)題的收斂性。數(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ì)算機(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.