基于多鄰域策略重心反向學習的差分進化算法

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

(1.武漢科技大學計算機科學與技術學院，湖北 武漢，430065； 2.武漢科技大學智能信息處理與實時工業系統湖北省重點實驗室，湖北 武漢，430065)

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

Piotrowski[13]提出了具有全局和局部鄰域變異算子的自適應文化基因差分進化算法，該算法隨機選擇全局和局部變異策略，然后根據權重來自適應調整其對個體進化的影響，并且使用了局部搜索算法NMA(Nelder-Mead algorithm)。文獻[13]中的算法在收斂精度和收斂速度等性能上都有極大的改善，但其采用的是多種變異策略，算法的學習成本高，而且對鄰域空間探索不夠充分。本文在文獻[13]的基礎上構建基于多鄰域策略和鄰域重心反向學習的差分進化(MCOBDE)算法，首先根據種群進化狀態動態選擇鄰域策略，同時在不同的鄰域策略中采用不同的鄰域拓撲結構，然后在鄰域空間中進行重心反向學習。最后通過15個測試函數來驗證本文算法的有效性和準確性，并與其他算法的實驗結果進行比較。

1 DE算法

DE算法是基于群體的自適應全局優化算法，其首先要隨機初始化種群，然后再迭代進行差分變異、雜交、選擇3個DE算法的基本操作。差分變異是DE算法進入迭代后最先執行的算子，而且差分變異是差分進化思想最顯著的特征。種群按照順序執行差分變異，按照差分變異策略隨機選擇多個不同的個體進行變異操作，最常見的差分變異策略有以下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為變異所得到的個體；Xi1,g～Xi5,g為從當前種群中隨機選取的5個不同個體；Xi,g為當前個體；Xbest,g為當前全局最優個體；F為縮放比例；g為當前進化代數。

雜交即交叉，根據交叉概率CR對變異算子產生的變異個體Vi與當前個體進行重組，得到一個實驗個體Ui。然后進行選擇操作，即實驗個體與種群中原先的個體比較適應度值，適應度值優的個體保留進入下一代，適應度值差的個體淘汰。

2 MCOBDE算法

2.1 鄰域策略的選擇

為了提高DE算法的性能，必須保證算法在進化前期具有更好的探索能力，以便盡可能地找到最優解，避免“早熟”，從而提高算法精度；而在進化后期，則需要種群能盡快收斂到最優解附近，提高算法收斂速度。因此本文提出在不同進化階段依照概率來選擇不同的鄰域策略以及相應的鄰域拓撲結構，即

(6)

式中：N為選擇的鄰域策略；L表示局部鄰域策略，采用環形鄰域拓撲結構，G表示全局鄰域策略，采用星形鄰域拓撲結構；rand為[0,1]區間均勻分布的隨機數；Gmax為最大進化代數。

由式(6)可知，算法在進化前期選擇局部鄰域策略的概率較大，而在后期選擇全局鄰域策略的概率較大。局部鄰域策略使用環形拓撲結構在算法前期有利于提高全局搜索能力，全局鄰域策略使用星形拓撲結構則有利于加快算法收斂。

2.2 鄰域重心反向學習

文獻[13]對鄰域空間沒有進行充分探索，算法尋優能力不足，容易陷入局部最優，因此本文引入鄰域重心反向學習機制。反向學習[14]的主要思想是同時評估當前個體和反向個體，擇優選擇，以此來加快搜索。周凌云等[15]據此提出鄰域重心反向學習機制，鄰域重心及重心反向點的定義如下。

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

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

(7)

即

(8)

定義2重心反向點：若一個離散均勻的整體的重心為M，則該整體中某一點Xi的反向點定義為

(9)

反向點位于一個具有動態邊界的搜索空間，記Xi,j∈[aj,bj]。動態邊界可以讓搜索空間不斷縮小，其計算公式為

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

(10)

如反向點超出搜索邊界，可按下式重新計算反向點：

(11)

然而實驗表明，采用式(11)重新計算的反向點可能聚集到一塊較小的區域，導致算法陷入局部最優，因此本文采用下式在搜索空間內重新計算反向點:

(12)

應用鄰域重心反向點學習時，為了防止反向點與其他個體重復，造成重復評估，影響算法的收斂速度，可在原先的鄰域重心計算公式中引入收縮因子k，即

(13)

式中：k為[0,1]區間均勻分布的隨機數。k的引入避免了出現重復點，也拓展了反向搜索范圍。

本文首次提出將鄰域重心反向計算應用到DE算法中，鄰域重心反向學習能使種群在算法前期利用鄰域搜索經驗充分探索鄰域空間，而在算法后期能更多地保留有用信息，保持種群的多樣性。

2.3 變異策略的選擇

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

(14)

式中：Xr1,g、Xr2,g表示從個體在局部鄰域策略下采用環形鄰域結構的鄰居中隨機選擇的兩個不同個體，并且r1≠r2≠i；Xt1,g、Xt2,g表示從個體在全局鄰域策略下采用星形鄰域拓撲結構的鄰居中隨機選擇的兩個不同個體，并且t1≠t2≠i。

多次實驗表明，如果算法當前采用的是局部鄰域策略，選擇DE/rand/1變異策略有利于算法的全局搜索，同時局部鄰域下的鄰域范圍可能為1，DE/rand/1能防止出現父個體不足的情況；如果算法當前采用的是全局鄰域策略，選擇DE/current-to-best/1變異策略有利于算法的快速收斂，同時DE/current-to-best/1變異策略有一定的擾動，能避免算法陷入局部最優。

2.4 選擇學習

個體在進化過程中要實時選擇不同的父個體進行學習。個體的狀態不同，需要選擇的父個體也不同，選擇不恰當的父個體進行學習，不僅對個體自身的幫助較小，同時又白白消耗了計算資源。本文參照文獻[16]，根據當前個體是否為全局最優個體來選擇不同的父個體。

(1)當前個體為全局最優個體時，則該個體從其鄰域結構學習到的有益信息較少，因此應當重新選擇合適的個體進行學習，即

(15)

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

(2)當前個體非全局最優個體時，說明該個體鄰域內的有益信息未被充分利用，則該個體繼續采用式(14)的相應策略進行學習。

2.5佳點集

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

i=1,2,…,NP}

(16)

其中

(17)

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

本文算法在搜索范圍內產生佳點集，設種群搜索范圍為[Xmin,Xmax]，則取值公式為

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

(18)

2.6 算法實現

在MCOBDE算法中，環形鄰域范圍K是一個在(0,(NP-1)/2]區間的隨機整數，交叉概率CR、縮放比例F以及鄰域重心反向學習概率P均為[0,1] 區間的常數。算法具體實現如下。

BEGIN

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

(2)隨機生成(0,(NP-1)/2]范圍的一個整數K，為環形鄰域結構的鄰域個體數，令g=0；

(3)根據隨機生成的鄰域范圍，按環形鄰域拓撲結構確定每個個體的鄰居；

(4)whileg

(5) ifrand≤sqrt(g/Gmax)

(6) 選擇局部鄰域策略，采用環形鄰域拓撲結構進行學習

(7) fori=1 toNPdo

(8) ifrand

(9) 個體i進行鄰域重心反向學習

(10) end if

(11) forj=1 toDdo

(12) ifrand

(13) ifi為全局最優個體

(14) 根據式(15)選擇相應的變異策略來學習

(15) else

(16) 根據式(14)選擇相應的變異策略來學習

(17) end if

(18) end if

(19) end for

(20) if 新個體的目標函數值小于原先個體

(21) 更新種群

(22) 更新個體i的目標函數值到Fit數組

(23) end if

(24) end for

(25) else

(26) fori=1 toNPdo

(27) 采用全局鄰域策略及星形鄰域拓撲結構進行學習

(28) ifrand

(29) 個體i進行鄰域重心反向學習

(30) end if

(31) forj=1 toDdo

(32) ifrand

(33) ifi為全局最優個體

(34) 根據式(15)選擇相應的變異策略來學習

(35) else

(36) 根據式(14)選擇相應的變異策略來學習

(37) end if

(38) end if

(39) end for

(40) if 新個體的目標函數值小于原先個體

(41) 更新種群

(42) 更新個體i的目標函數值到Fit數組

(43) end if

(44) end for

(45) end if

(46) 將最優個體以及最優個體目標函數值保存到相應的數組中

(47)g=g+1

(48)end while

END

3 實驗分析

3.1 參數設置

MCOBDE算法的各項參數設置：在低維情況下種群規模NP=150，問題維度D=30，最大演化代數Gmax=2000，最大函數評價次數FES=300 000；在高維情況下NP=250，D=50，Gmax=2000，FES=500 000；交叉概率CR=0.9，縮放比例F=0.5，鄰域重心反向學習概率P=0.3。

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

3.2 測試函數

為了驗證本文算法的適用性、有效性和準確性，選擇CEC2015[20]中的15個標準測試函數，具體定義如表1所示，其中f1、f2為單峰函數，f3、f4、f5為簡單多峰函數，f6、f7、f8為混合函數，f9～f15為復合函數。

表1 標準測試函數

3.3 實驗結果與分析

3.3.1 收斂精度

表2為各算法的實驗結果在低維情況下的平均值、最小值和方差對比，其中最好結果已加粗標出。從平均值指標來看，對于f1、f6、f8、f10、f11、f12測試函數，MCOBDE算法要優于參與比較的其他算法，對于f9、f15測試函數，MCOBDE算法與其他算法性能持平。同時，MCOBDE算法在測試函數f2、f6、f7、f8、f10、f11、f12的最小值指標上比較有優勢，在測試函數f1、f5、f11的方差指標上優勢明顯。

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

綜上所述，針對低維問題，MCOBDE算法總體上優于其他算法，這說明合適的鄰域結構以及鄰域重心反向學習確實能提高算法的尋優能力，同時也能使算法具有較強的穩定性。

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

(a) 測試函數f1

(b)測試函數f8

(c) 測試函數f10

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

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

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

續表

測試函數指標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 收斂速度

采用固定精度的方法測試算法的收斂速度，最大函數評價次數FES均為300 000，預設收斂精度VTR如表4所示。

表4 預設收斂精度VTR

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

3.4 算法復雜度分析

根據算法實現分析其復雜度。算法步驟(1)初始化種群以及適應度計算復雜度為O(NP·D)，步驟(9)鄰域重心反向學習復雜度為O(D)，步驟(11)～(23)針對每一維的變異、交叉、選擇的復雜度為O(D)，則步驟(7)～(24)每一次迭代的復雜度為O(NP·D)，同理步驟(26)～(44)每一次迭代的復雜度也為O(NP·D)，因此步驟(4)～(48)的復雜度為O(NP·D·Gmax)。綜上所述，略去低階項，MCOBDE算法的復雜度為O(NP·D·Gmax)，與標準DE算法的復雜度一致，故MCOBDE算法在獲得較優計算效果的前提下并沒有增加過多的計算時間開銷。

表5 給定目標精度下的平均評價次數

4 結語

本文提出了一種多鄰域策略重心反向學習的差分進化算法MCOBDE。該算法根據當前進化狀態選擇合適的鄰域策略，同時不同的鄰域策略使用恰當的鄰域拓撲結構，從而提高了算法的收斂精度和收斂速度，并且鄰域重心反向學習的加入使得種群能更好地探索鄰域空間，增加找到最優解的概率。MCOBDE算法的時間復雜度同標準DE算法一致。通過對15個測試函數的實驗以及與其他幾個有代表性的DE算法的比較，證明了本文算法的適用性、有效性和準確性。

參考文獻

[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] 李牧東,趙輝,翁興偉,等.基于最優高斯隨機游走和個體篩選策略的差分進化算法[J].控制與決策, 2016,31(8):1379-1386.

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

[4] 劉會超,吳志健.基于旋轉學習機制的差分進化算法[J].電子學報, 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] 周新宇,吳志健,王暉.一種精英反向學習的差分進化算法[J].小型微型計算機系統,2013,34(9):2129-2134.

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

[8] 魏文紅,周建龍,陶銘,等.一種基于反向學習的約束差分進化算法[J]. 電子學報,2016,44(2):426-436.

[9] 王亞輝,吳金妹,賈晨輝.基于動態種群多策略差分進化模型的多目標進化算法[J].電子學報,2016,44(6):1472-1480.

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

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

[12] 張斌,李延暉,郭昊.基于反向學習的跨種群差分進化算法[J].計算機應用,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] 周凌云,丁立新,彭虎,等.一種鄰域重心反向學習的粒子群優化算法[J].電子學報,2017,45(11):2815-2824.

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

[17] 張鈴,張鈸.佳點集遺傳算法[J].計算機學報,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.