魏文紅　王甲海　陶　銘　袁華強(qiáng)

1(東莞理工學(xué)院計(jì)算機(jī)學(xué)院　廣東東莞　523808)2(中山大學(xué)計(jì)算機(jī)科學(xué)系　廣州　510006) (weiwh@dgut.edu.cn)

?

基于泛化反向?qū)W習(xí)的多目標(biāo)約束差分進(jìn)化算法

魏文紅1王甲海2陶銘1袁華強(qiáng)1

1(東莞理工學(xué)院計(jì)算機(jī)學(xué)院廣東東莞523808)2(中山大學(xué)計(jì)算機(jī)科學(xué)系廣州510006) (weiwh@dgut.edu.cn)

摘要差分進(jìn)化算法是一種簡(jiǎn)單有效的進(jìn)化算法，基于泛化反向?qū)W習(xí)的機(jī)制在進(jìn)化算法中經(jīng)?？梢砸龑?dǎo)種群的進(jìn)化.針對(duì)多目標(biāo)的約束優(yōu)化問題，提出了一種基于泛化反向?qū)W習(xí)的多目標(biāo)約束差分進(jìn)化算法.該算法采用基于泛化反向?qū)W習(xí)的機(jī)制(generalized opposition-based learning, GOBL)產(chǎn)生變換種群，然后在種群初始化和代跳躍階段，利用非支配排序、擁擠距離和約束處理技術(shù)從原始種群和其變換種群中選擇更優(yōu)的種群個(gè)體作為新的種群繼續(xù)迭代進(jìn)化；該算法通過采用基于泛化反向?qū)W習(xí)的機(jī)制，可以引導(dǎo)種群個(gè)體慢慢向最優(yōu)的Pareto前沿逼近，以求得最優(yōu)解集.最后采用多目標(biāo)Benchmark問題對(duì)該算法進(jìn)行了實(shí)驗(yàn)評(píng)估，實(shí)驗(yàn)結(jié)果表明：與NSGA-Ⅱ，MOEA?D及其他的多目標(biāo)進(jìn)化算法相比，提出的算法具有更好的收斂性，并且產(chǎn)生的解能夠逼近最優(yōu)的Pareto前沿.

關(guān)鍵詞差分進(jìn)化；泛化反向?qū)W習(xí)；多目標(biāo)優(yōu)化；約束優(yōu)化;非支配排序

多目標(biāo)優(yōu)化問題(multi-objective optimization problems, MOPs)在許多領(lǐng)域都有廣泛的應(yīng)用，特別是科學(xué)、工程和經(jīng)濟(jì)領(lǐng)域[1].與單目標(biāo)優(yōu)化問題不同，多目標(biāo)優(yōu)化問題必須同時(shí)優(yōu)化多個(gè)目標(biāo)函數(shù).由于多個(gè)目標(biāo)函數(shù)相互沖突，所以不能像求解單目標(biāo)優(yōu)化問題一樣，總能找到一個(gè)最優(yōu)或近優(yōu)解，而是求解到一個(gè)滿足所有目標(biāo)函數(shù)折中的解集，這個(gè)解集稱之為Pareto最優(yōu)解[2].由于現(xiàn)實(shí)中的科學(xué)和工程問題都存在著各種各樣的約束條件，因此多目標(biāo)約束優(yōu)化問題(multi-objective constrained optimization problems, MCOPs)引起了研究者們的關(guān)注[3-5].因?yàn)榧s束條件的出現(xiàn)，會(huì)導(dǎo)致可行解區(qū)域減小并使得搜索解的過程變得更為復(fù)雜，因此如何采用約束處理機(jī)制來處理MCOPs，將是一個(gè)值得研究的課題.

進(jìn)化算法(evolution algorithm， EA)是一種隨機(jī)的、基于種群的優(yōu)化算法，它在每一次運(yùn)行中可以找到多個(gè)最優(yōu)解，天生具有解決MOPs的特性.在過去的幾十年中，提出了大量的多目標(biāo)進(jìn)化算法[3-8]，典型的代表主要有：Deb等人[3]提出的快速和精英選擇的多目標(biāo)非支配排序遺傳算法(nondominated sorting genetic algorithm， NSGA-Ⅱ)和Zhang等人[8]提出的基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decom-position， MOEAD).

差分進(jìn)化算法(differential evolution， DE)是由Storn和Price[9]首次提出的，它是一種功能強(qiáng)大、結(jié)構(gòu)簡(jiǎn)單、易用且魯棒性強(qiáng)的全局優(yōu)化算法，該算法在解決單目標(biāo)約束優(yōu)化問題(COPs)時(shí)已經(jīng)取得了顯著的成就.Abbass等人[10]首次將DE算法用來解決MOPs，稱為Pareto前沿差分進(jìn)化算法(Pareto-frontier differ-ential evolution， PDE).在PDE算法中，通過DE產(chǎn)生子代，然后子代與父代通過支配關(guān)系進(jìn)行比較，丟棄支配解，只保留非支配解到下一代中.Madavan[11]提出了Pareto差分進(jìn)化方法(Pareto differential evolution approach, PDEA)，該算法與PDE類似，通過DE產(chǎn)生子代，然后合并父代與子代個(gè)體，再計(jì)算它們的Pareto非支配排序和多樣性排序，最后根據(jù)排序選擇保留最優(yōu)個(gè)體.Xue等人[12]提出了多目標(biāo)差分進(jìn)化算法(multi-objective differential evolution, MODE)，該算法與NSGA-Ⅱ類似，也采用了Pareto非支配排序和擁擠距離排序技術(shù)，不同的是，MODE的適應(yīng)值首先通過Pareto非支配排序計(jì)算，然后根據(jù)擁擠距離值改變.Robic等人[13]提出了多目標(biāo)優(yōu)化差分進(jìn)化算法(differential evolution for multi-objective optimization, DEMO)，該算法與MODE有點(diǎn)相似，仍然采用了Pareto非支配排序和擁擠距離排序技術(shù)，但是它又像PDEA一樣，把父代和子代合并，再計(jì)算它們的Pareto非支配排序和擁擠距離排序，以提升候選解的均勻分布.

基于反向?qū)W習(xí)(opposition-based learning， OBL)的機(jī)制是由Al-Qunaieer等人[14]首次提出的，該方法為了獲得更優(yōu)的解來進(jìn)行下一次迭代，在每次迭代過程中，不僅要評(píng)價(jià)本次搜索到的最優(yōu)解，而且還要評(píng)價(jià)與該最優(yōu)解處于相反方向的解，然后得出最終的最優(yōu)解，用來進(jìn)行下一次迭代.最近基于反向?qū)W習(xí)的機(jī)器學(xué)習(xí)方法被廣泛用于一些啟發(fā)式進(jìn)化算法如差分進(jìn)化、粒子群、人工神經(jīng)網(wǎng)絡(luò)、蟻群和人工蜜蜂算法等[15-16].根據(jù)基于反向?qū)W習(xí)的原理，Wang等人[17]提出了一種基于泛化反向?qū)W習(xí)(generalized opposition-based learning, GOBL)的機(jī)制，GOBL采用轉(zhuǎn)換搜索空間技術(shù)把當(dāng)前空間的解轉(zhuǎn)換到一個(gè)新的空間去，即在求解過程中，不但要考慮當(dāng)前空間的候選解，而且還要考慮轉(zhuǎn)換空間的候選解.由于同時(shí)搜索當(dāng)前空間和轉(zhuǎn)換空間的解，GOBL能夠很快地發(fā)現(xiàn)最優(yōu)解.

Rahnamayan等人[18]首次提出了基于反向?qū)W習(xí)的差分進(jìn)化算法，在該算法中，采用基于反向?qū)W習(xí)的機(jī)制來初始化種群.之后的幾年里，包括Rahnamayan在內(nèi)的許多專家學(xué)者，分別提出了改進(jìn)的基于反向?qū)W習(xí)的差分進(jìn)化算法[19-23].后來OBL機(jī)制也被用于解決多目標(biāo)優(yōu)化問題，Peng等人[24]提出了一種解決多目標(biāo)優(yōu)化問題的基于反向?qū)W習(xí)的多目標(biāo)差分進(jìn)化算法(opposition-based multi-objective differential evolution algorithm，OMODE)，該算法采用OBL機(jī)制產(chǎn)生初始種群的反向種群，然后通過Pareto非支配排序和擁擠距離排序從原初始種群和其反向種群中選最優(yōu)個(gè)體組成新的初始種群繼續(xù)迭代.Dong等人[25]提出了一種基于反向操作的多目標(biāo)差分進(jìn)化算法(multi-objective differential evolution based on opposite operation, MDEOO)，與OMODE不同的是，該算法不但在種群初始化階段產(chǎn)生反向種群，而且在子代的迭代過程中也產(chǎn)生子代的反向種群，然后仍然采用Pareto非支配排序和擁擠距離排序技術(shù)從原始種群和其反向種群中選擇最優(yōu)的個(gè)體繼續(xù)迭代.

最近Wang等人[22]采用GOBL機(jī)制，提出了一種基于泛化反向?qū)W習(xí)的差分進(jìn)化算法(generalized opposition-based differential evolution, GODE)，該算法被證明具有較快的收斂速度和求解精度.然而該算法卻不能用于解決多目標(biāo)優(yōu)化問題，更不能解決多目標(biāo)約束優(yōu)化問題.另外包括OMODE和MDEOO在內(nèi)的基于反向?qū)W習(xí)的多目標(biāo)差分進(jìn)化算法也不能解決多目標(biāo)約束優(yōu)化問題.在這種背景下，本文提出了一種基于泛化反向?qū)W習(xí)的多目標(biāo)約束差分進(jìn)化算法(generalized opposition-based multi-objective constrained differential evolution, GOMCDE)，并且針對(duì)多目標(biāo)測(cè)試函數(shù)集進(jìn)行了實(shí)驗(yàn)測(cè)試.測(cè)試結(jié)果顯示，與NSGA-Ⅱ和MOEAD及其他相關(guān)算法相比，GOMCDE算法具有更強(qiáng)的全局搜索性能、更快的收斂速度和更好的Pareto前沿.

1相關(guān)背景知識(shí)

1.1多目標(biāo)約束優(yōu)化問題

在多目標(biāo)約束優(yōu)化問題中，既存在等式約束條件和不等式約束條件，還包括向量x的上界和下界，具體如下：

(1)

(2)

(3)

(4)

其中,f(x)為k個(gè)目標(biāo)函數(shù)，需要同時(shí)優(yōu)化；x=(x1,x2,…,xn)為n維決策向量；gj(x) ≤ 0和hj(x)=0分別表示q個(gè)不等式約束和m-q個(gè)等式約束；函數(shù)fk，gl和hl為線性或非線性實(shí)數(shù)函數(shù)；upj和lowj分別為變量xj的上界和下界.另外，假定可行解空間中滿足所有約束的點(diǎn)集合用U表示，搜索空間中滿足上界和下界約束的點(diǎn)集合用S表示，其中S?U.

為了考慮多個(gè)目標(biāo)之間的平衡，引入了解之間的支配概念.假定解向量x=(x1,x2,…,xn)，y=(y1,y2,…,yn)，如果xi≤yi,i=1,2,…,n且x≠y,則xy，即稱為x支配y.如果對(duì)于一個(gè)解向量滿足?x∈U,xx*，則稱?x∈U,xx*為Pareto最優(yōu)解.由所有Pareto最優(yōu)解組成的集合，稱為Pareto最優(yōu)解集(Pareto set， PS).在多目標(biāo)優(yōu)化問題中，Pareto最優(yōu)解集在目標(biāo)空間對(duì)應(yīng)的目標(biāo)向量稱為Pareto前沿(Pareto front， PF)，具體表示如下：

(5)

求解多目標(biāo)約束優(yōu)化問題的目標(biāo)，就是要找到一個(gè)滿足各種約束條件的Pareto前沿.

1.2差分進(jìn)化算法

差分進(jìn)化算法是一類比較流行的進(jìn)化算法，并且具有良好的性能，廣泛地應(yīng)用于各種應(yīng)用領(lǐng)域.在差分進(jìn)化算法中，一般包括NP個(gè)種群，每個(gè)個(gè)體向量的維度為n.一般地，個(gè)體表示為：向量xi,t=(x1i,t,x2i,t,…,xni,t)，其中i=1,2,…,NP，NP為種群大小，n為個(gè)體向量的維度，t為當(dāng)前種群的代數(shù).差分進(jìn)化算法包括3個(gè)主要的操作：變異、交叉和選擇[13].

1) 變異.在變異操作中，對(duì)于每個(gè)種群產(chǎn)生目標(biāo)向量vi,t，變異策略主要如下：

(6)

(7)

(8)

(9)

(10)

其中，下標(biāo)r1，r2，r3，r4，r5都是隨機(jī)從集合{1,2,…,NP}{i}中選取的；xbest,t為種群在第t代最好的個(gè)體；縮放因子F為實(shí)數(shù)，F(xiàn)∈[0,1].

2) 交叉.交叉操作主要產(chǎn)生試驗(yàn)變量ui,t=(u1i,t,u2i,t,…,uni,t)，具體如下：

(11)

其中，i=1,2,…,NP,j=1,2,…,n；jrandom是屬于1～n之間的一個(gè)隨機(jī)整數(shù)；randomj(0,1)為對(duì)于每個(gè)j產(chǎn)生[0,1]均勻分布的隨機(jī)數(shù)；使用參數(shù)jrandom是為了保證試驗(yàn)向量ui,t不同于目標(biāo)向量xi,t；交叉概率因子CR的取值通常為0～1.

3) 選擇.在選擇操作中，目標(biāo)向量xi,t和試驗(yàn)向量ui,t根據(jù)它們的適應(yīng)值進(jìn)行比較，選擇適應(yīng)值更優(yōu)的進(jìn)入下一代種群：

(12)

1.3反向?qū)W習(xí)

Fig. 1　An example for opposite point.圖1　反向點(diǎn)的例子

(13)

如果對(duì)于一個(gè)n維向量的反向點(diǎn)，則用如下定義表示.

定義2. 假設(shè)P=(z1,z2,…,zn)為一個(gè)n維空間的點(diǎn)，其中z1,z2,…,zn∈且zi∈[ai,bi]，?i∈{1,2,…,n}，則P的反向點(diǎn)由式(14)決定.

(14)

有了反向點(diǎn)的定義之后，那么基于反向?qū)W習(xí)的優(yōu)化可以定義如下:

1.4泛化反向?qū)W習(xí)

OBL僅僅是求反向點(diǎn)，而GOBL則是把當(dāng)前空間的點(diǎn)或候選解變換到一個(gè)新的空間，然后和OBL原理一樣，同時(shí)評(píng)價(jià)當(dāng)前空間和變換空間的候選解，選出最優(yōu)的候選解.在文獻(xiàn)[17]中，GOBL被證明具有更強(qiáng)的能力發(fā)現(xiàn)全局最優(yōu)解.

(15)

(16)

其中,random(a,b)為產(chǎn)生[a,b]中的隨機(jī)數(shù).

定義5. 假設(shè)P=(z1,z2,…,zn)為一個(gè)n維空間的點(diǎn)，其中z1,z2,…,zn∈且zi∈[ai,bi]，?i∈{1,2,…,n}.則P的轉(zhuǎn)換空間點(diǎn)的元素可由式(17)計(jì)算.

(17)

其中,k=random(0,1).

(18)

2GOMCDE算法

根據(jù)GOBL定義可知，基于泛化反向?qū)W習(xí)的機(jī)制需要比較種群與轉(zhuǎn)換種群的適應(yīng)值.而對(duì)于多目標(biāo)約束優(yōu)化問題的適應(yīng)值比較不能像單目標(biāo)無約束優(yōu)化問題一樣簡(jiǎn)單處理.本文采用適應(yīng)值變換、Pareto非支配排序和擁擠距離排序技術(shù)來處理GOBL中的適應(yīng)值比較問題.

2.1適應(yīng)值變換約束處理技術(shù)

為了解決多目標(biāo)約束優(yōu)化問題，我們必須在GOMCDE算法中加入約束處理技術(shù).我們知道，在無約束的差分進(jìn)化算法中，適應(yīng)值都等于目標(biāo)函數(shù)值，但是在約束差分進(jìn)化算法中，由于約束的存在，不能簡(jiǎn)單地考慮適應(yīng)值等于目標(biāo)函數(shù)值，必須要考慮約束條件的存在.比如，對(duì)于最小值優(yōu)化問題，解向量x的目標(biāo)函數(shù)值比y小，但x卻違反了約束條件而y沒有違反約束條件.此時(shí)，應(yīng)該考慮可能解向量y比x更優(yōu).基于這種原理，我們采用了適應(yīng)值變換技術(shù)來處理約束優(yōu)化問題.

一般地，對(duì)于約束優(yōu)化問題，經(jīng)常會(huì)把等式約束轉(zhuǎn)化成不等式約束，具體如下：

(19)

其中,l∈{q+1,q+2,… ,m}；δ為等式約束違反的容忍因子，一般取正整數(shù).解x到第l個(gè)約束的距離可以表示為

(20)

那么解x到可行解區(qū)域的邊界距離，即約束違反程度可以表示為

(21)

在適應(yīng)值變換約束處理技術(shù)中，為了更好地處理約束差分進(jìn)化算法中的適應(yīng)值，采用應(yīng)值變換方法把種群分成3種狀態(tài)：不可行狀態(tài)、半可行狀態(tài)和可行狀態(tài).

1) 不可行狀態(tài).在不可行狀態(tài)下，種群只包含了不可行解，因此不用考慮目標(biāo)函數(shù)值，只需要考慮約束違反程度.約束違反程度可以通過式(21)計(jì)算，此時(shí)適應(yīng)值計(jì)算式為

(22)

2) 半可行狀態(tài).在半可行狀態(tài)下，種群既包含了部分可行解又包含了部分不可行解，因此就必須在目標(biāo)函數(shù)值和約束違反程度之間找到一個(gè)平衡點(diǎn).從解的層面分析，此時(shí)把種群細(xì)分為可行解組(Z1)和不可行解組(Z2).因此解xi,t的目標(biāo)函數(shù)值f′(xi,t)就可以轉(zhuǎn)換成：

(23)

其中,φ是上一代種群的可行解比率；xbest,t和xworst,t分別是可行解組Z1最優(yōu)和最差的解.進(jìn)一步把式(23)歸一化為

(24)

式(20)可以計(jì)算約束違反程度，在此狀態(tài)下，式(21)歸一化為

(25)

因此最終的適應(yīng)值可以表示為

(26)

3) 可行狀態(tài).在可行狀態(tài)下，種群中所有個(gè)體都是可行解，因此就可以看作是無約束優(yōu)化問題來處理.此時(shí)適應(yīng)值就等于目標(biāo)函數(shù)值f(xi,t)，具體為

(27)

通過適應(yīng)值變換技術(shù)，所有的個(gè)體都基于變換后的適應(yīng)值進(jìn)行比較，選擇適應(yīng)值更優(yōu)的個(gè)體繼續(xù)進(jìn)化.對(duì)于多目標(biāo)約束優(yōu)化問題，種群中的個(gè)體采用Pareto非支配排序技術(shù)進(jìn)行比較.從適應(yīng)值變換的原理可以看出，對(duì)于多目標(biāo)無約束優(yōu)化問題，適應(yīng)值變換技術(shù)同樣適用，即無約束優(yōu)化問題中的種群個(gè)體屬于適應(yīng)值變換中的第3種狀態(tài)：可行狀態(tài).

2.2Pareto非支配排序

在Pareto非支配排序之前，必須先計(jì)算：1)支配數(shù)np，它是解p支配其他解的個(gè)數(shù)；2)支配集Sp.在Pareto非支配排序過程中，首先從支配集Sp中選取所有np=0的成員q加入鏈表Q中，然后設(shè)置其他成員的支配數(shù)減1，重復(fù)這2步直到所有的成員都加入到鏈表Q中為止.

2.3擁擠距離

擁擠距離用來衡量解分布的密度，在非支配集I中，解i的擁擠距離等于解i的鄰居解i-1和解i+1之間沿著每個(gè)目標(biāo)的平均距離，具體可根據(jù)式(28)計(jì)算.在計(jì)算擁擠距離時(shí)，首先要根據(jù)目標(biāo)函數(shù)值排序種群.在本文中，由于約束的存在，我們根據(jù)變換后的適應(yīng)值來排序種群，然后再根據(jù)式(28)計(jì)算每個(gè)解的擁擠距離.由于式(28)并不能應(yīng)用于邊界解的擁擠距離的計(jì)算，所以邊界解的擁擠距離通常被設(shè)置為無窮大.

I[i]distance=(I[i+1].m-I[i-1].m)

(28)

2.4算法描述

絕大多數(shù)的進(jìn)化算法都是在種群初始化階段和代跳躍階段使用OBL機(jī)制求其反向種群.在本文中，我們也在種群初始化階段和代跳躍階段使用GOBL機(jī)制求其變換種群.對(duì)于隨機(jī)生成的初始種群P0(其中種群大小為NP，個(gè)體向量的維度為n)，通過式GOPji,0=k(aj+bj)-Pji,0計(jì)算出其變換種群GOP0.其中，i=1,2,…,NP；j=1,2,…,n；k為[0,1]之間的隨時(shí)數(shù).然后采用Pareto非支配排序和擁擠距離排序技術(shù)根據(jù)變換后的適應(yīng)值，從種群P0和GOP0中選出NP個(gè)適應(yīng)值更優(yōu)的個(gè)體組成新的初始種群P0.在種群代跳躍階段，與單目標(biāo)優(yōu)化問題相同的是，該階段的執(zhí)行也必須滿足一個(gè)代跳躍概率J，在絕大部分情況下J=0.3[18].與單目標(biāo)優(yōu)化問題不同的是，變換種群的計(jì)算式與種群初始化階段類似，仍然采用[a,b]作為決策空間.即GOPji,t=k(aj+bj)-Pji,t，其中t為種群的代數(shù).最后在個(gè)體的生成選擇階段，與其他多目標(biāo)差分進(jìn)化算法的流程一樣，采用Pareto非支配排序和擁擠距離排序技術(shù)根據(jù)變換后的適應(yīng)值，從父代群Pt-1、子代種群Pt和變換種群GOP中選出NP個(gè)適應(yīng)值更優(yōu)的個(gè)體繼續(xù)迭代.GOMCDE算法偽代碼如下：

算法1. GOMCDE偽代碼.

輸入：初始種群P0=(x1,0,x2,0,…,xNP,0);

輸出：外部非支配集E中的個(gè)體.

① 評(píng)價(jià)種群P0,求出變換后的適應(yīng)值和約束違反程度;

② for (i=0;i

③ for (j=0;j

④GOPji,0=k×(aj+bj)-Pji,0;

⑤ ifGOPji,0bj

⑥GOPji,0=random(aj,bj);

⑦ end if

⑧ end for

⑨ end for

⑩ 評(píng)價(jià)變換種群GOP0,求出變換后的適應(yīng)值和約束違反程度;

從算法1的描述中可以看出，GOMCDE算法簡(jiǎn)單且容易操作，它采用適應(yīng)值變換技術(shù)不但可以解決多目標(biāo)約束優(yōu)化問題，同時(shí)也適用于多目標(biāo)無約束優(yōu)化問題.由于GOBL的時(shí)間復(fù)雜度為O(NP×n)，Pareto非支配排序的時(shí)間復(fù)雜度為O(k×NP×NP)，擁擠距離排序的時(shí)間復(fù)雜度為O(k×NP×logNP)，所以GOMCDE算法的時(shí)間復(fù)雜度為O(NP×(n+k×NP)).

3實(shí)驗(yàn)測(cè)試

為了進(jìn)一步驗(yàn)證GOMCDE算法的有效性，我們對(duì)GOMCDE算法和NSGA-Ⅱ[3]，EAMO[26]，CHMEO[5]，CMODE[6]，CMOPSO[27]等算法針對(duì)多目標(biāo)約束優(yōu)化問題進(jìn)行了對(duì)比實(shí)驗(yàn)測(cè)試.用于測(cè)試的約束優(yōu)化問題主要包括BNN[28]，SRN[29]，TNK[30]，CONSTR[31]，CTP1-CTP7[31]，Welded Beam Problem[26]，其中Welded Beam Problem是一個(gè)現(xiàn)實(shí)生活中的測(cè)試問題.在這些測(cè)試問題中，有些具有連續(xù)的Pareto前沿，有些則是不連續(xù)的.為了證明GOMCDE算法對(duì)于多目標(biāo)無約束優(yōu)化問題同樣有效，我們對(duì)GOMCDE算法和NSGA-Ⅱ[3]，MOEAD[8]，MODE-RMO[32]，OMODE[24]，MDEOO[25]等算法針對(duì)ZDT1-ZDT4[33]和ZDT6[33]等無約束優(yōu)化問題進(jìn)行了對(duì)比實(shí)驗(yàn)測(cè)試.在所有的實(shí)驗(yàn)過程中，實(shí)驗(yàn)環(huán)境為64位的Windows 7系統(tǒng)，其中CPU為Intel Core TM 2.83 GHz，內(nèi)存為4 GB，編程語言為Maltab 2013 b.

3.1實(shí)驗(yàn)參數(shù)設(shè)置

1) 種群大小.NP=100.

2) 交叉概率.CR=0.8.

3) 縮放因子.F=0.2.

4) 代跳躍概率.J=0.3.

5) 最大代數(shù).Gmax=100.

3.2性能評(píng)價(jià)指標(biāo)

1) Pareto前沿PF[3].Pareto非支配集中的最優(yōu)解映射在目標(biāo)空間中的目標(biāo)向量.

2) 收斂性評(píng)價(jià)指標(biāo)r[3].表示近似解到Pareto前沿最優(yōu)解的歐氏距離，r值越小，表示近似解越接近Pareto前沿，收斂性越好.r的計(jì)算公式為

(29)

其中,N為非支配解的個(gè)數(shù)，di為相鄰非支配解之間的歐氏距離.

3) 多樣性評(píng)價(jià)指標(biāo)Δ[3].表示近似解集的分散程度，Δ值越小，表示解集的分布性越好，即多樣性就越好.當(dāng)Δ=0時(shí)，說明所有的解沿著Pareto前沿均勻分布.Δ的計(jì)算公式為

(30)

4) 超體積評(píng)價(jià)指標(biāo)IH(hypervolume indicator)[34].表示近似解集A在目標(biāo)空間相對(duì)于參考點(diǎn)所支配的空間大小，IH值越大，解集A在目標(biāo)空間所支配的區(qū)域就越大，即該解集A就越接近最優(yōu)解，分布性越好，同時(shí)也可以表示收斂性越好.

6) 基于ε支配的評(píng)價(jià)指標(biāo)Iε[34].對(duì)于給定的ε>0和參考集R，Iε可以定義為

(31)

其中,A和B為2個(gè)近似解集.Iε值越小，表示算法的收斂性越好.

7) Mann-Whitney檢驗(yàn)分析[35].該檢驗(yàn)分析是由Mann和Whitney提出的針對(duì)2個(gè)獨(dú)立樣本進(jìn)行分析的非參數(shù)檢測(cè)方法，它在這2獨(dú)立樣本的總體分布未知的情況下，通過2組樣本的分析來推斷總體的分布是否存在顯著差異.

3.3性能評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)中所有算法對(duì)于每一個(gè)測(cè)試函數(shù)都運(yùn)行50次，在每一次運(yùn)行過程中設(shè)置Max_FEs=2.5×104.

1) 針對(duì)約束優(yōu)化問題的比較

Table 1　Mann-Whitney Analysis onandIεBetween GOMCDE and Other Algorithms

Fig. 2　Pareto front on CTP1 for six algorithms.圖2　6種算法針對(duì)CTP1測(cè)試問題的Pareto前沿

我們隨機(jī)地選取了CTP1測(cè)試問題做了Pareto前沿的測(cè)試，圖2顯示了這6種算法的Pareto前沿測(cè)試結(jié)果，NSGA-Ⅱ算法雖然能夠逼近最優(yōu)Pareto前沿，但其解的分布性較差；EAMO算法的分布性較優(yōu)于NSGA-Ⅱ算法，但是它的收斂性稍差;CMODE算法與EAMO算法類似;CHMEO，CMOPSO算法在收斂性和分布性方面都明顯優(yōu)于前面3種算法，但是當(dāng)它們與GOMCDE算法比較時(shí)，卻又不及GOMCDE算法.所以GOMCDE算法不但具有較好的收斂性，而且還具有比較均勻的分布性，明顯優(yōu)于其他5種算法.

Fig.s.圖3　6種算法針對(duì)CTP4測(cè)試問題關(guān)于和Iε的統(tǒng)計(jì)盒圖

2) 針對(duì)無約束優(yōu)化問題比較

因?yàn)镚OMCDE算法也可以適用于無約束優(yōu)化問題，所以我們也對(duì)GOMCDE算法與NSGA-Ⅱ，MOEAD，MODE-RMO以及其他2類基于OBL機(jī)制的多目標(biāo)算法OMODE，MDEOO針對(duì)無約束的Benchmark問題進(jìn)行了實(shí)驗(yàn)測(cè)試，表2顯示了比較結(jié)果，其中粗體表示該算法的值最優(yōu)，旁邊括號(hào)表示這6種算法的排名.

Table 2　Convergence and Diversity Comparison Between GOMCDE and Other Algorithms

從表2可以看到，GOMCDE算法明顯優(yōu)于其他算法，絕大部分結(jié)果都排在第一的位置；而且OMODE，MDEOO算法比NSGA-Ⅱ，MOEAD，MODE-RMO算法也略占優(yōu)勢(shì)，這是由于OMODE和MDEOO算法都采用了OBL機(jī)制的原因.另外還可以看出，MDEOO算法比OMODE算法稍占優(yōu)勢(shì)，這是因?yàn)殡m然它們都采用了OBL機(jī)制，但OMODE算法只是在種群初始化階段采用OBL機(jī)制，而MDEOO算法在種群初始化和代跳躍階段都采用了OBL機(jī)制.GOMCDE算法比MDEOO算法較優(yōu)是因?yàn)镚OMCDE算法在種群初始化和代跳躍階段采用了GOBL機(jī)制.

對(duì)于無約束優(yōu)化問題，我們隨機(jī)地選取了ZDT2測(cè)試問題做了Pareto前沿的測(cè)試，圖4顯示了這6種算法的Pareto前沿測(cè)試結(jié)果.從測(cè)試結(jié)果來看，GOMCDE算法和OMODE算法、MDEOO算法雖然都達(dá)到了最優(yōu)Pareto前沿，但是GOMCDE算法在分布性方面明顯要優(yōu)于OMODE算法和MDEOO算法；NSGA-Ⅱ，MOEAD，MODE-RMO算法無論是在收斂性還是分布性方面均稍弱于OMODE算法和MDEOO算法，更弱于GOMCDE算法.

Fig. 4　Pareto front on ZDT2 for six algorithms.圖4　6種算法針對(duì)ZDT2測(cè)試問題的Pareto前沿

4結(jié)束語

GOBL是一種泛化的OBL機(jī)制，把GOBL機(jī)制應(yīng)用于進(jìn)化算法被證明能夠加快算法的收斂速度和提高算法的求解精度.然而GOBL機(jī)制卻從來沒有應(yīng)用于多目標(biāo)優(yōu)化問題中，更沒有用來解決多目標(biāo)約束優(yōu)化問題.針對(duì)此情況，本文結(jié)合GOBL機(jī)制，提出了GOMCDE算法.該算法首先利用GOBL機(jī)制生成變換種群；然后采用Pareto非支配排序、擁擠距離排序和約束處理技術(shù)從初始種群和其變換種群中選取最優(yōu)的個(gè)體組成新的初始種群繼續(xù)迭代；最后為了加速收斂速度，采用GOBL機(jī)制代跳躍方法產(chǎn)生子代種群的變換種群，再次使用Pareto非支配排序、擁擠距離排序和約束處理技術(shù)從父代種群、子代種群及其變換種群中選擇最優(yōu)的個(gè)體組成新的子代種群繼續(xù)迭代.為了驗(yàn)證本文算法的優(yōu)勢(shì)，針對(duì)多目標(biāo)測(cè)試函數(shù)集進(jìn)行了實(shí)驗(yàn)測(cè)試.測(cè)試結(jié)果表明，與其他相關(guān)算法相比，GOMCDE算法具有更強(qiáng)的全局搜索性能、更快的收斂速度和更好的Pareto前沿.

參考文獻(xiàn)

[1]Zhou A, Qu B, Li H. Multiobjective evolutionary algorithms: A survey of the state of the art[J]. Swarm and Evolutionary Computation, 2011, 1(1): 32-49

[2]He Z, Yen G, Zhang J. Fuzzy-based Pareto optimality for many-objective evolutionary algorithms[J]. IEEE Trans on Evolutionary Computation, 2014, 18(2): 269-285

[3]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197

[4]Yen G G, Leong W F. A multiobjective particle swarm optimizer for constrained optimization[J]. Recent Algorithms and Applications in Swarm Intelligence Research, 2011, 2(1): 1-23

[5]Woldesenbet G, Yen G, Tessema G. Constraint handling in multiobjective evolutionary optimization[J]. IEEE Trans on Evolutionary Computation, 2009, 13(3): 514-525

[6]Qu B, Suganthan P N. Constrained multi-objective optimization algorithm with an ensemble of constraint handling methods[J]. Engineering Optimization, 2011, 43(4): 403-416

[7]Zheng Jinhua, Liu Lei, Li Miqing, et al. Difference selection strategy for solving complex multi-objective problems[J]. Journal of Computer Research and Development, 2015, 52(9): 2123-2134 (in Chinese)(鄭金華, 劉磊, 李密青, 等. 差分選擇策略在復(fù)雜多目標(biāo)優(yōu)化問題中的研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(9): 2123-2134)

[8]Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731

[9]Storn R, Price K. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359

[10]Abbass H A, Sarker R, Newton C. PDE: A Pareto frontier differential evolution approach for multi-objective optimization problems[C] //Proc of IEEE Congress on Evolutionary Computation, vol 2. Piscataway, NJ: IEEE, 2001: 831-836

[11]Madavan N K. Multiobjective optimization using a Pareto differential evolution approach[C] //Proc of IEEE Congress on Evolutionary Computation, vol 2. Piscataway, NJ: IEEE, 2002: 1145-1150

[12]Xue F, Sanderson A C, Graves R J. Pareto-based multi-objective differential evolution[C] //Proc of IEEE Congress on Evolutionary Computation, vol 2. Piscataway, NJ: IEEE, 2003: 862-869

[13]Robic T, Filipic B. DEMO: Differential evolution for multiobjective optimization[G] //LNCS 3410: Proc of Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2005: 520-533

[14]Al-Qunaieer F S, Tizhoosh H R, Rahnamayan S. Opposition based computing—A survey[C] //Proc of the 6th IEEE World Congress on Computational Intelligence. Piscataway, NJ: IEEE, 2010: 1-7

[15]Xu Q Z, Wang L, Wang N, et al. A review of opposition-based learning from 2005 to 2012[J]. Engineering Applications of Artificial Intelligence, 2014, 29: 1-12

[16]Wang H. Opposition-based barebones particle swarm for constrained nonlinear optimization problems[J]. Mathematical Problems in Engineering, 2012, 2012: 1-12

[17]Wang H, Wu Z, Liu Y, et al. Space transformation search: A new evolutionary technique[C] //Proc of World Summit Genetic Evolutionary Computation. New York: ACM, 2009: 537-544

[18]Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition-based differential evolution algorithms[C] //Proc of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2006: 2010-2017

[19]Ahandani M A, Alavi-Rad H. Opposition-based learning in the shuffled differential evolution algorithm[J]. Soft Computing, 2012, 16(8): 1303-1337

[20]Omran M G H. CODEQ: An effective metaheuristic for continuous global optimization[J]. International Journal of Metaheuristics, 2010, 1(2): 108-131

[21]Miao X F, Mu D J, Han X W, et al. A hybrid differential evolution for numerical optimization[C] //Proc of Int Conf on Biomedical Engineering and Informatics. Piscataway, NJ: IEEE, 2009: 1-5

[22]Wang H, Rahnamayan S, Wu Z J. Parallel differential evolution with self adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems[J]. Journal of Parallel Distributed Computing, 2013, 73(1): 62-73

[23]Omran M G H, Salman A. Constrained optimization using CODEQ[J]. Chaos, Solitons Fractals, 2009, 42(2): 662-668

[24]Peng L, Wang Y, Dai G. A novel opposition-based multi-objective differential evolution algorithm for multi-objective optimization[G] //LNCS 5370: Proc of Advances in Computation and Intelligence. Berlin: Springer, 2008: 162-170

[25]Dong N, Wang Y. Multiobjective differential evolution based on opposite operation[C] //Proc of Int Conf on Computational Intelligence and Security, vol 1. Piscataway, NJ: IEEE, 2009: 123-127

[26]Ray T, Tai K, Seow K C. An evolutionary algorithm for multiobjective optimization[J]. Engineering Optimization, 2001, 33(3): 399-424

[27]Wang Jianlin, Wu Jiahuan, Zhang Chaoran, et al. Constrained multi-objective particle swarm optimization algorithm based on self-adaptive evolutionary learning[J]. Control and Decision, 2014, 29(10): 1765-1770 (in Chinese)(王建林, 吳佳歡, 張超然, 等. 基于自適應(yīng)進(jìn)化學(xué)習(xí)的約束多目標(biāo)粒子群優(yōu)化算法[J]. 控制與決策, 2014, 29(10): 1765-1770)

[28]Binh T T, Korn U. MOBES: A multi-objective evolution strategy for constrained optimization problems[C] //Proc of the 3rd Int Conf on Genetic Algorithms. New York: ACM, 1997: 176-182

[29]Srinivas N, Deb K. Multi-objective function optimization using non-dominated sorting genetic algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248

[30]Tanaka M, Watanabe H, Furukawa Y, et al. GA-based decision support system for multi-criteria optimization[C] //Proc of Int Conf on Systems, Man and Cybernetics, vol 2. Piscataway, NJ: IEEE, 1995: 1556-1561

[31]Deb K, Pratap A, Meyarivan T. Constrained test problems for multi-objective evolutionary optimization[G] //LNCS 1993: Proc of Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2001: 284-298

[32]Chen X, Du W, Qian F. Multi-objective differential evolution with ranking-based mutation operator and its application in chemical process optimization[J]. Chemometrics and Intelligent Laboratory Systems, 2014, 136: 85-96

[33]Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195

[34]Zitzler E, Thiele L, Laumanns M, et al. Performance assessment of multiobjective optimizers: An analysis and review[J]. IEEE Trans on Evolutionary Computation, 2003, 7(2): 117-132

[35]Fonseca C M, Knowles J D, Thiele L, et al. A tutorial on the performance assessment of stochastic multiobjective optimizers[G] //LNCS 3410: Proc of the 3rd Int Conf on Evolutionary Multi-Criterion Optimization, vol 216. Berlin: Springer 2005: 240-258

Wei Wenhong, born in 1977. Associate professor in Dongguan University of Technology. His main research interests include evolutionary algorithms, multi-objective optimization and machine learning.

Wang Jiahai, born in 1977. Associate professor in Sun Yat-sen University. His main research interests include compu-tational intelligence and its applications.

Tao Ming, born in 1986. Associate professor in Dongguan University of Technology. His main research interests include intelligence computing and distributed computing.

Yuan Huaqiang, born in 1966. Professor in Dongguan University of Technology. His main research interests include intelligence computing.

Multi-Objective Constrained Differential Evolution Using Generalized Opposition-Based Learning

Wei Wenhong1, Wang Jiahai2, Tao Ming1, and Yuan Huaqiang1

1(ComputerInstitute,DongguanUniversityofTechnology,Dongguan,Guangdong523808)2(DepartmentofComputerScience,SunYat-senUniversity,Guangzhou510006)

AbstractDifferential evolution is a simple and efficient evolution algorithm to deal with nonlinear and complex optimization problems. Generalized opposition-based learning (GOBL) often guides population to evolve in the evolutionary computing. However, real-world problems are inherently constrained optimization problems often with multiple conflicting objectives. Hence, for resolving multi-objective constrained optimization problems, this paper proposes a constrained differential evolution algorithm using generalized opposition-based learning. In this algorithm, firstly, the transformed population is generated using general opposition-based learning in the population initialization. Secondly, the better individuals that are selected from the initial population and the transformed population using non-dominated sorting, crowding distance sorting and constraint handling techniques compose the new initial population. Lastly, based on a jumping probability, the transformed population is calculated again after generating new populations, and the fittest individuals that are selected from the union of the current population and the transformed population compose new population using the same techniques. The solution can be evolved toward Pareto front slowly according to the generalized opposition-based learning, so that the best solutions set can be found. The proposed algorithm is tested in multi-objective benchmark problems and compared with NSGA-Ⅱ, MOEA?D and other multi-objective evolution algorithms. The experimental results show that our algorithm is able to improve convergence speed and generate solutions which approximate to the best optimal Pareto front.

Key wordsdifferential evolution; generalized opposition-based learning (GOBL); multi-objective optimization; constrained optimization; non-dominated sorting

收稿日期：2015-09-08；修回日期：2015-12-30

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61170216,61300198,61572131)；廣東高?？萍紕?chuàng)新項(xiàng)目(2013KJCX0178)

通信作者：袁華強(qiáng)(hyuan66@163.com)

中圖法分類號(hào)TP18

This work was supported by the National Natural Science Foundation of China (61170216, 61300198, 61572131) and the Guangdong Science and Technology Innovation Project of Higher Education (2013KJCX0178).