基于泛化反向學習的多目標約束差分進化算法

魏文紅　王甲?！√铡°憽≡A強

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

?

基于泛化反向學習的多目標約束差分進化算法

魏文紅1王甲海2陶銘1袁華強1

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

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

關鍵詞差分進化；泛化反向學習；多目標優(yōu)化；約束優(yōu)化;非支配排序

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

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

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

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

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

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

1相關背景知識

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

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

(1)

(2)

(3)

(4)

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

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

(5)

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

1.2差分進化算法

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

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

(6)

(7)

(8)

(9)

(10)

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

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

(11)

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

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

(12)

1.3反向學習

Fig. 1　An example for opposite point.圖1　反向點的例子

(13)

如果對于一個n維向量的反向點，則用如下定義表示.

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

(14)

有了反向點的定義之后，那么基于反向學習的優(yōu)化可以定義如下:

1.4泛化反向學習

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

(15)

(16)

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

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

(17)

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

(18)

2GOMCDE算法

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

2.1適應值變換約束處理技術

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

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

(19)

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

(20)

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

(21)

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

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

(22)

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

(23)

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

(24)

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

(25)

因此最終的適應值可以表示為

(26)

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

(27)

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

2.2Pareto非支配排序

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

2.3擁擠距離

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

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

(28)

2.4算法描述

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

算法1. GOMCDE偽代碼.

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

輸出：外部非支配集E中的個體.

① 評價種群P0,求出變換后的適應值和約束違反程度;

② 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

⑩ 評價變換種群GOP0,求出變換后的適應值和約束違反程度;

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

3實驗測試

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

3.1實驗參數(shù)設置

1) 種群大小.NP=100.

2) 交叉概率.CR=0.8.

3) 縮放因子.F=0.2.

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

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

3.2性能評價指標

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

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

(29)

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

3) 多樣性評價指標Δ[3].表示近似解集的分散程度，Δ值越小，表示解集的分布性越好，即多樣性就越好.當Δ=0時，說明所有的解沿著Pareto前沿均勻分布.Δ的計算公式為

(30)

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

6) 基于ε支配的評價指標Iε[34].對于給定的ε>0和參考集R，Iε可以定義為

(31)

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

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

3.3性能評價指標

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

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

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

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

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

Fig.s.圖3　6種算法針對CTP4測試問題關于和Iε的統(tǒng)計盒圖

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

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

Table 2　Convergence and Diversity Comparison Between GOMCDE and Other Algorithms

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

對于無約束優(yōu)化問題，我們隨機地選取了ZDT2測試問題做了Pareto前沿的測試，圖4顯示了這6種算法的Pareto前沿測試結果.從測試結果來看，GOMCDE算法和OMODE算法、MDEOO算法雖然都達到了最優(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種算法針對ZDT2測試問題的Pareto前沿

4結束語

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

參考文獻

[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)(鄭金華, 劉磊, 李密青, 等. 差分選擇策略在復雜多目標優(yōu)化問題中的研究[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ō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

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

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

中圖法分類號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).