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

沈 鑫，鄒德旋，張 鑫

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

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

沈 鑫，鄒德旋，張 鑫

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

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

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

差分進(jìn)化(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算法到了進(jìn)化后期，種群的多樣性降低，容易出現(xiàn)早熟收斂和收斂精度不高的問題。

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

1 標(biāo)準(zhǔn)的差分進(jìn)化算法

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

(1)

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

(2)

(3)

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

(4)

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

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

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

2.1 隨機(jī)變異操作

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

(5)

2.2 擾動(dòng)操作

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

if rand

(6)

else

end

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

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

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

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

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

(7)

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

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

(8)

(9)

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

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

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

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

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

步驟5利用貪婪原則進(jìn)行選擇，較好的個(gè)體將存活，進(jìn)入下一代；

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

3 實(shí)驗(yàn)仿真與分析

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

仿真實(shí)驗(yàn)使用Matlab8.3軟件來編程實(shí)現(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ù)值見文獻(xiàn)[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；算法對(duì)不同測試函數(shù)的最大迭代次數(shù)在表中給出；種群的邊界范圍是[-100,100]；維數(shù)D=100。

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

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

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

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

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

圖1 收斂曲線

圖2 收斂曲線

圖3 收斂曲線

圖4 收斂曲線

圖5 收斂曲線

圖6 收斂曲線

圖7 收斂曲線

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

4 結(jié)束語

SRDE算法將RMDE算法中的隨機(jī)策略選擇，小概率擾動(dòng)和參數(shù)自適應(yīng)結(jié)合起來用于函數(shù)優(yōu)化，更好的利用了種群信息和有效避免了早熟收斂。將SRDE算法、DE/rand/1/bin策略的DE算法、DE/best/1/bin策略的DE算法、RMDE算法、PSO算法用來優(yōu)化7個(gè)經(jīng)典函數(shù)并對(duì)結(jié)果進(jìn)行對(duì)比，結(jié)果表明：SRDE算法具有較強(qiáng)的全局搜索能力和收斂精度。在接下來的工作中，將改進(jìn)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] 李目,何怡剛,周少武,等.一種差分進(jìn)化算法優(yōu)化小波神經(jīng)網(wǎng)絡(luò)及其在弱信號(hào)檢測中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(3):29-31.

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

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

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

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

[7] 張雪霞,陳維榮,戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化[J].電子學(xué)報(bào),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ìn)化算法[J].計(jì)算機(jī)與應(yīng)用,2010,46(18):9-12.

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

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

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

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

[14] 歐陽海濱,高立群,孔祥勇.隨機(jī)變異差分進(jìn)化算法[J].東北大學(xué)學(xué)報(bào):自然科學(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