張 斌，李延暉，郭 昊

華中師范大學(xué) 信息管理學(xué)院，武漢 430079)(*通信作者電子郵箱hbguohao@163.com)

基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法

張 斌，李延暉，郭 昊*

華中師范大學(xué) 信息管理學(xué)院，武漢 430079)(*通信作者電子郵箱hbguohao@163.com)

針對(duì)差分進(jìn)化(DE)算法存在的尋優(yōu)精度低、收斂速度慢等問(wèn)題，借鑒混沌分散策略、反向?qū)W習(xí)策略(OBL)以及跨種群并行機(jī)制，提出一種基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法(OLCPDE)。采用混沌分散策略進(jìn)行種群初始化，將種群劃分為精英種群和普通種群，對(duì)兩個(gè)子種群分別采用標(biāo)準(zhǔn)的差分進(jìn)化策略和基于反向?qū)W習(xí)的差分進(jìn)化策略；同時(shí)，為進(jìn)一步提高算法對(duì)單峰函數(shù)的求解精度和穩(wěn)定性，采用了一種跨種群的差分進(jìn)化策略，運(yùn)用三種策略對(duì)子種群進(jìn)行操作，達(dá)到共同進(jìn)化的目的。實(shí)驗(yàn)獨(dú)立運(yùn)行30次，OLCPDE在12個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)中，有11個(gè)函數(shù)都能穩(wěn)定地收斂到全局最優(yōu)解，優(yōu)于對(duì)比算法。實(shí)驗(yàn)結(jié)果表明，OLCPDE收斂精度高，能有效避免陷入局部最優(yōu)點(diǎn)。

差分進(jìn)化；反向?qū)W習(xí)；跨種群；混沌搜索；函數(shù)優(yōu)化

0 引言

差分進(jìn)化(Differential Evolution, DE)算法[1]是基于群體差異的啟發(fā)式優(yōu)化算法，其原理簡(jiǎn)單、受控參數(shù)少、魯棒性強(qiáng)，易于理解和實(shí)現(xiàn)[2]。DE算法作為一種簡(jiǎn)單實(shí)用的全局搜索算法，已被證明是求解非線性、不可微和超高維等復(fù)雜函數(shù)的有效手段[3]，在科學(xué)研究與實(shí)際工程領(lǐng)域都得到了廣泛的應(yīng)用[4]。

類似于其他的進(jìn)化算法，DE算法也存在著早熟和收斂速度過(guò)慢的現(xiàn)象，為了解決這些問(wèn)題，國(guó)內(nèi)外很多學(xué)者對(duì)DE算法進(jìn)行了大量的改進(jìn)，算法的改進(jìn)主要聚焦在三個(gè)方面，一是對(duì)參數(shù)的選取機(jī)制的研究，如Brest等[5]引入自適應(yīng)縮放因子(Factor, F)和交叉概率(Crossover Rate, CR)，提出一種參數(shù)自適應(yīng)的差分進(jìn)化算法;汪慎文等[6]通過(guò)改變變異算子的學(xué)習(xí)方式，提出樸素差分進(jìn)化算法。二是對(duì)差分變異策略的研究，如呂銘晟等[7]將標(biāo)準(zhǔn)差分進(jìn)化算法的兩種變異策略串行組合，提出多變異策略差分進(jìn)化算法。三是DE與其他具有某種優(yōu)良特性的策略的集成，如王叢佼等[8]采用DE標(biāo)準(zhǔn)框架，當(dāng)群體適應(yīng)值方差小于一定閾值時(shí)，引入極值優(yōu)化算法，提出基于極值優(yōu)化的混合差分進(jìn)化算法；匡芳君等[9]設(shè)置初始種群為隨機(jī)雙種群，分別采用混沌差分進(jìn)化算法和混沌粒子群優(yōu)化算法協(xié)同尋優(yōu)，提出混沌差分進(jìn)化粒子群協(xié)同優(yōu)化算法；張大斌等[10]在魚群算法快速收斂的基礎(chǔ)上引入差分進(jìn)化算法，提出基于差分進(jìn)化的魚群算法。學(xué)者們的改進(jìn)不同程度地提升了DE的收斂性能，然而DE及其改進(jìn)算法依然存在收斂精度不高、對(duì)不同特征的基準(zhǔn)測(cè)試函數(shù)魯棒性不好等問(wèn)題，例如文獻(xiàn)[5-8]的算法在病態(tài)的Rosenbrock函數(shù)上均表現(xiàn)不佳。

本文將混沌分散策略和反向?qū)W習(xí)機(jī)制引入差分進(jìn)化算法中，設(shè)計(jì)了一種基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法 (Cross-Population Differential Evolution algorithm based on Opposition-based Learning, OLCPDE)。該算法通過(guò)混沌分散策略產(chǎn)生初始種群，按適應(yīng)度值大小將種群劃分為精英種群和普通種群，對(duì)精英種群采用標(biāo)準(zhǔn)的DE/best/1/bin差分進(jìn)化策略，對(duì)普通種群采用反向?qū)W習(xí)改進(jìn)的DE/rand/2/bin差分進(jìn)化策略；為了增加算法的魯棒性，提高算法對(duì)單峰函數(shù)的求解精度和穩(wěn)定性，同時(shí)采用了跨種群的DE/best/1/bin差分進(jìn)化策略，借助種群間的并行機(jī)制和多種策略，以達(dá)到提高收斂速度，增強(qiáng)全局搜索能力的目的。通過(guò)選取測(cè)試函數(shù)進(jìn)行尋優(yōu)仿真驗(yàn)證了算法具有較高的收斂速度和全局搜索能力。

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

DE算法是一種基于實(shí)數(shù)編碼的群體優(yōu)化算法，與其他進(jìn)化算法類似，首先需要將種群初始化，然后對(duì)種群個(gè)體進(jìn)行交叉、變異和選擇操作，通過(guò)多次迭代，最終使種群個(gè)體趨于全局最優(yōu)解。差分進(jìn)化算法的主要操作如下：

1)種群初始化。令Xi(t)=(xi1,xi2,…,xiD)為第t代種群的第i個(gè)個(gè)體，根據(jù)式(1)在可行域內(nèi)隨機(jī)產(chǎn)生種群規(guī)模為NP，個(gè)體分量為D的初始種群X(0)。

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

(1)

2)變異操作。變異操作為差分進(jìn)化算法的核心，從種群中隨機(jī)選擇一個(gè)個(gè)體Xr1，作為待變異個(gè)體，再隨機(jī)選擇兩個(gè)個(gè)體Xr2，Xr3(NP≥4)作為擾動(dòng)個(gè)體，根據(jù)式(2)，將這兩個(gè)個(gè)體的向量差縮放后與待變異個(gè)體進(jìn)行向量合成，得到變異后的個(gè)體Ui。

uij(t+1)=xr1j(t)+F·(xr2j(t)-xr3j(t));

r1≠r2≠r3

(2)

其中：F為縮放比例因子，通常取值為[0.5,1]。

3)交叉操作。依式(3)，將變異后的個(gè)體和當(dāng)前的演化個(gè)體以離散交叉的方式進(jìn)行交叉操作生成中間個(gè)體Ci(t+1)，以提高種群多樣性。

cij(t+1)=

(3)

其中：rand(D)是區(qū)間[1,D]的隨機(jī)整數(shù)，CR∈[0,1]是交叉概率。

4)選擇操作。根據(jù)式(4)，對(duì)中間個(gè)體和當(dāng)前個(gè)體之間進(jìn)行貪婪選擇，通過(guò)計(jì)算個(gè)體目標(biāo)函數(shù)值，將其進(jìn)行比較，選擇適應(yīng)度大的作為下代種群個(gè)體。

(4)

此外，DE算法還有多種差分策略，以上的基本差分算法實(shí)質(zhì)上采用的是DE/rand/1/bin策略，除此之外，還有很多常用和經(jīng)典的差分策略，如本文后續(xù)部分使用到的差分策略是DE/best/1/bin和DE/rand/2/bin，如式(5)和式(6)。

uij(t+1)=xbestj(t)+F·(xr2j(t)-xr3j(t));r2≠r3

(5)

uij(t+1)=xr1j(t)+F·(xr2j(t)+xr3j(t)-xr4j(t)-xr5j(t));r1≠r2≠r3≠r4≠r5

(6)

2 基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法

DE算法在進(jìn)化過(guò)程中，個(gè)體間差異性逐漸變小，種群多樣性降低，算法探索能力下降，容易陷入局部最優(yōu)，出現(xiàn)早熟等問(wèn)題，為此學(xué)者們從不同的角度對(duì)算法進(jìn)行了改進(jìn)。標(biāo)準(zhǔn)DE算法在尋優(yōu)過(guò)程中的控制參數(shù)保持不變，無(wú)法較好地滿足進(jìn)化各階段算法對(duì)參數(shù)的特殊要求，基于此學(xué)者們提出了參數(shù)自適應(yīng)的DE算法；由于初始種群隨機(jī)產(chǎn)生，初始解的質(zhì)量無(wú)法保證，因此一些學(xué)者對(duì)初始化進(jìn)行了改進(jìn)；差分策略是DE算法的標(biāo)志性特征，影響著算法收斂速度和尋優(yōu)精度，因此學(xué)者們提出了多種不同的差分進(jìn)化策略；DE算法的貪婪選擇策略在提高算法收斂速度的同時(shí)降低了種群的多樣性，為避免早熟，學(xué)者們改進(jìn)了選擇策略；考慮到單個(gè)種群在進(jìn)化過(guò)程中容易喪失多樣性，學(xué)者們提出了多個(gè)子種群進(jìn)化模式，通過(guò)種群間的信息共享和交換，保證算法繼續(xù)進(jìn)化。在學(xué)習(xí)總結(jié)學(xué)者們的改進(jìn)策略的基礎(chǔ)之上，本文同時(shí)對(duì)種群初始化、選擇策略和單種群進(jìn)化模式等三個(gè)方面進(jìn)行了改進(jìn)，提出了基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法。

2.1 基于混沌分散策略的種群初始化

標(biāo)準(zhǔn)DE算法的初始種群是隨機(jī)產(chǎn)生的，用這種方式產(chǎn)生的初始種群，可能會(huì)使一些種群個(gè)體集中在某一區(qū)域或者遠(yuǎn)離最優(yōu)解，無(wú)法保證初始解的質(zhì)量，因此，限制了算法的求解效率。而混沌是非線性動(dòng)力學(xué)系統(tǒng)中特有的一種現(xiàn)象，具有內(nèi)在的隨機(jī)性和遍歷性等特點(diǎn)，它能彌補(bǔ)隨機(jī)產(chǎn)生種群的缺點(diǎn)，提高初始種群的質(zhì)量，為后續(xù)的差分操作找到最優(yōu)解提供了保證。常用的混沌模型是一維Logistic映射[11]，其迭代公式為:

yk+1=μyk(1-yk);k=0,1,…

(7)

其中：k為迭代次數(shù)，μ為控制系統(tǒng)混沌行為的參數(shù)。當(dāng)μ值確定后，由任意初值y0∈[0,1],可以迭代出一個(gè)確定的時(shí)間序列y1,y2, …,yk。當(dāng)μ=4時(shí)，系統(tǒng)沒(méi)有穩(wěn)定解，是[0,1]區(qū)間的滿映射，呈現(xiàn)出完全混沌狀態(tài)。

2.2 反向?qū)W習(xí)精英選擇策略

反向?qū)W習(xí)策略(Opposition-BasedLearning,OBL)是近年來(lái)計(jì)算智能領(lǐng)域中出現(xiàn)的一種新技術(shù)，已應(yīng)用到多種優(yōu)化算法中[12-15]。它的主要思想是：對(duì)一個(gè)可行解，同時(shí)計(jì)算并評(píng)估其反向解，從中選擇較優(yōu)的解作為下一代種群。反向?qū)W習(xí)機(jī)制通過(guò)搜索更多有效區(qū)域來(lái)提高群體的多樣性，增強(qiáng)算法的全局搜索能力。本文將其應(yīng)用在對(duì)普通種群的選擇策略上，具體步驟如下：

其中:

i=1,2,…,NP-「NP/2?;j=1,2,…,D

將反向?qū)W習(xí)精英選擇策略用于對(duì)普通種群變異交叉后進(jìn)行選擇操作，能夠有效地提升普通種群進(jìn)化后的個(gè)體的質(zhì)量，縮小與精英種群個(gè)體之間的差距，促進(jìn)種群之間的交流。反向?qū)W習(xí)策略通過(guò)變換算法的搜索空間，對(duì)當(dāng)前及反向空間進(jìn)行搜索，使算法避免陷入局部最優(yōu)，有效提高算法尋優(yōu)概率[16]。3.3節(jié)的實(shí)驗(yàn)結(jié)果驗(yàn)證了該策略的有效性。

2.3 子種群的并行差分進(jìn)化策略

OLCPDE算法是一種并行的差分進(jìn)化算法，進(jìn)化示意圖如圖1所示。該算法根據(jù)適應(yīng)度，將種群劃分2個(gè)子種群：精英種群和普通種群。適應(yīng)度好的前「NP/2?個(gè)個(gè)體組成精英種群，適應(yīng)度差的后NP-「NP/2?個(gè)個(gè)體組成普通種群。對(duì)精英種群選用DE/best/1/bin策略進(jìn)行差分操作，該策略以當(dāng)前種群最好的個(gè)體為基準(zhǔn)個(gè)體，再加上一個(gè)隨機(jī)擾動(dòng)向量，在當(dāng)前最好的個(gè)體周圍進(jìn)行搜索，具有很好的局部搜索能力。對(duì)普通種群選用DE/rand/2/bin策略進(jìn)行差分操作，該策略在當(dāng)前種群中隨機(jī)選取個(gè)體為基準(zhǔn)個(gè)體，再加上兩個(gè)隨機(jī)擾動(dòng)向量進(jìn)行變異和交叉，選擇操作上采用了反向?qū)W習(xí)精英選擇策略，不僅擴(kuò)大了普通種群的搜索范圍，提高了全局搜索能力，而且增加了普通種群產(chǎn)生優(yōu)質(zhì)解的概率，有利于種群間的交流。

圖1 并行進(jìn)化示意圖

為了增加算法的魯棒性，提高算法的收斂精度和穩(wěn)定性，以期能獲得穩(wěn)定的最優(yōu)解，本文提出了一種跨種群的DE/best/1/bin策略進(jìn)行差分進(jìn)化。該策略生成種群規(guī)模為「NP/2?，以精英種群中當(dāng)前最好的個(gè)體為基準(zhǔn)個(gè)體，隨機(jī)選取普通種群中的兩個(gè)個(gè)體組成擾動(dòng)向量進(jìn)行差分進(jìn)化，在當(dāng)前最優(yōu)點(diǎn)的附近進(jìn)一步搜索，防止了算法的早熟，增加了搜索的精細(xì)性。3.3節(jié)的實(shí)驗(yàn)結(jié)果驗(yàn)證該策略的有效性。

2.4 算法的實(shí)現(xiàn)過(guò)程

步驟1 種群初始化。利用混沌分散種群初始化策略產(chǎn)生規(guī)模為NP的初始種群，計(jì)算個(gè)體適應(yīng)度，并將其按適應(yīng)度值大小進(jìn)行排序，選取前「NP/2?個(gè)個(gè)體組成初始精英種群，剩余NP-「NP/2?個(gè)個(gè)體組成初始普通種群。

步驟2 對(duì)精英種群采用DE/best/1/bin差分策略進(jìn)行差分進(jìn)化，得到個(gè)體數(shù)為「NP/2?的進(jìn)化后種群。

步驟3 對(duì)普通種群采用DE/rand/2/bin差分策略進(jìn)行變異和交叉，采用2.2節(jié)的反向?qū)W習(xí)精英選擇策略進(jìn)行選擇，得到個(gè)體數(shù)為NP-「NP/2?的進(jìn)化后種群。

步驟4 選取精英種群中的當(dāng)前最優(yōu)個(gè)體為待變異個(gè)體，從普通種群中隨機(jī)選擇兩個(gè)個(gè)體組成擾動(dòng)向量，采用跨種群的DE/best/1/bin策略進(jìn)行交叉、變異和選擇，得到個(gè)體數(shù)為「NP/2?的進(jìn)化后種群。

步驟5 將三種策略進(jìn)化后的NP+「NP/2?個(gè)個(gè)體按適應(yīng)度值大小排序，選取適應(yīng)度大的前「NP/2?個(gè)個(gè)體作為子代精英種群，選取適應(yīng)度小的后NP-「NP/2?個(gè)個(gè)體作為子代普通種群。

步驟6 判斷是否滿足算法終止的條件，若當(dāng)前迭代次數(shù)小于最大迭代次數(shù)并且沒(méi)有尋到最優(yōu)值則轉(zhuǎn)向步驟2，否則轉(zhuǎn)步驟7。

步驟7 結(jié)束尋優(yōu)，輸出結(jié)果。

3 函數(shù)仿真與分析

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

為了測(cè)試OLCPDE算法的性能，本文選取了12個(gè)具有不同特點(diǎn)的基準(zhǔn)Benchmark函數(shù)進(jìn)行測(cè)試，其中f1至f6為單峰函數(shù)，f7至f12為多峰函數(shù)，測(cè)試函數(shù)的特征描述如表1所示。

表1 測(cè)試函數(shù)

選取4種典型算法與OLCPDE算法進(jìn)行比較，分別是策略為DE/rand/1/bin和DE/rand/2/bin的標(biāo)準(zhǔn)差分進(jìn)化算法、被廣泛認(rèn)可的jDE[5]和RMDE[17]。本文選取種群規(guī)模NP=80，問(wèn)題維度n=10。差分進(jìn)化算法的參數(shù)設(shè)置主要涉及縮放因子F和交叉概率CR兩個(gè)參數(shù)，OLCPDE、DE/rand/1/bin、DE/rand/2/bin取F=0.5，CR=0.8；jDE的F和CR是自適應(yīng)的，參照文獻(xiàn)[5]的設(shè)置；RMDE參照文獻(xiàn)[16]的設(shè)置F=0.5，CR=0.9，調(diào)和參數(shù)Mr=0.99。設(shè)置f2最大迭代次數(shù)設(shè)為4 000，f10最大迭代次數(shù)為2 000，f11、f12最大迭代次數(shù)為1 000，其余的函數(shù)最大迭代次數(shù)設(shè)為300。

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 算法收斂的性能

采用上述5種算法對(duì)表1中12個(gè)測(cè)試函數(shù)進(jìn)行尋優(yōu)，每種算法的每個(gè)函數(shù)獨(dú)立運(yùn)行30次，尋優(yōu)結(jié)果見(jiàn)表2，收斂曲線如圖2所示(除圖2(g)、(h)、(j)外，其他子圖的縱軸均為對(duì)數(shù)坐標(biāo)軸)。

表2 OLCPDE與4種經(jīng)典算法的收斂性能對(duì)比

根據(jù)表2和圖2，對(duì)算法性能從收斂速度、求解精度以及穩(wěn)定性等多角度進(jìn)行對(duì)比分析。

對(duì)于f1、f4、f5、f6函數(shù)，OLCPDE算法在較少的迭代次數(shù)下，能夠穩(wěn)定地收斂到全局最優(yōu)解，而其他4種算法無(wú)論是收斂速度還是求解精度都要差于OLCPDE算法。對(duì)于非凸、病態(tài)單峰函數(shù)f2，OLCPDE算法、DE/rand/1/bin算法、jDE算法和RMDE算法均有可能求解到最優(yōu)解，但只有前兩種算法最穩(wěn)定。對(duì)于步長(zhǎng)函數(shù)f6，除RMDE算法，其余四種算法均能穩(wěn)定求解到全局最優(yōu)解，其中OLCPDE算法的收斂速度最快。綜合f1～f6函數(shù)的求解結(jié)果，在求解單峰函數(shù)方面，OLCPDE算法具有較快的收斂速度、較強(qiáng)的全局搜索能力和穩(wěn)定性。

對(duì)于f7、f8、f9函數(shù)，OLCPDE算法的收斂速度、求解精度和穩(wěn)定性都要好于其他算法，雖然在對(duì)f9函數(shù)求解時(shí)發(fā)生了1次早熟，但求解的精度仍好于其他4種算法；對(duì)于f10、f11、f12函數(shù)，OLCPDE算法、DE/rand/1/bin算法和jDE算法表現(xiàn)得十分出色，都能穩(wěn)定地求解到全局最優(yōu)解，且這三種算法的求解速度差別不大。綜合f7～f12函數(shù)的求解結(jié)果，求解多峰復(fù)雜函數(shù)時(shí)，OLCPDE算法同樣具有較好的收斂速度、求解精度以及魯棒性。

綜上所述，無(wú)論單峰函數(shù)或多峰函數(shù)，OLCPDE算法均可快速獲取最優(yōu)值，實(shí)驗(yàn)結(jié)果明顯優(yōu)于其他算法，說(shuō)明OLCPDE算法具有更好的尋優(yōu)性能。

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

由表3可以看出，在最大迭代次數(shù)相同的情況下，對(duì)于f1～f9函數(shù)OLCPDE算法的平均耗時(shí)最短，DE/rand/1/bin算法、DE/rand/2/bin算法、jDE算法次之，RMDE算法的耗時(shí)最長(zhǎng)。對(duì)于f10～f12函數(shù)，OLCPDE函數(shù)平均耗時(shí)大于DE/rand/1/bin算法、DE/rand/2/bin算法、jDE算法，約是它們耗時(shí)的1.5倍。分析算法可知，DE/rand/1/bin算法、DE/rand/2/bin算法、jDE算法和RMDE算法的時(shí)間復(fù)雜度相同，均為O(NP*D)，其中RMDE算法的過(guò)程更為復(fù)雜，所以耗時(shí)較多。雖然，OLCPDE算法的時(shí)間復(fù)雜度為O(3NP*D/2)，但是由于算法的收斂速度較快，在最大迭代次數(shù)之內(nèi)搜索到全局最優(yōu)點(diǎn)，停止搜索，因此對(duì)f1～f9函數(shù)搜索的時(shí)間消耗小于其他算法。

圖2 OLCPDE與4種經(jīng)典算法的收斂曲線

s

3.3OLCPDE算法策略分析

3.3.1 普通種群選用反向?qū)W習(xí)精英選擇策略的有效性分析

為了測(cè)試反向?qū)W習(xí)精英選擇策略在算法中的有效性，按照對(duì)照實(shí)驗(yàn)的原則，設(shè)置3個(gè)參照算法，分別是：普通種群使用1對(duì)1貪婪選擇的OLCPDE算法(記作CPDE)、精英種群使用了反向?qū)W習(xí)精英選擇策略的OLCPDE算法(記作EOLCDE)和跨種群策略使用反向?qū)W習(xí)精英選擇的OLCPDE算法(記作COLCDE)與OLCPDE算法進(jìn)行比較，參數(shù)設(shè)置與3.1節(jié)相同，尋優(yōu)結(jié)果見(jiàn)表4。

根據(jù)表4可以看出，對(duì)于上述12種函數(shù)，除了f3函數(shù)，不使用反向?qū)W習(xí)精英選擇策略的CPDE算法均無(wú)法快速穩(wěn)定地收斂到全局最優(yōu)點(diǎn)，說(shuō)明了使用反向?qū)W習(xí)精英選擇策略能有效加快算法的收斂；將反向?qū)W習(xí)精英選擇策略分別用于對(duì)精英種群和對(duì)跨種群進(jìn)行選擇的EOLCDE算法和COLCDE算法，能夠?qū)ふ业揭徊糠趾瘮?shù)的最優(yōu)值，但是對(duì)于其他函數(shù)，則容易陷入局部最優(yōu)。因此，引入反向?qū)W習(xí)精英選擇策略能夠提高算法的收斂精度和速度，將反向?qū)W習(xí)精英選擇用作普通種群的選擇策略，才能夠最有效地提升算法的全局尋優(yōu)能力。

3.3.2 跨種群策略對(duì)函數(shù)尋優(yōu)的有效性分析

為了測(cè)試跨種群策略在算法中的有效性，設(shè)置了取消跨種群策略的OLCPDE算法(記作OLDE)與OLCPDE算法分別對(duì)6個(gè)單峰函數(shù)和6個(gè)多峰函數(shù)進(jìn)行對(duì)比測(cè)試，參數(shù)設(shè)置與3.1節(jié)相同，尋找到最優(yōu)解的次數(shù)統(tǒng)計(jì)結(jié)果見(jiàn)表5。

根據(jù)表5可以看出雖然跨種群策略對(duì)多峰函數(shù)的尋優(yōu)的影響性不顯著，但是它能有效提升單峰函數(shù)尋優(yōu)的成功次數(shù)，使用跨種群策略的OLCPDE算法能夠防止單峰函數(shù)早熟，增加算法的穩(wěn)定性。

表4 OLCPDE與3個(gè)參照算法的收斂性能和尋到最優(yōu)值的成功次數(shù)對(duì)比

表5 OLCPDE與OLDE對(duì)單峰和多峰函數(shù)尋優(yōu)成功次數(shù)比較

3.4OLCPDE算法分析

根據(jù)上述圖表可以看出，除個(gè)別多峰函數(shù)外，OLCPDE算法均能夠穩(wěn)定地收斂到全局最優(yōu)解。通過(guò)對(duì)本文算法策略性能的進(jìn)行分析，結(jié)論如下：

1)通過(guò)對(duì)反向?qū)W習(xí)精英選擇策略的性能進(jìn)行分析，證明該策略有效提升DE算法的尋優(yōu)精度；同時(shí)，將該策略用于普通種群，能最大限度地提高算法的尋優(yōu)精度，大幅提升尋到最優(yōu)解的概率。若取消該策略，使用標(biāo)準(zhǔn)DE算法的選擇策略，除個(gè)別單峰函數(shù)，均無(wú)法達(dá)到最優(yōu)解。

2)通過(guò)分析跨種群策略對(duì)算法的影響，證明運(yùn)用該策略能有效提升單峰函數(shù)尋優(yōu)成功的次數(shù)，進(jìn)一步提升算法尋優(yōu)的穩(wěn)定性。

3)本文算法采用多個(gè)子種群進(jìn)化模式，提高種群多樣性，有效彌補(bǔ)單種群進(jìn)化過(guò)程中種群多樣性不足的缺陷，防止算法早熟。

綜上所述，本文算法策略的使用能有效提升算法性能，無(wú)論單峰函數(shù)還是多峰函數(shù)，OLCPDE算法均能高效、穩(wěn)定地尋到最優(yōu)解。

4 結(jié)語(yǔ)

針對(duì)差分進(jìn)化算法尋優(yōu)精度低、收斂速度慢等缺陷，本文提出了一種基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法(OLCPDE)，引入混沌分散策略來(lái)種群初始化能有效提升初始種群的質(zhì)量，對(duì)普通子種群應(yīng)用反向?qū)W習(xí)精英選擇策略，擴(kuò)大種群的搜索范圍，提升算法的全局搜索能力，采用跨種群的差分進(jìn)化策略，進(jìn)一步增強(qiáng)了算法尋優(yōu)的穩(wěn)定性。通過(guò)對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)，說(shuō)明了OLCPDE算法能有效地避免早熟，具有較好的收斂速度、優(yōu)化精度和魯棒性。將改進(jìn)的算法應(yīng)用到實(shí)際的工程中，進(jìn)一步檢驗(yàn)算法的性能，是下一步將要研究的內(nèi)容。

)

[1]STORNR,PRICEK.Differentialevolution—asimpleandefficientheuristicforglobaloptimizationovercontinuousspaces[J].JournalofGlobalOptimization, 1997, 11(4): 341-359.

[2]VESTERSTROMJ,THOMSENR.Acomparativestudyofdifferentialevolution,particleswarmoptimization,andevolutionaryalgorithmsonnumericalbenchmarkproblems[C]//Proceedingsofthe2004IEEECongressonEvolutionaryComputation.Piscataway,NJ:IEEE, 2004:267-282.

[3]PRICEK,STORNRM,LAMPINENJA.Differentialevolution:apracticalapproachtoglobaloptimization(naturalcomputingseries) [J].NaturalComputing, 2005, 141(2): 1-24.

[4]VARADARAJANM,SWARUPKS.Networklossminimizationwithvoltagesecurityusingdifferentialevolution[J].ElectricPowerSystemsResearch, 2008, 78(5): 815-823.

[5]BRESTJ,GREINERS,BOSKOVICB,etal.Self-adaptingcontrolparametersindifferentialevolution:acomparativestudyonnumericalbenchmarkproblems[J].IEEETransactionsonEvolutionaryComputation, 2006, 10(6): 646-657.

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

[7] 呂銘晟, 沈洪遠(yuǎn), 李志高, 等.多變異策略差分進(jìn)化算法的研究與應(yīng)用[J]. 計(jì)算機(jī)工程, 2014, 40(12): 146-150.(LYUMS,SHENHY,LIZG,etal.Researchandapplicationofdifferentialevolutionalgorithmundermultiplemutationstrategy[J].ComputerEngineering, 2014, 40(12): 146-150.)

[8] 王叢佼, 王錫淮, 肖建梅.基于極值優(yōu)化的混合差分進(jìn)化算法[J]. 計(jì)算機(jī)科學(xué), 2013, 40(5): 257-260.(WANGCJ,WANGXH,XIAOJM.Hybriddifferentialevolutionaryalgorithmbasedonextremaloptimization[J].ComputerScience, 2013, 40(5): 257-260.)

[9] 匡芳君, 張思揚(yáng), 金忠, 等.混沌差分進(jìn)化粒子群協(xié)同優(yōu)化算法[J]. 微電子學(xué)與計(jì)算機(jī), 2014, 31(8): 29-33, 39.(KUANGFJ,ZHANGSY,JINZ,etal.Chaoticdifferentialevolutionparticleswarmcooperativeoptimizationalgorithm[J].Microelectronics&Computer, 2014, 31(8): 29-33, 39.)

[10] 張大斌, 楊添柔, 溫梅,等.基于差分進(jìn)化的魚群算法及其函數(shù)優(yōu)化應(yīng)用[J]. 計(jì)算機(jī)工程, 2013, 39(5): 18-22, 27.(ZHANGDB,YANGTR,WENM,etal.Fishwarmalgorithmbasedondifferentialevolutionanditsfunctionoptimizationapplication[J].ComputerEngineering, 2013, 39(5): 18-22, 27.)

[11]OUCM.Designofblockciphersbysimplechaoticfunctions[J].IEEEComputationalIntelligenceMagazine, 2008, 3(2): 54-59.

[12] 周新宇, 吳志健, 王暉.一種精英反向?qū)W習(xí)的差分演化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013, 34(9):1647-1652.(ZHOUXY,WUZJ,WANGH.Adifferentialevolutionalgorithmusingeliteopposition-basedlearning[J].JournalofChineseComputerSystems, 2013, 34(9): 1647-1652.)

[13]WANGH,WUZ,RAHNAMAYANS.Enhancedopposition-baseddifferentialevolutionforsolvinghigh-dimensionalcontinuousoptimizationproblems[J].SoftComputing, 2011, 15(11): 2127-2140.

[14]WANGH,WUZ,RAHNAMAYANS,etal.Enhancingparticleswarmoptimizationusinggeneralizedopposition-basedlearning[J].InformationSciences, 2011, 181(20): 4699-4714.

[15]AHANDANIMA,ALAVI-RADH.Opposition-basedlearningintheshuffleddifferentialevolutionalgorithm[J].SoftComputing, 2012, 16(8): 1303-1337.

[16] 董小剛, 鄧長(zhǎng)壽, 譚毓澄, 等.求解大規(guī)模優(yōu)化問(wèn)題的正交反向混合差分進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(6): 1656-1661.(DONGXG,DENGCS,TANYC,etal.Hybridizationdifferentialevolutionalgorithmoforthogonalcrossoverandopposition-basedlearningforlarge-scaleoptimizationproblem[J].ApplicationResearchofComputers, 2016, 33(6): 1656-1661.)

[17] 歐陽(yáng)海濱, 高立群, 孔祥勇.隨機(jī)變異差分進(jìn)化算法[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 34(3): 330-334.(OUYANGHB,GAOLQ,KONGXY,Randommutationdifferentialevolutionalgorithm[J].JournalofNortheasternUniversity(NaturalScience), 2013, 34(3): 330-334.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(71471073, 71171093),theFundamentalResearchFundsfortheCentralUniversities(CCNU14Z02016).

ZHANG Bin, born in 1993, M. S. candidate. His research interests include logistics system optimization, intelligent optimization.

LI Yanhui, born in 1974, Ph. D., professor. His research interests include logistics and supply chain management, management information system.

GUO Hao, born 1987, Ph. D. candidate. His research interests include logistics system optimization.

Cross-population differential evolution algorithm based on opposition-based learning

ZHANG Bin, LI Yanhui, GUO Hao*

(School of Information Management, Central China Normal University, Wuhan Hubei 430079, China)

Aiming at the deficiencies of traditional Differential Evolution (DE) algorithm, low optimization accuracy and low convergence speed, a Cross-Population Differential Evolution algorithm based on Opposition-based Learning (OLCPDE) was proposed by using chaos dispersion strategy, opposition-based optimization strategy and multigroup parallel mechanism. The chaos dispersion strategy was used to generate the initial population, then the population was divided into sub-groups of the elite and the general, and a standard differential evolution strategy and a differential evolution strategy of Opposition-Based Learning (OBL) were applied to the two sub-groups respectively. Meanwhile, a cross-population differential evolution strategy was applied to further improve the accuracy and enhance population diversity for unimodal function. The sub-groups were handled through these three strategies to achieve co-evolution. After the experiments are totally run for 30 times independently, it is proven that the proposed algorithm can stably converge to the global optimal solution in 11 functions among 12 standard test functions, which is superior to other comparison algorithms. The results indicate that the proposed algorithm not only has high convergence precision but also effectively avoid trapping in local optimum.

Differential Evolution (DE); Opposition-Based Learning (OBL); cross-population; chaos search; function optimization

2016- 08- 02;

2016- 09- 28。

國(guó)家自然科學(xué)基金資助項(xiàng)目(71471073,71171093);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(CCNU14Z02016)。

張斌(1993—),男,湖北襄陽(yáng)人,碩士研究生,主要研究方向：物流系統(tǒng)優(yōu)化、智能計(jì)算; 李延暉(1974—),男,湖南衡陽(yáng)人,教授,博士,主要研究方向：物流與供應(yīng)鏈管理、管理信息系統(tǒng); 郭昊(1987—),男,湖北荊州人,博士研究生,主要研究方向：物流系統(tǒng)優(yōu)化。

1001- 9081(2017)04- 1093- 07

10.11772/j.issn.1001- 9081.2017.04.1093

TP301.6;TP18

A