朱占磊,李 征,趙瑞蓮

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029) (*通信作者電子郵箱lizheng@mail.buct.edu.cn)

基于線性權(quán)重最優(yōu)支配的高維多目標(biāo)優(yōu)化算法

朱占磊,李 征*,趙瑞蓮

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029) (*通信作者電子郵箱lizheng@mail.buct.edu.cn)

在高維多目標(biāo)優(yōu)化問題中，Pareto支配關(guān)系存在非支配解隨優(yōu)化目標(biāo)數(shù)增加呈指數(shù)級增長和種群選擇壓力下降等問題。針對這些問題，基于線性權(quán)重聚合函數(shù)和支配關(guān)系兩種比較多目標(biāo)解方法的思想，提出一種線性權(quán)重最優(yōu)支配關(guān)系(LWM-dominance)，并理論證明了LWM非支配解集是Pareto非支配解集的子集，同時保留了種群中重要的角解。進(jìn)一步地，基于LWM支配關(guān)系，實(shí)現(xiàn)了一個高維多目標(biāo)進(jìn)化優(yōu)化算法，基于該算法的實(shí)驗驗證了LWM支配關(guān)系的性質(zhì)。在隨機(jī)解空間中的實(shí)驗結(jié)果表明LWM支配關(guān)系適用于5～15個目標(biāo)的高維多目標(biāo)優(yōu)化問題，通過DTLZ1～DTLZ7高維多目標(biāo)優(yōu)化問題進(jìn)化過程中LWM非支配解集與Pareto非支配解集規(guī)模的對比實(shí)驗，結(jié)果表明優(yōu)化目標(biāo)數(shù)為10和15時非支配解的比例平均下降了約17%。

進(jìn)化優(yōu)化算法；高維多目標(biāo)優(yōu)化；線性權(quán)重函數(shù)；支配關(guān)系；Pareto前沿

0 引言

多目標(biāo)優(yōu)化問題普遍存在并已被廣泛研究。實(shí)際工程中的優(yōu)化問題往往會涉及3個以上的優(yōu)化目標(biāo),甚至?xí)噙_(dá)10～15個目標(biāo)[1],這些問題被稱為高維多目標(biāo)優(yōu)化問題(Many-objective Optimization Problems, MaOP)[2]。

進(jìn)化多目標(biāo)優(yōu)化算法是解決多目標(biāo)優(yōu)化問題最有效的方法之一,其中廣泛使用的NSGA-II(Non-dominated Sorting Genetic Algorithm II)[3]可以有效的解決2～3個目標(biāo)的多目標(biāo)優(yōu)化問題。但在高維多目標(biāo)優(yōu)化問題中,隨著目標(biāo)個數(shù)增加,基于Pareto支配關(guān)系最優(yōu)解的選擇壓力被削弱,造成解集中非支配個體的比例呈指數(shù)上升[4],算法性能急劇下降。因此,在高維多目標(biāo)優(yōu)化問題中,需要研究一種新的支配關(guān)系來提高區(qū)分解集中個體優(yōu)劣的能力,增強(qiáng)最優(yōu)解的選擇壓力,從而減小解集中非支配解的占比,提升算法性能。

在高維多目標(biāo)優(yōu)化問題的研究中,解的比較方法可分為兩類[5]:

1)基于聚合函數(shù)的方法,即把多目標(biāo)優(yōu)化問題的目標(biāo)向量通過聚合函數(shù)映射為一個實(shí)數(shù)值,進(jìn)而比較這個實(shí)數(shù)值來確定解的優(yōu)劣關(guān)系。線性加權(quán)函數(shù)是最常用的聚合函數(shù)[6-8]。但存在以下問題:首先,權(quán)重向量在線性加權(quán)函數(shù)中具有重要作用,權(quán)重的選取會影響優(yōu)化算法在進(jìn)化過程的搜索方向;其次,權(quán)重向量通常需要在進(jìn)化算法執(zhí)行前由領(lǐng)域?qū)＜乙罁?jù)經(jīng)驗確定[9],并且在進(jìn)化算法執(zhí)行過程中通常是不變的,難以動態(tài)調(diào)整進(jìn)化過程中的搜索方向[10]。最后,線性權(quán)重聚合函數(shù)的方法需要優(yōu)化目標(biāo)為同一量綱或者可以轉(zhuǎn)化為同一量綱,具有一定的局限性。

2)基于支配關(guān)系的方法,即通過一種支配關(guān)系來權(quán)衡解的優(yōu)劣。此類方法最終的結(jié)果通常是一個解集合,需要領(lǐng)域?qū)＜彝ㄟ^更高層次的領(lǐng)域經(jīng)驗和知識來進(jìn)一步選取最終解。

在解決高維多目標(biāo)優(yōu)化問題的方法中,基于聚合函數(shù)的方法計算簡單,但由于目標(biāo)數(shù)量的增加,進(jìn)一步加劇了權(quán)重向量的確定難度,難以保證結(jié)果的準(zhǔn)確;使用基于支配關(guān)系的方法求解,目前廣泛使用的Pareto支配關(guān)系,其最優(yōu)解的選擇能力隨優(yōu)化問題目標(biāo)數(shù)的增加而急劇下降。如何改進(jìn)Pareto支配關(guān)系是近年來高維多目標(biāo)優(yōu)化算法的研究熱點(diǎn)之一[11]。文獻(xiàn)[12]提出了γ-cons支配關(guān)系,這是Pareto支配關(guān)系的一種泛化,是Pareto支配關(guān)系的一般形式；但是實(shí)際計算過程中錐形的夾角需要人工確定。文獻(xiàn)[13]使用線性權(quán)重作為Pareto支配關(guān)系之外的第二選擇標(biāo)準(zhǔn)；但是它只考慮了有限的k種固定權(quán)重,只是幫助Pareto區(qū)分解集的一種次要手段。本文綜合聚合函數(shù)和支配關(guān)系的方法提出了一種線性權(quán)重最優(yōu)支配關(guān)系(Linear Weighted Minimal/Maximal dominance， LWM-dominance),核心思想是考慮在線性加權(quán)聚合函數(shù)方法中,不同的權(quán)重向量會影響到解的優(yōu)劣關(guān)系,若存在權(quán)重向量,使得某個解對應(yīng)目標(biāo)向量的聚合函數(shù)值在解集中是最優(yōu)的,相對于其他解更有被保留下來的必要。這類解通常是在某個目標(biāo)上達(dá)到了當(dāng)前的最優(yōu)值,或者各個目標(biāo)上取值相對不會太差。

LWM支配關(guān)系借鑒并融合了聚合函數(shù)和支配關(guān)系兩種解比較的方法,具有以下優(yōu)點(diǎn):LWM支配關(guān)系借鑒了線性加權(quán)聚合函數(shù)的思想,但不需要計算聚合函數(shù)中具體的權(quán)重向量,只用本文算法驗證其存在性即可。在支配關(guān)系方面,Pareto定義的是一種解和解的支配關(guān)系,而LWM支配關(guān)系定義的是一種解和解集之間的支配關(guān)系。在高維多目標(biāo)問題的優(yōu)化算法中,LWM支配關(guān)系可以替換現(xiàn)有的Pareto支配關(guān)系。

本文首先給出LWM支配關(guān)系的定義,然后提出并證明了LWM支配關(guān)系的兩個重要性質(zhì)；同時本文在NSGA-II算法中框架中融合了LWM支配關(guān)系,實(shí)現(xiàn)了一個高維多目標(biāo)進(jìn)化優(yōu)化算法。通過隨機(jī)解空間中兩種支配關(guān)系的非支配解占比的研究,得出LWM支配關(guān)系適用于5～15個目標(biāo)的高維多目標(biāo)優(yōu)化問題的結(jié)論?；贒TLZ1～DTLZ7高維多目標(biāo)優(yōu)化問題的實(shí)驗結(jié)果表明本文提出的高維多目標(biāo)進(jìn)化優(yōu)化算法在進(jìn)化過程中非支配解的占比要低于Pareto支配關(guān)系,LWM支配關(guān)系對NSGA-II算法得到的非支配解集有很好的約減效果。

1 LWM支配關(guān)系定義及推論

不失一般性,本文中考慮的優(yōu)化問題均為最小化優(yōu)化,即對于每個優(yōu)化的子目標(biāo)越小越好。形式化的表述為:

minf(x)=(f1(x),f2(x),…,fm(x))

(1)

s.t.x∈S?Rn

其中:x是n維實(shí)數(shù)空間中的決策向量；S是可行域;fi(x)為優(yōu)化問題的第i(i=1,2,…,m)個目標(biāo)函數(shù)；m為目標(biāo)函數(shù)的個數(shù)。在問題1(式(1))描述的基礎(chǔ)上,給出以下兩個定義：

定義1 Pareto支配。解xA,xB∈S,若xA稱為Pareto支配xB,當(dāng)且僅當(dāng)對于?i=1,2,…,m均有fi(xA)≤fi(xB),同時?i使得fi(xA)lt;fi(xB)。

定義2 Pareto非支配解。解x*∈S被稱為Pareto非支配解(也稱作最優(yōu)解),當(dāng)且僅當(dāng)S中不存在其他解支配x*?？尚杏騍中所有的Pareto非支配解組成Pareto非支配解集(最優(yōu)解集),而非支配解集對應(yīng)的目標(biāo)向量組成的曲面稱為Pareto前沿面(Pareto Front, PF)。

下面給出LWM支配關(guān)系和LWM非支配解的定義。

定義3 LWM支配。解x∈X被稱為LWM支配解集X,當(dāng)且僅當(dāng)存在某個向量w=(w1,w2,…,wm)∈Rm+使得w(f(x))T取得最小,即對于?x′∈X且x′≠x均有w(f(x))Tlt;w(f(x′))T。同時,類似地,解x也被稱為LWM非支配解(最優(yōu)解)。解集X中的所有LWM非支配解組成LWM非支配解集,LWM非支配解集對應(yīng)的目標(biāo)向量組成的曲面稱為LWM前沿面(LWM Front, LWMF)。

本文接下來將給出LWM支配關(guān)系的兩個推論以及相應(yīng)的證明。

推論1 LWM非支配解也是Pareto非支配解,也就是LWM非支配解集是Pareto非支配解集的子集。

證明 根據(jù)Pareto支配關(guān)系的定義,某個解支配其他解,當(dāng)且僅當(dāng)這個解在所有的目標(biāo)上均不大于另一個解,同時兩個解的目標(biāo)向量不能完全相等,也就至少在某些子目標(biāo)要小。接下來使用反證法來證明推論1。

推論1的逆命題為:至少存在一個解是LWM非支配解,但是它不是Pareto非支配解,也就是存在某個解支配它。

不失一般性,假設(shè)解x是LWM支配關(guān)系下的非支配解,但是它又被解x′在Pareto支配關(guān)系下支配。根據(jù)定義1可以得出fi(x′)≤fi(x)(i=1,2,…,m),因此,對于?w∈Rm+滿足w(f(x′))T≤w(f(x))T。同時,由于x是一個是LWM支配關(guān)系下的非支配解,根據(jù)定義3可知?w∈Rm+使得w(f(x))Tlt;w(f(x′))T,顯然這兩個不等式之間是矛盾的。

LWM非支配解集是Pareto非支配解集的一個子集,雖然理論上兩個集合存在相等的可能性,但是實(shí)驗數(shù)據(jù)表明LWM支配關(guān)系可以有效地約減Pareto非支配解集的規(guī)模。

推論2 如果一個解在某個目標(biāo)取得最優(yōu),那么這個解為LWM非支配解。

證明 假設(shè)該解為x,可以構(gòu)造一個權(quán)重向量w=(w1,w2,…,wm),滿足如下性質(zhì):

其中:ε是一個足夠小的正實(shí)數(shù)。此權(quán)重向量w可使w(f(x))T最小,保證了w的存在性。也就證明了含有最優(yōu)子目標(biāo)的解為LWM支配關(guān)系下的非支配解。

含有最優(yōu)子目標(biāo)的解在多目標(biāo)優(yōu)化問題中是比較重要的,也被稱為角解[14-15],而LWM支配關(guān)系保證了角解會被保留下來。

2 基于LWM支配關(guān)系的高維多目標(biāo)優(yōu)化算法

本章給出了基于LWM支配關(guān)系的優(yōu)化算法,算法框架基本同NSGA-II一致,主要區(qū)別是使用LWM支配關(guān)系替換了Pareto支配關(guān)系。算法的框架如下。

算法1 基于LWM支配關(guān)系的高維多目標(biāo)優(yōu)化算法。

輸入 種群大小N、種群最大迭代次數(shù)T。

輸出 LWM非支配解集合LWMF。

步驟1 初始化進(jìn)化種群P0,種群的規(guī)模為N,并令種群迭代次數(shù)t=0。

步驟2 對于第t次迭代的種群Pt實(shí)施交叉、變異操作,獲得臨時的子代種群Qt。

步驟3 把Pt和Qt合并得到種群Rt=Pt∪Qt,對Rt使用LWM支配關(guān)系進(jìn)行非支配排序,并得到前N個個體構(gòu)成子代種群Pt+1。

步驟4 判斷是否滿足進(jìn)化的終止條件：如果滿足,輸出種群的非支配解；否則,t增加1,轉(zhuǎn)到步驟2。

基于LWM支配關(guān)系的非支配排序過程如下:第i次遍歷種群時,對于每個解,判斷其是否為LWM非支配解。如果是,則加入Fi,其中Fi為第i層非支配解集,遍歷結(jié)束之后對當(dāng)前種群去除Fi之后得到的新種群進(jìn)行同樣的遍歷操作,同時i增加1,直到種群中的解個數(shù)變?yōu)?或者0。

通過推論1可以得出,LWM非支配解集是Pareto非支配解集的一個子集。在本文中求解一個解集的LWM非支配解集是通過把它轉(zhuǎn)化為一個線性規(guī)劃問題來解決的。

s.t.w(f(x))Tlt;w(f(x′))T； ?x′∈X,x′≠x

(2)

wigt;0;i=1,2,…,m

線性規(guī)劃問題2(式(2))通常會出現(xiàn)三種情況:1)沒有可行解,這種情況顯然對應(yīng)解x不是LWM非支配解。2)存在無界解,此時wi均大于0,且某個wi可以任意大,因此對應(yīng)解x是LWM非支配解。3)存在最優(yōu)解,理論上存在最優(yōu)解w,解x符合LWM非支配解的定義,因此是LWM非支配解,但實(shí)際上由于計算精度誤差的問題,有可能得到的wi均為接近0的小數(shù),此時實(shí)際上x不是LWM非支配解。因此需要判斷得到的s的值,大于某個閾值s才能認(rèn)為是一個LWM非支配解。

3 實(shí)驗與驗證

本文在jMetal[16]開源多目標(biāo)優(yōu)化框架的基礎(chǔ)上實(shí)現(xiàn)了基于LWM支配關(guān)系的多目標(biāo)優(yōu)化算法,并通過實(shí)驗比較在高維多目標(biāo)優(yōu)化問題中,LWM支配關(guān)系與Pareto支配關(guān)系的優(yōu)劣，具體包括兩種支配關(guān)系在種群進(jìn)化過程中非支配解個數(shù)的對比,以及LWM支配關(guān)系對Pareto非支配解集約減能力的驗證。

選擇壓力體現(xiàn)的是支配關(guān)系區(qū)分支配解和非支配解的能力,可以通過種群中非支配解的個數(shù)來評價。為了確定LWM支配關(guān)系適用的優(yōu)化問題的目標(biāo)數(shù)范圍,實(shí)驗首先在隨機(jī)解空間中對比了兩種支配關(guān)系非支配解的個數(shù),之后選取了7個廣泛用于多目標(biāo)優(yōu)化算法性能比較的多目標(biāo)優(yōu)化問題DTLZ1～DTLZ7[17],它們的決策變量和目標(biāo)維數(shù)是可以擴(kuò)展的。為了防止實(shí)驗結(jié)果受進(jìn)化算法隨機(jī)性的影響,所有實(shí)驗均獨(dú)立運(yùn)行10次,并計算運(yùn)行結(jié)果的平均值。實(shí)驗是在Intel CORE i7 CPU和8 GB RAM的PC上完成的。

3.1 LWM支配關(guān)系適用優(yōu)化目標(biāo)數(shù)范圍的研究

為了確定LWM支配關(guān)系適用的優(yōu)化問題目標(biāo)數(shù)范圍,在隨機(jī)解空間進(jìn)行了模擬實(shí)驗,通過在m維空間中進(jìn)行均勻采樣模擬隨機(jī)解空間對應(yīng)的目標(biāo)向量,然后對比其中LWM非支配解個數(shù)和Pareto非支配解個數(shù)隨著優(yōu)化問題目標(biāo)數(shù)增多的變化情況。

實(shí)驗在目標(biāo)數(shù)取值2～20的范圍內(nèi),對于每個目標(biāo)數(shù)取值,均隨機(jī)生成1 000個實(shí)數(shù)向量來表示優(yōu)化問題的種群對應(yīng)在解空間的目標(biāo)向量,然后分別計算出隨機(jī)種群中Pareto非支配解和LWM非支配解的個數(shù)。得到的結(jié)果如圖1所示?？梢钥闯鲈趦?yōu)化問題的目標(biāo)函數(shù)在區(qū)間[5,15]時,LWM支配關(guān)系對Pareto支配關(guān)系的約減效果比較明顯。

圖1 隨機(jī)種群中兩種支配關(guān)系非支配解個數(shù)對比

3.2 LWM支配關(guān)系和Pareto支配關(guān)系選擇壓力的比較

實(shí)驗通過對在DTLZ1～DTLZ7優(yōu)化問題進(jìn)化過程中種群中LWM非支配解和Pareto非支配解隨著種群進(jìn)化代數(shù)增加的變化情況,來分析LWM支配關(guān)系在高維多目標(biāo)優(yōu)化問題中是否增強(qiáng)了Pareto支配關(guān)系的選擇壓力。

在3.1節(jié)隨機(jī)解空間中的實(shí)驗結(jié)果表明,LWM支配關(guān)系適用于優(yōu)化目標(biāo)數(shù)在5～15的高維多目標(biāo)優(yōu)化問題,因此實(shí)驗中對DTLZ1～DTLZ7系列優(yōu)化問題分別選取5、10、15和20個目標(biāo)進(jìn)行實(shí)驗,其自變量的個數(shù)是隨著目標(biāo)數(shù)確定的,計算的公式由文獻(xiàn)[17]中給出。在基于LWM支配關(guān)系的優(yōu)化算法和NSGA-II算法框架中,兩者的實(shí)驗參數(shù)設(shè)置一致:種群規(guī)模均為100，采用聯(lián)賽選擇，模擬二進(jìn)制交叉和多項式變異,最大迭代次數(shù)均為100。實(shí)驗采用非支配解個數(shù)占比度量兩種支配關(guān)系的選擇壓力。

圖2展示了7個優(yōu)化問題的種群非支配解個數(shù)的隨著進(jìn)化代數(shù)增加的變化情況?？梢钥闯?1)對于DTLZ1～DTLZ7這7個優(yōu)化問題,在進(jìn)化初始階段LWM非支配解的比例小于Pareto支配關(guān)系的非支配解,這是因為在初始階段種群近似于隨機(jī)解集,因此和3.1節(jié)中隨機(jī)解空間中的實(shí)驗結(jié)果表現(xiàn)類似。2)對于這7個優(yōu)化問題,優(yōu)化目標(biāo)數(shù)為10和15時,LWM非支配解的個數(shù)明顯小于Pareto非支配解的個數(shù),總體相對于Pareto非支配解約減了17%；當(dāng)目標(biāo)數(shù)達(dá)到20時,兩者差距不再明顯。3)圖中存在有LWM非支配解的比例高出Pareto非支配解的情況,因為此時的LWM非支配解和Pareto非支配解不在同一次進(jìn)化過程,這與推論1不矛盾。

3.3 LWM支配關(guān)系對Pareto非支配解的約減能力

推論1說明了LWM非支配解集是Pareto非支配解集的子集,因此LWM支配關(guān)系可以約減Pareto非支配解集的規(guī)模。

圖2 種群中非支配解個數(shù)隨著種群進(jìn)化的變化曲線

實(shí)驗通過對比Pareto非支配解集中解的個數(shù)和使用LWM支配關(guān)系約減之后的個數(shù)來說明LWM支配關(guān)系的約減能力。首先,使用基于Pareto支配關(guān)系的進(jìn)化優(yōu)化算法得到表1中優(yōu)化問題的Pareto非支配解集,然后對這些解集使用LWM支配關(guān)系進(jìn)行約減。該實(shí)驗中進(jìn)化優(yōu)化算法的種群規(guī)模為100,獨(dú)立運(yùn)行10次并記錄結(jié)果最后取平均。實(shí)驗優(yōu)化問題及結(jié)果如表1所示。

表1 LWM支配關(guān)系對Pareto非支配解集的約減效果

注:PF為Pareto非支配解的個數(shù)；LWMF為LWM支配關(guān)系約減后解的個數(shù)。

對比表1中的PF和LWMF可以看出:1)因為優(yōu)化目標(biāo)數(shù)取值為10,進(jìn)化算法結(jié)束之后,大小為100的種群中絕大部分都是Pareto非支配解,這也驗證了隨著目標(biāo)數(shù)增多,在高維多目標(biāo)優(yōu)化問題的解種群中非支配解占比高的問題；2)LWM支配關(guān)系對Pareto非支配解集有明顯的約減效果,可以顯著地減小Pareto非支配解集的規(guī)模。總體上,LWMF相對于Pareto非支配解集約減了20.64%。實(shí)驗驗證了前文的推論1,即LWM非支配解是Pareto非支配解的子集。

3.4 討論與分析

3.1節(jié)和3.2節(jié)的實(shí)驗分別驗證了本文提出的LWM支配關(guān)系可以提高高維多目標(biāo)優(yōu)化問題在進(jìn)化過程中種群的選擇壓力,以及LWM支配關(guān)系可以有效約減Pareto非支配解集的規(guī)模。LWM支配關(guān)系雖然借鑒了線性聚合函數(shù)方法的思想,但是LWM非支配解的判定只需要確定權(quán)重的存在性,因此避免了線性聚合函數(shù)方法中確定權(quán)重向量參數(shù)的問題,這或許也避免了線性權(quán)重聚合函數(shù)方法需要轉(zhuǎn)化為同一量綱的問題。

由于LWM支配關(guān)系在判定LWM非支配解的過程中需要求解線性規(guī)劃問題2,引入了額外的計算,因此相對于使用Pareto支配關(guān)系的NSGA-II算法花費(fèi)了更多的時間,算法效率有所下降。

4 結(jié)語

高維多目標(biāo)優(yōu)化問題是目前演化計算領(lǐng)域的研究熱點(diǎn)之一,需要提出新的支配關(guān)系以解決目前廣泛使用的Pareto支配關(guān)系在高維多目標(biāo)優(yōu)化問題中非支配解隨目標(biāo)數(shù)的增加呈指數(shù)級增長等問題。

本文提出了一種線性權(quán)重最優(yōu)支配關(guān)系(LWM-dominance)的新型支配關(guān)系來解決傳統(tǒng)的Pareto支配關(guān)系在高維多目標(biāo)優(yōu)化問題中面臨的選擇壓力問題。本文證明了LWM非支配解集是Pareto非支配解集的一個子集,同時保留了解集中比較重要的角解。最后本文在NSGA-II算法框架的基礎(chǔ)上實(shí)現(xiàn)了一個高維多目標(biāo)進(jìn)化優(yōu)化算法。

實(shí)驗結(jié)果表明:LWM支配關(guān)系適用于5～15個目標(biāo)的高維多目標(biāo)優(yōu)化問題;基于LWM支配關(guān)系的高維多目標(biāo)進(jìn)化優(yōu)化算法在進(jìn)化過程中非支配解的比例要低于基于Pareto支配關(guān)系的非支配解的比例;LWM支配關(guān)系可以對Pareto非支配解集進(jìn)行約減,并具有良好的約減效果。

References)

[1] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.

[2] ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y. Evolutionary many-objective optimization: a short review[C]// CEC 2008: Proceedings of the 2008 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2008: 2419-2426.

[3] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[4] GARZA-FABRE M, PULIDO G T, COELLO C A C. Ranking methods for many-objective optimization[C]// MICAI 2009: Proceedings of the 2009 Mexican International Conference on Artificial Intelligence. Berlin: Springer, 2009: 633-645.

[5] DEB K. Multi-objective optimization using evolutionary algorithms[M]. New York: John Wiley amp; Sons, 2001: 47-75.

[6] STEHR G, GRAEB H, ANTREICH K. Performance trade-off analysis of analog circuits by normal-boundary intersection[C]// Proceedings of the 40th Annual Design Automation Conference. New York: ACM, 2003: 958-963.

[7] KLAMROTH K, J?RGEN T. Constrained optimization using multiple objective programming[J]. Journal of Global Optimization, 2007, 37(3): 325-355.

[8] HUGHES E J. Multiple single objective Pareto sampling[C]// CEC 2003: Proceedings of the 2003 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2003: 2678-2684.

[9] LI B, LI J, TANG K, et al. Many-objective evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 13.

[10] KUNG H T, LUCCIO F, PREPARATA F P. On finding the maxima of a set of vectors[J]. Journal of the ACM, 1975, 22(4): 469-476.

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

[12] EMMERICH M, DEUTZ A, KRUISSELBRINK J, et al. Cone-based hypervolume indicators: Construction, properties, and efficient computation[C]// EMO 2013: Proceedings of the 2013 International Conference on Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2013: 111-127.

[13] RACHMAWATI L, SRINIVASAN D. A multi-objective evolutionary algorithm with weighted-sum niching for convergence on knee regions[C]// Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 749-750.

[14] SINGH H K, ISAACS A, RAY T. A pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4): 539-556.

[15] WANG H, YAO X. Corner sort for Pareto-based many-objective optimization[J]. IEEE Transactions on Cybernetics, 2014, 44(1): 92-102.

[16] DURILLO J J, NEBRO A J. jMetal: a Java framework for multi-objective optimization[J]. Advances in Engineering Software, 2011, 42(10): 760-771.

[17] HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506.

Many-objectiveoptimizationalgorithmbasedonlinearweightedminimal/maximaldominance

ZHU Zhanlei, LI Zheng*, ZHAO Ruilian

(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029,China)

In Many-objective Optimization Problems (MaOP), the Pareto dominance has exponential increase of non-dominated solutions and the decrease of selection pressure with increasing optimization objectives. To solve these issues, a new type of dominance, namely Linear Weighted Minimal/Maximal dominance (LWM-dominance) was proposed based on the ideas of comparing multi-objective solutions by using linear weighted aggregation and Pareto dominance. It is theoretically proved that LWM non-dominated solution set is a subset of Pareto non-dominated solution set, meanwhile the important corner solutions are reserved. Furthermore, an MaOP algorithm based on LWM dominance was presented. The empirical studies proved the corollaries of the proposed LWM dominance. In detail, the experimental results in random objective space show that the LWM dominance is suitable for the MaOPs with 5-15 objectives; the experiment on comparing the number of LWM non-dominated solutions and Pareto non-dominated solutions with subjects of DTLZ1-DTLZ7 shows that the proportion of non-dominated solutions decreases by about 17% on average when the number of optimization objectives is 10 and 15.

evolutionary optimization algorithm; many-objective optimization; linear weighted function; dominant relationship; Pareto Front (PF)

2017- 04- 05;

2017- 05- 30。

國家自然科學(xué)基金資助項目(61472025,61672085)。

朱占磊(1990—),男,河南許昌人,碩士研究生,主要研究方向:進(jìn)化優(yōu)化算法、多目標(biāo)優(yōu)化; 李征(1974—),男,河北清苑人,教授,博士生導(dǎo)師,CCF高級會員,主要研究方向:基于搜索的軟件工程、軟件測試; 趙瑞蓮(1964—),女,山西忻州人,教授,博士生導(dǎo)師,CCF會員,主要研究方向:軟件測試、軟件可靠性分析。

1001- 9081(2017)10- 2823- 05

10.11772/j.issn.1001- 9081.2017.10.2823

TP18

A

This work is partially supported by the National Natural Science Foundation of China (61472025, 61672085).

ZHUZhanlei, born in 1990, M. S. candidate. His research interests include evolutionary optimization algorithm, many-objective optimization.

LIZheng, born in 1974, Ph. D., professor. His research interests include search-based software engineering, software testing.

ZHAORuilian, born in 1964, Ph. D. professor. Her research interests include software testing, software reliability analysis.