基于正交設(shè)計模型的多目標(biāo)進化算法

吳金妹 王亞輝 賈晨輝

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

基于正交設(shè)計模型的多目標(biāo)進化算法

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

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

為提高多目標(biāo)進化算法在求解復(fù)雜多目標(biāo)問題上的收斂性和解集多樣性，提出了一種基于正交設(shè)計模型的多目標(biāo)進化算法。該算法在基于分解技術(shù)的多目標(biāo)進化算法框架下，將正交實驗設(shè)計方法同分解技術(shù)相融合。利用正交實驗設(shè)計方法，有針對性地對父代個體進行重組，并生成多個保留優(yōu)良基因的子代個體，避免了盲目性搜索以提高算法收斂性，并應(yīng)用分解技術(shù)選擇優(yōu)秀個體來維持全局搜索和局部尋優(yōu)的動態(tài)平衡。將該算法與目前典型的優(yōu)異算法在18個標(biāo)準(zhǔn)測試函數(shù)集上進行對比測試，仿真結(jié)果表明所提算法相比另外4種算法具有良好的競爭力，在保持良好收斂性的同時，所獲得的Pareto前端分布更加均勻，尤其在求解具有復(fù)雜Pareto解集的問題時，能保持較好的搜索性能。為了測試算法在求解含有約束問題的性能，將其應(yīng)用于I型主梁多目標(biāo)優(yōu)化設(shè)計中，獲得的Pareto前沿較均勻，且解集域較寬廣，對比分析表明了算法的工程實用性。

多目標(biāo)進化算法； MOEA/D； 正交設(shè)計模型； I型主梁設(shè)計

引言

多目標(biāo)優(yōu)化問題(Multi-objective optimization problem, MOP)是一類廣泛存在于科學(xué)研究與工程實踐中的復(fù)雜優(yōu)化問題，其存在至少兩個以上的優(yōu)化目標(biāo)，且多個目標(biāo)之間相互沖突，決策過程中不存在滿足所有優(yōu)化目標(biāo)的單一最優(yōu)解，而是一組折衷的Pareto解集。進化算法是一類通過模擬自然界的進化過程來求解復(fù)雜優(yōu)化問題的有效算法，由于其對所求問題的性質(zhì)不敏感且采用基于群體方式的多點搜索策略，因此非常適合于求解多目標(biāo)問題。

自1985年Schaffer提出第一個多目標(biāo)進化算法[1]起，在30多年的多目標(biāo)優(yōu)化研究過程中，主要致力于2個方面的探索：①收斂性研究，即算法獲得的PF(Pareto front)和PS(Pareto set)盡可能的逼近真實PF和PS解集。②多樣性研究，即算法求解的PF和PS盡可能的均勻分布。對于上述2方面問題，一般采用不同評價機制可以滿足，而評價機制主要區(qū)分為3大類[2-3]：①基于支配關(guān)系評價機制[4-8]，主要有NSGA-II[4]、SPEA2[6]、NPGA[7]、PESA[8]等。②基于指標(biāo)評價機制[9-12]，其中典型的性能指標(biāo)函數(shù)為超體積HV(Hypervolume)[9]，主要算法有IBEA[10]、SMSEMOA[11]和HyPE[12]等。③基于分解技術(shù)的評價機制[13-20]，此類方法的代表算法有C-MOGA[13]、MOEA/D[14]和MOEA/D框架下的優(yōu)化算法[15-20]等。

MOEA/D算法是一類新型的進化算法框架，其主要思想為將一個多目標(biāo)問題分解為若干個子問題進行求解，同時利用鄰域策略來建立子問題之間的聯(lián)系，從而獲得對Pareto解集的逼近。

正交實驗設(shè)計(Orthogonal experimental designing, DOE)[21]是一種解決多因素、多水平的實驗設(shè)計方法，能以較少的實驗次數(shù)找到最好或較好的實驗條件。文獻[22-24]將DOE引入進化算法中，結(jié)果均表明了DOE對算法性能有一定的提升。基于此，本文在MOEA/D算法框架下，將一種正交設(shè)計模型(Orthogonal designing model)引入算法中，提出一種基于正交設(shè)計和分解技術(shù)的多目標(biāo)進化算法(MOEA/D-OD)。最后，采用18個復(fù)雜基準(zhǔn)測試函數(shù)，同其他4種具有代表性算法進行對比仿真測試。

1 多目標(biāo)優(yōu)化概況

一個具有n個決策變量，m個目標(biāo)函數(shù)的MOP的基本形式為

(1)

其中，Ω為可行域空間，fi(x)→R(i=1,2,…,m)為第i個目標(biāo)函數(shù)。由于多個目標(biāo)之間相互沖突，因此一般情況下，MOP的最優(yōu)解不是一個解而是一個Pareto最優(yōu)解集的集合。

定義1(Pareto支配)：假設(shè)xp、xq∈Ω，若滿足式(2)，則稱xp支配xq(記為xp?xq)。

(2)

定義2(Pareto最優(yōu)解)：一個解x*∈Xf被稱為Pareto最優(yōu)解，當(dāng)且僅當(dāng)滿足如下條件

?x∈Xf:x?x*

(3)即在可行解集當(dāng)中，若不存在任何一個可行解x相對于x*是Pareto占優(yōu)的，則稱x*為Pareto最優(yōu)解。

定義3(Pareto最優(yōu)解集)：對于MOP，其Pareto最優(yōu)解集(Pareto set, PS)是所有Pareto最優(yōu)解的集合

PS={x*|?x∈Xf:x?x*}

(4)

定義4(Pareto前端)：Pareto最優(yōu)解集PS在目標(biāo)空間的投影集合稱為Pareto前端(Pareto front, PF)，即

PF={F(x)|x∈PS}

(5)

2 正交設(shè)計模型的多目標(biāo)進化算法

2.1MOEA/D算法框架

MOEA/D[14]算法將MOP分解為一組單目標(biāo)優(yōu)化問題，每個單目標(biāo)問題稱為子問題；各子問題之間相互協(xié)作同時優(yōu)化這組子問題，從而獲得對Pareto最優(yōu)解集的逼近。

(1)分解技術(shù)

(6)

(2)鄰居子問題

由于每個子問題對應(yīng)一個權(quán)重向量，子問題的鄰居是根據(jù)每個權(quán)重向量與其歐式距離最小的T個權(quán)重向量的編號對應(yīng)的個體來確定的。MOEA/D算法框架的重組算子的父代個體選擇源于領(lǐng)域子，并且新個體會替換鄰域中個體，從而使新個體盡可能地參與進化。

2.2 正交設(shè)計模型

(1)正交實驗設(shè)計

采用LEUNG等[22]提出的LM(QK)構(gòu)造方法，具體方法見表1。LM(QK)正交表表示該實驗系統(tǒng)具有K個因素，每個因素具有Q個水平，M是構(gòu)造的組合數(shù)量。

(2)正交設(shè)計交叉算子

父代個體之間的重組以交換個體之間的優(yōu)秀基因，同時引入更多的啟發(fā)式信息對解空間進行有效的搜索，能夠增強子代個體在解空間的采樣范圍，維持進化過程中種群的多樣性，避免算法陷入局部收斂。遺傳操作算子就是通過父代個體的組合生成潛在的優(yōu)秀解，該過程可以被視為是實驗組合。因此，正交設(shè)計來重新組合父代個體進而生成優(yōu)秀的子代個體是合理的。本文采用正交實驗設(shè)計在子代個體的樣本空間內(nèi)組合出具有代表性的子代個體，以提高搜索效率。

考慮任意2個具有實數(shù)編碼的父代個體e=(e1,e2,…,eD)和g=(g1,g2,…,gD)，正交設(shè)計交叉的首要步驟是對這2個個體進行離散化得到Q個水平，具體方式為

(7)

由于維數(shù)D通常大于因素K，如果直接應(yīng)用正交表，則構(gòu)造出的正交表會比較龐大，同時對于不同的維數(shù)D，需要重新構(gòu)造正交表。因此考慮將決策向量個體隨機分成K個子向量

(8)

其中，t1,t2,…,tK-1是隨機生成的正整數(shù)且滿足1

在得到K個子向量后，將每個子向量Hi視為一個因素，同時定義其Q個水平為

(9)

在D維的實數(shù)空間內(nèi)，將每個子向量看作是正交實驗設(shè)計中的一個因素，即K個因素，同時結(jié)合父代個體離散化得到Q個水平，這樣就將對父代個體的重組操作轉(zhuǎn)換為K個因素、Q個水平的正交實驗問題。此時，就可以應(yīng)用正交表LM(QK)來對其每個因素Hi以及因素對應(yīng)的Q個水平組合生成M子代個體，其具體操作見以下算法。

(1)將參與重組的父代個體進行離散化，將決策向量隨機分成K個子向量H1,H2,…,HK，定義因素Hi的Q個水平為L(Hi)={Li1,Li2,…,LiQ}，具體操作方法如下：隨機生成t1,t2,…tK-1的正整數(shù)且滿足1

(2)構(gòu)造正交表LM(QK)，根據(jù)正交表LM(QK)安排實驗，產(chǎn)生M個子代個體。

在得到子代個體中，需要利用選擇算子從子代個體中選擇優(yōu)秀的個體參與到下一代的進化，多目標(biāo)中常用基于Pareto方法或者輔以擁擠距離來評價個體的優(yōu)劣。然而，由于得到的子代群體較小，子代個體大部分都是互不支配的并且擁擠距離的區(qū)分也不太明顯，難以從子代群體中選擇到優(yōu)秀的個體。分解技術(shù)將一個多目標(biāo)問題分解為若干子問題，每一個個體對應(yīng)著一個具體的適應(yīng)度，該適應(yīng)度表征了該個體與其最優(yōu)參考點的接近程度，該值越小則該個體與最優(yōu)參考個體越接近，因此該個體就越優(yōu)秀。根據(jù)式(6)計算每個子代個體的適應(yīng)度，選擇出gte(x|λi,z*)值最小的子代個體作為最終的子代個體參與到種群的后續(xù)進化中。

為了能夠方便地說明問題，此處給出一個簡單的實例。首先將其隨機分割為Q個水平，設(shè)隨機生成的t1=2,t2=4,t3=5，則其K個因素為

(10)

其次，按照式(10)得到其每個因素的水平為

在得到4個因素以及每個因素對應(yīng)的3個水平后，就可以根據(jù)L9(34)正交表來進行組合實驗，得到的9個組合實驗如表1所示，每一行代表一次實驗組合。其中單元格中括號前的數(shù)字表示對應(yīng)實驗組合中該因素下的第幾個水平，如第一行第一列的1(L11)表示第一次實驗組合中因素L(H1)的第一個水平(L11)，其他依次類推。

表1 L9(34)正交表生產(chǎn)個體Tab.1 L9(34) orthogonal table production offspring

2.3 算法流程

MOEA/D-OD算法輸入為：①多目標(biāo)優(yōu)化問題。②停止準(zhǔn)則。③N：MOEA/D-OD所分解的子問題個數(shù)。④λ1,λ2,…,λN：分布均勻的N個權(quán)重向量。⑤T：權(quán)重向量的鄰居規(guī)模。⑥N：種群NP的大小。

(1)初始化

①設(shè)置EP=?。

②計算任何2個權(quán)重向量的歐氏距離，為每個權(quán)重向量選出最近的T個向量作為它的鄰居。設(shè)B(i)={i1,i2,…,iT}(i=1,2,…,N)，其中λi1,λi2,…,λiT為距離λi最近的T個權(quán)重向量。

③初始化種群x1,x2,…,xN，設(shè)FVi=F(xi)(i=1,2,…,N)。

④采用基于問題的特點方法初始化z=(z1,z2,…,zm)T。

⑤迭代計時器gen=0。

(2)主循環(huán)

(a)從鄰域中隨機選擇3個個體Xr1,gen、Xr2,gen、Xr3,gen，生產(chǎn)新的個體Vi,gen

其中，i=1,2,…,N;j∈{1,2,…,D}。

(b)進行多項式變異操作，產(chǎn)生子代個體y。

(c)利用新解y更新鄰域內(nèi)的子問題。

②否則，從鄰域中隨機選擇兩個個體并利用正交交叉算子生成子代個體y，其中正交表采用L9(34)。更新鄰域內(nèi)的子問題，替換鄰居中最差解。

(3)停止判斷

判斷gen>MaxGen。如果是，則停止算法并輸出結(jié)果；否則返回步驟(2)。

3 實驗仿真及分析

為測試MOEA/D-OD算法性能，本文選取WFG系列和F9系列共18個測試函數(shù)進行實驗，并同MOEA/D-DE[20]、NSGA-II[4]、SMPSO[25]、AbYSS[26]算法對比分析。

3.1 測試函數(shù)和性能評價指標(biāo)

為了檢驗MOEA/D-OD算法的有效性，本文使用WFG系列[27]和LZ09_F(1-9)[28]系列基準(zhǔn)函數(shù)，共18個測試函數(shù)。其中WFG系列函數(shù)的PF具有混合凸和凹、連續(xù)和非連續(xù)、線性、欺騙性、多模態(tài)等特性，本文WFG問題采用2目標(biāo)函數(shù)，其具體函數(shù)表達式見文獻[28]。LZ09_F(1-9)系列基準(zhǔn)函數(shù)是由ZHANG等[28]于2009年提出，這9個函數(shù)具有復(fù)雜的PS，其中F6和F9為非凸PF，其他函數(shù)為凸函數(shù)，F(xiàn)7和F8為多峰問題，F(xiàn)1～F5和F7～F9為2目標(biāo)函數(shù)，F(xiàn)6為3目標(biāo)函數(shù)。

由于沒有單一的評價指標(biāo)能夠全面地評估一種MOEA算法的性能，按照經(jīng)驗本文選用HV[9]和IGD[14]兩種被廣泛使用的性能指標(biāo)。HV和IGD均為一個綜合型指標(biāo)，兩者均能評價算法的收斂性和多樣性。對于HV指標(biāo)，其數(shù)值越大，表明算法獲得非支配解集越接近真實的PF，而IGD指標(biāo)，則是數(shù)值越小，算法性能越優(yōu)異。

3.2 算法對比實驗

在此，將MOEA/D-OD同MOEA/D-DE、NSGA-II、SMPSO、AbSYY在測試函數(shù)上進行仿真分析，其中5種算法的每次運行最大次數(shù)為250次，當(dāng)2目標(biāo)時，種群大小為300，當(dāng)3目標(biāo)時，種群大小為500。對于MOEA/D-OD算法的參數(shù)如下：pcmin=0.2,pcmax=0.8,CR=1，F(xiàn)=0.5，變異概率為1/η，η為個體的決策變量長度，鄰域大小T=20,鄰域搜索概率δ=0.9，子問題更新數(shù)目nr為2或3。其他4種算法的參數(shù)，參照文獻中設(shè)置的參數(shù)進行設(shè)置。本文算法均采用JAVA進行編寫，對比算法源于Jmetal框架，其算法原代碼來源于http:∥jmetal.sourceforge.net。將5種算法同時運行30次，結(jié)果如表2、3所示。

表2 HV性能指標(biāo)的均值和標(biāo)準(zhǔn)差Tab.2 HV mean and standard deviation

注：*最優(yōu)解，下同。

表3 IGD性能指標(biāo)的均值和標(biāo)準(zhǔn)差Tab.3 IGD mean and standard deviation

從表2可知，MOEA/D-OD算法占優(yōu)的問題個數(shù)為11個，MOEA/D-DE、NSGA-II和AbYSS算法獲得2個，SMPSO算法僅獲得1個。對于WFG系列問題，MOEA/D-OD和MOEA/D-DE求解獲得數(shù)值都較接近，處于一個數(shù)量級，但是MOEA/D-OD整體上優(yōu)于MOEA/D-OD，由此表明MOEA/D-OD性能較MOEA/D-DE更穩(wěn)定，收斂性也更好。在WFG1問題上，MOEA/D-OD算法較NSGA-II、SMPSO和AbSYY更優(yōu)；對于WFG(2,3,5,7,9)問題，5種算法性能相當(dāng)；對于WFG4問題，AbSYY算法最優(yōu)，SMPSO算法相對最差；對于WFG6問題，MOEA/D-OD算法遠優(yōu)于AbSYY算法；對于WFG8問題，NSGA-II算法性能最優(yōu)，MOEA/D-OD性能排名2。對于LZ09系列函數(shù)，MOEA/D-OD算法較其他4種算法而言占有絕對優(yōu)勢，其中除了F7問題，性能稍差于MOEA/D-DE算法。

由表3可知，MOEA/D-OD算法占優(yōu)的問題為9/18，MOEA/D-DE和AbYSS算法為3/18，SMPSO算法獲得了2/18，NSGA-II僅獲得1個最優(yōu)值。在WFG1問題上，MOEA/D-OD算法較另外4種更優(yōu)；對于WFG2問題，SMPSO算法性能最優(yōu)，MOEA/D-OD、MOEA/D-DE和NSGA-II性能相當(dāng)，AbSYY性能最差，相差一個數(shù)量級；對于WFG(3,5,7,9)問題，5種算法性能差距較??；對于WFG4問題，AbSYY算法最優(yōu)；對于WFG6問題，MOEA/D-OD、MOEA/D-DE和SMPSO算法性能在一個數(shù)量級，其中SMPSO稍占優(yōu)，AbSYY性能最差；對于WFG8問題，NSGA-II算法性能最優(yōu)，MOEA/D-OD、MOEA/D-DE和SMPSO性能相當(dāng)。對于LZ09系列函數(shù)，MOEA/D-OD算法較其他4種算法而言占有絕對優(yōu)勢，其中除了F(7,5)問題，性能稍差于MOEA/D-DE算法。對于LZ09系列函數(shù)，MOEA/D-OD算法整體上優(yōu)于MOEA/D-DE算法，表明在MOEA/D框架下采用OD模型能夠有效提高算法的整體性能。對于F(2,4,7,9)問題，MOEA/D-OD較NSGA-II、SMPSO和AbSYY數(shù)值上基本都提高了1個量級。

對MOEA/D-OD與MOEA/D-DE、NSGA-II、SMPSO和AbSYY，5種算法進行Friedman測試，測試結(jié)果如表4所示。從測試數(shù)據(jù)可以看出，MOEA/D-OD算法性能排名第1，MOEA/D-DE算法排名第2，MOEA/D-OD算法比MOEA/D-DE算法整體性能平均提高10%左右。對于HV指標(biāo)，MOEA/D-OD算法相對NSGA-II、SMPSO和AbSYY算法，統(tǒng)計數(shù)值分別是1.916倍、2.3倍和2.19倍；對于IGD指標(biāo)， MOEA/D-OD算法相對NSGA-II、SMPSO和AbSYY算法分別提高了36%、38%和51%。綜合以上分析可以得出，MOEA/D-OD算法相比另外4種算法，具有較強的競爭力。

為了評估算法的收斂速度，繪制了MOEA/D-OD、MOEA/D-DE、NSGA-II、SMPSO和AbSYY算法隨著進化代數(shù)的IGD值，如圖1所示。從收斂速度看，MOEA/D-OD算法在F2問題上相對于其他算法具有較快的收斂速度。SMPSO算法對于F(1,4,5,7)問題，在進化初期都有較快的收斂速度，也表明了SMPSO算法的鉗制粒子飛行速度的方法具有快速的全局尋優(yōu)能力，但其后期進化能力較弱。MOEA/D-OD算法在問題F(3,4,8,9)上，后期尋優(yōu)能力較強。對于F(5,7)問題，MOEA/D-DE算法后期具有很好的尋優(yōu)效果。

表4 HV和IGD上的Friedman排名Tab.4 Friedman ranking of HV and IGD

4 工程實例

鑒于MOEA/D-OD算法在求解無約束多目標(biāo)問題方面的良好性能，為了進一步驗證其在求解多目標(biāo)約束問題的能力，將其應(yīng)用于某主梁的多目標(biāo)設(shè)計問題。主梁的示意圖如圖2所示，主梁尺寸在滿足幾何和強度約束條件下，梁的截面積和靜載彎曲力最小，其中已知E=2×104kN/cm2，σα=16 kN/cm2，P=600 kN，Q=50 kN，L=200 cm。

圖1 F(1-9)系列進化過程中IGD值Fig.1 Evolution of mean IGD metric values versus generations

圖2 I型梁設(shè)計示意圖Fig.2 Schematic diagram of I-beam design

由于問題存在約束，本文采用DEB[29]提出的多目標(biāo)法處理違反約束的個體。MOEA/D-OD算法的基本參數(shù)為：最大進化代數(shù)為300次，種群大小為500，pcmin=0.2,pcmax=0.8,CR=1，F(xiàn)=0.5，變異概率為1/η，η為個體的決策變量長度，鄰域大小T=20,鄰域搜索概率δ=0.9，子問題更新數(shù)目nr=3。根據(jù)文獻[30]，可得到數(shù)學(xué)模型為

約束條件

其中

10≤x1≤80 10≤x2≤50

0.9≤x3≤5 0.9≤x4≤5

圖3 Pareto 前沿圖Fig.3 Diagram of Pareto front

圖3為MOEA/D-OD算法求解I型梁多目標(biāo)優(yōu)化設(shè)計問題獲得的Pareto前沿，由圖可知獲得PF較均勻，解集域較廣。為了對比算法的性能，將MOEA/D-OD算法與文獻[30]中的結(jié)果進行對比，其中本文算法獲得極端解為(126.704 7,0.061 523)和(850.000,0.005 903)，文獻[30]中，NSGA-II獲得的極端解為(135.555,0.039 74)和(850.000,0.005 903)，MOPSO-CD獲得的極端解為(128.170 8,0.049 401)和(850.000,0.005 903)，RM-MEDA獲得的極端解為(127.391,0.054 075)和(850.000,0.005 903)，MOTLBO獲得的極端解為(126.705 1,0.052 304)和(850.000,0.005 903)。由對比可知，本文算法求得的解集更寬廣，與文獻[30]中提出的MOTLBO算法性能相當(dāng)。

5 結(jié)束語

提出了一種正交設(shè)計模型，并采用差分進化策略與其協(xié)同進化?；诖耍岢隽嘶谡辉O(shè)計模型MOEA/D算法的MOEA/D-OD算法。將MOEA/D-OD算法與MOEA/D-DE、NSGA-II、SMPSO、AbSYY算法在18個基本測試數(shù)上進行仿真對比實驗，分析結(jié)果表明：正交實驗?zāi)Ｐ湍軌蛴行У卣业椒N群的結(jié)構(gòu)信息，算法獲得Pareto解集更逼近真實的PF，尤其是在求解具有復(fù)雜PS的LZ09系列函數(shù)。相對于僅采用DE算子，MOEA/D-OD算法較MOEA/D-DE算法整體性能更優(yōu)，魯棒性更強。將MOEA/D-OD算法應(yīng)用于某主梁多目標(biāo)設(shè)計問題求解時，算法能獲得較均勻的PF，對比驗證表明了工程實用性。

1 SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms[C]∥Proceedings of the 1st International Conference on Genetic Algorithms, Mahwah, NJ: Lawrence Erlbaum Associates Inc., 1985: 93-100.

2 LI K, SAM Kwong, ZHANG Q F, DEB K. Interrelationship-based selection for decomposition multi-objective optimization [J]. IEEE Transactions on Cybernetics,2015,45(10):2076-2088.

3 周愛民,張青富,張桂戌.一種基于混合高斯模型的多目標(biāo)進化算法[J].軟件學(xué)報,2014,25(5):913-928. ZHOU A M, ZHANG Q F, ZHANG G X. Multi-objective evolutionary algorithm based on mixture Gaussian models [J]. Journal of Software,2014, 25(5):913-928.(in Chinese)

4 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.

5 楊咚咚,馬晶晶,焦李成,等.一種改進ε支配的等度規(guī)映射方法[J].軟件學(xué)報,2011,22(10):2291-2304. YANG D D, MA J J, JIAO L C, et al. Improvedεdominance by isomap [J]. Journal of Software, 2011, 22(10):2291-2304.(in Chinese)

6 ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength Pareto evolutionary algorithm[C]∥Evolutionary Methods for Design, Optimization and Control with Application to Industrial Problems (EUROGEN 2001), International Centre for Numerical Methods in Engineering (CIMNE), Athens, 2002: 95-100.

7 HORN J, NAFPLIOTIS N, GOLDBERG D E. A niched Pareto genetic algorithm for multi-objective optimization[C]∥Proceedings of the 1st IEEE Conference on Evolutionary Computation, 1994: 82-87.

8 CORNE D W, KNOWLES J D, OATES M J. The Pareto envelope-based selection algorithm for multi-objective optimization[C]∥Proceedings of the 6th Work-shop on Parallel Problem Solving from Nature (PPSN VI), Springer, Berlin, Heidelberg, 2000:839-848.

9 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.

10 ZITZLER E, KüNZLI S. Indicator-based selection in multi-objective search [C]∥Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), Springer, Berlin, Heidelberg, 2004: 832-842.

11 BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: multi-objective selection based on dominated hypervolume [J]. European Journal of Operational Research, 2007, 181(3):1653-1669.

12 BADER J, ZITZLER E. HypE: an algorithm for fast hypervolume-based many-objective optimization [J]. Evolutionary Computation, 2011, 19(1): 45-76.

13 MURATA T, ISHIBUCHI H, GEN M. Specification of genetic search directions in cellular multi-objective genetic algorithms[C]∥Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Springer, Berlin, Heidelberg, 2001: 82-95.

14 ZHANG Q F, LI H. MOEA/D: a multi-objective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.

15 LI H, LANDA S D. An adaptive evolutionary multi-objective approach based on simulated annealing [J]. Evolutionary Computation, 2011, 19(4): 561-595.

16 王亞輝,賈晨輝,趙仁鵬.基于分解機制的多目標(biāo)蝙蝠算法及應(yīng)用[J/OL].農(nóng)業(yè)機械學(xué)報,2015,46(4):316-324. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx. DOI: 10.6041/j.issn.1000-1298.2015.04.047. WANG Y H, JIA C H, ZHAO R P. Multi-objective bat algorithm based on decomposition and its application[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(4):316-324.(in Chinese)

17 ZHANG Q, LI H, DARINGER M, et al. MOEA/D with NBI-style tchebycheff approach for portfolio management [C]∥IEEE Congress on Evolutionary Computation, 2010:1-8.

18 MA X, QI Y, LI L, et al. MOEA/D with uniform decomposition measurement for many-objective problems [J]. Soft Compute, 2014, 18:2541-2564.

19 QI Y, MA X, LIU F, et al. MOEA/D with adaptive weight adjustment [J]. Evolutionary Computation, 2014, 22(2):231-264.

20 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.

21 趙選民. 實驗設(shè)計方法[M]. 北京: 科學(xué)出版社,2006.

22 LEUNG Y W, WANG Y. An orthogonal genetic algorithm with quantization for global numerical optimization [J].IEEE Transactions on Evolutionary Computation, 2001, 5(1): 41-53.

23 蔡自興,江中央,王勇,等.一種新的基于正交實驗設(shè)計的約束優(yōu)化進化算法[J].軟件學(xué)報,2010,33(5):855-864. CAI Z X, JIANG Z Y, WANG Y, et al. A novel constrained optimization evolutionary algorithm based on orthogonal experimental design [J]. Journal of Software, 2010,33(5):855-864.(in Chinese)

24 公茂果,焦李成,楊咚咚,等.進化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報,2009,20(2):271-289. GONG M G, JIAO L C, YANG D D, et al. Research on evolutionary multi-objective optimization algorithms [J]. Journal of Software, 2009, 20(2):271-289.(in Chinese)

25 NEBRO A J, DURILLO J J, GARCA J, et al. SMPSO: a new PSO-based metaheuristic for multiobjective optimization[C]∥IEEE Symposium on Computational Intelligence in Multi-criteria Decision-making,2009:66-73.

26 NEBRO A J, LUNA F, ABLE E, et al. AbYSS: adapting scatter search to multi-objective optimization [J]. IEEE Transactions on Evolutionary Computation, 2008,12(4):439-457.

27 HUBAND S, BARONE L, WHILE L, et al. A scalable multi-objective test problem toolkit [C]∥Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), Springer, Berlin, Heidelberg, 2005: 280-295.

28 ZHANG Q, LIU W，LI H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances[C]∥IEEE Congress on Evolutionary Computation, 2009:203-208.

29 DEB K. An efficient constraint handling method for genetic algorithms [J]. Computation Methods in Applied Mechanics and Engineering, 2000, 86(2-4):311-338.

30 ZOU F, WANG L, HEI X, et al. Multi-objective optimization using teaching-learning-based optimization algorithm[J]. Engineering Applications of Artificial Intelligence, 2013, 26(4): 1291-1300.

Multi-objective Evolutionary Algorithm Based on Orthogonal Designing Model

WU Jinmei1WANG Yahui1JIA Chenhui2

(1.CollegeofMechanicalEngineering,NorthChinaUniversityofWaterResourcesandElectric,Zhengzhou450011,China2.CollegeofMechanicalEngineering,HenanUniversityofScienceandTechnology,Luoyang471023,China)

Aiming to improve the convergence and diversity of multi-objective evolutionary algorithms (MOEAs) for solving complicated high dimensional multi-objective optimization problems, a multi-objective evolutionary algorithm based on orthogonal designing model (MOEA/D-OD) was proposed. Under the framework of multi-objective evolutionary algorithm with decomposition scheme as typical characteristics, the orthogonal designing model (ODM) was incorporated into decomposition mechanism. By utilizing ODM, the good genes carried by the recombinant parents were obtained by offspring to avoid blindness of searching to improve the convergence of the proposed algorithm. The decomposition mechanism was applied to selection to balance exploitation and exploration. MOEA/D-OD was compared with four state-of-the-art MOEAs on 18 benchmark testing problems. Experimental results indicated that MOEA/D-OD can obtain good convergence while having uniform distribution and wild coverage for Pareto sets. The searching performance can stay well when solving complex problems with complicated PS. To validate its performance on constraint multi-objective optimization problems, the proposed MOEA/D-OD was applied to solve the I-beam with two conflict objectives. Compared with other algorithms, the uniformly distributed Pareto sets obtained by MOEA/D-OD showed its practicability for engineering problems, which was an effective approach for solving high dimensional and complicated multi-objective optimization problems.

multi-objective evolutionary algorithm; MOEA/D; orthogonal designing model; I-beam design

10.6041/j.issn.1000-1298.2017.02.049

2016-06-07

2016-07-10

國家自然科學(xué)基金項目(51475142)和河南省高等學(xué)校重點科研項目(17A460020、17A460019)

吳金妹(1988—)，女，講師，主要從事機械設(shè)計制造和系統(tǒng)優(yōu)化設(shè)計研究，E-mail： wujinmei@ncwu.edu.cn

TP18

A

1000-1298(2017)02-0362-08