荊東星 張清安

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

0 引 言

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

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

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

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

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

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

1 基本概念

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

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

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

(1)

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

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

x∈Ω

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

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

(2)

2) Pareto最優(yōu)解集：對于單個解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]，為多目標優(yōu)化研究提供了一條新的思路。穩(wěn)態(tài)MOEA中，兩個種群(進化種群EA和歸檔集Archive)同時進行優(yōu)化。首先通過隨機初始化生成初始EA種群，將該種群的非支配解集存入到Archive內(nèi)，然后分別從EA和Archive中隨機挑選一個個體(如圖1中的p和e)進行交叉變異操作生成一個新的子代個體c。最后根據(jù)EA保留機制和Archive保留機制分別判斷子代個體能否被EA種群或Archive種群接納。其示意圖如圖1所示。

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

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

2 ε-支配的缺陷

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

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

(3)

式中：p和q為目標空間的兩個解；m為目標的維度。

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

圖2 ε-支配

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

圖3 非支配解集

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

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

在本文提出的算法(PTEA)中，采用了Pareto支配以及截斷機制來共同維持Archive種群的性能。Pareto支配維持Archive種群的收斂性，截斷機制維持Archive種群的分布性。

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

PTEA的算法步驟如下：

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

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

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

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

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

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

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

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

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

4 性能評價指標及測試問題

4.1 評價指標

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

(4)

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

4.2 測試問題

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

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

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

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

5) 目標范圍不一致問題：SDTLZ2。

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

5 實驗結(jié)果

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

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

(a) PTEA (b) ε-MOEA

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

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

(a) PTEA (b) ε-MOEA

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

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

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

表1 算法在各個測試問題上的IGD值

續(xù)表1

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

6 結(jié) 語

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

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