基于動態(tài)種群多策略差分進化模型的多目標進化算法

王亞輝,吳金妹,賈晨輝

(1.華北水利水電大學機械學院,河南鄭州 450011;2.河南科技大學機電工程學院,河南洛陽 471023)

?

基于動態(tài)種群多策略差分進化模型的多目標進化算法

王亞輝1,吳金妹1,賈晨輝2

(1.華北水利水電大學機械學院,河南鄭州 450011;2.河南科技大學機電工程學院,河南洛陽 471023)

針對復雜的多目標優(yōu)化問題,根據不同差分進化策略的特點,提出一種基于動態(tài)種群多策略差分進化模型和分解機制的多目標進化算法(MOEA/D-DPMD).該算法將種群劃分為3個子種群,每個子種群分配一種差分進化策略.為了提高算法的性能,依據每種差分進化策略的貢獻度,動態(tài)的調整子種群的規(guī)模,各差分進化策略之間相互配合協同進化.采用具有復雜的PS的LZ09系列基準函數,測試新算法的性能,仿真結果表明鄰域規(guī)模為25時性能最好.通過不同差分進化策略之間的對比分析,新算法也具有較強的優(yōu)勢.將其與MOEAD/DE和NSGA-II算法對比分析,結果顯示該算法的收斂性和多樣性均優(yōu)于另外兩種算法,是求解復雜多目標問題的有效方法.

分解機制;多策略差分進化;動態(tài)種群;多目標優(yōu)化

1　引言

多目標優(yōu)化問題(Multi-objective Optimization Problem,MOP)在科學研究和工程應用領域廣泛存在,是一類具有挑戰(zhàn)性的優(yōu)化問題.相對單目標問題而言,MOP目標之間相互沖突,難以得到最優(yōu)解,而是一組折中的Pareto最優(yōu)解集.傳統的多目標優(yōu)化算法將各個子目標聚合成單目標函數,其共同缺點就是一次運行只能得到一個Pareto最優(yōu)解.由于進化算法在一次運行后能夠獲得一組Pareto最優(yōu)解,因此進化算法在多目標優(yōu)化領域的研究越來越多,國際上主流算法主要以NSGA-II[1],SPEA2[2],PAES[3],MOEA/D[4],IBEA[5],HypE[6]為代表.對于上述算法,根據評價關系大體可分為三類:(1)Pareto占優(yōu)或變形的Pareto占優(yōu)評價關系的MOEA算法,如NSGA-II,SPEA2,paε-MyDE[7]等;(2)基于性能指標的MOEA算法,采用HV性能指標,該類算法時間復雜度較高,如IBEA,HypE等;(3)基于分解機制的MOEA算法,如MOEA/D等.

基于分解技術的多目標進化算法(Multi-objective Optimization Evolutionary Algorithm,MOEA)是一類新的MOEA框架[4,8,9],該算法的研究主要從四個方面進行:(1)將MOEA/D算法同其他啟發(fā)式算法相結合[10～13];(2)將新的分解機制融入到MOEA/D框架[14～16];(3)新的權重向量方法[17～20];(4)在MOEA/D中加入新重組或變異算子[9,21～23].

差分進化策略對提高算法的全局搜索能力和多樣性有較好的效果[8,24].基于上述研究基礎,本文提出一種新的基于分解和動態(tài)種群多策略差分進化模型的多目標優(yōu)化算法(Multi-objective Evolutionary Algorithm Based on Dynamic Population Multi-strategy Differential Models and Decomposition,MOEA/D-DPMD).本文工作相對于文獻[8]的工作的主要區(qū)別:(1)將種群劃分了幾個子種群,每個子種群分配一種差分進化策略,采用該種形式有兩個好處:一者不增加算法的復雜度,二者可以形成多種差分進化策略的協同進化;(2)在進化過程中,為了避免某一次差分進化策略的進化停滯,影響算法整體的整體性能,從而將依據進化策略對更新鄰域個體貢獻度的不同,動態(tài)的調整每個子種群的規(guī)模.本文分析了不同進化代數,不同鄰域大小和不同差分進化策略的對算法性能的影響.將MOEA/D-DPMD同MOEA/D和NSGA-II對比分析,實驗結果表明新算法在收斂精度和收斂速度方面都取得了較好的效果.

2　基于動態(tài)種群多策略差分進化模型的多目標進化算法

2.1分解機制

分解機制[4]是由Zhang在MOEA/D中提出一種求解多目標問題的策略,其將MOP分解為一系列的子問題,然后利用單目標進化算法來求解每個子問題.在MOEA/D中,常用的分解方法有權重向量法[25]、切比雪夫法[26]以及邊界插入法[24～27],其中以切比雪夫法應用最為廣泛,其分解機制為:

subject tox∈Ω

每個子問題對應一個權重向量,子問題的鄰居是通過計算每個權重向量與其歐式距離最小的T個權重向量來確定的.每一代種群由每個子問題的當前最優(yōu)解構成,對每個子問題的進化操作被限制在鄰居內進行.在每一代t,采用切比雪夫機制的MOEA/D保存的個體信息方式有:

(1)組成群體的N個點:x1,x2,…,xN∈Ω,其中xi為子問題i的當前最優(yōu)解;

(2)FV1,FV2,…,FVN其中FVi=F(xi),i=1,2,…,N;

(3)z=(z1,z2,…,zm)T,其中zi為目標函數fi目前為止所找到的最優(yōu)值;

2.2動態(tài)種群多策略差分進化模型

文獻[8]中表明差分進化策略有利于提高MOEA/D算法的性能;文獻[28]中多策略差分進化有利于提高算法的多樣性和分布性,文中分析了不同進化策略的優(yōu)劣.

本文選取3種差分進化模式:DE/rand/1/bin,DE/best/1/bin和DE/rand-to-best/1/bin,3種進化模式動態(tài)協同進化,其中3種進化模式的重組公式如下

(1)DE/rand/1/bin模式,其重組公式為:Vi=Xr1+F(Xr1-Xr2)

(2)DE/best/1/bin模式,其重組公式為:Vi=Xbest+F(Xr1-Xr2)

(3)DE/rand-to-best/1/bin模式,其重組公式為:

Vi=Xi+F(Xbest-Xi)+F(Xr1-Xr2)

其中DE/rand/1/bin模式中,隨機選擇一個個體Xr1為基準個體,并由Xr1與隨機差分向量經過重組產生嘗試個體Vi,其特性是全局搜索能力突出,具有較強的全局收斂性能并且不易陷入局部收斂,但是其收斂速度較慢;DE/best/1/bin模式中,基準個體是當前群體中的最優(yōu)個體Xbest,通過Xbest與隨機差分向量進行重組產生嘗試個體Vi,該模式的全局搜索能力較弱,局部尋優(yōu)能力和繼承特性較強,收斂速度快但是容易陷入局部最優(yōu);在DE/rand-to-best/1/bin模式中,其以Xi為基準個體,產生固定差分向量(Xbest-Xi)和隨機差分向量(Xr1-Xr2),然后將其線性組合得到嘗試個體Vi,其特點是能夠很好地保持全局搜索和局部尋優(yōu)之間的平衡,對各類優(yōu)化問題具有良好的適應性,但是魯棒性較差.

各差分進化模式存在著搜索性能上的差異,但具有共通之處,即產生嘗試個體的重組方式基本一致,都是通過將基準個體和差分向量進行線性組合而得到新的向量.但各種模式在結構及進化方式上的共通特性和搜索性能差異上的特點,使得共性與差異之間可以協同進化.

基于此,隨機生成大小為N種群NP,將種群NP劃分為三個子種群IA,IB和IC,使得個ξ1個體在子種群IA中,ξ2個個體在子種群中IB,ξ3個個體在子種群IC中,此時ξ1=ξ2=ξ3=N/3.將每個子種群分配一種進化模型,進行協同進化,其多策略差分進化過程為

fori=1:Ndo

ifi∈IA

DE/rand/1/bin操作產生子代個體yi

else ifi∈IB

DE/best/1/bin操作產生子代個體yi

else

DE/rand-to-best/1/bin操作產生子代個體yi

end for

如果IA,IB,IC的大小不改變,會存在一種不利算法進化的現象,即在進化過程中,若某一進化策略停滯將會導致算法的整體性能和效率的降低,因此本文采用動態(tài)子種群的方法,主要流程為:

(1)多策略差分進化,產生新的子代個體yi.

(2)更新參考點,若zj

(3)計算每種策略的進化成功率

其中,κi是指在第i個子種群中第i中策略產生的子代個體至少能在T個個體中更新一個個體的次數.

(4)重新計操作數種群的規(guī)模,其中ξ1=N×τ1,ξ2=N×τ2,ξ1=N-ξ1-ξ2,然后更新ξ1、ξ2和ξ3.

采用此種動態(tài)種群多策略差分進化策略,根據差分進化策略在進化過程的貢獻,不斷的動態(tài)的調整子種群的大小,這種進化方式提高算法的效率,保證了算法的收斂性,同時由于3種差分進化策略都參與進化,又利于算法的多樣性.為了避免,在進化過程某一種差分進化策略強占優(yōu)于其它2種策略,則給τ1,τ2,τ3定一個范圍.如果τ<τmin,取τ=τmin;如果τ>τmax,取τ=τmax,其中τmax=0.8,τmin=0.15.

基于此,基于動態(tài)種群多策略差分進化模型的多目標進化算法(MOEA/D-DPMD)流程如下:

輸入:

(1)多目標優(yōu)化問題;

(2)停止準則;

(3)N:MOEA/D-DPMD所分解的子問題個數;

(4)λ1,λ2,…,λN:分布均勻的N個權重向量;

(5)T:權重向量的鄰居規(guī)模;

(6)種群NP的大小為N;

Step1初始化

(1)設置EP=φ;

(2)計算任何兩個權重向量的歐式距離,為每個權重向量選出最近的T個向量作為它的鄰居.設B(i)={i1,i2,…,iT},i=1,2,…,N,其中λi1,λi2,…,λiT為距離λi最近的T個權重向量;

(3)初始化種群x1,x2,…,xN,設FVi=F(xi),i=1,2,…,N;

(4)隨機將種群NP={1,2,…,N}分為三個子種群IA,IB,IC,使得ξ1個個體在子種群IA中,ξ2個個體在子種群IB中,ξ3個個體在子種群IC中,初始時設定ξ1=ξ2=ξ3=[N/3].

Step2動態(tài)協同差分進化

(1)協同差分操作,如3.2節(jié)所述;

(2)更新參考點.若zj

(3)更新子問題.若gte(yi|λk,z)≤gte(xk|λk,z)則xk=yi且F(xk)=F(yi),其中k∈B(i)={i1,i2,…,iT};

(4)計操作數代種群的貢獻率,如3.2節(jié)所述;

(5)更新ξ1,ξ2,ξ3.

Step3停止判斷:若G>Gmax,則停止算法并輸出結果,否則返回到Step2.

2.3時間復雜度分析

為了評估MOEA/D-DPMD算法的計算效率,將其與MOEA/D-DE和NSGA-II進行對比分析.MOEA/D-DE在種群進化的過程中始終采用單一的DE算子,而MOEA/D-DPMD是動態(tài)的將種群分解為三個子種群然后對不同的種群采用不同的DE算子,兩者具有相同的計算框架,故其時間復雜度相同.假設三種算法的種群大小均為N、目標數均為m.在單次迭代中,當利用DE算子進化得到新解后,需要更新參考點Z*和規(guī)模為T的鄰居,因此MOEA/D-DE和MOEA/D-DPMD的時間復雜度為O(mNT).NSGA-II的時間開銷主要用于其非支配排序操作,非支配排序需要將種群中的個體進行兩兩比較才能確定支配關系,因此其時間復雜度為O(mN2).由于鄰居規(guī)模T小于種群規(guī)模N(T約等于0.1N～0.2N),因此MOEA/D-DPMD和MOEA/D-DE具有相同的時間復雜度,但是低于NSGA-II.

3　實驗仿真與分析

為了檢驗MOEA/D-DPMD算法的有效性,本文使用文獻[8]中提出的LZ09-F(1～9)系列基準函數,這9個函數具有復雜的PS,其中F6和F9為非凸PF,其它函數為凸函數,F7和F8為多峰問題,F1～F5和F7～F9為2目標函數,F6為3目標函數.

3.1性能指針

由于采用的測試函數均可得到其理論最優(yōu)值,本文選取HV[29]與IGD[30]兩個評價指針對算法性能進行綜合評價.

3.2不同的進化代數的影響

表1是MOEA/D-DPMD對9個測試函數運算結果的IGD指針的統計結果.由表1中可見,隨著計算代數的增加,IGD度量值顯著減小,特別是100代至200代之間變化明顯,但250代與300代的差距較小.經過300代計算,對于測試集LZ09具有復雜的PS和難以獲得均勻的PF.圖1為MOEA/D-DPMD算法獲得的最終解集.由1(a)所示,對于F1～F4,F7和F9問題,算法獲得的最優(yōu)解PF都很好地逼近了真實PF解集,在F5和F8問題上存在少量的間斷部分,F6問題上獲得的PF較均勻,但在端點處有少許點沒有完全收斂到端點.由1(b)可知,由于LZ09問題復雜的PS,算法的尋優(yōu)過程較困難,但是MOEA/D-DPMD算法基本上都能有效逼近真實的PS.圖1(c)和1(d)為MOEA/D-DPMD算法運行30次中獲得所有的PF和PS值,由圖可知算法獲得解集能完全覆蓋所有問題的PF和PS,且收斂性和多樣性都較好,但在F8問題上PS收斂性稍差.

表1　不同進化代數G的MOEA/D-DPMD性能分析

3.3鄰域大小對比分析

對于MOEA/D-DPMD算法中,鄰域規(guī)模T的大小會對算法的收斂速度和多樣性都有一定的影響[31].為了驗證不同鄰域大小對算法性能的具體表現,將鄰域大小分為10,15,20,25,30進行對比分析.MOEA/D-DPMD的參數設定為:當2目標問題時種群大小為300,3目標時為500;最大計算代數G為250代;3個DE策略的控制參數均取CR=1.0,F=0.5;鄰域搜索概率δ=0.9;多項式變異操作數參數η=20,Pm=1/Var,其中Var為決策變量長度.

對上述9個測試函數各獨自運行30次,使用IGD進行評價.為了更準確的了解,采用Friedman進行統計分析鄰域T的大小對算法性能的影響,其具體的表現如圖2所示.由圖2可知,在T=25時,算法的IGD值最小,因此綜合考慮采用鄰域T=25.

3.4不同的差分進化策略分析

MOEA/D-DPMD算法分別采用了三種差分進化策略協同進化,為了對比不同的差分進化模式對算法的影響,分別將不同的差分進化模式融入基于分解機制的多目標進化算法框架中,得到算法1,2,3,其中算法1為單獨將DE/rand/1/bin策略融入MOEA/D算法框架中,算法2為單獨將DE/best/1/bin策略,算法3單獨將為DE/rand-to-best/1/bin策略,算法4為MOEA/D-DPMD算法.

四種算法的參數設置為:對于2目標問題,種群規(guī)模為300,對于3目標問題,種群的規(guī)模為500,迭代次數為250.三種差分模式中,CR和F均分別設置為1.0和0.5,多項式變異操作數參數η=20,Pm=1/Var,其中Var為決策變量長度.四種算法對每個問題均連續(xù)獨立運行30次,利用盒圖來表示算法對各測試問題的實驗統計結果.從圖3來看,在F1～F9上,MOEA/D-DPMD所得到的PF均最為集中,表明在30次獨立運行中,其所得到的結果非常穩(wěn)定.并且,MOEA/D-DPMD所得到的數據的中位值均小于其它三種單獨策略的算法所得到的中位值,表明其收斂性和覆蓋性均優(yōu)于其它三種算法,尤其是在F(1,2,4,6,8,9)上優(yōu)勢更為明顯.進一步分析可知,僅僅采用一種差分策略時,算法所得到的中位值和上下四分位比較接近,說明3種算法的性能大致相當,但是采用協同進化機制的MOEA/D-DPMD的性能有了較大程度的提升.由此可說明:1)采用協同進化機制的MOEA/D-DPMD相比采用單一差分策略的算法而言,其所得的Pareto前端更加逼近真實的Pareto前端9且分布均勻,其性能有了較大程度的提升;2)協同進化的MOEA/D-DPMD的魯棒性更強,能夠更好地求解各類具有不同PS的復雜優(yōu)化問題.

3.5算法對比實驗

本節(jié)比較MOEA/D-DPMD算法與NSGA-II[1]和MOEA/D-DE[8]算法,其中3種算法的計算代數為250代,對于2目標問題種群NP大小為300,對于3目標問題時為500,其中所有DE策略的控制參數均取CR=1.0,F=0.5,多項式變異操作數參數η=20,Pm=1/Var,其中Var為決策變量長度.MOEA/D-DPMD算法和MOEA/D其它參數為:鄰域大小T=25,鄰域搜索概率δ=0.9;NSGA-II算法其它參數為:SBX[32]交叉概率Pc=0.9.對每個測試函數均獨立運行30次,然后統計指標HV、和IGD的均值和標準差,所得結果如表2～3所示.

由表2可知,MOEA/D-DPMD算法獲得了6個最優(yōu)值,MOEA/D-DE獲得了3個最優(yōu)值,NSGA-II算法未獲得最優(yōu)值.F1,F4和F6問題上,MOEA/D-DE取得較好的結果,對于F2,F3,F5和F7～F9問題上MOEA/D-DPMD性能最好,NSGA-II未取得較好的結果.其中對于F1和F4,MOEA/D-DE所獲得的HV均值同MOEA/D-DPMD所獲得均值相等,僅方差上取勝.

由表3可知,9個測試函數中MOEA/D-DPMD算法獲得了7個最優(yōu)值;MOEA/D-DE獲得2個最優(yōu)值;NSGA-II不能取得較好值.資料分析表明,在F4問題上,MOEA/D-DE性能較好,MOEA/D-DE所得結果的IGD均值是MOEA/D-DPMD所得均值的1.24倍;對于F3,F5,F7～F9問題上,MOEA/D-DPMD所得結果的IGD均值分別是MOEA/D-DE所得均值的1.19,1.29,1.18,1.12,1.41倍;對于F1,F2和F6問題,兩算法獲得結果接近.

表2　HV標準平均值及方差

表3　IGD標準平均值及方差

綜合以上分析我們可以得出結論,MOEA/D-DPMD與MOEA/D-DE、NSGA-II相比,具有較強的競爭力.

4　總結

本文在MOEA/D算法框架下,將一種動態(tài)種群多策略差分進化模型融入框架中,提出一種基于動態(tài)種群多策略差分進化模型和分解機制的多目標進化算法(MOEA/D-DPMD).該算法將種群劃分為幾個子種群,每個子種群分配一種DE策略,在進化過程中,根據不同DE策略對種群的貢獻度,動態(tài)的分配下一代DE策略作用的子種群的規(guī)模,多種DE策略相互配合,協同進化.通過實驗分析結果表明:

(1)MOEA/D-DPMD算法的鄰域T大小為25時,綜合性能最好;

(2)不同的差分進化模型對比分析,可知動態(tài)種群多策略差分進化模型較單差分進化策略的所獲得的解更逼近真實的PF且分布均勻,其性能有了較大程度的提升;

(3)同MOEA/D-DE和NSGA-II對比,MOEA/D-DPMD在收斂性和覆蓋性要優(yōu)于其它兩種算法.在進化中的IGD平均值對比,表明同樣情況下,MOEA/D-DPMD所需要的評價次數要低于其它兩種算法.下一步的研究方向為,將其進一步修正用于求解高維多目標優(yōu)化問題和含有約束問題工程實際問題中.

[1]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[2]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength Pareto evolutionary algorithm for multi-objective optimization[A].Proceedings of the Evolutionary Methods for Design,Optimization and Control[C].Athens:International Center for Numerical Methods in Engineering,2002.95-100.

[3]Knowles J D,Corne D W.Approximating the non-dominated front using the Pareto archive evolution strategy[J].Evolutionary Computation,2000,8(2):149-172.

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

[5]Zitzler E,Kunzli S.Indicator-based selection in multiobjective search[J].Proc of the Parallel Problem Solving from Nature (PPSN VIII)[C].Berlin,Heidelberg:Springer-Verlag,2004.LNCS 3242,832-842.

[6]Bader J,Zitzler E.HypE:An algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation,2011,19 (1):45-76.

[7]Hernadez-Diaz AG,Santana-Quintero LV,Coello Coello CA,Molina J.Pareto-Adaptive ε-dominance[J].Evolutionary Computation,2007,15(4):493-517.

[8]Li H,Zhang Q.Multi-objective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.

[9]周愛民,張青富,張桂戌.一種基于混合高斯模型的多目標進化算法[J].軟件學報,2014,25(5):913-928.

Zhou Ai-min,ZHANG Qing-fu,ZHANG Gui-xu.Multi-objective evolutionary algorithm based on mixture Gaussian models[J].Journal of Software,2014,25(5):913-928.(in Chinese)

[10]H Li,D Landa-Silva.An adaptive evolutionary multi-objective approach based on simulated annealing[J].Evolutionary Computation,2011,19(4):561-595.

[11]N Moubayed,A Petrovski,J McCall.A novel smart multi-objective particle swarm optimization based on decomposition[A].International Conference on Parallel Problem Solving from Nature[C].Berlin Heidelberg:Springer,2010.1-10.

[12]Z Martinez,C Coello Coello.A multi-objective particle swarm optimizer based on decomposition[A].Genetic and Evolutionary Computation Conference[C].New York:ACM,2011.69-76.

[13]王亞輝,賈晨輝,趙仁鵬.基于分解機制的多目標蝙蝠算法[J].農業(yè)機械學報,2015,46(4):316-324.

Wang Yahui,Jia Chenhui,Zhao RenPeng.Multi-objective bat algorithm based on decomposition[J].Transactions of the Chinese Society for Agricultural Machinery,2015,46(4):316-324.(in Chinese)

[14]Q Zhang,H Li,D Maringer,E Tsang.MOEA/D with NBI-style Tchebycheff approach for portfolio management[A].IEEE Congress on Evolutionary Computation[C].Barcelona:IEEE,2010.1-8.

[15]H Ishibuchi,Y Sakane,N Tsukamoto,Y Nojima.Adaptation of scalarizing functions in MOEA/D:An adaptive scalar zing function-based multi-objective evolutionary algorithm[A].International Conference on Evolutionary Multi-Criterion Optimization[C].Berlin Heidelberg:Springer,2009.438-452.

[16]H Ishibuchi,Y Sakane,N Tsukamoto,Y Nojima.Simultaneous use of different scalarizing functions in MOEA/D[A].Genetic and Evolutionary Computation Conference[C].New York:ACM,2010.519-526.

[17]Y Tan,Y Jiao,H Li,X Wang.MOEA/D + uniform design:a new version of MOEA/D for optimization problems with many objectives[J].Compute Opera Res,2013,40(6):1648-1660.

[18]X Ma,Y Qi,L Li,F Liu,et al.MOEA/D with uniform decomposition measurement for many-objective problems[J].Soft Compute,2014,18:2541-2564.

[19]F Gu,H Liu.A novel weight design in multi-objective evolutionary algorithm[A].International Conference on Computational Intelligence and Security[C].Nanning:IEEE,2010.137-141.

[20]Y Qi,X Ma,F Liu,L Jiao,et al.MOEA/D with adaptive weight adjustment[J].Evolutionary Computation,2014,22(2):231-264.

[21]C Chen,Q Zhang.Enhancing MOEA/D with guided mutation and priority update for multi-objective optimization[A].IEEE Congress on Evolutionary Computation[C].Trondheim:IEEE,2009.209-216.

[22]W Huang,H Li.On the differential evolution schemes in MOEA/D[A].International Conference on Natural Computation[C].Yantai:IEEE,2010.2788-2792.

[23]H Li,D Landa-Silva.An adaptive evolutionary multi-objective approach based on simulated annealing[J].Evolutionary Computation,2011,19 (4):561-595.

[24]畢曉君,肖婧.基于自適應差分進化的多目標進化算法[J].計算機集成制造系統,2011,17(12):2660-2665.

Bi Xiao-jun,Xiao Jing.Multi-objective evolutionary algorithm based on self-adaptive differential evolution[J].Computer Integrated Manufacturing Systems,2011,17(12):2660-2665.(in Chinese)

[25]Miettinen K.Nonlinear Multi-objective Optimization.Norwell[M].MA:Kluwer,1999.

[26]Das I,J E Dennis.Normal-boundary intersection:A new method for generating Pareto optimal points in multi-criteria optimization problems[J].SIAM J Optim,1998,8(3):631-657.

[27]Messac A,Ismail-Yahaya,C Mattson.The normalized constraint method for generating the Pareto frontier[J].Struct Multidisc Optim,2003,25:86-98.

[28]詹騰,張屹,朱大林,劉錚,等.基于多策略差分進化的元胞多目標遺傳算法[J].計算機集成制造系統,2014,20(6):1342-1351.

Zhan Teng,Zhang Yi,Zhu Da-lin,Liu Zheng,et al.A cellular genetic algorithm based on multi-strategy differential evolution for multi-objective optimization[J].Computer Integrated Manufacturing Systems,2014,20(6):1342-1351.(in Chinese)

[29]Zitzler E,Thiele L.Multi-objective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

[30]Bosman T,Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.

[31]Ishibuchi H,Akedo N,Nojima Y.Relation between neighborhood size and MOEA/D performance on many-objective problems[A].Evolutionary Multi-Criterion Optimization[C].Berlin Heidelberg:Springer,2013.459-474.

[32]DEB K,AGRAWAL R B.Simulated binary crossover for continuous search space[J].Complex Systems,1995,9(2):115-148.

王亞輝女,1970年出生,河南濮陽人,副教授、碩士生導師,主要從事先進制造技術和現代設計方法研究工作.

E-mail:wangyahui@ ncwu.edu.cn

吳金妹女,1976年生,海南屯昌人,講師,主要從事機械設計制造及設備方面的研究工作.

E-mail:wujinmei@ ncwu.edu.cn

賈晨輝男,1970年11月出生,博士、副教授、碩士研究生導師.主要研究方向為:計算機集成制造技術、系統工程、虛擬樣機設計技術、機器人技術的研究工作.

Multi-objective Evolutionary Algorithm Based on Dynamic Population Multi-strategy Differential Models

WANG Ya-hui1,WU Jin-mei1,JIA Chen-hui2

(1.SchoolofMechanicalEngineering,NorthChinaUniversityofWaterResourcesandElectricPower,Zhengzhou,Henan450011,China;2.SchoolofMechatronicsEngineering,HenanUniversityofScienceandTechnology,Luoyang,Henan471023,China)

According to the characteristics of differential evolution,a multi-objective evolutionary algorithm based on dynamic population multi-strategy differential models and decomposition (MOEA/D-DPMD) is proposed to solve the expensive problems.The algorithm divides the population into three sub-populations and each sub-population is corresponding to a differential evolution strategy.In order to improve the performance of the algorithm,the size of sub-population is adjusted dynamically on the basis of a differential evolution strategy contribution.Each strategy is adopted to participate in coordination during the evolution process.Through the test simulation on the LZ09 benchmarks with complicated Pareto Set (PS),MOEA/D-DPMD shows a best performance with a neighborhood size of 25.Via the comparative analysis of different schemes of differential strategy,MOEA/D-DPMD also performs well.The experimental results indicate that MOEA/D-DPMD has a better performance in terms of convergence and diversity compared with MOEA/D and NSGA-II,which is an effective way for solving complex multi-objective optimization problems.

decomposition mechanism;multi-strategy differential evolution;dynamic population;multi-objective optimization

2015-05-11;修回日期:2015-09-20;責任編輯：李勇鋒

國家自然科學基金(No.51475142)

TP18

A

0372-2112 (2016)06-1472-09