基于正交設計模型的多目標進化算法

吳金妹 王亞輝 賈晨輝

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

基于正交設計模型的多目標進化算法

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

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

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

多目標進化算法； MOEA/D； 正交設計模型； I型主梁設計

引言

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

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

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

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

1 多目標優化概況

一個具有n個決策變量，m個目標函數的MOP的基本形式為

(1)

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

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

(2)

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

?x∈Xf:x?x*

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

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

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

(4)

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

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

(5)

2 正交設計模型的多目標進化算法

2.1MOEA/D算法框架

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

(1)分解技術

(6)

(2)鄰居子問題

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

2.2 正交設計模型

(1)正交實驗設計

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

(2)正交設計交叉算子

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

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

(7)

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

(8)

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

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

(9)

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

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

(2)構造正交表LM(QK)，根據正交表LM(QK)安排實驗，產生M個子代個體。

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

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

(10)

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

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

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

2.3 算法流程

MOEA/D-OD算法輸入為：①多目標優化問題。②停止準則。③N：MOEA/D-OD所分解的子問題個數。④λ1,λ2,…,λN：分布均勻的N個權重向量。⑤T：權重向量的鄰居規模。⑥N：種群NP的大小。

(1)初始化

①設置EP=?。

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

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

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

⑤迭代計時器gen=0。

(2)主循環

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

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

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

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

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

(3)停止判斷

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

3 實驗仿真及分析

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

3.1 測試函數和性能評價指標

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

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

3.2 算法對比實驗

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

表2 HV性能指標的均值和標準差Tab.2 HV mean and standard deviation

注：*最優解，下同。

表3 IGD性能指標的均值和標準差Tab.3 IGD mean and standard deviation

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

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

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

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

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

4 工程實例

鑒于MOEA/D-OD算法在求解無約束多目標問題方面的良好性能，為了進一步驗證其在求解多目標約束問題的能力，將其應用于某主梁的多目標設計問題。主梁的示意圖如圖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型梁設計示意圖Fig.2 Schematic diagram of I-beam design

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

約束條件

其中

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型梁多目標優化設計問題獲得的Pareto前沿，由圖可知獲得PF較均勻，解集域較廣。為了對比算法的性能，將MOEA/D-OD算法與文獻[30]中的結果進行對比，其中本文算法獲得極端解為(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算法性能相當。

5 結束語

提出了一種正交設計模型，并采用差分進化策略與其協同進化。基于此，提出了基于正交設計模型MOEA/D算法的MOEA/D-OD算法。將MOEA/D-OD算法與MOEA/D-DE、NSGA-II、SMPSO、AbSYY算法在18個基本測試數上進行仿真對比實驗，分析結果表明：正交實驗模型能夠有效地找到種群的結構信息，算法獲得Pareto解集更逼近真實的PF，尤其是在求解具有復雜PS的LZ09系列函數。相對于僅采用DE算子，MOEA/D-OD算法較MOEA/D-DE算法整體性能更優，魯棒性更強。將MOEA/D-OD算法應用于某主梁多目標設計問題求解時，算法能獲得較均勻的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 周愛民,張青富,張桂戌.一種基于混合高斯模型的多目標進化算法[J].軟件學報,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 楊咚咚,馬晶晶,焦李成,等.一種改進ε支配的等度規映射方法[J].軟件學報,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 王亞輝,賈晨輝,趙仁鵬.基于分解機制的多目標蝙蝠算法及應用[J/OL].農業機械學報,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 趙選民. 實驗設計方法[M]. 北京: 科學出版社,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 蔡自興,江中央,王勇,等.一種新的基于正交實驗設計的約束優化進化算法[J].軟件學報,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 公茂果,焦李成,楊咚咚,等.進化多目標優化算法研究[J].軟件學報,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

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

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

TP18

A

1000-1298(2017)02-0362-08