一種基于截?cái)鄼C(jī)制的穩(wěn)態(tài)優(yōu)化算法求解多目標(biāo)優(yōu)化問題

荊東星 張清安

(湘西民族職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系 湖南 湘西 416000)

0 引 言

許多實(shí)際優(yōu)化問題，通常需要同時(shí)求解2～3個(gè)高度復(fù)雜、非線性并且?guī)в袥_突性的目標(biāo)[1]。這類問題通常被定義為多目標(biāo)優(yōu)化問題(MOPs)。而多目標(biāo)優(yōu)化算法(MOEAs)非常適合于求解此類問題。因此，在過去的幾十年里，MOEAs得到了飛速發(fā)展，并在工程領(lǐng)域得到廣泛應(yīng)用[2-4]。

對(duì)于MOPs來說，MOEAs的一個(gè)關(guān)鍵優(yōu)勢(shì)是基于種群特性，它允許種群中的個(gè)體在單個(gè)執(zhí)行過程中同時(shí)收斂到Pareto面的不同區(qū)域。一般來說，可以將MOEAs的優(yōu)化目標(biāo)簡(jiǎn)單歸納為以下兩個(gè)方面[5]：

1) 收斂：將種群到MOP的Pareto面的距離最小化。

2) 分布：種群廣泛且均勻的分散在MOP的Pareto面上。

為了實(shí)現(xiàn)以上目標(biāo)，近年來，研究者提出了大量有效的MOEAs[6]。而根據(jù)其每次進(jìn)化過程中產(chǎn)生的子代個(gè)數(shù)可以將現(xiàn)有的MOEAs大致分為兩類：一類是基于種群進(jìn)化的MOEA[7]；另一類是基于個(gè)體進(jìn)化的穩(wěn)態(tài)MOEA[8]。第一類中，具有代表性的算法有Zitzler等提出的SPEA[9]及其改進(jìn)版本SPEA2[10]，Srinivas等[11]提出的NSGA，以及Deb等[7]在此基礎(chǔ)上提出的NSGA-II等。而第二類的代表性算法則有Deb等[8]提出的ε-MOEA?；诜N群的MOEA一直備受關(guān)注，而基于個(gè)體的穩(wěn)態(tài)MOEA自從2006年被提出后，在多目標(biāo)優(yōu)化領(lǐng)域鮮有文獻(xiàn)出現(xiàn)。

因此，本文首先分析ε-MOEA所存在的問題，然后提出一種基于截?cái)鄼C(jī)制的穩(wěn)態(tài)MOEA。該算法首先采用Pareto支配控制進(jìn)化種群和歸檔種群的收斂性，然后采用一種新的截?cái)鄼C(jī)制維持歸檔集種群的分布性能。另外，本文的算法除默認(rèn)參數(shù)外(如：種群大小，變異率，交叉率等)，無需任何參數(shù)。通過實(shí)驗(yàn)比較分析可以發(fā)現(xiàn)，本文算法在求解2～3維MOPs時(shí)，能夠獲得良好性能(收斂性和分布性)的解集。

1 基本概念

1.1 問題描述及相關(guān)性質(zhì)

為了便于描述，本文所采用的優(yōu)化問題為最小化問題。一般地，最大化問題通常也可以通過公式轉(zhuǎn)換為最小化問題，問題的表達(dá)形式可以定義如下：

minimizeF(x)=f1(x),…,fm(x))T

(1)

s.t.gi(x)≥0j=1,2,…,J

hk(x)=0k=1,2,…,K

x∈Ω

在多目標(biāo)優(yōu)化中，以下概念得到了很好的定義和廣泛應(yīng)用。

1) Pareto支配：對(duì)于兩個(gè)不同的解，x1，x2∈X,如果滿足式(2),則認(rèn)為x1支配x2，并可以用x1x2表示。

(2)

2) Pareto最優(yōu)解集：對(duì)于單個(gè)解x*∈X，如果不存在其他解x′∈X滿足x′x*，那么它將被視為Pareto最優(yōu)解。所有Pareto最優(yōu)解構(gòu)成了Pareto最優(yōu)解集。

1.2 穩(wěn)態(tài)MOEA模型

2003年由Deb等人首次提出穩(wěn)態(tài)MOEA[8]，為多目標(biāo)優(yōu)化研究提供了一條新的思路。穩(wěn)態(tài)MOEA中，兩個(gè)種群(進(jìn)化種群EA和歸檔集Archive)同時(shí)進(jìn)行優(yōu)化。首先通過隨機(jī)初始化生成初始EA種群，將該種群的非支配解集存入到Archive內(nèi)，然后分別從EA和Archive中隨機(jī)挑選一個(gè)個(gè)體(如圖1中的p和e)進(jìn)行交叉變異操作生成一個(gè)新的子代個(gè)體c。最后根據(jù)EA保留機(jī)制和Archive保留機(jī)制分別判斷子代個(gè)體能否被EA種群或Archive種群接納。其示意圖如圖1所示。

圖1 穩(wěn)態(tài)算法模型

一般而言，EA保留機(jī)制采用的是Pareto支配策略，通過Pareto支配策略將收斂性好的個(gè)體保留下來。而Archive保留機(jī)制不僅需要考慮種群的收斂性，還要保證種群能夠均勻且廣泛地分布在整個(gè)Pareto面上。例如，ε-MOEA的Archive保留機(jī)制采用的是ε-支配策略來保證種群的收斂性和分布性。

2 ε-支配的缺陷

ε-支配方法是由Laumanns等[12]提出，主要思想是根據(jù)值將目標(biāo)空間劃分為若干個(gè)網(wǎng)格，每個(gè)網(wǎng)格內(nèi)只允許一個(gè)個(gè)體存在。因此，當(dāng)兩個(gè)解p、q滿足下式條件時(shí)，認(rèn)為pε-支配。

(1-εi)·fi(p)≤fi(q) ?i∈{1,2,…,m}

(3)

式中：p和q為目標(biāo)空間的兩個(gè)解；m為目標(biāo)的維度。

圖2給出了ε-支配的示意圖，個(gè)體p的ε-支配范圍為ABCDA所圍繞的區(qū)域，而原始Pareto支配范圍為PECFP構(gòu)成的區(qū)域?？梢园l(fā)現(xiàn)，ε-支配的區(qū)域要明顯大于Pareto支配的區(qū)域。在ABCDA區(qū)域的個(gè)體都將被p支配掉。另外，當(dāng)同一個(gè)網(wǎng)格內(nèi)存在多個(gè)解時(shí)，如圖2中的1和2，ε-支配需要從中選擇一個(gè)性能最好的解保留下來。首先判斷這些解的Pareto支配關(guān)系，只考慮其中的非Pareto支配解。然后從中挑選距離所在網(wǎng)格的圓點(diǎn)最近的個(gè)體。在圖2中，解1離網(wǎng)格圓點(diǎn)更近，因此它將被保留。

圖2 ε-支配

進(jìn)一步發(fā)現(xiàn)，種群的大小以及性能都依賴于值的設(shè)置，當(dāng)ε值設(shè)置過大，種群的數(shù)量將會(huì)過小，MOPs的某些區(qū)域可能很難搜索到；而當(dāng)值設(shè)置過小，種群的數(shù)量則會(huì)過于龐大而限制算法的優(yōu)化速度。如何為特定問題設(shè)置合適的值沒有一個(gè)很好的解決方案。另外，ε-支配很難保證種群的廣泛性，因其特有的性質(zhì)，位于Pareto面邊界的解很容易被支配掉[13]。如圖3所示，目標(biāo)空間被劃分為400個(gè)均勻網(wǎng)格，網(wǎng)格的寬度等于ε。根據(jù)ε的性質(zhì)，在目標(biāo)空間中最大能夠容納20個(gè)非ε支配解，然而ε-支配策略實(shí)際只能允許12個(gè)非ε支配解在目標(biāo)空間中。因?yàn)檫@些解將會(huì)把與所在網(wǎng)格平行或垂直的其他網(wǎng)格中的所有解支配掉。從圖3中解的分布可以發(fā)現(xiàn)，靠近邊界的解的分布要比中間位置的稀疏。

圖3 非支配解集

為了使得Archive中的解的數(shù)量可控，且具有良好的性能。本文對(duì)ε-MOEA的Archive保留機(jī)制進(jìn)行了修改，并提出了一種新的穩(wěn)態(tài)優(yōu)化算法。

3 一種新的穩(wěn)態(tài)算法

在本文提出的算法(PTEA)中，采用了Pareto支配以及截?cái)鄼C(jī)制來共同維持Archive種群的性能。Pareto支配維持Archive種群的收斂性，截?cái)鄼C(jī)制維持Archive種群的分布性。

在截?cái)鄼C(jī)制中，首先采用歐氏距離計(jì)算各個(gè)個(gè)體之間的距離，然后選擇最短距離的兩個(gè)個(gè)體，再判斷它們第二短的距離。如果第二短的距離也相等再判斷它們第三短的距離，依次類推，直到找到距離不一樣為止，然后刪除距離短的個(gè)體。其與SPEA2的修剪類似，唯一區(qū)別是SPEA2只考慮了兩次比較。而當(dāng)維度達(dá)到3維時(shí)，在目標(biāo)空間中可能存在多個(gè)第二短距離相等的情況。

PTEA的算法步驟如下：

Step1初始化參數(shù)。設(shè)置種群大小N，最大進(jìn)化代數(shù)MAXGEN，交叉率Pc，變異率Pm。

Step2初始化種群。采用隨機(jī)初始化方法初始化大小為N的EA種群。

Step3構(gòu)建初始Archive。將EA種群進(jìn)行Pareto非支配排序，將非支配解集復(fù)制到Archive中。

Step4生成單個(gè)子個(gè)體。從EA種群和Archive種群中隨機(jī)挑選一個(gè)個(gè)體進(jìn)行交叉變異產(chǎn)生新個(gè)體。

Step5更新EA種群。如果子代個(gè)體被EA種群中的個(gè)體支配，不考慮更新。如果EA種群中不存在個(gè)體支配新的子代，判斷EA種群是否存在個(gè)體被子代支配。如果存在則隨機(jī)替換一個(gè)被支配的個(gè)體，如果不存在，則隨機(jī)替換EA種群中的個(gè)體。

Step6更新Archive種群。首先判斷子代與Archive種群中個(gè)體的支配關(guān)系，如果子代被支配，不更新Archive種群。如果Archive種群中存在個(gè)體被子代支配，從中隨機(jī)挑選一個(gè)被子代替換。當(dāng)Archive種群中的解與子代互為非支配解時(shí)，需考慮兩種情況：(1) Archive種群數(shù)量小于N-1，此時(shí)直接將子代保留到Archive中。(2) Archive種群數(shù)量大于N-1，此時(shí)引入截?cái)鄼C(jī)制替換Archive中的解。這樣可以保證種群大小為一個(gè)固定值。

Step7判斷終止條件。本文的終止條件是進(jìn)化次數(shù)t=MAXGEN。如果未滿足條件則返回到Step 4,否則終止條件。

一直以來，林語堂始終堅(jiān)持充分肯定女性的生命存在和人生價(jià)值，他呼吁：“我愿意看見新時(shí)代的女子，——她要無愧的標(biāo)立、表現(xiàn)、發(fā)揮女性的不同，建造新女性于別個(gè)的女性之上?！盵2]150可見，他的女性觀是進(jìn)步的，是符合時(shí)代潮流的。作者將木蘭作為貫穿小說的中心人物，既賦予她超凡脫俗的氣質(zhì)和才華，又使她扮演著賢妻良母的傳統(tǒng)角色，把經(jīng)過其文化道德篩選的全部女性美揉合于他的女主人公木蘭一身,使木蘭達(dá)到形體美、心靈美、人性美的高度統(tǒng)一，繼而升華到理想美的境界。[3]

Step8輸出最終解集，算法結(jié)束。

4 性能評(píng)價(jià)指標(biāo)及測(cè)試問題

4.1 評(píng)價(jià)指標(biāo)

為了更好地分析算法的性能，本文采用的評(píng)價(jià)指標(biāo)為反向世代距離(IGD)[14]。IGD作為綜合評(píng)價(jià)指標(biāo)，通過計(jì)算Pareto面到種群的距離的平均值來判斷種群的分布性和收斂性。其計(jì)算公式表示為:

(4)

式中：P為最終種群；|P*|為Pareto面上參考點(diǎn)集P*的數(shù)量；d(x*,P)為參考點(diǎn)x*到離種群中各個(gè)解的最小距離。由式(4)可知，當(dāng)IGD值越小時(shí)，種群的性能越好。

4.2 測(cè)試問題

本文選擇了8個(gè)具有代表性的測(cè)試問題[15-16]來驗(yàn)證算法的性能，分別為：

1) 規(guī)整簡(jiǎn)單型Pareto面問題：DTLZ1、DTLZ2以及凸面DTLZ2(CDTLZ2)；

2) 倒轉(zhuǎn)Pareto面問題：IDTLZ1、IDTLZ2；

3) 非連續(xù)問題：DTLZ7；

5) 目標(biāo)范圍不一致問題：SDTLZ2。

本文還對(duì)IGD數(shù)據(jù)進(jìn)行了顯著性比較[17]，其中+、-、=分別表示比PETA顯著好、顯著差以及沒有顯著區(qū)別。

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

本文挑選了3種具有代表性的多目標(biāo)優(yōu)化算法(ε-MOEA[8]、NSGA-II[7]以及PESA-II[18])進(jìn)行對(duì)比實(shí)驗(yàn)，得到的3維優(yōu)化問題的最終解集。其中為穩(wěn)態(tài)算法，在進(jìn)化種群中采用Pareto支配維持進(jìn)化種群的收斂性，在歸檔集中采用ε-支配維持歸檔集種群的收斂和分布性。ε-MOEA最終目的是要獲得一組良好性能的歸檔集種群。NSGA-II采用非支配排序策略將種群劃分為若干個(gè)非支配層，再根據(jù)層序?qū)⒏复鷤€(gè)體逐層保留到下一代，當(dāng)保留下來的個(gè)體大于種群大小時(shí)，則在當(dāng)前非支配層(臨界層)中挑選部分個(gè)體保留下來。NSGA-II在臨界層中采用聚集距離維持算法的分布性，從該層中挑選分布性好的個(gè)體保留下來。SPEA-II是在PESA[19]基礎(chǔ)上的改進(jìn)，它將目標(biāo)空間劃分為若干個(gè)超網(wǎng)格，PESA-II的過程包括選擇超網(wǎng)格以及在該網(wǎng)格中隨機(jī)選擇一個(gè)個(gè)體保留。

圖4給出了PTEA與其他3種算法在3目標(biāo)DTLZ1測(cè)試問題上的最終解集。從直觀上說，PTEA和ε-MOEA的分布性表現(xiàn)得最好，然而ε-MOEA很難搜索到Pareto面的邊界。 通過圖4可以看出ε-MOEA的廣泛性沒有PTEA的好。而其他兩個(gè)算法的最終解集的分布明顯不如前面的兩個(gè)算法。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖4 各算法在3目標(biāo)DTLZ1測(cè)試問題上的最終解集

圖5給出的是各算法在3目標(biāo)DTLZ2測(cè)試問題上的最終解集，不管是均勻性，還是廣泛性，PTEA的表現(xiàn)都要優(yōu)于其他3種算法。PTEA的解集均勻地覆蓋了整個(gè)Pareto面。而對(duì)于其他3種算法來說，ε-MOEA和PESA-II的性能差不多，都要好于NSGA-II。NSGA-II的解集雖然能夠廣泛地分布在Pareto面上，但是它的均勻性不是很理想。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖5 各算法在3目標(biāo)DTLZ2測(cè)試問題上的最終解集

在降維問題上，如圖6所示，PTEA已經(jīng)覆蓋到了整個(gè)Pareto面，而在Pareto面的兩端解的分布明顯稀疏與中間部分。而其他兩個(gè)算法同樣有小部分區(qū)域沒有解的分布。比如圖6(c)的Pareto面的上半部分區(qū)域以及圖6(d)的Pareto面的上半部分和中部區(qū)域相對(duì)來說都比較稀疏。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖6 各算法在3目標(biāo)DTLZ5測(cè)試問題上的最終解集

圖7給出了4種算法在非連續(xù)問題(DTLZ7)的優(yōu)化結(jié)果，該問題的Pareto面由4個(gè)區(qū)域組成?？梢园l(fā)現(xiàn)，ε-MOEA的分布性要稍好于PTEA，但是廣泛性沒有本文算法好。在DTLZ7問題上，本文算法的分布性與NSGA-II和PESA-II沒有太大的區(qū)別。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖7 各算法在3目標(biāo)DTLZ7測(cè)試問題上的最終解集

對(duì)于CDTLZ1測(cè)試問題，它是DTLZ1測(cè)試問題的變體，其Pareto面為凸面。如圖8所示，表現(xiàn)最好的是PTEA，其次是PESA-II。雖然ε-MOEA的解集看似均勻分布，但它沒有搜索到整個(gè)Pareto面，而是大部分解集都聚集到了Pareto面的中部位置。而與ε-MOEA的解集分布相反的是NSGA-II的大部分解集聚集在了Pareto面的邊界。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖8 各算法在3目標(biāo)CDTLZ1測(cè)試問題上的最終解集

圖9和圖10給出了各算法在倒轉(zhuǎn)Pareto面問題上的解集分布，在這兩個(gè)問題上，PTEA的性能同樣也是最好的。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖9 各算法在3目標(biāo)IDTLZ1測(cè)試問題上的最終解集

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖10 各算法在3目標(biāo)IDTLZ2測(cè)試問題上的最終解集

最后是SDTLZ1問題，該問題的各個(gè)目標(biāo)的取值范圍都不相同，本文將各個(gè)維度i的取值范圍設(shè)置為[0,2i]。從圖11中解集的分布可以看出，PTEA和ε-MOEA的分布最均勻，而4種算法的分布廣泛性相當(dāng)。

(a) PTEA (b) ε-MOEA

(c) NSGA-II (d) PESA-II圖11 各算法在3目標(biāo)SDTLZ2測(cè)試問題上的最終解集

因此，從分布均勻以及分布廣度兩個(gè)角度觀察，本文算法都要優(yōu)于其他3種算法。同時(shí)，本文算法避免了額外的參數(shù)設(shè)置，極大提高了算法的實(shí)用性。

本文除了從直觀上體現(xiàn)算法性能外，還給出了定量分析。如表1給出了4種算法在不同測(cè)試函數(shù)上綜合性能的數(shù)據(jù)結(jié)果，表中的數(shù)據(jù)為算法運(yùn)行30次統(tǒng)計(jì)得到的IGD平均值。 表1中的A、B、C、D、E、F、G、H分別表示DTLZ1、DTLZ2、DTLZ5、DTLZ7、CDTLZ2、IDTLZ1、IDTLZ2、SDTLZ2測(cè)試問題。

表1 算法在各個(gè)測(cè)試問題上的IGD值

續(xù)表1

從表1中可以看出，總共16個(gè)測(cè)試問題，PTEA有14個(gè)表現(xiàn)得最好，僅3維的DTLZ7和3維的SDTLZ2分別稍差于NSGA-II和ε-MOEA算法。而就顯著性而言，本文算法有14個(gè)測(cè)試問題顯著優(yōu)于ε-MOEA，15個(gè)測(cè)試問題顯著優(yōu)于NSGA-II和PESA-II。

6 結(jié) 語

本文針對(duì)穩(wěn)態(tài)多目標(biāo)優(yōu)化算法，提出了一種基于截?cái)鄼C(jī)制的穩(wěn)態(tài)優(yōu)化算法(PTEA)。本文還通過一系列對(duì)比實(shí)驗(yàn)驗(yàn)證了該算法的性能。從算法的最終解集的分布以及IGD統(tǒng)計(jì)數(shù)據(jù)可以發(fā)現(xiàn)，PTEA能有效地平衡種群的分布性和收斂性。

雖然PTEA能夠很好地優(yōu)化2～3維的優(yōu)化問題，但是它很難在高維優(yōu)化問題上獲得良好的解集。其主要原因是PTEA依賴Pareto支配機(jī)制引導(dǎo)種群收斂，而Pareto支配隨著維度的增加其作用將急劇減弱。因此，引入一種新的收斂機(jī)制將是后續(xù)的研究方向。