范衠，李文姬，謝淑香

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

約束多目標(biāo)進(jìn)化算法修補(bǔ)算子的研究

范衠，李文姬，謝淑香

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

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

約束多目標(biāo)進(jìn)化算法；反向?qū)W習(xí)；修補(bǔ)算子

0 引 言

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

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

1 修補(bǔ)算子

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

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

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

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

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

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

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

2 約束多目標(biāo)測試問題

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

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

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

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

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

（續(xù)表）

3 實(shí)驗(yàn)研究

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

3）算法終止準(zhǔn)則：每個(gè)算法在進(jìn)行300 000次函數(shù)評價(jià)后終止.

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

3.2 算法性能指標(biāo)

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

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

HV指標(biāo)的定義如下：

其中，νol（i）表示集合A中的個(gè)體i和參考點(diǎn)r=（r1，r2，…，rm）圍成的超體積，在本實(shí)驗(yàn)中r=（1.0，1.0）.HV指標(biāo)越大，則表明算法的多樣性和收斂性更好.

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

表2 5種算法在CTP2-CTP8、MCOP1-MCOP7上分別運(yùn)行30次所得的HV指標(biāo)的均值和方差

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

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

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

基于MOEA/D框架5種修補(bǔ)算子的IGD指標(biāo)收斂曲線如圖3所示：

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

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

表4 5種算法在CTP2-CTP8、MCOP1-MCOP7上分別運(yùn)行30次所得的IGD指標(biāo)的均值和方差

4 總結(jié)

本文提出了一種新型的修補(bǔ)算子，該修補(bǔ)算子采用方向修補(bǔ)的策略來修復(fù)違反盒型約束的不可行解，為了驗(yàn)證所提出的修補(bǔ)算子的性能，通過設(shè)計(jì)實(shí)驗(yàn)在MOEA/D框架下與其他4種修補(bǔ)算子在CTP2-8和MCOP1-7測試問題中進(jìn)行了對比.實(shí)驗(yàn)的結(jié)果表明，所提出的修補(bǔ)算子在絕大多數(shù)測試問題上其收斂性和多樣性都要優(yōu)于其他4中修補(bǔ)算子.今后的研究工作將對現(xiàn)有的及提出的靜態(tài)修補(bǔ)算子進(jìn)行拓展，使得修補(bǔ)算子能根據(jù)不同的約束多目標(biāo)優(yōu)化測試問題自動(dòng)學(xué)習(xí)以動(dòng)態(tài)的調(diào)整修補(bǔ)區(qū)間，進(jìn)一步測試動(dòng)態(tài)修補(bǔ)算子在實(shí)際工程優(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］鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，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-），男，博士，教授、博士生導(dǎo)師.研究方向：人工智能研究.E-mail：zfan@stu.edu.cn

國家自然科學(xué)基金資助項(xiàng)目（61175073）；粵東數(shù)控一代創(chuàng)新應(yīng)用綜合服務(wù)平臺（2013B011304002）