用于約束多目標(biāo)優(yōu)化問題的雙群體差分進化算法孟紅云1張小華2劉三陽1(1.西安電子科技大學(xué)應(yīng)用數(shù)學(xué)系，西安，710071；2.西安電子科技大學(xué)智能信息處理研究所，西安，710071)摘要：首先給出一種改進的差分進化算法，然后提出一種基于雙群體搜索機制的求解約束多目標(biāo)優(yōu)化問題的差分進化算法.該算法同時使用兩個群體，其中一個用于保存搜索過程中找到的可行解，另一個用于記錄在搜索過程中得到的部分具有某些優(yōu)良特性的不可行解，避免了構(gòu)造罰函數(shù)和直接刪除不可行解.此外，將本文算法、NSGA-II和SPEA的時間復(fù)雜度進行比較表明，NSGA-II最優(yōu)，本文算法與SPEA相當(dāng).對經(jīng)典測試函數(shù)的仿真結(jié)果表明，與NSGA-H相比較，本文算法在均勻性及逼近性方面均具有一定的優(yōu)勢.關(guān)鍵字：差分進化算法；約束優(yōu)化問題；多目標(biāo)優(yōu)化問題；中圖分類號：TP181引言達(dá)爾文的自然選擇機理和個體的學(xué)習(xí)能力推動進化算法的出現(xiàn)和發(fā)展，用進化算法求解優(yōu)化問題已成為一個研究的熱點［1-3］.但目前研究最多的卻是無約束優(yōu)化問題.然而，在科學(xué)研究和工程實踐中，許多實際問題最終都?xì)w結(jié)為求解一個帶有約束條件的函數(shù)優(yōu)化問題，因此研究基于進化算法求解約束優(yōu)化問題是非常有必要的.不失一般性，以最小化問題為例，約束優(yōu)化問題(ConstrainedOptimizationProblem，COP)可定義如下：minF(X)=(f(X)fG)A,f(X))Xg 1 2(1)(COP)s.t.g(X)<0,i=1,A,p(1)元=(氣,X2,A,X)GRn稱為n維決氣(X)=0,j=1,A,q其中F(X)為目標(biāo)函數(shù)，gi(X),七(x)稱為約束條件策向量.將滿足所有約束條件的解空間S稱為(1)的可行域.特別的，當(dāng)k=1時，(1)為單目標(biāo)優(yōu)化問題；當(dāng)k>1時，(1)為多目標(biāo)優(yōu)化問題.g,(X)為第i個不等式約束，氣(x)元=(氣,X2,A,X)GRn稱為n維決(2)(h(x)一5<0'：h(X)一5<0(2)故在以后討論問題時，僅考慮帶不等式約束的優(yōu)化問題.進一步，如果X使得不等式約束g,(X)=0，則稱約束g’G)在X處是積極的.在搜索空間S中，滿足約束條件的決策變量X稱為可行解，否則稱為不可行解.定義1(全局最優(yōu)解)X*=(X*,x；,A,X*)是COP的全局最優(yōu)解，是指X*gS且F(X*)不劣于可行域內(nèi)任意解J所對應(yīng)的目標(biāo)函數(shù)F(y)，表示為F(X*)主F(y).對于單目標(biāo)優(yōu)化問題，F(xiàn)(x*)主F(y)等價為F(x*)<F(y)，而對于多目標(biāo)優(yōu)化問題是指不存在y，使得F(y)Pareto優(yōu)于F(X*).目前，進化算法用于無約束優(yōu)化問題的文獻居多，與之比較，對約束優(yōu)化問題的研究相對較少［4-6］。文［7］對當(dāng)前基于進化算法的各種約束處理方法進行了較為詳細(xì)的綜述.對于約束優(yōu)化問題的約束處理方法基本上分為兩類:基于罰函數(shù)的約束處理技術(shù)和基于多目標(biāo)優(yōu)化技術(shù)的約束處理技術(shù).由于罰函數(shù)法在使用中不需要約束函數(shù)和目標(biāo)函數(shù)的解析性質(zhì)，因此經(jīng)常被應(yīng)用于約束優(yōu)化問題，但該類方法對罰因子有很強的依賴性，需要根據(jù)具體問題平衡罰函數(shù)與目標(biāo)函數(shù).為了避免復(fù)雜罰函數(shù)的構(gòu)造，Verdegay等［8］將進化算法中的競爭選擇用于約束處理，并在比較兩個解的性能時提出了三個準(zhǔn)則，但他的第三個準(zhǔn)則一可行解優(yōu)于不可行解一這一準(zhǔn)則合理性不強.然而該文的這一準(zhǔn)則卻為進化算法求解約束優(yōu)化問題提供了新思路，獲得了良好效果.因為在現(xiàn)實中存在一大類約束優(yōu)化問題，其最優(yōu)解位于約束邊界上或附近，對于這類問題，在最優(yōu)解附近的不可行解的適應(yīng)值很可能優(yōu)于位于可行域內(nèi)部的大部分可行解的適應(yīng)值，因此無論從適應(yīng)值本身還是從最優(yōu)解的相對位置考慮，這樣的不可行解對找到最優(yōu)解都是很有幫助的，故如何有效利用搜索過程中的部分具有較好性質(zhì)的不可行解是解決此類問題的難點之一.基于以上考慮，本文擬給出一種求解約束多目標(biāo)優(yōu)化問題的基于雙群體機制的差分進化算法，并對文中算法的時間復(fù)雜度與NSGA-I%］和SPEA［10進行比較，最后用實驗仿真說明文中算法的可行性及有效性.2用于約束優(yōu)化的雙群體差分進化算法差分進化算法差分進化算法是一類簡單而有效的進化算法，已被成功應(yīng)用于求解無約束單目標(biāo)和多目標(biāo)優(yōu)化問題［11-14］.該算法在整個運行過程中保持群體的規(guī)模不變，它也有類似于遺傳算法的變異、交叉和選擇等操作，其中變異操作定義如下：C=P+F.（P-P） （3）r1 r2 r3其中P1,P2,P3為從進化群體中隨機選取的互不相同的三個個體，F(xiàn)為位于區(qū)間［0.5,1］中的參數(shù).（3）式表示從種群中隨機取出的兩個個體P,P的差，經(jīng)參數(shù)F放大或縮小后被加r2r3到第三個個體七上，以構(gòu)成新的個體C二?,A,c「?為了增加群體的多樣性，交叉操作被引入差分進化算法，具體操作如下：TOC\o"1-5"\h\z針對父代個體P=3,A,x）的每一分量x，產(chǎn)生位于區(qū)間［0,1］中的隨機數(shù)p，根據(jù)p與r1 n i i i參數(shù)CR的大小關(guān)系確定是否用c替換x，以得到新的個體P，=（x',A,x'），i i r1 n\o"CurrentDocument"其中x'=］''叩匚CR.如果新個體P‘優(yōu)于父代個體P，則用P'來替換P，否則i［x,ifp>CR r r r r保持不變.在差分進化算法中，選擇操作采取的是貪婪策略，即只有當(dāng)產(chǎn)生的子代個體優(yōu)于父代個體時才被保留，否則，父代個體被保留至下一代.大量研究與實驗發(fā)現(xiàn)差分進化算法在維護群體的多樣性及搜索能力方面功能較強，但收斂速度相對較慢，因此本文擬給出一種改進的差分進化算法用于多目標(biāo)優(yōu)化問題，仿真實驗表明，改進的差分進化算法在不破壞原有算法維護群體多樣性的前提下，可改善差分進化算法的收斂速度.基于雙群體的差分進化算法2.2.1基本概念以下僅討論帶不等式約束的多目標(biāo)優(yōu)化問題

定義定義minF定義定義minF(x)=min(fG)A,fG))s.t.g(x)<0,i=1,A,px=(x,A,x)l<x<u,j=1,A,n1njjjx稱為(4)的不可行解，是指至少存在一個1<i<p，滿足gi(x)>0.x違反約束的強度，即約束違反度函數(shù)定義為P(x)=甘max(0,g(x)3，本文i(4)i=1定義x違反約束的數(shù)目N(x)=YNum(g*》，其中Num(x)=J^,：＞；.i=1 I,一定義不可行解x優(yōu)于不可行解歹，是指x的約束向量＜pG)NG》Pareto優(yōu)于j的約束向量(PG)N(j)).2.2.2基本思想由上一節(jié)分析可知，在搜索過程中遇到的不可行解不能簡單丟掉.因此，在設(shè)計算法時不但要考慮算法的收斂速度，而且還必須保證群體中可行解的優(yōu)勢地位；另一方面，對于多目標(biāo)優(yōu)化問題，維持搜索群體的多樣性與考慮群體的收斂速度是同等重要的.基于此考慮，本節(jié)采用基于雙群體的差分進化算法求解約束多目標(biāo)優(yōu)化問題，其中群體PoPf用來保存搜索過程中遇到的可行解，PoP用來保存搜索過程中遇到的占優(yōu)不可行解，同時PoPf具有較強的記憶功能，可記憶PoPf中每一個體搜索到的最優(yōu)可行解和整個群體PoPf到目前為止搜索到的最優(yōu)可行解，分別記為lbest和gbest，其中l(wèi)best表示個體對自身的思考和認(rèn)知，gbest表示個體間的信息交流，這一點和PSO算法類似.與此同時，我們還通過一種改進的差分進化算法產(chǎn)生新的群體，在產(chǎn)生新群體的過程中，群體PoP中的部分個體參與了個體再生，并通過新生成的個體更新PoP、PoP、lbest和gbest.為了避免性能較優(yōu)的不可行解被刪除，本文擬采用雙群體搜索機制，其中群體PoP=4,x,A,x｝用于記錄可行解，群體PoP=4,j,A,j｝記錄不可行解，f12 N1 C 12 N2N「N2分別為群體PoPf與PoPgbest=g,g,A,g｝分別為群體1 2 N3的規(guī)模，滿足氣＞NN「N2分別為群體PoPf與PoPgbest=g,g,A,g｝分別為群體1 2 N3PoPf迄今為止搜索到最優(yōu)可行解.2.2.3改進的差分進化算法為了維護群體PoPf的多樣性和收斂性，同時有效的利用已搜索到的不可行解的某些優(yōu)良特性，下面給出一種改進的差分進化算法，并通過以下兩種方式產(chǎn)生新的個體.方法1：C=x+F(z-x)+F(g-x)尸1 1r2 r2 2r4 r3其中x,x,x(=PoP,ZeIbest,gegbest.方法2：C=x+FG-y)+F(g-y)r1 1r2 r3 2r4 r5其中xePoP,y,yePoP,ZeIbest,gegbest.方法1的目的在于通過向最優(yōu)個體學(xué)習(xí)，改善算法的收斂速度.方法2的主要目的在于和不可行個體進行信息交流，共享不可行解的一些優(yōu)良特性，增加群體的多樣性.在具體操作過程中，首先用改進的差分進化算法產(chǎn)生新的個體C=G］,A,匕)，然后針對父代個體P=(x,A,x)的每一個分量x，產(chǎn)生位于區(qū)間［0,1］中的隨機數(shù)p，根據(jù)p與參數(shù)CR的r1 n i i i大小關(guān)系確定是否用c來替換x，得到新的個體P，=(x',A,x').i i r1 n如果P：是可行解，而且PoPf的規(guī)模小于給定規(guī)模N，則可直接將P；插入PoPf；如果插入后的群體的規(guī)模大于給定規(guī)模%，首先兩兩比較PoPf中的個體，如果存在兩個個體x,xePoP，滿足F(x)Pareto優(yōu)于F(x)，則將個體x刪除，如果不存在，也就是ij / i j i說集合PoPf中任意兩個個體所對應(yīng)的目標(biāo)向量都不可比較，則計算PoPf中任意兩個個體間的距離，隨機刪除距離最小的兩個個體中的一個.如果P：是不可行解，而且PoP的規(guī)模小于給定規(guī)模N2，則可直接將P：插入群體PoP中；如果PoP等于給定規(guī)模閾值N2，計算插入P：后的群體PoP中任意兩個個體的約束向量，如果存在兩個個體y,，yiePoPf,滿足約束向量(P(yi)N(yi))pareto優(yōu)于約束向量(P(y:,N&?，則刪除y；如果不存在，則刪除滿足P(y)=maxP(y)的個體y.jj j 1 yePoPc 1經(jīng)過以上操作，群體PoPf和PoPC的規(guī)模不會大于給定規(guī)模閾值.最后利用新生成的群體PoP更新最優(yōu)個體集合Ibest和gbest，群體gbest的更新方法和SPEA算法中外部群f體的更新方法相同，而Ibest的更新方法如下：如果新生成的可行解P'rPareto優(yōu)于對應(yīng)的局部最優(yōu)解Z，則用P'替換Z,否則不予替換.i r i算法的基本流程綜上所述，基于雙群體的差分進化算法的約束處理技術(shù)的流程可表示如下：stepl.隨機生成N(N>N1+N「個個體，判斷每一個體的可行性，然后根據(jù)個體可行性將其插入到對應(yīng)的群體PoPf或PoP中；并初始化Ibest和gbest及參數(shù)CR和P.step2.判斷搜索是否結(jié)束，如果結(jié)束，轉(zhuǎn)向step5，否則轉(zhuǎn)向step3.

step3.生成隨機數(shù)〃，如果p>0,根據(jù)方法1,生成新的個體P,否則，根據(jù)方法2生成新的個體P'，如果P'是可行解，將P'插入到PoP中；否則P'插入到PoP中，反r r r f r c復(fù)執(zhí)行直到生成N個可行解.istep4.根據(jù)新生成的群體PoPf更新最優(yōu)個體集lbest和gbest，轉(zhuǎn)向step2.step5.輸出最優(yōu)解集gbest.3算法分析算法的性能衡量約束優(yōu)化問題的算法性能的衡量可分為兩部分，一部分為最終獲得的最優(yōu)解的性能的衡量，如通過GD[15]來度量最優(yōu)群體的逼近性，SP[16]來衡量最優(yōu)解的分布均勻性，或通過計算目標(biāo)函數(shù)的次數(shù)衡量算法的復(fù)雜度和算法的收斂速度.另一部分是針對約束優(yōu)化問題來衡量群體的多樣性，Koziel&來衡量群體的多樣性，Koziel&Michalewicz[i7]給出一種多樣性度量準(zhǔn)則P其定義如下:(5)其中|F|表示每一次搜索過程中生成的可行解的數(shù)目，|S|為所生成的所有個體的數(shù)目.相應(yīng)地，為了衡量群體中的不可行解違反約束的強度，可采用約束違反度函數(shù)的均值來度量:TOC\o"1-5"\h\zP=ZP(y)/|PoP| (6)avg cyePoPc其中|PoPI表示集合PoP所包含元素的數(shù)目.然而在實際問題中，決策者往往只對某一范c c圍的最優(yōu)解感興趣，故下邊只評價本文算法對標(biāo)準(zhǔn)測試函數(shù)最終獲得的最優(yōu)解集的逼近性與均勻性，并與NSGA-II進行比較.算法的時間復(fù)雜性分析我們僅考慮種群規(guī)模對算法時間復(fù)雜度的影響，設(shè)可行群體PoPf的規(guī)模為N1，不可行群體PoP的規(guī)模為N2，群體lbest的規(guī)模為N1，群體gbest的最大規(guī)模為N3，則文中算法迭代一次的時間復(fù)雜度可計算如下：算法中重組和變異操作的時間復(fù)雜度為0(N1)；判斷進化群體中個體可行性所需時間復(fù)雜度為0(N1)；更新群體PoPf、Po「和lbest的時間復(fù)雜度分別為0(N1)、0(N2)和O(N1)；計算群體PoPf和gbest的適應(yīng)度所需時間復(fù)雜度為0(N1+N3)；用于更新最優(yōu)群體gbest的時間復(fù)雜度最差為0((N1+N3)2)；保持最優(yōu)群體gbest和進化群體PoPf多樣性的時間復(fù)雜度最差為0((N+N)3)+(N+N)log(N+N))；1 3 1 3 1 30((氣0((氣+N3)2)(7)0(N)+0(N)+0(N)+0(N)+0(N)+0(N+N)+TOC\o"1-5"\h\z1 1 1 2 1 1 30((N+N)3)+0((N+N)log(N+N))13 13 13上述復(fù)雜度可簡化為0((N+N)3)+0((N+N)2)+0((N+N)log(N+N)) (8)1 3 1 3 1 3 1 3設(shè)N為所有種群的規(guī)模，令N=N1+N2+N3，則本文算法的時間復(fù)雜度0((N+N)3)+0((N+N)2)+0((N+N)log(N+N))<0(N3) (9)13 13 13 13

NSGA-n［9］和SPEA［10］是多目標(biāo)進化算中兩個最具有代表性的優(yōu)秀算法，這兩個算法的時間復(fù)雜度最差分別為O(N2)和O((N+N)3)，其中N,N分別為進化種群規(guī)模和外部種群集的規(guī)模.因而，SPEA和本文算法的時間復(fù)雜度最差為O(N3)，這比NSGA-H的時間復(fù)雜度稍高一些，但接下來的實驗結(jié)果告訴我們，本文算法的均勻性及逼近性卻明顯優(yōu)于NSGA-II.事實上，SPEA和本文算法的時間復(fù)雜度主要用于環(huán)境選擇(Environmentalselection)上,如果文中對gbest采取NSGA-I中的多樣性保持策略，則本文算法的復(fù)雜度將降至O(N2).4實驗結(jié)果與分析測試函數(shù)與參數(shù)設(shè)置x1c(x>ffG)]minF(x)=min|f^_.=min為了驗證本文給出算法的可行性，我們采用Deb［18］建議的用來測試約束多目標(biāo)優(yōu)化算法性能的四個常見的測試函數(shù)來檢驗本文算法的性能.可行解集合的規(guī)模N1=100，不可行解集合的規(guī)模N2=10x1c(x>ffG)]minF(x)=min|f^_.=min1-羯]|gG)=cosGIf(_)-el-sin(B)fG)>aIsin{伽[sin(0If(x)-e〕+cos(0)f(x)]c}Id2 1 2 1其中 c(x)=41+^5x2-10cos(2兀x' ， 0<x<1,-5<x<5,i=2,3,4,5.i=2i i 1 i測試函數(shù)選取不同的參數(shù)0,a,b,c,d,e時，所構(gòu)造的測試函數(shù)性質(zhì)不同，可行解和不可行解的分布也不同，最終導(dǎo)致全局Pareto最優(yōu)解集的不同.其中通過控制參數(shù)b的大小，可以控制Pareto前端不連續(xù)的段數(shù)，b越大段數(shù)越多；而較小參數(shù)d可以使得每一不連續(xù)Pareto前端僅包含一個Pareto點；參數(shù)a調(diào)節(jié)連續(xù)可行域到Pareto前端的點的距離，a越大距離越遠(yuǎn)，其作用在于調(diào)節(jié)問題求解的難度；參數(shù)c的作用在于改變分段Pareto前端之間的分布特性，當(dāng)c=1時，Pareto前端為均勻分布；當(dāng)c>1時，Pareto前端向f較大的1方向移動；當(dāng)c<1時，則Pareto前端向f2較大的方向移動.基于以上分析我們選取不同的參數(shù)構(gòu)造4個常用的測試函數(shù)檢驗本節(jié)算法的性能，這些測試函數(shù)的參數(shù)取值具體如下.

圖測試函數(shù)CTP1在目標(biāo)空間示意圖 圖測試函數(shù)CTP2圖測試函數(shù)CTP1在目標(biāo)空間示意圖 圖測試函數(shù)CTP2在目標(biāo)空間示意圖圖測試函數(shù)CTP3在目標(biāo)空間示意圖 圖測試函數(shù)CTP4在目標(biāo)空間示意圖測試函數(shù)CTP1：0=0.1兀，a=40,b=0.5,c=1,d=2,e=—2.可行解、不可行解、全局Pareto前端分布如圖所示.測試函數(shù)CTP2：0=—0.05兀，a=40,b=5,c=1,d=6,e=0.可行解、不可行解、全局Pareto前端分布如圖所示．測試函數(shù)CTP3：0=—0.2k,a=0.2,b=10,c=1,d=6,e=1.可行解、不可行解、全局Pareto前端分布如圖所示.測試函數(shù)CTP4：0=—0.2兀,a=0.1,b=10,c=1,d=0.5,e=1.可行解、不可行解、全局Pareto前端分布如圖所示.實驗結(jié)果與分析在相同的測試函數(shù)和目標(biāo)函數(shù)計算次數(shù)下，將本文算法和經(jīng)典的NSGA-II算法進行比較,并將各自算法獨立運行30次，然后統(tǒng)計兩種算法所得Pareto最優(yōu)解集的均勻性(Spacing,SP)與逼近性(Generationaldistance,GD)的最好、最差、均值、方差和中間值，以此作為衡量算法性能的標(biāo)準(zhǔn).由于真實Pareto最優(yōu)集是未知的，故我們將兩種算法所得的60個近似Pareto最優(yōu)解集之并集的Pareto濾集作為真實Pareto最優(yōu)解集的逼近，其中測試函數(shù)CTP1,CTP2,CTP3的函數(shù)值計算次數(shù)為10200，而CTP4的函數(shù)值計算次數(shù)為610014.這里，集合1的Pareto濾集Pareto(I)定義為Pareto(I)={xIxe1,3yeI,F(y)匹F(x)}.圖、、、為從30次運行中隨機選擇的一次運行結(jié)果，從實驗曲線可以看到本文算法求出的ParetoFront在逼近性方面要優(yōu)于NSGA-II.圖測試函數(shù)CTP1的ParetoFront 圖測試函數(shù)CTP2的ParetoFront圖測試函數(shù)CTP3的ParetoFront 圖測試函數(shù)CTP4的ParetoFront為了進一步定量的評價兩種算法的逼近性與均勻性，表，，，給出了兩種算法對上述四個測試函數(shù)的SP，GD的統(tǒng)計結(jié)果，從表中數(shù)據(jù)容易看出，在解集的逼近性和均勻性方面本文算法對四個測試函數(shù)的標(biāo)準(zhǔn)方差都明顯小于經(jīng)典的NSGA-II算法，這說表測試函數(shù)CTP1評價準(zhǔn)則的統(tǒng)計結(jié)果bestworstavgmedian.SPNSGAII0.5749Proposed0.5705GDNSGAII0.0017Proposed表測試函數(shù)CTP2評價準(zhǔn)則的統(tǒng)計結(jié)果bestworstavgmedian.SPNSGAII0.3924ProposedGDNSGAIIProposed表測試函數(shù)CTP3評價準(zhǔn)則的統(tǒng)計結(jié)果一bestworstavgmedian.SPNSGAIIProposedGDNSGAIIProposed表測試函數(shù)CTP4評價準(zhǔn)則的統(tǒng)計結(jié)果bestworstavgmedian.SPNSGAIIProposedGDNSGAIIProposed明本文的算法性能更穩(wěn)定.另一方面，上述定量的度量結(jié)果也表明在搜索過程中適當(dāng)?shù)倪\用性能較優(yōu)的不可行解的信息不僅有助于保持群體的多樣性，而且增強了算法的搜索功能，并在一定程度上起到了維持解集的均勻性的作用.5結(jié)論本文借助粒子群算法的基本思想給出了一種改進的差分進化算法，在適當(dāng)?shù)睦貌糠謨?yōu)良不可行個體的基礎(chǔ)上，提出了用于約束多目標(biāo)優(yōu)化問題的雙群體差分進化算法.該算法中的兩個群體分別用于記錄進化過程中的可行解及部分性能較優(yōu)的不可行解，其優(yōu)點在于可以充分利用每次迭代產(chǎn)生的子代個體的信息.此外，還對文中算法的時間復(fù)雜度與NSGA-II和SPEA進行比較.經(jīng)典測試函數(shù)的數(shù)值仿真結(jié)果表明，本文算法無論在解集的逼近性及均勻性方面都優(yōu)于NSGA-II算法，這表明文中提出的基于雙群體的差分進化算法可用于求解帶約束的多目標(biāo)優(yōu)化問題方面有一定的優(yōu)勢.正如“沒有免費的午餐定理”[19所指出的，任何一種算法不可能在所有的性能方面占盡優(yōu)勢，雖然本文算法在求解約束多目標(biāo)優(yōu)化問題方面具有一定的優(yōu)勢，但計算量要稍高于NSGA-IIO接下來我們的研究將致力于如何降低算法的時間復(fù)雜度及本文算法的實際應(yīng)用。參考文獻.MitsuoGenandRunweiCheng,Geneticalgorithms&EngineeringDesign.JohnWiley&Sons,Inc,NewYork,1997.’.FredGlover,HeuristicsforIntegerprogrammingusingsurrogateconstraints.DecisionSciences,1977，8(1):156-166;.David,Geneticinsearch,optimizationandmachinelearning.Addison-WesleyPublishingCo.,Reading,Massachusetts,1989..WangYuexuan,LiuLianchen,etc,.ConstrainedMultiobjectiveOptimizationEvolutionaryAlgorithm.JournalofTsinghuaUniv(Sci&Tech),2005,45(1),103-106.(王躍宣，劉連臣等.處理帶約束的多目標(biāo)優(yōu)化進化算法.清華大學(xué)學(xué)報(自然科學(xué)版)，2005,45(1)，103-106)..ZhangYongde,HuangShabai.OnAntColonyAlgorithmforSolvingMultiobjectiveOptimizationProblems.ControlandDecision.2004,20(2),170-174.(張勇德，黃莎白.多目標(biāo)優(yōu)化問題的蟻群算法研究.控制與決策，2005，20(2)，170-174.).GaoYugen,ChengFeng,etc,.ANewImprovedGeneticAlgorithmsBasedonConvertingInfeasibleIndividualsintoFeasibleOnesandItsPropertyAnalysis.ActaElectronicaSinica，2006，34(4)，638-641.(高玉根，程峰，王燦，王國彪.基于違約解轉(zhuǎn)化法的遺傳算法及其性能分析.電子學(xué)報，2006,34(4)，638-641)..CarlosA.CoelloCoello.TheoreticalandNumericalConstraint-HandlingTechniquesusedwithEvolutionaryAlgorithms:ASurveyoftheStateoftheArt,ComputerMethodsinAppliedMechanicsandEngineering,Vol.191,No.11--12,pp.1245--1287,January2002..FernandoJimenezandJoseL.Verdegay.Evolutionarytechniquesforconstrainedoptimizationproblems.InHans-JurgenZimmermann,editor,7thEuropeanCongressonIntelligentTechniquesandSoftComputing(EUFIT'99),Aachen,Germany,1999.VerlagMainz.ISBN3-89653-808-X..KalyanmoyDeb,AmritPratap,SameerAgarwal,andT.Meyarivan.AFastandElitistMultiobjectiveGeneticAlgorithm:NSGA--II,IEEETransactionsonEvolutionaryComputation,2002,6(2),182--197..EckartZitzlerandLotharThiele.Multiobjectiveevolutionaryalgorithms:Acomparativecasestudyandthestrengthparetoapproach.IEEETrans.OnEvolutionaryComputation,1999,3(4),257-271..Storn，R.andK.Price(1995).Differentialevolution:asimpleandefficientadaptiveschemeforglobaloptimizationovercontinuousspaces.TechnicalReportTR-95-012,InternationalComputerScienceInstitute,Berkeley..Yung-ChienLin,Kao-ShingHwang,andFeng-ShengWang.HybridDifferentialEvolutionwithMultiplierUpdatingMethodforNonlinearConstrainedOptimizationProblems.CEC'2002,volume1,pages872-877,Piscataway,NewJersey,May2002..Abbass,H.,Sarker,R.andNewton,C.PDE:APareto-frontierDifferentialEvolutionApproachforMulti-objectiveOptimizationProblems.ProceedingsoftheCongressonEC2001(CEC’2001),,IEEEServiceCenter,Piscataway,NewJersey,971-978..LiBing-yu,XiaoYun-shi,WuQi-di.Hybridalgorithmbasedonparticleswarmoptimizationforsolvingconstrainedoptimizationproblems.ControlandDecision,2004,19(7),804-807.(李炳宇，蕭蘊詩，吳啟迪.一種基于粒子群算法求解約束優(yōu)化問題的混合算法，控制與決策，2004,19⑺,804-807)..Veldhuizenand.lamont.MultiobjectiveEvolutionaryAlgorithmResearch:Ahistoryandanalysis.Dept.SchoolofEng.,AirForce.,Wright-PattersonAFB,Schott.Faulttolerantdesignusingsingleandmulticriteriageneticalgorithmoptimization.Master'sthesis,DepartmentofAeronauticsandAstronautics,MassachusettsInstituteofTechnology,1995..andMichalewicz.Evolutionaryalgorithms,homomorphousMapping,andconstrainedparameteroptimization.EvolutionaryComputation,1996,7(1):19-44..KalyanmoyDeb,AmritPratap,andT.Meyarivan.ConstrainedTestProblemsforMulti-objectiveEvolutionaryOptimization.In:Proceedingsofthe1stInternationalConferenceonEvolutionaryMulti-CriterionOptimization,Zurich,Switzerland,2001,Springer-Verlag,284-298.Wolpert.,Macready..Nofreelunchtheoremsforsearch.SantaFe,NM:SantaFeInstitute.TechnicalReport:SFI-TR-05-010,1995.ADifferentialEvolutionBasedondoublePopulationsforConstrainedMulti-objectiveOptimizationProblemMENGHong-yun1,ZHANGXiao-hua2,LIUSan-yang1(1.Dept.ofAppliedMath.,XidianUniversity,Xi'an710071,China；2.InstituteofIntelligentInformationProcessing,XidianUniversity,Xi'an,710071)Abstract:Animproveddifferentialevolutionapproachisgivenfirst,andanewalgorithmbasedondoublePopulationsforConstrainedMulti-objectiveOptimizationProblem(CMOP)ispresented.Intheproposedalgorithm,twopopulationsareadopted,oneisforthefeasiblesolutionsfoundduringtheevolution,andtheotherisforinfeasiblesolutionswithbetterperformancewhichareallowedtoparticipateintheevolutionwiththeadvantageofavoidingdifficultiessuchasconstructingpenaltyfunctionanddeletinginfeasiblesolutionsdirectly.Inaddition,thetimecomplexityoftheproposedalgorithm,NSGA-HandSPEAarecompared,whichshowthebestisNSGA-II,followedbySPEAandouralgorithmsimultaneously.TheexperimentsonbenchmarksindicatethatouralgorithmissuperiortoNSGA-IIinthemeasureofGDandSP.Keywords:DifferentialEvolution;ConstrainedOptimizationProblem;multi-objectiveoptimizationproblem;BackgroundConstrainedoptimization,bothfornonlinearprogrammingandmulti-objectiveoptimization,isaveryimportantproblemandhasavarietyofapplicationsinengineering,management,mathematicsandotherfields.A