均勻鄰域?qū)ξ坏淖赃m應(yīng)差分進(jìn)化算法

趙新超，熊 卿，馮 帥

(北京郵電大學(xué)理學(xué)院，北京 100876)

0 引言

差分進(jìn)化(differential evolution,DE)由文獻(xiàn)[1]提出，它是一種有效、簡單、魯棒的全局優(yōu)化算法。該算法以初始種群向量開始搜索，關(guān)鍵思想在于構(gòu)造差分變異信息，該信息來自于當(dāng)前群體中不同個體的差異性，即不同個體的差分向量信息。近些年來，DE的發(fā)展得到學(xué)者的廣泛關(guān)注[2-11]。為了提升差分算法的性能，Rahnamayan等[12]引入了對位學(xué)習(xí)(opposition-based learning， OBL)概念。OBL背后的主要思想是同時考慮當(dāng)前位置及其相應(yīng)的對位估計，以便實現(xiàn)對當(dāng)前候選解和對位解的同時搜索。OBL策略已經(jīng)被用于很多群智能優(yōu)化算法研究中[12-16]。OBL被用于提升差分算法性能，這種方法被稱為基于對位學(xué)習(xí)的差分進(jìn)化(opposition-based differential evolution，ODE)[12]。ODE在種群初始化期間同時使用對位點，并且還用于進(jìn)化過程中產(chǎn)生的新的種群。ODE自提出之后，因其收斂速度加快的特性被學(xué)者深入研究：文獻(xiàn)[17]將種群劃分為精英種群和普通種群，分別采用標(biāo)準(zhǔn)的和基于反向?qū)W習(xí)的差分進(jìn)化策略，提出一種基于對位學(xué)習(xí)的跨種群差分進(jìn)化算法；文獻(xiàn)[18]通過反向精英學(xué)習(xí)機(jī)制和高斯隨機(jī)分布提高算法的性能，提出一種基于反向?qū)W習(xí)的自適應(yīng)差分進(jìn)化算法。

先前對差分算法的研究使得算法性能得到了不同程度的提升，隨著OBL策略引入差分算法，收斂速度慢的問題得到有效改善。然而，ODE易陷入局部最優(yōu)以及早熟收斂等，這些不足問題還沒有得到有效解決。針對此問題，本文提出了基于均勻鄰域?qū)ξ坏淖赃m應(yīng)差分進(jìn)化(neighborhood opposition-based differential evolution,NODE)算法，通過擴(kuò)大當(dāng)前解對位點鄰域的搜索區(qū)域的思路提高群體多樣性，針對對位鄰域變異的操作，增加找到最優(yōu)解的可能性，同時減緩了精英學(xué)習(xí)的強(qiáng)度，從而在一定程度上避免過早陷入局部陷阱的問題。

1 DE算法

DE是一種基于種群差分信息的進(jìn)化搜索方法。在迭代過程中，變異運算是新解生成過程中最主要的運算，有很多變種的差分變異策略，本文以經(jīng)典DE/rand/1/bin變異為例介紹,具體步驟為：

第1步，種群初始化。用方程(1)產(chǎn)生初始種群中每個個體向量xi：

xij=aj+rand(0,1)×(bj-aj),

(1)

其中：xi=(xi1,xi2,…,xiD),i=1,2,…,Np，D表示問題的維數(shù)，Np表示種群規(guī)模；bj與aj分別表示個體向量第j維的上界與下界；rand(0,1)表示[0,1]之間的均勻分布隨機(jī)數(shù)。

第2步，變異操作。對于當(dāng)前代的每個個體xi，在種群中隨機(jī)選擇3個互不相同的個體向量xa，xb，xc，a,b,c∈[1 …Np]，s.t.a≠b≠c≠i；依照式(2)生成變異個體vi，

vij=xaj+F(xbj-xcj),

(2)

其中：i=1,2,…,Np;j=1,2,…,D;放縮因子F∈[0,2]用于控制差分向量(xb-xc)的放縮程度。

第3步，雜交操作。該操作中差分算法以一定的概率Cr∈[0,1]依照式(3)生成測試個體向量ui，

(3)

其中：i=1,2,…,Np;j=1,2,…,D;jrand∈[1,2,…,D]是預(yù)先產(chǎn)生的一個隨機(jī)整數(shù)，該參數(shù)交叉操作能夠保證測試個體向量ui至少有一維分量來自變異個體向量vi，可以避免與父代個體向量xi相同，以達(dá)到提高種群多樣性的目的。

第4步，選擇操作。這一階段處理種群中每一個目標(biāo)個體向量xi，將目標(biāo)個體向量與新產(chǎn)生的測試個體向量ui按式(4)進(jìn)行評估并貪婪選擇，將較優(yōu)個體保留到下一代種群，

(4)

其中：i=1,2,…,Np;f(x)表示解向量x的適應(yīng)度值，假設(shè)f(x)是最小化問題。

2 ODE算法

在專注于OBL之前，先給出對位數(shù)概念[12]。

(5)

類似地，該定義可以被延展到高維空間。

(6)

與所有其他群體優(yōu)化算法類似，DE算法的兩個主要操作是可分的，即種群初始化和通過諸如變異、交叉、選擇的進(jìn)化操作產(chǎn)生新一代。構(gòu)建基于OBL的差分算法框架[12]，基于對位差分進(jìn)化算法選擇DE/rand/1/bin作為父算法，并將基于對位點搜索的思想嵌入到DE中加速其收斂速度，提高算法性能。

第1步，基于對位的種群初始化。按式(1)得到初始種群P，包含Np個隨機(jī)產(chǎn)生的個體，按式(6)產(chǎn)生包含Np個對位個體的對位種群OP，最后從初始種群{P∪OP}中選擇Np個適應(yīng)度最高的個體。

第2步，對種群中每一個個體執(zhí)行差分進(jìn)化操作。按照式(2)對種群中每一個個體實施差分變異操作獲得變異個體向量vi，再按照式(3)對種群中每一個個體xi和變異個體向量vi進(jìn)行交叉操作獲得測試個體向量ui。

第3步，按式(4)對個體目標(biāo)向量xi和測試個體向量ui執(zhí)行選擇操作。

第4步，基于對位的種群跳轉(zhuǎn)。產(chǎn)生一個[0,1]間的隨機(jī)數(shù)r，判斷是否小于跳轉(zhuǎn)概率Jr∈[0,1]。若r

(7)

3 NODE算法

3.1 研究動機(jī)

經(jīng)典ODE算法基于對位學(xué)習(xí)概念，利用當(dāng)前解與其對位解一起競爭共同選擇較優(yōu)解，從而獲得一個具有更好適用度的解，以達(dá)到加速收斂、提高算法性能的目的。然而經(jīng)典ODE算法只是根據(jù)解群體搜索區(qū)域的幾何中心獲取一個確定的對位點。本文研究動機(jī)是：對于很多問題而言，這種OBL策略在一定程度上可以加速搜索最優(yōu)解的過程，OBL策略之所以能有效的一個基本假設(shè)是問題對最優(yōu)解的局部鄰域不完全具有對稱性，因此當(dāng)前點和對位點一般具有適應(yīng)度的差距。同時ODE選取一個對位點的做法使得找到最優(yōu)解的可能性較低，假如幾何中心偏離，對位點就會偏離，找到最優(yōu)解的可能性就會降低。

3.2 NODE算法

針對這個問題，本文提出了NODE算法，在傳統(tǒng)對位點的基礎(chǔ)上做了一次步幅由當(dāng)前群體信息和當(dāng)前對位點決定的對位隨機(jī)擾動，在保持經(jīng)典OBL擴(kuò)大搜索區(qū)域這一優(yōu)勢的前提下，擴(kuò)大了OBL鄰域有效范圍，并充分利用了當(dāng)前群體和當(dāng)前個體的雙重信息，有效提高了算法的搜索有效性。

本文提出的在經(jīng)典對位點鄰域做多階段自適應(yīng)均勻擾動的策略如下：

(8)

(9)

(10)

3)多階段OBL 基于OBL的均勻鄰域變異操作的優(yōu)點是擴(kuò)大搜索區(qū)域，增加找到最優(yōu)解的可能性，不足之處在于，隨著搜索區(qū)域的增大，收斂速度會相應(yīng)減緩。為了更好地平衡收斂精度和收斂速度之間的關(guān)系，盡可能在保持多樣性的同時提高收斂速度，在自適應(yīng)調(diào)節(jié)搜索區(qū)域的同時，引入了多階段擾動策略，通過控制半徑擾動參數(shù)Ra來減小搜索區(qū)域。

算法初期，當(dāng)Ra較大時，算法群體會沿對位點較大的鄰域搜索，增加找到更有潛力區(qū)域的可能性；算法中期，當(dāng)Ra較小時，擾動策略會保證算法群體在對位點較小的鄰域搜索，使當(dāng)前解在當(dāng)前有潛力區(qū)域搜索，同時依然保持跳出區(qū)域的可能；算法臨近結(jié)束階段，半徑參數(shù)Ra很小，保證算法群體幾乎僅向當(dāng)前對位點學(xué)習(xí)，從而保證算法有更好的收斂性。

3.3 算法流程

本文沿用經(jīng)典的ODE算法框架，基于均勻鄰域的自適應(yīng)對位變異學(xué)習(xí)機(jī)制嵌入到種群初始化階段和種群跳躍階段，其偽代碼如下。

算法1 對位種群初始化階段

生成均勻分布的隨機(jī)種群P0，

for(i=1;i≤NP;i++)，

for(j=1;j≤D;j++)，

OP0i,j=aj+bj-P0i,j，

算法2 對位種群跳躍階段

if(rand(0,1)

{if(t≤T/3)，

Ra=Ra1，

else if (T/3

Ra=Ra2，

else，

Ra=Ra3，

}

for(i=1;i≤NP;i++)，

for(j=1;j≤D;j++)，

在當(dāng)前種群{P∪OP*}中選擇Np個適應(yīng)度最高的個體。

4 仿真實驗結(jié)果與分析

為了驗證提出的NODE算法的性能，將NODE與經(jīng)典DE(DE/rand/1/bin)、文獻(xiàn)[12]提出的ODE進(jìn)行了對比分析，測試函數(shù)采取CEC 2014測試函數(shù)集[19]。

4.1 測試函數(shù)與參數(shù)設(shè)置

在CEC 2014測試函數(shù)集的各類函數(shù)中選出代表性算例構(gòu)成本文的基準(zhǔn)測試函數(shù)集，所有測試函數(shù)均為高維可伸縮的函數(shù)。選取CEC 2014函數(shù)簡介如下：f2、f3為單峰函數(shù)，f6、f9、f10、f11為多峰函數(shù)，f18、f20為混合函數(shù)，f27、f29為組合函數(shù)，為方便起見，這些函數(shù)在本文中重新標(biāo)記為F1～F10。這些測試函數(shù)的編號、名稱、分類、搜索區(qū)域以及理論最優(yōu)值如表1所示，搜索區(qū)域為[-100，100]D，有關(guān)測試函數(shù)詳細(xì)信息見文獻(xiàn)[20]。算法對比實驗的具體參數(shù)設(shè)置如下：種群規(guī)模Np=50，搜索空間維數(shù)D=50，跳轉(zhuǎn)概率Jr=0.3，控制參數(shù)Ra1=10-2,Ra2=10-3,Ra3=10-6。

表1 基準(zhǔn)測試函數(shù)

4.2 數(shù)值實驗對比

DE、ODE和NODE算法的數(shù)值結(jié)果統(tǒng)計見表2，該統(tǒng)計結(jié)果包括30次獨立運行最終結(jié)果的最優(yōu)值Min、平均值Mean和標(biāo)準(zhǔn)差STD，最優(yōu)的結(jié)果用粗黑體表示。從表2結(jié)果可以看出：

1)在10個測試函數(shù)中,NODE、ODE和DE在30次最終結(jié)果統(tǒng)計的最優(yōu)值上分別取得7個、5個和4個最優(yōu)結(jié)果。

2)NODE、ODE和DE在10個測試函數(shù)最終結(jié)果的平均值上分別取得10個、0個和0個最優(yōu)結(jié)果。

3)結(jié)合這兩個指標(biāo)分析，NODE、ODE和DE分別取得17個、5個和4個最優(yōu)結(jié)果。

4)結(jié)合這兩個指標(biāo)，NODE、ODE和DE最優(yōu)結(jié)果數(shù)量加和的近似比分別為17/20、5/20和4/20。

5)NODE、ODE和DE在這兩項指標(biāo)的結(jié)果排名加和分別為24、41和47。

6)NODE、ODE和DE在這兩項指標(biāo)結(jié)果排名加和的近似比分別為24/20、41/20和47/20。

7)對于單峰函數(shù)和混合函數(shù)，NODE的結(jié)果略優(yōu)于其他算法。

8)對于多峰函數(shù)，NODE在F5與F6的統(tǒng)計結(jié)果遠(yuǎn)優(yōu)于其他算法，在F3與F4中略優(yōu)于其他算法。

9)對于組合函數(shù)，NODE在F9與F10的統(tǒng)計結(jié)果明顯優(yōu)于其他算法。

綜合表2結(jié)果和相應(yīng)分析可以看出，在CEC 2014的10個測試函數(shù)上，NODE得到的平均結(jié)果有明顯的優(yōu)勢，最優(yōu)值統(tǒng)計結(jié)果也比ODE、DE表現(xiàn)得更好，特別是多峰函數(shù)和組合函數(shù)，優(yōu)勢更加明顯。

為討論3個算法在平均結(jié)果統(tǒng)計的顯著性，對算法DE、ODE和NODE的平均值做Friedman統(tǒng)計檢驗[20]，其平均秩分別為5.888 9，5.222 2，3.888 9?？梢?，NODE與DE、ODE有顯著性差異。綜上所述，本文提出的NODE策略和算法能顯著提高算法的性能，比ODE、DE能夠取得更滿意的結(jié)果。

4.3 在線進(jìn)化趨勢對比

為考查算法的平均進(jìn)化趨勢和綜合在線性能，圖2給出3個算法在30次獨立運行中在線性能演示對比分析。第一類單峰函數(shù)相對簡單，所以從后三類測試函數(shù)中選擇6個函數(shù)代表，分別為多峰函數(shù)F3、F5、F6，混合函數(shù)F7、F8和組合函數(shù)F9。

從圖2結(jié)果可以看出：1)NODE比ODE和DE有較為明顯的進(jìn)化優(yōu)勢；2)在算法的前期，NODE和ODE進(jìn)化趨勢表現(xiàn)大致相當(dāng)，且都優(yōu)于DE；3)隨著算法的進(jìn)行，在函數(shù)F3、F7、F8、F9上NODE比ODE表現(xiàn)略好，在函數(shù)F5、F6上NODE明顯優(yōu)于ODE；4)對于多峰函數(shù)，NODE在F5、F6上的進(jìn)化趨勢遠(yuǎn)優(yōu)于其他算法，在F3略優(yōu)于其他算法，可以分析出，當(dāng)求解多峰函數(shù)時NODE的性能比其他算法優(yōu)勢較明顯；5)對F7、F8、F93個函數(shù)，NODE的結(jié)果略優(yōu)于其他算法，但當(dāng)把后期進(jìn)化圖局部放大依然可以看出NODE相較于其他算法的進(jìn)化優(yōu)勢。

表2 3種算法數(shù)值實驗結(jié)果統(tǒng)計

綜合表2和圖2可以看出，本文提出的NODE算法具有更加明顯的全局搜索優(yōu)勢和對最優(yōu)解相對準(zhǔn)確的定位能力，特別對多峰函數(shù)表現(xiàn)更加突出，從而證明本文所提幾種策略的有效性。

4.4 最終結(jié)果離散度對比

為進(jìn)一步考查3種算法在多次運行最終結(jié)果中的離散程度，圖3給出3個算法6個函數(shù)在30次獨立運行中在線性能對比分析和箱型圖。縱坐標(biāo)的5條線從上到下分別為最大值、上四分位數(shù)、中位數(shù)、下四分位數(shù)、最小值，同樣選擇函數(shù)F3、F5、F6、F7、F8、F9為代表。

從圖3可以看出：1)中位數(shù)方面，NODE、ODE和DE分別取得6個、0個和0個最優(yōu)結(jié)果；2)上下四分位數(shù)方面，NODE、ODE和DE分別取得4個、1個和1個最小；3)數(shù)據(jù)異常值方面，NODE、ODE和DE在函數(shù)F3、F9上分別有1個、0個和1個，NODE、ODE和DE在函數(shù)F8上各有1個；4)對于多峰函數(shù)，NODE在F3、F5、F6的中位數(shù)與其他算法的中位數(shù)差值較大，可以看出，當(dāng)求解多峰函數(shù)時NODE的性能比其他算法優(yōu)勢較明顯；5)對于混合函數(shù)和組合函數(shù)，NODE在F7、F8、F9的中位數(shù)略小于其他算法，可以看出，NODE當(dāng)求解混合函數(shù)和組合函數(shù)時的性能比其他算法優(yōu)勢相對較小。

綜合可以看出，本文提出的NODE算法中位數(shù)表現(xiàn)最優(yōu)，且多次運行結(jié)果較集中，因此算法具有較好的性能表現(xiàn)，且具有較好的穩(wěn)定性和魯棒性，特別針對多峰函數(shù)優(yōu)化具有較為明顯的優(yōu)勢。

5 結(jié)論

本文在經(jīng)典對位學(xué)習(xí)的差分進(jìn)化算法ODE的基礎(chǔ)上，引入了基于對位鄰域的均勻變異算子和多階段擾動策略，充分利用了當(dāng)前群體和個體的雙重信息，提出了一種基于對位鄰域?qū)W習(xí)的自適應(yīng)差分進(jìn)化算法NODE。在經(jīng)典對位點的鄰域做均勻變異運算，有效擴(kuò)大了搜索區(qū)域，增加找到最優(yōu)解的可能性；在變異階段，利用當(dāng)前群體解中每一維度的最大值和最小值來自適應(yīng)調(diào)控搜索區(qū)域的大小，提高了算法的收斂精度；算法引入多階段擾動策略，根據(jù)算法的不同進(jìn)化進(jìn)程，調(diào)控算法的收斂速度。最后，選用CEC 2014每一類測試函數(shù)中10個代表性基準(zhǔn)測試函數(shù)，對本文所提算法NODE與差分進(jìn)化算法DE、經(jīng)典對位差分進(jìn)化算法ODE進(jìn)行對比仿真實驗，結(jié)果表明，本文提出的NODE算法總體性能更好，更容易找到最優(yōu)解，收斂精度更高，并且具有更好的魯棒性。