均勻鄰域?qū)ξ坏淖赃m應差分進化算法

趙新超，熊 卿，馮 帥

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

0 引言

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

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

1 DE算法

DE是一種基于種群差分信息的進化搜索方法。在迭代過程中，變異運算是新解生成過程中最主要的運算，有很多變種的差分變異策略，本文以經(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]之間的均勻分布隨機數(shù)。

第2步，變異操作。對于當前代的每個個體xi，在種群中隨機選擇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]是預先產(chǎn)生的一個隨機整數(shù)，該參數(shù)交叉操作能夠保證測試個體向量ui至少有一維分量來自變異個體向量vi，可以避免與父代個體向量xi相同，以達到提高種群多樣性的目的。

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

(4)

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

2 ODE算法

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

(5)

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

(6)

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

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

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

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

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

(7)

3 NODE算法

3.1 研究動機

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

3.2 NODE算法

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

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

(8)

(9)

(10)

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

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

3.3 算法流程

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

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

生成均勻分布的隨機種群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++)，

在當前種群{P∪OP*}中選擇Np個適應度最高的個體。

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

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

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

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

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

4.2 數(shù)值實驗對比

DE、ODE和NODE算法的數(shù)值結(jié)果統(tǒng)計見表2，該統(tǒng)計結(jié)果包括30次獨立運行最終結(jié)果的最優(yōu)值Min、平均值Mean和標準差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é)合這兩個指標分析，NODE、ODE和DE分別取得17個、5個和4個最優(yōu)結(jié)果。

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

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

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

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

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

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

綜合表2結(jié)果和相應分析可以看出，在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 在線進化趨勢對比

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

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

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

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

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

為進一步考查3種算法在多次運行最終結(jié)果中的離散程度，圖3給出3個算法6個函數(shù)在30次獨立運行中在線性能對比分析和箱型圖。縱坐標的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ù)差值較大，可以看出，當求解多峰函數(shù)時NODE的性能比其他算法優(yōu)勢較明顯；5)對于混合函數(shù)和組合函數(shù)，NODE在F7、F8、F9的中位數(shù)略小于其他算法，可以看出，NODE當求解混合函數(shù)和組合函數(shù)時的性能比其他算法優(yōu)勢相對較小。

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

5 結(jié)論

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