約束多目標進化算法修補算子的研究

范衠，李文姬，謝淑香

（汕頭大學工學院，廣東省數字信號與圖像處理技術重點實驗室，廣東 汕頭 515063）

約束多目標進化算法修補算子的研究

范衠，李文姬，謝淑香

（汕頭大學工學院，廣東省數字信號與圖像處理技術重點實驗室，廣東 汕頭 515063）

為了避免約束多目標進化算法陷入局部最優，提出了一種新的邊界修補算子.該邊界修復算子受到反向學習的啟發，把違法盒型約束的解修復到其對應的反向可行邊界，以增強約束多目標進化算法的多樣性.為了驗證所提的修補算子的有效性，在經典的約束多目標基準測試問題CTP2-CTP8上進行了實驗仿真，仿真的結果表明所提出的新型的修補算子在多樣性和收斂性上均優于現有的邊界修補算子.為了進一步驗證所提出的新型修補算子，設計了一組約束多目標優化問題MCOP1-MCOP7，作為CTP測試問題的有效補充.在MCOP1-MCOP7上的仿真結果同樣表明，所提出的新型邊界修補算子同時在收斂性和多樣性上要優于現有的修補算子.

約束多目標進化算法；反向學習；修補算子

0 引 言

進化算法（Evolutionary Algorithm，EA）是一類模擬大自然生物選擇與進化機制的隨機搜索算法，與傳統的迭代優化算法最大的區別是傳統的迭代算法從單一點開始進行迭代，而進化算法以種群為基礎進行迭代.由于進化算法適用于求解復雜的優化問題，且對優化問題的目標函數沒有連續可導等特殊要求，因而得到了廣泛應用.現實世界中的工程優化問題通常是帶有約束條件且包含多個目標，如汽車的成本和質量，機械手的循環周期和重量等優化問題.在多數情況下，同時優化的多個目標之間是相互沖突的，為了達到總體的目標最優，通常需要對相互沖突的目標進行綜合考慮.針對約束多目標的優化問題，研究者們設計并提出了多目標的進化算法（Multi-objective Evolutionary Algorithm，MOEA）以及相應的約束處理機制.通常情況下，約束條件大致可以分為兩類，等式約束和不等式約束.一般而言，一個約束的多目標優化問題可定義如下[1]：

其中，x=（x1，x2，…，xn）?Rn表示n維的決策變量，F（x）=（f（1x），f（2x），…，f（mx））?Rm表示m維的目標向量.g（ix）≥0定義了q個不等式約束，h（jx）=0定義了p個等式約束.在多目標優化問題中個體解的優劣采用支配關系來定義.x1支配x2表示為x1?x2，其定義為對于每個目標分量i∈｛1，…，m｝都有 fi（x1）≤fi（x2）且至少存在一個 i∈｛1，…，m｝滿足 f（ix1）＜f（ix2）.對于式（1），如果不存在其他解x∈Rn滿足x?x*，則x*稱為Pareto最優解，F（x*）稱為Pareto最優目標向量，所有的Pareto最優解構成Paretooptimal set（PS），相應的所有Pareto最優目標向量構成Pareto前沿（Pareto-optimal Front,PF）[2].現有的約束多目標進化算法是在多目標進化算法的基礎上加入約束處理機制而形成的[3].目前多目標優化算法大致可以分為三類，第一類是基于支配關系的多目標進化算法，即個體按非支配的關系進行選擇，典型的代表有NSGA-II[4]，PAES-II[5]，SPEA-II[6]等.第二類是基于分解的多目標進化算法，即把多目標的優化問題分解成多個單目標或者是簡單的多目標優化問題，典型的算法有IMMOGLS[7]、UGA[8]、cMOGA[9]、MOEA/D[10]和MOEA/D-M2M[11].第三類是基于優化指標的多目標進化算法，即個體的選擇根據其對評價指標的貢獻大小來選擇，典型的算法包括IBEA[12]、R2-IBEA[13]、SMS-EMOA[14]和HypE[15].現有的約束處理機制大致可以分為4類，即可行解維護機制，罰函數方法，約束與目標隔離的方法和多目標的進化算法[16].可行解維護的方法常常用于離散的組合多目標優化問題，這是因為對于組合的優化問題，不可行解中常常包含一些潛在的較好的模式，直接扔掉重新生成新解不利于種群的進化.典型的如車間調度的問題和車輛路徑規劃問題等，針對這類問題常常是設計合適的編碼和解碼方法或采用局部搜索的方法來保證個體可行.罰函數的方法通常是在目標函數中來增加約束懲罰項，把約束的多目標問題轉化為無約束的多目標優化問題，且不增加目標的數量.典型的方法包括隔離的懲罰函數法[17]、死懲罰函數法[18]、協同進化的罰函數法[19]和自適應的懲罰函數法[20-21].罰函數方法對罰因子的設置非常敏感，不同類型的問題對懲罰因子的要求也不相同.進化過程中的不同階段對懲罰因子的要求也不同，因而給該方法的應用帶來困難.約束與目標隔離的方法通常是把目標函數值和約束函數值分開考慮.典型的方法包括隨機排序法（Stochastic Ranking，SR）[22]、不可行解驅動的進化算法（Infeasible Driven Evolutionary Algorithm，IDEA）[23]和約束支配原則（Constraint Dominate Principle，CDP）[24].多目標的進化算法是把一個約束的多目標優化問題轉化為更高一維目標的無約束優化問題來求解，以回避優化問題的約束條件，典型的方法包括CW[25]和ATMES[26]，該方法存在的問題是目標維度的增加將急劇減小種群個體的選擇壓力，算法的收斂性極大下降，高維目標的優化問題，目前還在研究當中.本文所提出的新型的修補算子主要是針對決策變量違反邊界約束而設計的，可以歸類到可行解的維護機制，該邊界修復算子受到反向學習的啟發，把違法盒型約束的解修復到其對應的反向可行邊界，以增強約束多目標進化算法的多樣性.本文剩下的章節安排如下，第1節介紹了修補算子，第2節介紹了約束多目標基準測試問題，第3節對提出的修補算子進行了實驗研究，第4節對本文工作進行了總結.

1 修補算子

前面已經提到，修補算子是用來修復違反盒型約束的不可行解.目前，在不可行解的修復研究方面，大多數研究者集中在離散的約束優化問題，而對于連續的約束優化問題，很少有研究者注意到.目前，有2種常見的修補算子.第1種常見修補算子定義如下：

其中xi，j表示第i個個體的第j個分量，Lj表示第j個決策分量的下界，Uj表示第j個決策分量的上界.

另外一種常見的不可行解修補算子由王勇等人提出[27]，其定義如下：

本文提出了一種新型的修補算子，將違法盒型約束的解修復到其對應的反向可行邊界，其定義如下：

該修補算子受到反向學習[28]（Opposition-based Learning，OBL）概念的啟發，反向學習的基本思想是同時考慮個體相對應的反方向估計值能更有效地幫助算法搜索到全局最優解.針對式（3）的修補算子，其對稱形式可定義如下：

針對連續的約束多目標優化問題，一種常使用的方法是隨機生成一個新的可行解，其數學形式定義如下：

其中，rand表示0到1之間的一個隨機數.為了便于下一節的實驗的討論，把式（2）-（6）對應的修補算子分別用Repair-A、Repair-B、Repair-C、Repair-D和Repair-E來表示.

2 約束多目標測試問題

現有的約束多目標標準測試問題還很有限，主要的測試問題是由Deb教授提出的CTP測試問題[29]，CTP測試問題的定義如下：

值得注意的是，該測試問題的難度可以通過調整設計g（x）函數來實現.另外，不等式約束C（x）包含6個參數 (θ，a，b，c，d，e)，可以通過調節這6個參數來生成不同難度的約束多目標測試問題.Deb等人設計了7個基準的測試問題，分別命名為CTP2到CTP8.原始的CTP2-CTP8測試問題的決策變量的數量為2，求解容易，各種算法在該測試問題上的性能無法區分.為了增加問題的難度，把CTP2-CTP8測試問題的決策變量數量擴展到10個.為進一步說明本文所提出的新型修補算子的有效性，設計了一組新的約束多目標測試問題MCOP1-MCOP7.與CTP測試問題目標函數不變而約束變化不同，所設計的約束多目標測試問題約束不變而目標函數變化.約束函數的定義如下：

不等式約束C（x）包含5個參數（θ，a，b，cx，cy），可以通過調節這5個參數來改變約束的形狀，調節問題的難度.其中θ表示橢圓逆時針旋轉的角度，a和b分別控制橢圓的長短軸，cx和cy表示橢圓的中心.本文定義了一組約束函數的參數，具體形式如下：

約束多目標測試問題MCOP1-MCOP7的數學定義和理想的Pareto前沿如表1所示.其中橢圓的陰影部分表示不可行的目標區域.

表1 MCOP1-MCOP7的數學定義和理想的Pareto前沿

（續表）

3 實驗研究

3.1 實驗參數設置

為了評估本文所提出的修補算子的性能，在MOEA/D的框架下對第一節所述的5種補算子進行組合測試，測試問題包括CTP2-CTP8和MCOP1-MCOP7.組合后的5種算法對每個測試問題運行30次.5個算法的詳細算法參數設置如下：

1）交叉變異參數：變異概率Pm=1/n（n表示決策變量的個數），多項式變異中，變異指數為20，差分操作中，交叉概率CR=1.0，縮放因子F=0.5.

2）種群規模：N=300.

3）算法終止準則：每個算法在進行300 000次函數評價后終止.

4）鄰居的規模T=30，從鄰居中選擇個體的概率δ=0.9，鄰居解被替換最大數量nr=2.

3.2 算法性能指標

在多目標進化算法中，通常考察的是算法的收斂性和多樣性，通常采用的評價指標有兩種，分別是反世代距離（Inverted Generational Distance，IGD）指標[30]和超體積（Hypervolume，HV）指標[31].其中IGD指標的定義如下：

其中，P*表示理想的Pareto前沿集合，A表示進化算法獲得的近似Pareto集合.m表示目標的數量，表示集合P*的大小，d（y*，A）表示集合P*中的元素y*到集合A的最小歐式距離.IGD指標能同時反應算法的收斂性和多樣性.IGD指標越小，則表明算法所獲得的結果越好.

HV指標的定義如下：

其中，νol（i）表示集合A中的個體i和參考點r=（r1，r2，…，rm）圍成的超體積，在本實驗中r=（1.0，1.0）.HV指標越大，則表明算法的多樣性和收斂性更好.

3.3 實驗結果

圖1 5種算法對CTP及MCOP測試問題的Pareto前沿

基于MOEA/D框架5種修補算子的Hypervolume指標收斂曲線如下圖2所示：

圖2 5種算法所得到的HV均值的收斂曲線

表2 5種算法在CTP2-CTP8、MCOP1-MCOP7上分別運行30次所得的HV指標的均值和方差

從圖1可以看出，修補算子Repair-C在MCOP4-MCOP7測試問題上，其獲得最優Pareto前沿要顯著優于其它4種修補算子，在其它測試問題中修補算子Repair-C的結果也不比其他4種修補算子差.表2的統計數據同樣表明修補算子Repair-C在MCOP4-MCOP7測試問題上具有顯著的優勢.從圖2中可以看出，修補算子Repair-C對CTP6、CTP8、MCOP4、MCOP5、MCOP6、MCOP7測試問題的Hypervolume指標的平均值要明顯優于其他4種修補算子.對CTP2、CTP3、CTP7、MCOP1、MCOP2和MCOP3測試問題，MOEAD-Repair-C算法的Hypervolumen指標的平均值不比其他4種算法差. MOEAD-Repair-D算法對CTP4和CTP5測試問題的Hypervolume指標的平均值要明顯優于其他4種算法.對5種算法在每個測試問題的Hypervolume進行排序，得到表3.

表3 5種算法在不同測試問題中所得的HV均值的排序情況

從表3可以看出，修補算子Repair-C整體表現最好，然后依次是Repair-D、Repair-E、Repair-A和Repair-B.

基于MOEA/D框架5種修補算子的IGD指標收斂曲線如圖3所示：

圖3 5種算法所得到的IGD均值的收斂曲線

從圖3中可以得出修補算子Repair-C對MCOP4、MCOP5、MCOP6、MCOP7測試問題的IGD指標的平均值要明顯優于其他4種算法.這是因為修補算子Repair-C采用反向的跳躍機制，有效增強了種群的多樣性，有效地避免陷入局部極優.對剩下的10個測試問題，修補算子Repair-C的IGD指標的平均值不比其他4種算法差.從表4可以得出修補算子Repair-C在CTP2、CTP6、CTP8和MCOP1-MCOP7測試問題上IGD指標優于其他4種修補算子.

表4 5種算法在CTP2-CTP8、MCOP1-MCOP7上分別運行30次所得的IGD指標的均值和方差

4 總結

本文提出了一種新型的修補算子，該修補算子采用方向修補的策略來修復違反盒型約束的不可行解，為了驗證所提出的修補算子的性能，通過設計實驗在MOEA/D框架下與其他4種修補算子在CTP2-8和MCOP1-7測試問題中進行了對比.實驗的結果表明，所提出的修補算子在絕大多數測試問題上其收斂性和多樣性都要優于其他4中修補算子.今后的研究工作將對現有的及提出的靜態修補算子進行拓展，使得修補算子能根據不同的約束多目標優化測試問題自動學習以動態的調整修補區間，進一步測試動態修補算子在實際工程優化問題中的效果.

［1］Fonseca C M,Fleming P J.Multiobjective optimization and multiple constraint handling with evolutionary algorithms.I.A unified formulation [J].Systems,Man and Cybernetics,Part A:Systems and Humans,IEEE Transactions on,1998,28(1):26-37.

［2］鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2007.

［3］Wang Y,Cai Z X,Zhou Y R,et al.Constrained optimization evolutionary algorithms[J].Journal of Software, 2009,20(1):11-29.

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

［5］Corne D W,Jerram N R,Knowles J D,et al.PESA-II:Region-based selection in evolutionary multiobjective optimization [C/OL]//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO'2001). [S.l.:s.n.]，2001 [2015-06-15].http://www.researchgate.net/publication/239062948_PESA-II_Regionbased_selection_in_evolutionary_multiobjective_optimization.

［6］Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm[EB/OL].[2015-06-15].http://www.kddresearch.org/Courses/Spring-2007/CIS830/Handouts/P8.pdf

［7］Ishibuchi H,Murata T.A multi-objective genetic local search algorithm and its application to flowshop scheduling [J].Systems,Man,and Cybernetics,Part C:Applications and Reviews,IEEE Transactions on, 1998,28(3):392-403.

［8］Leung Y W,Wang Y.Multiobjective programming using uniform design and genetic algorithm [J].Systems, Man,and Cybernetics,Part C:Applications and Reviews,IEEE Transactions on,2000,30(3):293-304.

［9］Murata T,Ishibuchi H,Gen M.Specification of genetic search directions in cellular multi-objective genetic algorithms[C]//Proceeding EMO'01 Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization.London:Springer-Verlag,2001:82-95.

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

［11］Liu H L,Gu F,Zhang Q.Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J].Evolutionary Computation,IEEE Transactions on,2014,18(3):450-455.

［12］Zitzler E,Künzli S.Indicator-based selection in multiobjective search[C]//Parallel Problem Solving from Nature-PPSN VIII.Heidelberg:Springer Berlin Heidelberg,2004:832-842.DOI:10.1007/978-3-540-30217-9_84.

［13］Phan D H,Suzuki J.R2-IBEA:R2 indicator based evolutionary algorithm for multiobjective optimization [EB/OL].[2015-06-15].http://www.cs.umb.edu/～jxs/pub/r2ibea.pdf

［14］Beume N,Naujoks B,Emmerich M.SMS-EMOA:Multiobjective selection based on dominated hypervolume [J].European Journal of Operational Research,2007,181(3):1653-1669.

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

［16］Yu X,Gen M.Introduction to evolutionary algorithms[M].London:Springer-Verlag London,2010.

［17］Le Riche R,Knopf-Lenoir C,Haftka R T.A segregated genetic algorithm for constrained structural optimization[C]//Proceedings of the 6th International Conference on Genetic Algorithms,Pittsburgh,PA, USA.[S.l.:s.n.],1995:558-565.

［18］Hoffmeister F,Sprave J.Problem-independent handling of constraints by use of metric penalty functions [EB/OL]. [2015-06-15].http://www.researchgate.net/publication/220801096_Problem-Independent_ Handling_of_Constraints_by_Use_of_Metric_Penalty_Functions

［19］Huang F,Wang L,He Q.An effective co-evolutionary differential evolution for constrained optimization[J]. Applied Mathematics and computation,2007,186(1):340-356.

［20］Hamida S B,Schoenauer M.ASCHEA:new results using adaptive segregational constraint handling[EB/OL]. [2015-06-15].http://www.opim.wharton.upenn.edu/～sok/papers/b/BenHamid-Schoenauer-cec2002.pdf. DOI:10.1109/CEC.2002.1007042.

［21］Coit D W,Smith A E,Tate D M.Adaptive penalty methods for genetic optimization of constrained combinatorial problems[J].INFORMS Journal on Computing,1996,8(2):173-182.

［22］Runarsson T P,Yao X.Stochastic ranking for constrained evolutionary optimization [J].Evolutionary Computation,IEEE Transactions on,2000,4(3):284-294.

［23］Ray T,Singh H K,Isaacs A,et al.Infeasibility driven evolutionary algorithm for constrained optimization[M] //Constraint-handling in evolutionary optimization.Springer Berlin Heidelberg,2009:145-165.

［24］Deb K.An efficient constraint handling method for genetic algorithms[J].Computer methods in applied mechanics and engineering,2000,186(2):311-338.

［25］Cai Z,Wang Y.A multiobjective optimization-based evolutionary algorithm for constrained optimization[J]. Evolutionary Computation,IEEE Transactions on,2006,10(6):658-675.

［26］Wang Y,Cai Z,Zhou Y,et al.An adaptive tradeoff model for constrained evolutionary optimization[J]. Evolutionary Computation,IEEE Transactions on,2008,12(1):80-92.

［27］Wang Y,Cai Z,Zhang Q.Differential evolution with composite trial vector generation strategies and control parameters[J].Evolutionary Computation,IEEE Transactions on,2011,15(1):55-66.

［28］Rahnamayan S,Tizhoosh H R,Salama M.Opposition-based differential evolution [J].Evolutionary Computation,IEEE Transactions on,2008,12(1):64-79.

［29］Deb K,Pratap A,Meyarivan T.Constrained test problems for multi-objective evolutionary optimization[M]// Evolutionary Multi-Criterion Optimization.Berlin:Springer Berlin Heidelberg,2001:284-298.

［30］Bosman P A N,Thierens D.The balance between proximity and diversity in multiobjective evolutionary algorithms[J].Evolutionary Computation,IEEE Transactions on,2003,7(2):174-188.

［31］Zitzler E,Thiele L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].Evolutionary Computation,IEEE transactions on,1999,3(4):257-271.

Research on Repair Operators in Constrained Multi-objective Evolutionary Algorithm

FAN Zhun，LI Wenji，XIE Shuxiang
（College of Engineering,Shantou University,Guangdong Provincial Key Laboratory of Digital Signal and Image Processing, Shantou 515063， Guangdong China）

In order to avoid falling into local optimum for constrained multi-objective evolutionary algorithm,we design a new repair operator which employs a reversed correction strategy to fix the solutions that violate the boxconstraint.This repair operator inspired by the concept of opposition-based learning.It fixes the infeasible solution that violates the box-constraint to its reversed feasible boundary,so that it can help to increase the diversity of constrained multi-objective evolutionary algorithm.We test the proposed repair operators and other existing repair operators in the framework of MOEA/D on CTP2 to CTP8 instances,the experimental results validate the proposed repair operator is better than existing repair operators in terms of both convergence and diversity.To further demonstrate the performance of proposed repair operator,we design a set of multi-objective constrained optimization problems named MCOP1 to MCOP7,as a complement of CTP benchmark test problems. The test results on MCOP1 to MCOP7 also show that the proposed repair operator is better than existing repair operators.

constrained multi-objective evolutionary algorithm;opposition-based learning;repair operators

TU43；O344

A

1001-4217（2015）03-0003-15

2015-06-19

范衠（1974-），男，博士，教授、博士生導師.研究方向：人工智能研究.E-mail：zfan@stu.edu.cn

國家自然科學基金資助項目（61175073）；粵東數控一代創新應用綜合服務平臺（2013B011304002）