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

范衠，李文姬，謝淑香

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

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

范衠，李文姬，謝淑香

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

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

約束多目標進化算法；反向?qū)W習；修補算子

0 引 言

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

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

1 修補算子

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

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

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

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

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

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

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

2 約束多目標測試問題

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

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

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

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

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

（續(xù)表）

3 實驗研究

3.1 實驗參數(shù)設(shè)置

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

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

2）種群規(guī)模：N=300.

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

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

3.2 算法性能指標

在多目標進化算法中，通?？疾斓氖撬惴ǖ氖諗啃院投鄻有?，通常采用的評價指標有兩種，分別是反世代距離（Inverted Generational Distance，IGD）指標[30]和超體積（Hypervolume，HV）指標[31].其中IGD指標的定義如下：

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

HV指標的定義如下：

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

3.3 實驗結(jié)果

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

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

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

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

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

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

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

4 總結(jié)

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

［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）；粵東數(shù)控一代創(chuàng)新應用綜合服務平臺（2013B011304002）