沈 鑫，鄒德旋，張 鑫

(江蘇師范大學(xué) 電氣工程及自動化學(xué)院，江蘇 徐州 221116)

隨機自適應(yīng)差分進化算法

沈 鑫，鄒德旋，張 鑫

(江蘇師范大學(xué) 電氣工程及自動化學(xué)院，江蘇 徐州 221116)

針對差分進化算法存在早熟收斂且與理想最優(yōu)值相差甚遠等缺陷。隨機自適應(yīng)差分進化算法被提出，該算法采用隨機選擇策略的變異操作，再加小概率擾動；對變異因子和交叉概率進行自適應(yīng)操作，以滿足算法不同階段的要求，其中交叉概率利用種群個體平均適應(yīng)度值作對比，有利于充分利用種群信息。對幾個標準函數(shù)進行測試并將該算法與其他4種方法進行比較，結(jié)果顯示該算法的優(yōu)化性能比其他方法好，具有較好的跳出局部最優(yōu)的能力和收斂精度。

差分進化算法；隨機變異；擾動；自適應(yīng)操作

差分進化(Differential Evolution,DE)算法[1]是在種群內(nèi)尋找最優(yōu)值的智能優(yōu)化算法。目前，DE算法在神經(jīng)網(wǎng)絡(luò)優(yōu)化[2]、電力系統(tǒng)無功優(yōu)化[3]、約束優(yōu)化[4]、車間調(diào)度[5]、控制[6]等方面得到了廣泛應(yīng)用。DE算法到了進化后期，種群的多樣性降低，容易出現(xiàn)早熟收斂和收斂精度不高的問題。

為克服以上缺點, 針對DE算法的改進主要在以下幾方面：控制參數(shù)[7]、變異策略[8-9]、種群結(jié)構(gòu)[10]、混合優(yōu)化算法[11-13]。文獻[14]提出了隨機變異差分進化算法(Random Mutation Differential Evolution Algorithm, RMDE)。本文在此基礎(chǔ)上提出了一種隨機自適應(yīng)差分進化算法(Self-adaptive Differential Evolution Algorithm with Random Mutation,SRDE)，SRDE算法在RMDE算法的基礎(chǔ)上又增加了對參數(shù)的自適應(yīng)操作，使其收斂精度更高，跳出局部最優(yōu)解的能力更強。

1 標準的差分進化算法

差分進化算法的基本思想是對初始化種群中的個體，進行變異、交叉、選擇操作，按照"適者生存"的原則來保留優(yōu)秀個體，實現(xiàn)種群更新。標準差分進化算法的步驟主要有以下5步：

(1)

(2)變異 DE通過差分向量實現(xiàn)個體變異，在變異中最常用的策略是DE/rand/1/bin，即

(2)

(3)

(4)選擇 DE基于貪婪原則選擇進入下一代的個體。

(4)

(5)終止判斷。若滿足條件(達到最大迭代數(shù)要求)，則停止搜索，輸出最優(yōu)解；否則，返回步驟(2)，繼續(xù)執(zhí)行變異，交叉和選擇操作。

2 隨機自適應(yīng)差分進化算法

SRDE算法在RMDE算法的基礎(chǔ)上，增加了參數(shù)自適應(yīng)操作。

2.1 隨機變異操作

變異操作是DE算法中非常重要的步驟。DE算法采用固定變異策略DE/rand/1,可以在算法搜索初期進行全局搜索，保證種群多樣性，但無法滿足搜索后期局部搜索要求，而采用DE/best/1策略可以加快搜索速度，但容易出現(xiàn)早熟收斂。為了既保證種群多樣性，又加快搜索速度。本文借鑒了RMDE算法中的隨機變異方法，在DE/rand/1和DE/best/1策略中隨機選擇，以適應(yīng)不同階段的要求。表達式為

(5)

2.2 擾動操作

在種群向最優(yōu)解進化過程中，算法可能搜索到的當前最優(yōu)解是全局最優(yōu)解，也可能是局部最優(yōu)解。如果是局部最優(yōu)解時，這時有可能陷入其中，跳出局部最優(yōu)就顯得非常重要；如果是全局最優(yōu)解，則個體不會被淘汰。針對這種情況，SRDE算法使用了一種小概率擾動策略，使其跳出局部最優(yōu)解，避免早熟收斂。表達式為

if rand

(6)

else

end

其中，xmin和xmax分別為搜索的上下邊界，p一般取>0.9,p=0.99。

2.3 自適應(yīng)變異因子和自適應(yīng)交叉概率

F和CR采取自適應(yīng)操作是為了滿足算法各個階段的要求，以平衡全局搜索和局部搜索。

2.3.1 自適應(yīng)變異因子

變異因子是用來對差異矢量進行縮放，根據(jù)要求SRDE算法將變異因子動態(tài)自適應(yīng)變化。具體表達為

(7)

2.3.2 自適應(yīng)交叉概率

自適應(yīng)交叉概率是根據(jù)上一代個體的適應(yīng)度值與上一代種群的平均適應(yīng)度值比較來自適應(yīng)調(diào)整。分兩種情況討論：一種是上一代個體的適應(yīng)度值小于等于上一代種群的平均適應(yīng)度值采用式(8i)；另一種是上一代個體的適應(yīng)度值大于上一代個體的平均適應(yīng)度值采用式(8ii)。當種群進化第一代時采用式(9)。具體表達式為

(8)

(9)

2.4 隨機自適應(yīng)差分進化算法具體步驟

步驟1初始化種群，設(shè)置參數(shù)，主要包括種群最大進化代數(shù)、種群規(guī)模、變異因子的最大最小值、交叉概率的最大最小值、種群的邊界；

步驟2計算種群個體的適應(yīng)度值，并求出最優(yōu)解對應(yīng)的最優(yōu)個體和平均適應(yīng)度值；

步驟3實施隨機變異自適應(yīng)操作，并加小概率擾動；

步驟4實施自適應(yīng)交叉操作；

步驟5利用貪婪原則進行選擇，較好的個體將存活，進入下一代；

步驟6終止判斷，當種群進化到最大代數(shù)時，輸出最優(yōu)解，算法結(jié)束；否則，g=g+1,返回步驟2。

3 實驗仿真與分析

本文選取7個標準測試函數(shù)[15]進行測試。為了驗證SRDE算法在函數(shù)優(yōu)化的性能，將SRDE算法與DE/rand/1/bin策略的DE算法、DE/best/1/bin策略的DE算法、RMDE算法、PSO算法進行比較。7個標準測試函數(shù)的具體表達式為

仿真實驗使用Matlab8.3軟件來編程實現(xiàn)，且電腦配置為Intel(R) Core(TM) i5-2450M CPU @ 2.50 GHz。算法的參數(shù)設(shè)置如下：DE/rand/1/bin和DE/best/1/bin策略的DE算法中F=0.5，CR=0.9；RMDE算法的參數(shù)值見文獻[14]；PSO算法的學(xué)習(xí)因子c1=c2=2，慣性權(quán)重w由0.9到0.4線性遞減，粒子最大速度100；SRDE算法的變異因子和交叉概率最小值，最大值分別是Fmin=0.1，F(xiàn)max=0.8，CRmin=0.1，CRmax=0.9，其他參數(shù)值與RMDE算法中的相同；種群規(guī)模NP=100；算法對不同測試函數(shù)的最大迭代次數(shù)在表中給出；種群的邊界范圍是[-100,100]；維數(shù)D=100。

表1是函數(shù)優(yōu)化的數(shù)據(jù)，算法對f1～f5的優(yōu)化是維數(shù)為100時，算法對f6和f7的優(yōu)化是維數(shù)為2時，各個算法性能比較將通過搜索的最優(yōu)值、平均值、標準差得出。每一種算法都獨立進行30次實驗。

表1 函數(shù)優(yōu)化結(jié)果

表1是算法在高維和2維時的數(shù)據(jù)，從表中可以看出DE/best/1/bin策略的DE算法和PSO算法的最優(yōu)解、平均值、標準差都較大，說明DE/best/1/bin策略的DE算法和PSO算法雖然可以加快搜索速度，但容易陷入局部最優(yōu)。對f1、f2、f3、f4、f5函數(shù)而言，SRDE算法搜索到的最優(yōu)解和收斂精度比RMDE算法好；對f3、f6、f7函數(shù)而言，SRDE算法都可以找到理想最優(yōu)解。表中的平均值代表算法的平均優(yōu)化性能，這也是重要的評價指標，下面的收斂曲線也是用平均函數(shù)值得到的平均優(yōu)化曲線。

綜上所述，SRDE算法跳出局部最優(yōu)的能力和收斂精度好于其他4種方法，說明對參數(shù)的自適應(yīng)是必不可少的，特別是將種群平均值引入來對比，充分利用其他個體的信息。從求解高維函數(shù)來看，SRDE算法對于求解高維問題有一定的優(yōu)勢。

圖1～圖5分別是100維時函數(shù)f1～f5的收斂曲線，圖6、圖7分別是2維時函數(shù)f6和f7的收斂曲線，橫坐標表示迭代次數(shù)，縱坐標表示平均函數(shù)值。

圖1 收斂曲線

圖2 收斂曲線

圖3 收斂曲線

圖4 收斂曲線

圖5 收斂曲線

圖6 收斂曲線

圖7 收斂曲線

從仿真曲線可以看出，SRDE算法明顯要好。對函數(shù)f1、f3、f4、f5而言，前期SRDE算法下降的比RMDE算法慢，但到了后期搜索速度加快，收斂精度變高。在表1中，函數(shù)f3在SRDE算法的搜索下可以找到理論最優(yōu)解，但所需要的最大迭代次數(shù)很大，從而需要更長的時間，從這個函數(shù)可以看出SRDE算法對某些函數(shù)而言需要的迭代次數(shù)很大，才能搜索到全局最優(yōu)解。綜上，SRDE算法在高維時的優(yōu)化性能比較優(yōu)越。

4 結(jié)束語

SRDE算法將RMDE算法中的隨機策略選擇，小概率擾動和參數(shù)自適應(yīng)結(jié)合起來用于函數(shù)優(yōu)化，更好的利用了種群信息和有效避免了早熟收斂。將SRDE算法、DE/rand/1/bin策略的DE算法、DE/best/1/bin策略的DE算法、RMDE算法、PSO算法用來優(yōu)化7個經(jīng)典函數(shù)并對結(jié)果進行對比，結(jié)果表明：SRDE算法具有較強的全局搜索能力和收斂精度。在接下來的工作中，將改進SRDE算法使之收斂速度加快。

[1] Storn R,Price K.Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[2] 李目,何怡剛,周少武,等.一種差分進化算法優(yōu)化小波神經(jīng)網(wǎng)絡(luò)及其在弱信號檢測中的應(yīng)用[J].計算機應(yīng)用與軟件,2010,27(3):29-31.

[3] 馬立新,孫進,彭華坤.多目標差分進化算法的電力系統(tǒng)無功優(yōu)化[J].控制工程,2013,20(5):953-956.

[4] 閤大海,李元香,龔文引,等.一種求解約束優(yōu)化問題的自適應(yīng)差分進化算法[J].電子學(xué)報,2016,44(10):2535-2542.

[5] 王萬良,范麗霞,徐新黎,等.多目標差分進化算法求解柔性作業(yè)車間批量調(diào)度問題[J].計算機集成制造系統(tǒng),2013,19(10):2481-2492.

[6] 李愛軍,王景,李佳,等.基于差分進化算法的飛行控制律評估[J].模式識別與人工智能,2014,27(3):256-262.

[7] 張雪霞,陳維榮,戴朝華.帶局部搜索的動態(tài)多群體自適應(yīng)差分進化算法及函數(shù)優(yōu)化[J].電子學(xué)報,2010,38(8):1825-1830.

[8] Qin A K,Huang V L,Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.

[9] 譚躍,譚冠政,伍雪冬.基于交叉變異策略的雙種群差分進化算法[J].計算機與應(yīng)用,2010,46(18):9-12.

[10] 夏慧明,王志剛,周永權(quán).多種群自適應(yīng)差分進化算法[J].小型微型計算機系統(tǒng),2014,35(4):850-853.

[11] 王志,胡小兵,何雪海.一種新的差分與粒子群算法的混合算法[J].計算機工程與應(yīng)用,2012,48(6):46-48.

[12] 楊俊,魏靜宣.梯度策略自適應(yīng)差分進化算法[J].電子科技,2016,29(1):25-27.

[13] 范瑜,金榮洪,耿軍平,等.基于差分進化算法和遺傳算法的混合優(yōu)化算法及其在陣列天線方向圖綜合中的應(yīng)用[J].電子學(xué)報,2004,32(12):1997-2000.

[14] 歐陽海濱,高立群,孔祥勇.隨機變異差分進化算法[J].東北大學(xué)學(xué)報:自然科學(xué)版,2013,34(3):330-334.

[15] Zou Dexuan,Gao Liqun,Wu Jianhua,et al. Novel global harmony search algorithm for unconstrained problems[J]. Neurocomputing,2010,73(16-18):3308-3318.

Self-adaptive Differential Evolution Algorithm with Random Mutation

SHEN Xin,ZOU Dexuan,ZHANG Xin

(School of Electrical Engineering and Automation,Jiangsu Normal University,Xuzhou 221116,China)

Aiming at the defects of differential evolution, such as the premature convergence and optimal value of differential evolution is far from the ideal optimal value. Self-adaptive differential evolution algorithm with random mutation was presented. Random choice strategy was adopted to execute mutation operation by the algorithm, which added to small-probability disturbance. To meet the requirements of different stages of the algorithm，the mutation factor and crossover rate performed the adaptive operation. The crossover rate was compared with the average of the fitness of individuals, which was beneficial to make full use of population information. Several standard functions were tested and the SRDE algorithm was compared with the other four methods. The results show that the optimization performance of SRDE algorithm is better than other methods, and it is better to jump out of local optimal ability and convergence precision.

differential evolution algorithm;random mutation; disturbance;self-adaptive operation

2017- 03- 21

國家自然科學(xué)基金青年基金(61403174)

沈鑫(1994-)，男，碩士研究生。研究方向：群智能算法。鄒德旋(1982-)，男，博士, 副教授。研究方向：群智能算法。張鑫(1994-)，男，碩士研究生。研究方向：群智能算法。

TN911;TP306.1

A

1007-7820(2018)02-051-05