一種基于截斷機制的穩(wěn)態(tài)優(yōu)化算法求解多目標優(yōu)化問題

荊東星 張清安

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

0 引 言

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

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

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

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

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

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

1 基本概念

1.1 問題描述及相關性質

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

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)解構成了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內，然后分別從EA和Archive中隨機挑選一個個體(如圖1中的p和e)進行交叉變異操作生成一個新的子代個體c。最后根據EA保留機制和Archive保留機制分別判斷子代個體能否被EA種群或Archive種群接納。其示意圖如圖1所示。

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

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

2 ε-支配的缺陷

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

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

(3)

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

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

圖2 ε-支配

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

圖3 非支配解集

為了使得Archive中的解的數量可控，且具有良好的性能。本文對ε-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初始化參數。設置種群大小N，最大進化代數MAXGEN，交叉率Pc，變異率Pm。

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

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

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

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

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

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

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

Step8輸出最終解集，算法結束。

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

4.1 評價指標

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

(4)

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

4.2 測試問題

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

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

2) 倒轉Pareto面問題：IDTLZ1、IDTLZ2；

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

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

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

5 實驗結果

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

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

(a) PTEA (b) ε-MOEA

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

圖5給出的是各算法在3目標DTLZ2測試問題上的最終解集，不管是均勻性，還是廣泛性，PTEA的表現都要優(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已經覆蓋到了整個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)化結果，該問題的Pareto面由4個區(qū)域組成。可以發(fā)現，ε-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所示，表現最好的是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給出了各算法在倒轉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種算法。同時，本文算法避免了額外的參數設置，極大提高了算法的實用性。

本文除了從直觀上體現算法性能外，還給出了定量分析。如表1給出了4種算法在不同測試函數上綜合性能的數據結果，表中的數據為算法運行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個表現得最好，僅3維的DTLZ7和3維的SDTLZ2分別稍差于NSGA-II和ε-MOEA算法。而就顯著性而言，本文算法有14個測試問題顯著優(yōu)于ε-MOEA，15個測試問題顯著優(yōu)于NSGA-II和PESA-II。

6 結 語

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

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