過(guò)曉芳,王宇平,代　才

(1. 西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710071；2.西安工業(yè)大學(xué) 理學(xué)院,陜西 西安 710032)

?

新的混合分解高維多目標(biāo)進(jìn)化算法

過(guò)曉芳1,2,王宇平1,代才1

(1. 西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710071；2.西安工業(yè)大學(xué) 理學(xué)院,陜西 西安 710032)

摘要:在基于分解技術(shù)求解高維多目標(biāo)優(yōu)化問(wèn)題的思想啟發(fā)下,為了提高多目標(biāo)優(yōu)化問(wèn)題非支配解集合的分布性和收斂性,提出新的基于個(gè)體支配關(guān)系的混合分解高維多目標(biāo)進(jìn)化算法.該算法采用分子種群的進(jìn)化模式,設(shè)計(jì)新的基于有效階的個(gè)體支配關(guān)系用于個(gè)體的比較和更新操作,以便在增加個(gè)體選擇壓力的同時(shí)提高解集分布的多樣性.為了改善該算法的局部搜索性能,將Powell搜索作為局部搜索算子,采用傳統(tǒng)優(yōu)化與進(jìn)化算法相融合的混合進(jìn)化策略.為了檢驗(yàn)提出算法的性能,將提出算法用于求解5～20個(gè)目標(biāo)的6類標(biāo)準(zhǔn)測(cè)試問(wèn)題,與同類算法相比,該算法在收斂性和分布性方面均具有較大的改進(jìn)和提高.

關(guān)鍵詞：多目標(biāo)優(yōu)化問(wèn)題；進(jìn)化算法；分子種群；個(gè)體支配關(guān)系

在科學(xué)研究和工程實(shí)踐領(lǐng)域,越來(lái)越多的多目標(biāo)優(yōu)化問(wèn)題涉及到3個(gè)或3個(gè)以上目標(biāo)對(duì)應(yīng)的高維多目標(biāo)優(yōu)化問(wèn)題[1](manyobjectiveoptimizationproblems,MAPs),而高維多目標(biāo)進(jìn)化算法的研究已經(jīng)成為進(jìn)化算法領(lǐng)域的一個(gè)研究熱點(diǎn)和難點(diǎn).

隨著多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)個(gè)數(shù)不斷增多,基于Pareto支配的個(gè)體排序策略會(huì)使種群中的大部分個(gè)體具有相同的排序值,此時(shí),進(jìn)化過(guò)程由于缺乏選擇壓力導(dǎo)致算法的搜索能力急劇下降[2-4].為了增加算法對(duì)非支配個(gè)體的排序和選擇能力,各國(guó)學(xué)者相繼提出兩類不同的策略對(duì)種群個(gè)體進(jìn)行排序.1)基于松散Pareto支配關(guān)系的個(gè)體排序策略[5-9]；2)基于評(píng)價(jià)指標(biāo)的個(gè)體適應(yīng)度賦值[10-12].這兩種方法雖然在一定程度上能夠增加個(gè)體的選擇壓力,但是在目標(biāo)數(shù)目較多的問(wèn)題中有一定的局限性.同時(shí),基于分解技術(shù)的多目標(biāo)進(jìn)化算法[13](multi-objectiveevolutionaryalgorithmsbasedondecomposition,MOEA/D)的提出為求解高維多目標(biāo)優(yōu)化問(wèn)題提供了一個(gè)全新的思路.它將傳統(tǒng)的數(shù)學(xué)規(guī)劃方法與進(jìn)化算法相結(jié)合,通過(guò)聚合函數(shù)把一個(gè)多目標(biāo)優(yōu)化問(wèn)題分解為若干個(gè)單目標(biāo)優(yōu)化子問(wèn)題并行求解.采用該算法有效地求解了具有多個(gè)目標(biāo)的優(yōu)化問(wèn)題,得到了越來(lái)越多研究者的廣泛關(guān)注并提出了許多改進(jìn)方法[14-17].

基于分解的技術(shù)在本質(zhì)上存在一些局限性,在實(shí)施子問(wèn)題解的更新操作中,新產(chǎn)生個(gè)體能否被舊個(gè)體取代完全取決于其在所屬子問(wèn)題中聚合函數(shù)的取值,但未考慮新個(gè)體實(shí)際所在目標(biāo)空間的位置,在一定程度上會(huì)影響種群的分布性[18-19].Liu等[19]提出新的基于分解思想求解多目標(biāo)優(yōu)化問(wèn)題的算法MOEA/D-M2M,將多目標(biāo)優(yōu)化問(wèn)題分解成相對(duì)簡(jiǎn)單的若干個(gè)多目標(biāo)優(yōu)化的子問(wèn)題,然后以并行的方式分別執(zhí)行進(jìn)化算法求出每個(gè)子問(wèn)題的非支配解集合,并構(gòu)成整個(gè)的Pareto最優(yōu)解集合.采用該方法較好地解決了MOEA/D算法中個(gè)體更新策略所帶來(lái)的多樣性性能下降的不足,但是在子種群內(nèi)部所采用的進(jìn)化策略在某種程度上導(dǎo)致了算法的搜索效率較低.

在基于利用分解的思路求解高維多目標(biāo)優(yōu)化問(wèn)題的思想啟發(fā)下,為了在改善非支配解集分布性的同時(shí)進(jìn)一步提高算法的收斂性能,本文提出新的基于個(gè)體支配關(guān)系的混合分解高維多目標(biāo)進(jìn)化算法(hybriddecompositionmanyobjectiveevolutionaryalgorithmbasedonnewdominancerelation,HDMOEA-NDR).在HDMOEA-NDR中,首先針對(duì)MOEA/D中所采用的權(quán)向量設(shè)計(jì)方法無(wú)法任意設(shè)置其大小數(shù)目的不足,采用均勻設(shè)計(jì)[19]的方法將目標(biāo)空間劃分成若干個(gè)子空間,并利用每個(gè)子空間對(duì)應(yīng)的子種群分別實(shí)施進(jìn)化操作,然后挑選出每個(gè)子種群的最佳非支配個(gè)體作為算法的非支配解集合.在每個(gè)子種群中,為了在提高個(gè)體選擇壓力的同時(shí)改善種群分布的多樣性,設(shè)計(jì)基于有效階的個(gè)體支配關(guān)系用于個(gè)體的選擇和更新操作.為了提高算法的局部搜索和全局搜索的性能,算法采用傳統(tǒng)優(yōu)化Powell搜索法和進(jìn)化算法相融合的混合進(jìn)化策略參與進(jìn)化操作.

1問(wèn)題背景

1.1多目標(biāo)優(yōu)化問(wèn)題

定義1多目標(biāo)優(yōu)化問(wèn)題和高維多目標(biāo)優(yōu)化問(wèn)題高維多目標(biāo)優(yōu)化問(wèn)題建立在多目標(biāo)優(yōu)化問(wèn)題的基礎(chǔ)上.不失一般性,多目標(biāo)優(yōu)化問(wèn)題(multi-objectiveoptimization,MOP)可以表述為

(1)

定義2Pareto支配對(duì)于決策空間中的兩個(gè)向量xA,xB,xAPareto支配xB(記為xAxB)當(dāng)且僅當(dāng)滿足

(?i)(fi(xA)≤fi(xB))∧

(?j)(fj(xA)

(2)

定義3Pareto最優(yōu)解或非支配解一個(gè)解x*被稱為Pareto最優(yōu)解當(dāng)且僅當(dāng)在決策空間中x*不會(huì)被其他解x所Pareto支配,其中,表示解個(gè)體之間的Pareto支配關(guān)系.決策空間中所有的Pareto最優(yōu)解集合構(gòu)成了Pareto最優(yōu)解集(Pareto set, PS),Pareto最優(yōu)解集中的所有Pareto最優(yōu)解在目標(biāo)空間中的像構(gòu)成了Pareto最優(yōu)前沿(Pareto front, PF).

(3)

在利用進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題的過(guò)程中,進(jìn)化算法使用適應(yīng)度函數(shù)引導(dǎo)群體向Pareto最優(yōu)前沿收斂.在設(shè)計(jì)算法時(shí)需要求出的非支配解集合不斷逼近真正的Pareto最優(yōu)解集,并盡可能均勻且寬廣地分布在目標(biāo)函數(shù)空間中.

1.2基于分解的MOEA/D算法的基本思想

MOEA/D是Zhang等[13]提出的一種基于分解思想求解多目標(biāo)優(yōu)化問(wèn)題的算法.它結(jié)合傳統(tǒng)的數(shù)學(xué)規(guī)劃方法與進(jìn)化算法,將一個(gè)多目標(biāo)優(yōu)化問(wèn)題(1)分解為若干個(gè)單目標(biāo)優(yōu)化子問(wèn)題,然后用進(jìn)化算法同時(shí)求解這些子問(wèn)題的最優(yōu)解作為多目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)解集合.其中,每一個(gè)單目標(biāo)優(yōu)化子問(wèn)題的目標(biāo)函數(shù)對(duì)應(yīng)一個(gè)有關(guān)特定權(quán)向量的聚合函數(shù),MOEA/D利用一組權(quán)向量集合來(lái)設(shè)置不同的搜索方向,不同的權(quán)向量將引導(dǎo)算法朝著目標(biāo)空間的不同區(qū)域進(jìn)行搜索.MOEA/D采用切比雪夫分解方法將多目標(biāo)優(yōu)化問(wèn)題分解成若干個(gè)如下式所示的單目標(biāo)優(yōu)化的子問(wèn)題：

(4)

2基于新個(gè)體支配關(guān)系的混合分解高維多目標(biāo)進(jìn)化算法

在基于分解思想求解高維多目標(biāo)優(yōu)化問(wèn)題的思想啟發(fā)下,為了在進(jìn)一步提高子問(wèn)題內(nèi)部個(gè)體向真正Pareto前沿收斂能力的同時(shí)改善非支配解集合的分布性,提出新的基于個(gè)體支配關(guān)系的混合分解高維多目標(biāo)進(jìn)化算法(hybrid decomposition many objective evolutionary algorithm based on new dominance relation, HDMOEA-NDR).按照MOEA/D-M2M的進(jìn)化模式,提出算法首先通過(guò)一組均勻分布的方向向量將目標(biāo)空間劃分成若干個(gè)子目標(biāo)空間,與此同時(shí),初始種群被這組方向向量分解成若干個(gè)子種群.在每個(gè)子種群中,針對(duì)高維多目標(biāo)優(yōu)化問(wèn)題中個(gè)體之間由于缺乏選擇壓力而導(dǎo)致收斂性下降的不足,設(shè)計(jì)新的個(gè)體支配關(guān)系用來(lái)比較非支配個(gè)體間的優(yōu)劣關(guān)系,并將該支配關(guān)系用于子種群內(nèi)部個(gè)體的選擇和更新操作.另外,為了在保證算法全局收斂的同時(shí)提高局部搜索性能,提出算法根據(jù)進(jìn)化的前、后階段自適應(yīng)地選擇不同區(qū)域的個(gè)體參與新個(gè)體的生成,設(shè)計(jì)一種將傳統(tǒng)優(yōu)化Powell搜索法和進(jìn)化算法相融合的混合進(jìn)化策略.

2.1子種群的劃分以及個(gè)體的更新策略

分子種群的進(jìn)化策略將高維多目標(biāo)優(yōu)化問(wèn)題劃分成若干個(gè)子問(wèn)題同時(shí)進(jìn)化.首先,它利用均勻設(shè)計(jì)的思想[14]并通過(guò)一組均勻分布的方向向量λ1,λ2,…,λN將目標(biāo)空間劃分為若干個(gè)子空間,同時(shí),將初始種群POP中的每個(gè)個(gè)體分配到離其最近的權(quán)向量所屬的子種群中,從而將初始種群劃分為若干個(gè)子種群,記為P1,P2,…,PN.子種群的劃分規(guī)則可以通過(guò)下式來(lái)實(shí)現(xiàn)：

Pi={x|x∈POP,<(F(x)-Z),λi> ≤

<(F(x)-Z),λj>}.

(5)

式中：Z為參考點(diǎn),Z=[z1,z2,…,zm]T,其中 zi=min{fi(x)|x∈Ω};F(x)-Z為個(gè)體x的目標(biāo)向量與參考點(diǎn)連線的方向向量；<>表示個(gè)體的方向向量與權(quán)向量的夾角,其取值越小,表示該個(gè)體離權(quán)向量越靠近.算法1描述了子種群的劃分策略.

算法1子種群的分配策略

輸入：初始種群POP和方向向量集合λ1,λ2,…,λN.

輸出：子種群P1,P2,…PN.

1)按照式(5)將種群中的每個(gè)個(gè)體并入所對(duì)應(yīng)的子種群P1,P2,…,PN中.

2)對(duì)于每個(gè)子問(wèn)題i,執(zhí)行

IF |Pi|≤K

在種群POP中隨機(jī)選擇(K-|Pi|)個(gè)個(gè)體放入子種群Pi中；

ELSE

在Pi中隨機(jī)選出兩個(gè)個(gè)體,根據(jù)2.2節(jié)提出的有效階支配關(guān)系去掉兩者之中的被支配個(gè)體,該過(guò)程重復(fù)(|Pi|-K)次,直到子種群Pi中具有K個(gè)個(gè)體.

END

2.2基于有效階的個(gè)體支配關(guān)系

在高維多目標(biāo)優(yōu)化問(wèn)題中,隨著優(yōu)化目標(biāo)個(gè)數(shù)的不斷增多,非支配個(gè)體在種群中所占的比例迅速上升,甚至種群中的絕大部分個(gè)體都變成非支配個(gè)體.此時(shí),傳統(tǒng)的Pareto支配關(guān)系已經(jīng)無(wú)法比較非支配個(gè)體間的優(yōu)劣關(guān)系.為了在子種群的進(jìn)化操作中增加個(gè)體間的選擇壓力并將靠近Pareto前沿的優(yōu)良個(gè)體挑出參與進(jìn)化操作,設(shè)計(jì)一種新的基于有效階的個(gè)體支配關(guān)系.

定義4基于有效階的個(gè)體支配關(guān)系對(duì)于定義1給定的多目標(biāo)優(yōu)化問(wèn)題,xA、xB是原始目標(biāo)集合{f1,f2,…,fm}下基于Pareto支配關(guān)系的兩個(gè)非支配個(gè)體,在原始目標(biāo)集{f1,f2,…,fm}中任取k個(gè)目標(biāo)函數(shù){fi1,fi2,…,fik}(ik∈{1,2,…,m})構(gòu)成原始目標(biāo)集的子集(稱為目標(biāo)子集),所有含k個(gè)目標(biāo)函數(shù)的目標(biāo)子集構(gòu)成的集合記為sk,即sk={P|P?{f1,f2,…,fm}∧|P|=k}.下面考慮給定k元目標(biāo)子集所構(gòu)成的集合sk中,個(gè)體xA與xB的Pareto支配關(guān)系.

對(duì)于固定的k,nb(xA,xB|k),ne(xA,xB|k)和nw(xA,xB|k)分別表示以sk中元素(fi1,fi2,…,fik)為目標(biāo)集比較xA、xB支配關(guān)系時(shí), 使xAParetoxB、xA和xB具有互不Pareto支配、xBParetoxA關(guān)系成立的k元素目標(biāo)子集的數(shù)目,分別記為

nb(xA,xB|k)=|{i|xA{i}xB,?i∈sk}|,

(6)

ne(xA,xB|k)=|{i|(xA{i}xB)∧

(xB{i}xA),?i∈sk}|,

(7)

nw(xA,xB|k)=|{i|xB{i}xA,?i∈sk}|.

(8)

式中：xA{i}xB表示以sk中元素i作為目標(biāo)集時(shí), 個(gè)體xA支配個(gè)體xB.

對(duì)于在原始目標(biāo)集合(f1,f2,…,fm)下的兩個(gè)互不支配的個(gè)體xA、xB來(lái)說(shuō),若滿足nb(xA,xB|k)+ne(xA,xB|k)>nw(xA,xB|k),則稱xAk階有效支配xB,記為xAkxB.例如,含有4個(gè)目標(biāo)的2個(gè)互不支配Pareto的個(gè)體xA、xB在每個(gè)目標(biāo)上的取值分別為(1 4 2 3)和(2 4 1 7).根據(jù)有效階支配關(guān)系的定義,分別考慮xA、xB在目標(biāo)集合的4個(gè)3元目標(biāo)子集下的Pareto支配關(guān)系,通過(guò)比較xA、xB分別在目標(biāo)子集(f1,f2,f3)、(f1,f3,f4)和(f2,f3,f4)下是互不支配的,即ne(xA,xB|k)=3；xA在目標(biāo)子集(f1,f2,f4)下Pareto支配xB,即nb(xA、xB|k)=1,而nw(xA,xB|k)=0,滿足xA3階有效支配xB的條件,即nb(xA,xB|3)+ne(xA,xB|3)>nw(xA,xB|3).

通常,首先取k=m-1,驗(yàn)證兩個(gè)互不Pareto支配的個(gè)體xA、xB在m-1階的目標(biāo)子集下是否滿足有效階支配關(guān)系.若無(wú)法滿足其中一個(gè)個(gè)體能夠有效階支配另一個(gè)個(gè)體,則考慮它們?cè)趍-2階的目標(biāo)子集下是否滿足有效階支配關(guān)系,依次類推.

依次分析在Pareto支配關(guān)系和有效階支配關(guān)系下比較兩個(gè)個(gè)體優(yōu)劣的時(shí)間復(fù)雜度,分別為O(mN2)和O(2mmN2),其中,m為目標(biāo)數(shù),N為進(jìn)化種群規(guī)模.盡管后者的時(shí)間復(fù)雜度高于前者,但是基于有效階的個(gè)體支配關(guān)系能夠有效地區(qū)分出兩個(gè)個(gè)體的優(yōu)劣關(guān)系.在一般情況下,只需考察個(gè)體在k=m-1階目標(biāo)子集下的有效階支配關(guān)系便可以區(qū)分兩兩非支配個(gè)體間的優(yōu)劣,因此時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)達(dá)不到O(2mmN2).另外,與傳統(tǒng)的基于Pareto的個(gè)體支配關(guān)系相比,在每個(gè)子種群中采用基于有效階的個(gè)體支配關(guān)系的優(yōu)越性如下.1)改善了高維多目標(biāo)優(yōu)化問(wèn)題中個(gè)體之間由于缺乏選擇壓力而導(dǎo)致收斂性下降的不足；2)彌補(bǔ)了僅用聚合函數(shù)評(píng)估個(gè)體優(yōu)劣導(dǎo)致種群多樣性下降的缺陷.

2.3混合進(jìn)化策略

在每個(gè)子種群的進(jìn)化操作中,為了提高算法的局部搜索和全局搜索的性能,融合進(jìn)化算法和傳統(tǒng)優(yōu)化算法,在進(jìn)化的不同階段自適應(yīng)地選擇不同區(qū)域的個(gè)體參與新個(gè)體的生成.在進(jìn)化過(guò)程的前期,為了增強(qiáng)算法的全局搜索能力,以較大的概率選擇其他子種群的個(gè)體進(jìn)行交叉操作；在進(jìn)化過(guò)程的后期,將傳統(tǒng)優(yōu)化的Powell搜索法作為局部搜索算子來(lái)產(chǎn)生新的個(gè)體,以此來(lái)提高算法的收斂速度.

Powell法是一類經(jīng)典、簡(jiǎn)單有效的直接搜索方法,它在函數(shù)尋優(yōu)的過(guò)程中僅僅借助函數(shù)值本身的信息,在優(yōu)化問(wèn)題中很方便使用.Powell法反復(fù)利用3個(gè)點(diǎn)的切比雪夫目標(biāo)函數(shù)信息進(jìn)行二次插值來(lái)逼近函數(shù)真正的極小值點(diǎn),計(jì)算量相對(duì)較小.Powell法非常適合作為一種啟發(fā)式局部搜索算子融入到MOEA/D的進(jìn)化操作中,以提高解的精度.

在每個(gè)子種群內(nèi)部,Powell局部搜索算子隨機(jī)選出其中的任意兩個(gè)個(gè)體和與該子種群內(nèi)的當(dāng)前最好個(gè)體構(gòu)成3個(gè)初始點(diǎn),分別記為x1、x2和xi,best,利用式(4)計(jì)算當(dāng)前3個(gè)個(gè)體對(duì)應(yīng)在所在子空間i中的切比雪夫函數(shù)值,并按照函數(shù)值的大小關(guān)系對(duì)三個(gè)個(gè)體予以重新排序x1′、x2′、x3′,其中g(shù)(x1′)

(9)

式中：過(guò)三點(diǎn)(x1′,g(x1′))、(x2′,g(x2′))和(x3′,g(x3′))作一個(gè)二次多項(xiàng)式,并用該二次多項(xiàng)式的極小值點(diǎn)作為原函數(shù)極小值點(diǎn)的近似.此時(shí),根據(jù)多元函數(shù)極值點(diǎn)存在的必要條件,利用二次函數(shù)的導(dǎo)數(shù)為0作為原函數(shù)極小值點(diǎn)的近似,即為xi,best.將新產(chǎn)生的最優(yōu)點(diǎn)xi,best和原先3個(gè)個(gè)體x1′、x2′、x3′的切比雪夫函數(shù)值進(jìn)行比較,并去掉最差的一個(gè)點(diǎn),利用余下的3個(gè)點(diǎn)繼續(xù)作二次插值,重新得到新的最小值點(diǎn)yi,best.如此繼續(xù)作二次插值,直到滿足一定的精度后停止.

2.4基于新的個(gè)體支配關(guān)系的分解高維多目標(biāo)進(jìn)化算法

在執(zhí)行過(guò)程中,設(shè)置的參數(shù)有：子問(wèn)題(權(quán)重向量)的個(gè)數(shù)N,每個(gè)子問(wèn)題對(duì)應(yīng)的子種群的規(guī)模K,每個(gè)權(quán)重向量的鄰居權(quán)向量的個(gè)數(shù)T,執(zhí)行選擇操作時(shí)用到的參數(shù)J,函數(shù)總共的評(píng)估次數(shù)Ev.算法的具體描述如下.

算法2HDMOEA-NRS主流程

1)初始化.

a)采用均勻設(shè)計(jì)[11]的方式產(chǎn)生N個(gè)權(quán)重向量λ1,λ2,…,λN.

b)隨機(jī)產(chǎn)生一個(gè)規(guī)模為N×K的初始化種群,x1,x2,…,xN×K,并計(jì)算初始種群的參考點(diǎn)Z=[z1,…,zm]T.

c)利用算法1將初始種群劃分為N個(gè)子種群,并且每個(gè)子種群中包含K個(gè)解,例如第i個(gè)子種群的個(gè)體記為{xi(K-1)+1,xi(K-1)+2,…,xiK},計(jì)算每個(gè)子種群的最好個(gè)體并將其記錄在xNK上.

d)計(jì)算兩兩權(quán)向量間的歐氏距離,對(duì)于每個(gè)子問(wèn)題i,將鄰居向量設(shè)置為B(i)=[i1,…,iT].

2)更新操作.對(duì)于每個(gè)子問(wèn)題i對(duì)應(yīng)的子種群,隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)r.根據(jù)隨機(jī)數(shù)與選擇操作參數(shù)J的大小關(guān)系,選擇位于不同區(qū)域的個(gè)體參與不同的交叉操作,以便增加算法的局部搜索和全局搜索能力.

3)選擇和交叉操作.若隨機(jī)數(shù)r

4)變異操作.對(duì)交叉操作后生成的新個(gè)體y執(zhí)行變異操作,生成新個(gè)體y′.

5)更新操作.用新個(gè)體y′更新參考點(diǎn)Z,并根據(jù)式(5)判斷新個(gè)體y′找到所屬的子種群Pl.比較y′與子種群Pl的最好個(gè)體xlK的有效階支配關(guān)系：當(dāng)y′kxlK時(shí),將新個(gè)體y′保留在子種群Pl中,并在子種群Pl中的其余K-1個(gè)個(gè)體中隨機(jī)刪除一個(gè)；當(dāng)xlKky′時(shí),將新個(gè)體y′舍棄.

3)判斷終止準(zhǔn)則.

若終止條件滿足,則將每個(gè)子種群的最好個(gè)體作為最終種群輸出；否則,轉(zhuǎn)步驟2).

3實(shí)驗(yàn)結(jié)果與分析

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

為了檢測(cè)HDMOEA-NRS算法的性能,將該算法用于求解5類目標(biāo)數(shù)可擴(kuò)展的測(cè)試問(wèn)題,分別包括具有多個(gè)局部Pareto Front的測(cè)試問(wèn)題DTLZ1、DTLZ2和DTLZ3[20]以及具有復(fù)雜Pareto Set的測(cè)試問(wèn)題F1和F2[21].每個(gè)測(cè)試問(wèn)題所求解的目標(biāo)數(shù)分別為5、10、15和20,并將數(shù)值試驗(yàn)的測(cè)試結(jié)果與三類的高維多目標(biāo)進(jìn)化算法,分別是采用分子種群的多目標(biāo)進(jìn)化算法MOEA/D-M2M[19]、均勻權(quán)向量設(shè)計(jì)的分解多目標(biāo)進(jìn)化算法UMOEA/D[14]和基于收縮和擴(kuò)展支配域的多目標(biāo)進(jìn)化算法NSGAII-CE[22]所得到的實(shí)驗(yàn)結(jié)果進(jìn)行比較.

針對(duì)數(shù)值實(shí)驗(yàn)中的每一個(gè)測(cè)試問(wèn)題,4種算法(HDMOEA-NRS, MOEA/D-M2M,UMOEA/D和NSGAII-CE)采用相同的進(jìn)化算子,個(gè)體均采用實(shí)數(shù)編碼,具體參數(shù)設(shè)置如下.1) 種群規(guī)模：HDMOEA-NRS、MOEA/D-M2M、UMOEA/D和NSGAII-CE的種群規(guī)模設(shè)置為N=200, HDMOEA-NRS采用Beume等[11]提出的均勻設(shè)計(jì)的方式產(chǎn)生權(quán)向量集合,鄰居向量|B(i)|=20,每個(gè)子種群中包含的個(gè)體數(shù)K=5.2)進(jìn)化操作采用差分進(jìn)化和多項(xiàng)式變異：在差分進(jìn)化操作中,交叉概率為0.5,比例因子為0.5；在多項(xiàng)式變異操作中,分布指數(shù)為20,變異概率為0.1.3)4個(gè)算法對(duì)于每個(gè)測(cè)試問(wèn)題的最大函數(shù)評(píng)估次數(shù)為400 000.4)選擇操作參數(shù)J為

式中：maxEv為函數(shù)的最大評(píng)估次數(shù).

在該數(shù)值實(shí)驗(yàn)中,采用IGD[23](inverted generational distance)指標(biāo)來(lái)度量算法的性能.IGD指標(biāo)可以同時(shí)度量算法所獲得非支配解集合的收斂性和分布性,其取值越小,算法的性能越好.每種算法對(duì)每個(gè)測(cè)試問(wèn)題獨(dú)立運(yùn)行20次,分別記錄IGD指標(biāo)在20次運(yùn)行后計(jì)算出的均值和方差.

為了驗(yàn)證在基于子種群的分解多目標(biāo)進(jìn)化算法中引入個(gè)體新支配關(guān)系和局部搜索策略對(duì)于算法收斂性的影響,將提出算法HDMOEA-NRS和MOEA/D-M2M針對(duì)5、10、15、20目標(biāo)的測(cè)試問(wèn)題DTLZ2分別獨(dú)立運(yùn)行20次,分別記錄GD (generational distance)指標(biāo)在20次運(yùn)行后計(jì)算出的均值和方差.其中,GD[23]指標(biāo)是用來(lái)度量算法所獲得非支配解集合的收斂性能,取值越小,算法的收斂性越好.

3.2對(duì)比實(shí)驗(yàn)結(jié)果

表1給出3種算法獨(dú)立運(yùn)行20次計(jì)算出非支配解集合IGD指標(biāo)的均值mean和方差std結(jié)果,對(duì)比同一測(cè)試問(wèn)題在3種不同算法下的IGD指標(biāo)均值,最優(yōu)結(jié)果在表1中用黑體加粗顯示.為了驗(yàn)證提出算法HDMOEA-NRS的性能與同類高維多目標(biāo)進(jìn)化算法相比的穩(wěn)定性,依次對(duì)每種算法獨(dú)立運(yùn)行20次后得到的IGD指標(biāo)樣本數(shù)據(jù)進(jìn)行顯著性水平為0.05的t檢驗(yàn),檢驗(yàn)結(jié)果如表1所示.在每一行所對(duì)應(yīng)的測(cè)試問(wèn)題中,“+”,“-”,“=”分別表示提出算法HDMOEA-NRS的性能優(yōu)于、劣于或者等于所比較算法.

表1　3種算法在不同測(cè)試函數(shù)時(shí)分別運(yùn)行10次得到的IGD統(tǒng)計(jì)結(jié)果

圖1　2種算法針對(duì)5、10、15、20目標(biāo)的測(cè)試問(wèn)題DTLZ2的GD指標(biāo)統(tǒng)計(jì)盒圖Fig.1　Statistical box diagram of two algorithms in DTLZ2 with 5,10,15,20 objectives

從表1可以看出,前兩種算法HDMOEA-NRS和MOEA/D-M2M的IGD指標(biāo)均值遠(yuǎn)遠(yuǎn)優(yōu)于UMOEA/D和NSGAII-CE,說(shuō)明通過(guò)采用分子種群分解技術(shù)的高維多目標(biāo)進(jìn)化算法HDMOEA-NRS和MOEA/D-M2M獲取的非支配解集合的收斂性和多樣性明顯優(yōu)于采用均勻權(quán)向量的分解多目標(biāo)進(jìn)化算法UMOEA/D,也優(yōu)于僅僅通過(guò)增加個(gè)體選擇壓力的方式來(lái)增加收斂性的算法NSGAII-CE.另一方面,對(duì)比HDMOEA-NRS和MOEA/D-M2M,提出算法HDMOEA-NRS的IGD均值在大多數(shù)測(cè)試問(wèn)題中優(yōu)于MOEA/D-M2M,表明算法提出的基于子種群內(nèi)部的個(gè)體排序策略和Powell搜索在提高算法的收斂性能方面的有效性和合理性.

圖1 給出提出算法HDMOEA-NRS和MOEA/D-M2M針對(duì)5、10、15、20目標(biāo)的測(cè)試問(wèn)題DTLZ2分別獨(dú)立運(yùn)行20次計(jì)算的GD指標(biāo)的統(tǒng)計(jì)盒圖,它能夠完整地反映數(shù)據(jù)的離散分布的統(tǒng)計(jì)特性.圖中,盒子的上、下兩條邊界線分別表示樣本數(shù)據(jù)的上、下四分位數(shù),盒子中間的水平線表示樣本的中位數(shù).從圖1可以看出,當(dāng)目標(biāo)數(shù)為5時(shí),2種算法的GD指標(biāo)均值相差不大；但是當(dāng)目標(biāo)數(shù)較多時(shí),算法HDMOEA-NRS的收斂性明顯優(yōu)于MOEA/D-M2M.

3.3個(gè)體新支配關(guān)系和局部搜索策略對(duì)于算法性能的影響分析

為了驗(yàn)證提出的基于有效階的個(gè)體支配關(guān)系對(duì)算法收斂性和分布性的影響,對(duì)提出算法HDMOEA-NRS進(jìn)行調(diào)整,將基于Pareto支配關(guān)系用于子種群內(nèi)部個(gè)體間優(yōu)劣關(guān)系的比較和個(gè)體更新操作,而其他進(jìn)化算子和參數(shù)設(shè)置保持不變.針對(duì)5、10、15、20個(gè)目標(biāo)的測(cè)試問(wèn)題DTLZ1,將HDMOEA-NRS與調(diào)整后的采用Pareto排序的算法分別獨(dú)立運(yùn)行20次,將計(jì)算出的IGD指標(biāo)均值進(jìn)行比較,結(jié)果如圖2所示.可以看出,提出算法將基于有效階的個(gè)體支配關(guān)系用于子種群內(nèi)部個(gè)體間優(yōu)劣關(guān)系的比較和個(gè)體更新操作,獲得的Pareto非支配解集合的收斂性和分布性具有更強(qiáng)的優(yōu)勢(shì).

為了驗(yàn)證采用的Powell局部搜索策略對(duì)于算法收斂性和分布性的影響,對(duì)提出算法HDMOEA-NRS進(jìn)行調(diào)整,在子種群的進(jìn)化操作中取消了Powell局部搜索,而其他進(jìn)化算子和參數(shù)設(shè)置保持不變.針對(duì)5、10、15、20個(gè)目標(biāo)的測(cè)試問(wèn)題DTLZ1,將HDMOEA-NRS與調(diào)整后算法分別獨(dú)立運(yùn)行20次,將計(jì)算出的IGD指標(biāo)均值進(jìn)行比較,結(jié)果如圖3所示.可以看出,當(dāng)目標(biāo)數(shù)為5時(shí),是否采用局部搜素算子對(duì)算法性能的影響不大,但是當(dāng)目標(biāo)數(shù)較多時(shí),采用局部搜索算子能夠較好地提高算法的收斂性能.

圖2　2種排序策略對(duì)于算法性能的影響Fig.2　Influence of performance with two ranking strategy

圖3　局部搜素算子的運(yùn)用對(duì)于算法性能的影響Fig.3　Influence of performance with use of local search operator

3.4參數(shù)敏感性分析

為了測(cè)試不同的實(shí)驗(yàn)參數(shù)設(shè)置對(duì)于算法性能的影響,針對(duì)測(cè)試問(wèn)題DTLZ1(5),分別檢驗(yàn)權(quán)向量的鄰居個(gè)數(shù)T和子種群的規(guī)模K對(duì)IGD性能指標(biāo)的影響.首先,在保持其他參數(shù)不變的情況下,測(cè)試當(dāng)T的取值分別為5、8、12、15、20、25、30時(shí),分別獨(dú)立運(yùn)行HDMOEA-NRS算法20次計(jì)算出IGD指標(biāo)的均值結(jié)果進(jìn)行比較,結(jié)果如表2所示.表2的數(shù)據(jù)表明,T的設(shè)置對(duì)IGD指標(biāo)的擾動(dòng)僅為4%,說(shuō)明T對(duì)算法的性能影響不大.在算法的執(zhí)行過(guò)程中,T的取值越大,表明算法的全局搜索能力越強(qiáng),本文取T=20.

為了驗(yàn)證不同的子種群規(guī)模K對(duì)算法性能的影響,在保持其他參數(shù)不變的情況下,測(cè)試當(dāng)K的取值分別為5、7、9、11、13、15時(shí),分別獨(dú)立運(yùn)行HDMOEA-NRS算法20次計(jì)算出IGD指標(biāo)的均值結(jié)果進(jìn)行比較,結(jié)果如表3所示.表3的數(shù)據(jù)表明, K的設(shè)置對(duì)IGD指標(biāo)的擾動(dòng)僅為3.7%,說(shuō)明K對(duì)算法的性能影響不大.子種群的規(guī)模越大,計(jì)算過(guò)程中函數(shù)的評(píng)估次數(shù)越多,從而增大了算法的計(jì)算量.取最小值K=5.

表2　不同的鄰域規(guī)模T的設(shè)置對(duì)IGD的影響

表3　不同的子種群規(guī)模K的設(shè)置對(duì)IGD的影響

4結(jié)語(yǔ)

為了進(jìn)一步改善高維多目標(biāo)優(yōu)化算法中非支配解集合的分布性和收斂性,在基于分解技術(shù)的思想啟發(fā)下,提出基于新個(gè)體支配關(guān)系的混合分解高維多目標(biāo)進(jìn)化算法.本文的主要貢獻(xiàn)在于設(shè)計(jì)新的基于有效階的個(gè)體支配關(guān)系用于子種群內(nèi)部個(gè)體間優(yōu)劣關(guān)系的比較和子種群的更新操作,在增加個(gè)體的選擇壓力的同時(shí)提高解集分布的多樣性；提出將Powell搜索作為局部搜索算子與進(jìn)化算法相融合的混合進(jìn)化策略,以提高基于分解算法的求解精度.實(shí)驗(yàn)結(jié)果表明,HDMOEA-NRS算法在提高算法的收斂性和改善非支配解集分布的多樣性上是有效的.

參考文獻(xiàn) (References):

[1]CHRISTIANVL.Asurveyonmulti-objectiveevolutionaryalgorithmsformany-objectiveproblems[J].ComputationalOptimizationandApplications, 2014, 58(3):707-756．

[2] 公茂果,焦李成,楊咚咚,等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào),2009, 2(20): 271-289．

GONGMao-guo,JIAOLi-cheng,YANGDong-dong,etal.Researchonevolutionarymulti-objectiveoptimizationalgorithms[J].JournalofSoftware, 2009, 2(20): 271-289．

[3] 孔維健. 高維多目標(biāo)進(jìn)化算法研究綜述[J]. 控制與決策, 2010,25(3)：321-326．

KONGWei-jian.Surveyonlarge-dimensionalmulti-objectiveevolutionaryalgorithms[J].ControlandDecision, 2010, 25(3): 321-326．

[4] 鞏敦衛(wèi). 基于集合的高維多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法[J]. 電子學(xué)報(bào), 2014, 42(1): 77-83．

GONGDun-wei.Solvingmany-objectiveoptimizationproblemsusingset-basedevolutionaryalgorithms[J].ActaElectronicaSinica, 2014, 42(1): 77-83．

[5]PIERRODF,KHUST,SAVICDA.Aninvestigationonpreferenceorderrankingschemeformulti-objectiveevolutionaryoptimization[J].IEEETransactionsonEvolutionaryComputation, 2007, 11(1): 17-45．

[6]ZOUXiu-fen,CHENYu,LIUMin-zhong.Anewevolutionaryalgorithmforsolvingmany-objectiveoptimizationproblems[J].IEEETransactionsonSystems,Man,andCybernetics,partB-Cybernetics, 2008, 38(5): 1402-1412．

[7]MOLINAJ,SANTANAL,HERNANDEZ-DIAZA,etal.G-dominance:referencepointbaseddominanceformultiobjectivemetaheuristics[J].EuropeanJournalofOperationalResearch, 2009, 197(2): 685-692．

[8]DEBK,JAINH.Anevolutionarymany-objectiveoptimizationalgorithmusingreference-point-basednondominatedsortingapproach,parti:solvingproblemswithboxconstraints[J].IEEETransactionsonEvolutionaryComputation, 2014, 18(4): 577-601.

[9]YUANYuan,HUAXu,WANGBo.Anewdominancerelationbasedevolutionaryalgorithmformany-objectiveoptimization[J].IEEETransactionsonEvolutionaryComputation, 2016,20(1): 16-37．

[10]ZITZLERE,SIMONK.Indicator-basedselectioninmulti-objectivesearch[C]∥ConferenceonParallelProblemSolvingfromNature(PPSNVIII).UK:Springer, 2004: 832-842．

[11]BEUMEN,NAUJOKSB,EMMERICHM.SMS-EMOA:multiobjectiveselectionbasedondominatedhypervolume[J].EuropeanJournalofOperationalResearch, 2007, 181(3): 1653-1669．

[12]WHILEL,BRADSTREETL,BARONEL.Afastwayofcalculatingexacthypervolumes[J].IEEETransactionsonEvolutionaryComputation, 2012, 16(1): 86-95．

[13]ZHANGQ,LIH.MOEA/D:amultiobjectiveevolutionaryalgorithmbasedondecomposition[J].IEEETransactionsonEvolutionaryComputation, 2007, 11(6): 712-731．

[14]TANYan-yan,JIAOYong-chang,LIHong.MOEA/D+uniformdesign:anewversionofMOEA/Dforoptimizationproblemswithmanyobjectives[J].ComputersandOperationsResearch, 2013, 40(6): 1648-1660．

[15]JIANGS,CAIZ,ZHANGJ,etal.MultiobjectiveoptimizationbydecompositionwithPareto-adaptiveweightvectors[C]∥Proceedingof7thInternationalConferenceonNaturalComputation.Shanghai:IEEE, 2011: 1260-1264．

[16]LIH,ZHANGQ.MultiobjectiveoptimizationproblemswithcomplicatedParetosets,MOEA/DandNSGA-II[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(2): 284-302．

[17]ZHOUA,ZHANGQ,ZHANGG.Amultiobjectiveevolutionaryalgorithmbasedondecompositionandprobabilitymodel[C]∥IEEECongressonEvolutionaryComputation. [S.l.]:IEEE, 2012: 1-8.

[18]QIY.MOEA/Dwithadaptiveweightadjustment[J].EvolutionaryComputation, 2014, 22(2): 231-264．

[19]LIUHai-lin,GUFang-qing,ZHANGQing-fu.Decompositionofamulti-objectiveoptimizationproblemsintoanumberofsimplemulti-objectivesub-problems[J].IEEETransactionsonEvolutionaryComputation, 2014, 18(3): 450-455．

[20]DebK,THIELEL,LAUMANNSM,etal.Scalablemultiobjectiveoptimizationtestproblems[C]∥IEEECongressonEvolutionaryComputation(CEC’02). [S.l.]:IEEE, 2002: 825-830．

[21]ZHANGQ,ZHOUA,ZHAOS,etal.Multi-objectiveoptimizationtestinstancesfortheCEC2009specialsessionandcompetition[R].Clemson:UniversityofEssex, 2008．

[22] 代才. 基于分解的多目標(biāo)進(jìn)化算法研究[D]. 西安：西安電子科技大學(xué),2014: 50-70．

DAICai.Researchonevolutionaryalgorithmsbasedondecompositionformany-objectiveoptimizationproblems[D].Xi’an:XidianUniversity, 2014: 50-70.

[23]ZITZLERE,LAUMANNSM,THIELEL.Performanceassessmentofmulti-objectiveoptimizers:analysisandreview[J].IEEETransactionsonEvolutionaryComputation, 2003, 7(2): 117-133.

收稿日期：2015-04-24.浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61472297，61272119，61402350，61502290);陜西省教育廳專項(xiàng)科研資助項(xiàng)目(16JK1381).

作者簡(jiǎn)介：過(guò)曉芳(1981-)，女，博士，講師，從事多目標(biāo)進(jìn)化算法的研究. ORCID: 0000-0002-8944-3400. E-mail: gxfang1981@126.com

DOI:10.3785/j.issn.1008-973X.2016.07.013

中圖分類號(hào)：TP 301

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-973X(2016)07-1313-09

Newhybriddecompositionmany-objectiveevolutionaryalgorithm

GUOXiao-fang1,2,WANGYu-ping1,DAICai1

(1. School of Computer, Xidian University, Xi’an 710071, China;2. School of Science, Xi’an Technological University, Xi’an 710032, China)

Abstract:A hybrid decomposition many-objective evolutionary algorithm based on a new dominance relation was proposed inspired by many-objective evolutionary algorithms based on decomposition in order to improve the diversity and convergence of the non-dominated solution set in many-objective optimization problems. The sub-population evolutionary pattern was adopted, and a new efficiency order based dominance relation was designed to compare and update individuals inside each subpopulation, which helps to increase selective pressure and improve diversity. Powell search was used as the local search operator in order to improve the performance of local search. A hybrid evolution strategy combining traditional optimization method with evolutionary algorithm was adopted. Six standard benchmark problems with 5 to 20 objectives were tested to demonstrate the effectiveness of the algorithm. Experimental results showed that the algorithm performed better than other available algorithms in convergence and diversity．

Key words:many-objective optimization problem; evolutionary algorithm; subpopulation; dominance relation