基于多鄰域策略重心反向?qū)W習(xí)的差分進(jìn)化算法

李 俊，鄒 杰，李 波，劉嘉麒

(1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢，430065； 2.武漢科技大學(xué)智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430065)

差分進(jìn)化(differential evolution，DE)算法最初用于解決切比雪夫多項(xiàng)式問(wèn)題[1]，后來(lái)發(fā)現(xiàn)它也是解決復(fù)雜優(yōu)化問(wèn)題的有效技術(shù)。DE算法對(duì)控制參數(shù)和變異策略比較敏感，不同的參數(shù)設(shè)置和變異策略適用于不同的問(wèn)題，相關(guān)研究成果也有不少。李牧東等[2]將隨機(jī)高斯游走策略運(yùn)用到DE算法中，提高了算法的開(kāi)發(fā)能力和收斂速度。彭虎等[3]提出一種基于三角骨架的差分進(jìn)化算法，其采用三角高斯變異策略以及三元交叉，能充分利用每個(gè)個(gè)體的有用信息，避免了潛在有用信息的丟失。劉會(huì)超等[4]提出旋轉(zhuǎn)學(xué)習(xí)機(jī)制并運(yùn)用到DE算法中，旋轉(zhuǎn)學(xué)習(xí)通過(guò)調(diào)整角度能搜索空間中的任意一點(diǎn)，從而提高算法的探索能力。Leon等[5]設(shè)計(jì)一種新的變異策略DE/Alopex/1，其不同之處在于使用群體中個(gè)體的適應(yīng)度值來(lái)計(jì)算移動(dòng)方向的概率。周新宇等[6]提出了基于精英反向?qū)W習(xí)的差分進(jìn)化算法，精英反向解能有效地保持種群的多樣性。劉罡等[7]提出基于分子動(dòng)理論的差分進(jìn)化算法，通過(guò)引入分子合力來(lái)控制粒子向全局最優(yōu)解靠近。魏文紅等[8]采用基于反向?qū)W習(xí)的機(jī)器學(xué)習(xí)方法，利用機(jī)器學(xué)習(xí)指導(dǎo)種群進(jìn)化，同時(shí)反向?qū)W習(xí)能保持種群多樣性。王亞輝等[9]將種群劃分為3個(gè)子種群,每個(gè)子種群分配一種差分進(jìn)化策略,然后根據(jù)每種策略的貢獻(xiàn)度來(lái)動(dòng)態(tài)調(diào)整子種群的規(guī)模，各差分進(jìn)化策略之間相互配合協(xié)同進(jìn)化。張貴軍等[10]提出一種基于共軛增強(qiáng)的差分進(jìn)化算法，以平衡算法的全局探測(cè)能力和局部搜索能力。汪慎文等[11]提出一種向優(yōu)秀個(gè)體靠攏同時(shí)遠(yuǎn)離較差個(gè)體的樸素差分進(jìn)化算法，能有效提高算法的收斂速度。張斌等[12]提出基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法，運(yùn)用3種策略對(duì)子種群進(jìn)行操作，提高了算法的求解精度和穩(wěn)定性。

Piotrowski[13]提出了具有全局和局部鄰域變異算子的自適應(yīng)文化基因差分進(jìn)化算法，該算法隨機(jī)選擇全局和局部變異策略，然后根據(jù)權(quán)重來(lái)自適應(yīng)調(diào)整其對(duì)個(gè)體進(jìn)化的影響，并且使用了局部搜索算法NMA(Nelder-Mead algorithm)。文獻(xiàn)[13]中的算法在收斂精度和收斂速度等性能上都有極大的改善，但其采用的是多種變異策略，算法的學(xué)習(xí)成本高，而且對(duì)鄰域空間探索不夠充分。本文在文獻(xiàn)[13]的基礎(chǔ)上構(gòu)建基于多鄰域策略和鄰域重心反向?qū)W習(xí)的差分進(jìn)化(MCOBDE)算法，首先根據(jù)種群進(jìn)化狀態(tài)動(dòng)態(tài)選擇鄰域策略，同時(shí)在不同的鄰域策略中采用不同的鄰域拓?fù)浣Y(jié)構(gòu)，然后在鄰域空間中進(jìn)行重心反向?qū)W習(xí)。最后通過(guò)15個(gè)測(cè)試函數(shù)來(lái)驗(yàn)證本文算法的有效性和準(zhǔn)確性，并與其他算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。

1 DE算法

DE算法是基于群體的自適應(yīng)全局優(yōu)化算法，其首先要隨機(jī)初始化種群，然后再迭代進(jìn)行差分變異、雜交、選擇3個(gè)DE算法的基本操作。差分變異是DE算法進(jìn)入迭代后最先執(zhí)行的算子，而且差分變異是差分進(jìn)化思想最顯著的特征。種群按照順序執(zhí)行差分變異，按照差分變異策略隨機(jī)選擇多個(gè)不同的個(gè)體進(jìn)行變異操作，最常見(jiàn)的差分變異策略有以下5種：

(1)DE/rand/1:

Vi,g=Xi1,g+F(Xi2,g-Xi3,g)

(1)

(2)DE/best/1:

Vi,g=Xbest,g+F(Xi1,g-Xi2,g)

(2)

(3)DE/current-to-best/1：

Vi,g=Xi,g+F(Xbest,g-Xi,g)+
F(Xi1,g-Xi2,g)

(3)

(4)DE/rand/2：

Vi,g=Xi1,g+F(Xi2,g-Xi3,g)+
F(Xi4,g-Xi5,g)

(4)

(5)DE/best/2：

Vi,g=Xbest,g+F(Xi1,g-Xi2,g)+
F(Xi3,g-Xi4,g)

(5)

式中：Vi,g為變異所得到的個(gè)體；Xi1,g～Xi5,g為從當(dāng)前種群中隨機(jī)選取的5個(gè)不同個(gè)體；Xi,g為當(dāng)前個(gè)體；Xbest,g為當(dāng)前全局最優(yōu)個(gè)體；F為縮放比例；g為當(dāng)前進(jìn)化代數(shù)。

雜交即交叉，根據(jù)交叉概率CR對(duì)變異算子產(chǎn)生的變異個(gè)體Vi與當(dāng)前個(gè)體進(jìn)行重組，得到一個(gè)實(shí)驗(yàn)個(gè)體Ui。然后進(jìn)行選擇操作，即實(shí)驗(yàn)個(gè)體與種群中原先的個(gè)體比較適應(yīng)度值，適應(yīng)度值優(yōu)的個(gè)體保留進(jìn)入下一代，適應(yīng)度值差的個(gè)體淘汰。

2 MCOBDE算法

2.1 鄰域策略的選擇

為了提高DE算法的性能，必須保證算法在進(jìn)化前期具有更好的探索能力，以便盡可能地找到最優(yōu)解，避免“早熟”，從而提高算法精度；而在進(jìn)化后期，則需要種群能盡快收斂到最優(yōu)解附近，提高算法收斂速度。因此本文提出在不同進(jìn)化階段依照概率來(lái)選擇不同的鄰域策略以及相應(yīng)的鄰域拓?fù)浣Y(jié)構(gòu)，即

(6)

式中：N為選擇的鄰域策略；L表示局部鄰域策略，采用環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)，G表示全局鄰域策略，采用星形鄰域拓?fù)浣Y(jié)構(gòu)；rand為[0,1]區(qū)間均勻分布的隨機(jī)數(shù)；Gmax為最大進(jìn)化代數(shù)。

由式(6)可知，算法在進(jìn)化前期選擇局部鄰域策略的概率較大，而在后期選擇全局鄰域策略的概率較大。局部鄰域策略使用環(huán)形拓?fù)浣Y(jié)構(gòu)在算法前期有利于提高全局搜索能力，全局鄰域策略使用星形拓?fù)浣Y(jié)構(gòu)則有利于加快算法收斂。

2.2 鄰域重心反向?qū)W習(xí)

文獻(xiàn)[13]對(duì)鄰域空間沒(méi)有進(jìn)行充分探索，算法尋優(yōu)能力不足，容易陷入局部最優(yōu)，因此本文引入鄰域重心反向?qū)W習(xí)機(jī)制。反向?qū)W習(xí)[14]的主要思想是同時(shí)評(píng)估當(dāng)前個(gè)體和反向個(gè)體，擇優(yōu)選擇，以此來(lái)加快搜索。周凌云等[15]據(jù)此提出鄰域重心反向?qū)W習(xí)機(jī)制，鄰域重心及重心反向點(diǎn)的定義如下。

定義1鄰域重心：(X1,…,Xn)是D維空間中處在同一鄰域中的帶有單位質(zhì)量的n個(gè)點(diǎn)，則該鄰域的重心定義為

M=(X1+X2+…+Xn)/n

(7)

即

(8)

定義2重心反向點(diǎn)：若一個(gè)離散均勻的整體的重心為M，則該整體中某一點(diǎn)Xi的反向點(diǎn)定義為

(9)

反向點(diǎn)位于一個(gè)具有動(dòng)態(tài)邊界的搜索空間，記Xi,j∈[aj,bj]。動(dòng)態(tài)邊界可以讓搜索空間不斷縮小，其計(jì)算公式為

aj=min(Xi,j),bj=max(Xi,j)

(10)

如反向點(diǎn)超出搜索邊界，可按下式重新計(jì)算反向點(diǎn)：

(11)

然而實(shí)驗(yàn)表明，采用式(11)重新計(jì)算的反向點(diǎn)可能聚集到一塊較小的區(qū)域，導(dǎo)致算法陷入局部最優(yōu)，因此本文采用下式在搜索空間內(nèi)重新計(jì)算反向點(diǎn):

(12)

應(yīng)用鄰域重心反向點(diǎn)學(xué)習(xí)時(shí)，為了防止反向點(diǎn)與其他個(gè)體重復(fù)，造成重復(fù)評(píng)估，影響算法的收斂速度，可在原先的鄰域重心計(jì)算公式中引入收縮因子k，即

(13)

式中：k為[0,1]區(qū)間均勻分布的隨機(jī)數(shù)。k的引入避免了出現(xiàn)重復(fù)點(diǎn)，也拓展了反向搜索范圍。

本文首次提出將鄰域重心反向計(jì)算應(yīng)用到DE算法中，鄰域重心反向?qū)W習(xí)能使種群在算法前期利用鄰域搜索經(jīng)驗(yàn)充分探索鄰域空間，而在算法后期能更多地保留有用信息，保持種群的多樣性。

2.3 變異策略的選擇

在不同的鄰域策略下種群的進(jìn)化狀態(tài)不同，所要達(dá)到的目的也不同。在局部鄰域策略下，種群需要盡可能地搜索解空間，因此要選擇探索能力強(qiáng)的變異策略；在全局鄰域策略下，種群則需要盡快收斂到最優(yōu)解附近，因此要選擇收斂速度快的變異策略。具體變異策略選擇如下：

(14)

式中：Xr1,g、Xr2,g表示從個(gè)體在局部鄰域策略下采用環(huán)形鄰域結(jié)構(gòu)的鄰居中隨機(jī)選擇的兩個(gè)不同個(gè)體，并且r1≠r2≠i；Xt1,g、Xt2,g表示從個(gè)體在全局鄰域策略下采用星形鄰域拓?fù)浣Y(jié)構(gòu)的鄰居中隨機(jī)選擇的兩個(gè)不同個(gè)體，并且t1≠t2≠i。

多次實(shí)驗(yàn)表明，如果算法當(dāng)前采用的是局部鄰域策略，選擇DE/rand/1變異策略有利于算法的全局搜索，同時(shí)局部鄰域下的鄰域范圍可能為1，DE/rand/1能防止出現(xiàn)父?jìng)€(gè)體不足的情況；如果算法當(dāng)前采用的是全局鄰域策略，選擇DE/current-to-best/1變異策略有利于算法的快速收斂，同時(shí)DE/current-to-best/1變異策略有一定的擾動(dòng)，能避免算法陷入局部最優(yōu)。

2.4 選擇學(xué)習(xí)

個(gè)體在進(jìn)化過(guò)程中要實(shí)時(shí)選擇不同的父?jìng)€(gè)體進(jìn)行學(xué)習(xí)。個(gè)體的狀態(tài)不同，需要選擇的父?jìng)€(gè)體也不同，選擇不恰當(dāng)?shù)母競(jìng)€(gè)體進(jìn)行學(xué)習(xí)，不僅對(duì)個(gè)體自身的幫助較小，同時(shí)又白白消耗了計(jì)算資源。本文參照文獻(xiàn)[16]，根據(jù)當(dāng)前個(gè)體是否為全局最優(yōu)個(gè)體來(lái)選擇不同的父?jìng)€(gè)體。

(1)當(dāng)前個(gè)體為全局最優(yōu)個(gè)體時(shí)，則該個(gè)體從其鄰域結(jié)構(gòu)學(xué)習(xí)到的有益信息較少，因此應(yīng)當(dāng)重新選擇合適的個(gè)體進(jìn)行學(xué)習(xí)，即

(15)

式中：Xbest1,g、Xbest2,g表示在全局鄰域策略下，除個(gè)體Xi,g外全局最優(yōu)的兩個(gè)個(gè)體，Xi,g采用DE/rand/1策略向Xbest1,g、Xbest2,g學(xué)習(xí)，這樣有利于加快算法的收斂；Xr1,g、Xr2,g表示在局部鄰域策略下，與個(gè)體Xi,g的歐式距離最遠(yuǎn)的兩個(gè)個(gè)體，Xi,g采用DE/rand/1策略向Xr1,g、Xr2,g學(xué)習(xí)，這樣有利于加大種群的搜索空間。

(2)當(dāng)前個(gè)體非全局最優(yōu)個(gè)體時(shí)，說(shuō)明該個(gè)體鄰域內(nèi)的有益信息未被充分利用，則該個(gè)體繼續(xù)采用式(14)的相應(yīng)策略進(jìn)行學(xué)習(xí)。

2.5佳點(diǎn)集

PNP(i)={({r1·i},{r2·i},…,{rD·i}),

i=1,2,…,NP}

(16)

其中

(17)

式(16)～式(17)中：{rj·i}表示rj·i的小數(shù)部分；t是滿足t≥2D+3的最小素?cái)?shù)。

本文算法在搜索范圍內(nèi)產(chǎn)生佳點(diǎn)集，設(shè)種群搜索范圍為[Xmin,Xmax]，則取值公式為

i=1,2,…,NP;j=1,2,…,D

(18)

2.6 算法實(shí)現(xiàn)

在MCOBDE算法中，環(huán)形鄰域范圍K是一個(gè)在(0,(NP-1)/2]區(qū)間的隨機(jī)整數(shù)，交叉概率CR、縮放比例F以及鄰域重心反向?qū)W習(xí)概率P均為[0,1] 區(qū)間的常數(shù)。算法具體實(shí)現(xiàn)如下。

BEGIN

(1)根據(jù)式(18)初始化種群，并計(jì)算目標(biāo)函數(shù)值，保存到Fit數(shù)組中；

(2)隨機(jī)生成(0,(NP-1)/2]范圍的一個(gè)整數(shù)K，為環(huán)形鄰域結(jié)構(gòu)的鄰域個(gè)體數(shù)，令g=0；

(3)根據(jù)隨機(jī)生成的鄰域范圍，按環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)確定每個(gè)個(gè)體的鄰居；

(4)whileg

(5) ifrand≤sqrt(g/Gmax)

(6) 選擇局部鄰域策略，采用環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)進(jìn)行學(xué)習(xí)

(7) fori=1 toNPdo

(8) ifrand

(9) 個(gè)體i進(jìn)行鄰域重心反向?qū)W習(xí)

(10) end if

(11) forj=1 toDdo

(12) ifrand

(13) ifi為全局最優(yōu)個(gè)體

(14) 根據(jù)式(15)選擇相應(yīng)的變異策略來(lái)學(xué)習(xí)

(15) else

(16) 根據(jù)式(14)選擇相應(yīng)的變異策略來(lái)學(xué)習(xí)

(17) end if

(18) end if

(19) end for

(20) if 新個(gè)體的目標(biāo)函數(shù)值小于原先個(gè)體

(21) 更新種群

(22) 更新個(gè)體i的目標(biāo)函數(shù)值到Fit數(shù)組

(23) end if

(24) end for

(25) else

(26) fori=1 toNPdo

(27) 采用全局鄰域策略及星形鄰域拓?fù)浣Y(jié)構(gòu)進(jìn)行學(xué)習(xí)

(28) ifrand

(29) 個(gè)體i進(jìn)行鄰域重心反向?qū)W習(xí)

(30) end if

(31) forj=1 toDdo

(32) ifrand

(33) ifi為全局最優(yōu)個(gè)體

(34) 根據(jù)式(15)選擇相應(yīng)的變異策略來(lái)學(xué)習(xí)

(35) else

(36) 根據(jù)式(14)選擇相應(yīng)的變異策略來(lái)學(xué)習(xí)

(37) end if

(38) end if

(39) end for

(40) if 新個(gè)體的目標(biāo)函數(shù)值小于原先個(gè)體

(41) 更新種群

(42) 更新個(gè)體i的目標(biāo)函數(shù)值到Fit數(shù)組

(43) end if

(44) end for

(45) end if

(46) 將最優(yōu)個(gè)體以及最優(yōu)個(gè)體目標(biāo)函數(shù)值保存到相應(yīng)的數(shù)組中

(47)g=g+1

(48)end while

END

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

3.1 參數(shù)設(shè)置

MCOBDE算法的各項(xiàng)參數(shù)設(shè)置：在低維情況下種群規(guī)模NP=150，問(wèn)題維度D=30，最大演化代數(shù)Gmax=2000，最大函數(shù)評(píng)價(jià)次數(shù)FES=300 000；在高維情況下NP=250，D=50，Gmax=2000，F(xiàn)ES=500 000；交叉概率CR=0.9，縮放比例F=0.5，鄰域重心反向?qū)W習(xí)概率P=0.3。

為了全面客觀地對(duì)MCOBDE算法進(jìn)行評(píng)價(jià)，本文將其與標(biāo)準(zhǔn)DE算法(DE/rand/1)以及研究人員近些年提出的優(yōu)秀算法JDE[18]、JADE[19]、tBBDE[3]、RDE[4]、DE/Alopex/1[5]、AM_DEGL[12]在收斂精度和收斂速度上進(jìn)行比較，各算法均獨(dú)立運(yùn)行20次。其他比較算法的參數(shù)設(shè)置均與原文獻(xiàn)一致。實(shí)驗(yàn)環(huán)境為：處理器Intel(R) Core(TM)i5-3470 @ 3.20 GHz，RAM 4 GB，win7 64位操作系統(tǒng)，MATLAB R2012a。

3.2 測(cè)試函數(shù)

為了驗(yàn)證本文算法的適用性、有效性和準(zhǔn)確性，選擇CEC2015[20]中的15個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，具體定義如表1所示，其中f1、f2為單峰函數(shù)，f3、f4、f5為簡(jiǎn)單多峰函數(shù)，f6、f7、f8為混合函數(shù)，f9～f15為復(fù)合函數(shù)。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 收斂精度

表2為各算法的實(shí)驗(yàn)結(jié)果在低維情況下的平均值、最小值和方差對(duì)比，其中最好結(jié)果已加粗標(biāo)出。從平均值指標(biāo)來(lái)看，對(duì)于f1、f6、f8、f10、f11、f12測(cè)試函數(shù)，MCOBDE算法要優(yōu)于參與比較的其他算法，對(duì)于f9、f15測(cè)試函數(shù)，MCOBDE算法與其他算法性能持平。同時(shí)，MCOBDE算法在測(cè)試函數(shù)f2、f6、f7、f8、f10、f11、f12的最小值指標(biāo)上比較有優(yōu)勢(shì)，在測(cè)試函數(shù)f1、f5、f11的方差指標(biāo)上優(yōu)勢(shì)明顯。

表2 MCOBDE與其他算法的比較(D=30)

綜上所述，針對(duì)低維問(wèn)題，MCOBDE算法總體上優(yōu)于其他算法，這說(shuō)明合適的鄰域結(jié)構(gòu)以及鄰域重心反向?qū)W習(xí)確實(shí)能提高算法的尋優(yōu)能力，同時(shí)也能使算法具有較強(qiáng)的穩(wěn)定性。

圖1是各算法在低維情況下求解測(cè)試函數(shù)f1、f8、f10的收斂曲線。從f1的收斂曲線可以看出，與其他算法相比，MCOBDE算法明顯收斂精度高、收斂速度快；對(duì)于測(cè)試函數(shù)f8和f10，MCOBDE算法的收斂速度和收斂精度也比其他算法占優(yōu)。

(a) 測(cè)試函數(shù)f1

(b)測(cè)試函數(shù)f8

(c) 測(cè)試函數(shù)f10

圖1Convergencecurvesoftestfunctionf1,f8,f10solvedbyeightalgorithms(D=30)

表3為各算法的實(shí)驗(yàn)結(jié)果在高維情況下的平均值、最小值和方差對(duì)比，其中最好數(shù)據(jù)已加粗顯示。從表中數(shù)據(jù)可以看出，D=50時(shí)，對(duì)于測(cè)試函數(shù)f1、f2、f6、f7、f8、f9、f10、f12、f15，MCOBDE在平均值指標(biāo)上要優(yōu)于(至少持平于)其他算法；對(duì)于測(cè)試函數(shù)f1、f2、f6、f7、f8、f9、f11、f12、f14、f15，MCOBDE在最小值指標(biāo)上要優(yōu)于(至少持平于)其他算法。這表明MCOBDE算法解決高維問(wèn)題時(shí)性能更為優(yōu)異，進(jìn)一步驗(yàn)證了MCOBDE算法具有很強(qiáng)的適應(yīng)性，對(duì)于不同類別和不同難度的問(wèn)題都有很好的尋優(yōu)能力。

表3 MCOBDE與其他算法的比較(D=50)

續(xù)表

測(cè)試函數(shù)指標(biāo)DE/rand/1JDEJADEtBBDERDEDE/Alopex/1AM_DEGLMCOBDEf9平均值1.01E+031.00E+031.01E+031.00E+031.01E+031.01E+031.01E+031.00E+03最小值1.01E+031.00E+031.01E+031.00E+031.01E+031.00E+031.01E+031.00E+03方差6.59E-022.03E-025.46E-017.69E-025.25E-021.36E-021.18E-013.17E-02f10平均值4.99E+034.25E+031.08E+041.95E+054.67E+033.48E+052.34E+031.96E+03最小值4.62E+033.54E+032.82E+033.13E+044.26E+032.05E+051.98E+031.66E+03方差5.64E+047.61E+042.33E+082.08E+104.99E+045.36E+097.70E+045.28E+04f11平均值1.63E+031.51E+031.75E+031.57E+031.52E+031.57E+031.52E+031.61E+03最小值1.57E+031.50E+031.41E+031.51E+031.51E+031.52E+031.40E+031.40E+03方差1.58E+032.97E+018.66E+041.88E+037.59E+014.35E+021.12E+037.15E+03f12平均值1.31E+031.31E+031.31E+031.31E+031.31E+031.31E+031.31E+031.31E+03最小值1.31E+031.31E+031.31E+031.31E+031.31E+031.31E+031.31E+031.31E+03方差4.64E-012.42E-011.08E+004.04E-014.93E-012.95E-011.22E+003.16E-01f13平均值1.53E+031.51E+031.51E+031.52E+031.53E+031.52E+031.50E+031.52E+03最小值1.53E+031.51E+031.50E+031.51E+031.52E+031.52E+031.49E+031.51E+03方差4.23E+007.93E+001.13E+019.86E+008.22E+003.73E+001.35E+011.86E+01f14平均值6.28E+047.06E+045.26E+046.41E+045.88E+045.09E+045.94E+045.86E+04最小值5.09E+045.09E+045.09E+045.09E+045.09E+045.09E+045.09E+045.09E+04方差1.21E+087.26E+072.04E+071.49E+081.03E+081.89E+004.89E+071.24E+08f15平均值1.60E+031.60E+031.60E+031.60E+036.85E+031.60E+031.60E+031.60E+03最小值1.60E+031.60E+031.60E+031.60E+031.60E+031.60E+031.60E+031.60E+03方差8.62E-051.40E-172.24E+015.44E-265.51E+081.47E-252.01E-162.97E-25

3.3.2 收斂速度

采用固定精度的方法測(cè)試算法的收斂速度，最大函數(shù)評(píng)價(jià)次數(shù)FES均為300 000，預(yù)設(shè)收斂精度VTR如表4所示。

表4 預(yù)設(shè)收斂精度VTR

各算法在維度D=30的情況下獨(dú)立運(yùn)行20次，比較達(dá)到預(yù)設(shè)精度所需要的平均評(píng)價(jià)次數(shù)，如表5所示。從表中可以看出，在給定精度下，MCOBDE算法針對(duì)大部分測(cè)試函數(shù)的平均評(píng)價(jià)次數(shù)與其他算法相比要少很多，表明MCOBDE算法具有更快的收斂速度。

3.4 算法復(fù)雜度分析

根據(jù)算法實(shí)現(xiàn)分析其復(fù)雜度。算法步驟(1)初始化種群以及適應(yīng)度計(jì)算復(fù)雜度為O(NP·D)，步驟(9)鄰域重心反向?qū)W習(xí)復(fù)雜度為O(D)，步驟(11)～(23)針對(duì)每一維的變異、交叉、選擇的復(fù)雜度為O(D)，則步驟(7)～(24)每一次迭代的復(fù)雜度為O(NP·D)，同理步驟(26)～(44)每一次迭代的復(fù)雜度也為O(NP·D)，因此步驟(4)～(48)的復(fù)雜度為O(NP·D·Gmax)。綜上所述，略去低階項(xiàng)，MCOBDE算法的復(fù)雜度為O(NP·D·Gmax)，與標(biāo)準(zhǔn)DE算法的復(fù)雜度一致，故MCOBDE算法在獲得較優(yōu)計(jì)算效果的前提下并沒(méi)有增加過(guò)多的計(jì)算時(shí)間開(kāi)銷。

表5 給定目標(biāo)精度下的平均評(píng)價(jià)次數(shù)

4 結(jié)語(yǔ)

本文提出了一種多鄰域策略重心反向?qū)W習(xí)的差分進(jìn)化算法MCOBDE。該算法根據(jù)當(dāng)前進(jìn)化狀態(tài)選擇合適的鄰域策略，同時(shí)不同的鄰域策略使用恰當(dāng)?shù)泥徲蛲負(fù)浣Y(jié)構(gòu)，從而提高了算法的收斂精度和收斂速度，并且鄰域重心反向?qū)W習(xí)的加入使得種群能更好地探索鄰域空間，增加找到最優(yōu)解的概率。MCOBDE算法的時(shí)間復(fù)雜度同標(biāo)準(zhǔn)DE算法一致。通過(guò)對(duì)15個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)以及與其他幾個(gè)有代表性的DE算法的比較，證明了本文算法的適用性、有效性和準(zhǔn)確性。

參考文獻(xiàn)

[1] Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces[R]. Berkeley: International Computer Science Institute, 1995. TR-95-012.

[2] 李牧東,趙輝,翁興偉,等.基于最優(yōu)高斯隨機(jī)游走和個(gè)體篩選策略的差分進(jìn)化算法[J].控制與決策, 2016,31(8):1379-1386.

[3] 彭虎,吳志健,周新宇,等.基于三角的骨架差分進(jìn)化算法[J].計(jì)算機(jī)研究與發(fā)展,2015,52(12):2776-2788.

[4] 劉會(huì)超,吳志健.基于旋轉(zhuǎn)學(xué)習(xí)機(jī)制的差分進(jìn)化算法[J].電子學(xué)報(bào), 2015,43(10):2040-2046.

[5] Leon M, Xiong N. Alopex-based mutation strategy in differential evolution[C]//2017 IEEE Congress on Evolutionary Computation (CEC). San Sebastian, Spain, July 2017: 1978-1984.

[6] 周新宇,吳志健,王暉.一種精英反向?qū)W習(xí)的差分進(jìn)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(9):2129-2134.

[7] 劉罡,李元香.分子動(dòng)理論的新型反向差分進(jìn)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(1):115-120.

[8] 魏文紅,周建龍,陶銘,等.一種基于反向?qū)W習(xí)的約束差分進(jìn)化算法[J]. 電子學(xué)報(bào),2016,44(2):426-436.

[9] 王亞輝,吳金妹,賈晨輝.基于動(dòng)態(tài)種群多策略差分進(jìn)化模型的多目標(biāo)進(jìn)化算法[J].電子學(xué)報(bào),2016,44(6):1472-1480.

[10] 張貴軍,王柳靜,周曉根,等.基于共軛增強(qiáng)策略的差分進(jìn)化算法[J]. 控制與決策,2017,32(7):1313-1318.

[11] 汪慎文,張文生,秦進(jìn),等.樸素差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用,2015, 35(5):1333-1335.

[12] 張斌,李延暉,郭昊.基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用,2017,37(4):1093-1099.

[13] Piotrowski A P. Adaptive memetic differential evolution with global and local neighborhood-based mutation operators[J]. Information Sciences, 2013, 241(12):164-194.

[14] Tizhoosh H R. Opposition-based learning: a new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. IEEE Computer Society, Vienna, 2005:695-701.

[15] 周凌云,丁立新,彭虎,等.一種鄰域重心反向?qū)W習(xí)的粒子群優(yōu)化算法[J].電子學(xué)報(bào),2017,45(11):2815-2824.

[16] 夏學(xué)文,桂凌,戴志鋒,等.基于多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO算法[J].電子學(xué)報(bào),2016,44(5):1090-1100.

[17] 張鈴,張鈸.佳點(diǎn)集遺傳算法[J].計(jì)算機(jī)學(xué)報(bào),2001,24(9):917-922.

[19] Zhang J Q, Sanderson A C. JADE: self-adaptive differential evolution with fast and reliable convergence performance[C]//IEEE Congress on Evolutionary Computation (CEC’07). IEEE, Singapore, 25-28 Sept. 2007:2251-2258.

[20] Liang J J , Qu B Y, Suganthan P N , et al. Problem definitions and evaluation criteria for the CEC 2015 competition on learning-based real-parameter single objective optimization[R]. Zhengzhou: Computational Intelligence Laboratory, Zhengzhou University. Singapore: Nanyang Technological University. 2014: Technical Report 201411A.