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

朱占磊,李 征,趙瑞蓮

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

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

0 引言

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

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

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

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

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

在解決高維多目標(biāo)優(yōu)化問(wèn)題的方法中,基于聚合函數(shù)的方法計(jì)算簡(jiǎn)單,但由于目標(biāo)數(shù)量的增加,進(jìn)一步加劇了權(quán)重向量的確定難度,難以保證結(jié)果的準(zhǔn)確;使用基于支配關(guān)系的方法求解,目前廣泛使用的Pareto支配關(guān)系,其最優(yōu)解的選擇能力隨優(yōu)化問(wèn)題目標(biāo)數(shù)的增加而急劇下降。如何改進(jìn)Pareto支配關(guān)系是近年來(lái)高維多目標(biāo)優(yōu)化算法的研究熱點(diǎn)之一[11]。文獻(xiàn)[12]提出了γ-cons支配關(guān)系,這是Pareto支配關(guān)系的一種泛化,是Pareto支配關(guān)系的一般形式；但是實(shí)際計(jì)算過(guò)程中錐形的夾角需要人工確定。文獻(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)重向量會(huì)影響到解的優(yōu)劣關(guān)系,若存在權(quán)重向量,使得某個(gè)解對(duì)應(yīng)目標(biāo)向量的聚合函數(shù)值在解集中是最優(yōu)的,相對(duì)于其他解更有被保留下來(lái)的必要。這類解通常是在某個(gè)目標(biāo)上達(dá)到了當(dāng)前的最優(yōu)值,或者各個(gè)目標(biāo)上取值相對(duì)不會(huì)太差。

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

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

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

不失一般性,本文中考慮的優(yōu)化問(wèn)題均為最小化優(yōu)化,即對(duì)于每個(gè)優(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)化問(wèn)題的第i(i=1,2,…,m)個(gè)目標(biāo)函數(shù)；m為目標(biāo)函數(shù)的個(gè)數(shù)。在問(wèn)題1(式(1))描述的基礎(chǔ)上,給出以下兩個(gè)定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 對(duì)于第t次迭代的種群Pt實(shí)施交叉、變異操作,獲得臨時(shí)的子代種群Qt。

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

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

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

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

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

(2)

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

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

3 實(shí)驗(yàn)與驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注:PF為Pareto非支配解的個(gè)數(shù)；LWMF為L(zhǎng)WM支配關(guān)系約減后解的個(gè)數(shù)。

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

3.4 討論與分析

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

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

4 結(jié)語(yǔ)

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

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

實(shí)驗(yàn)結(jié)果表明:LWM支配關(guān)系適用于5～15個(gè)目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題;基于LWM支配關(guān)系的高維多目標(biāo)進(jìn)化優(yōu)化算法在進(jìn)化過(guò)程中非支配解的比例要低于基于Pareto支配關(guān)系的非支配解的比例;LWM支配關(guān)系可以對(duì)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é)報(bào), 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。

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

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

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.