荊東星 張清安
(湘西民族職業(yè)技術(shù)學院計算機系 湖南 湘西 416000)
許多實際優(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時,能夠獲得良好性能(收斂性和分布性)的解集。
為了便于描述,本文所采用的優(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)解集。
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保留機制采用的是ε-支配策略來保證種群的收斂性和分布性。
ε-支配方法是由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)化算法。
在本文提出的算法(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é)束。
為了更好地分析算法的性能,本文采用的評價指標為反向世代距離(IGD)[14]。IGD作為綜合評價指標,通過計算Pareto面到種群的距離的平均值來判斷種群的分布性和收斂性。其計算公式表示為:
(4)
式中:P為最終種群;|P*|為Pareto面上參考點集P*的數(shù)量;d(x*,P)為參考點x*到離種群中各個解的最小距離。由式(4)可知,當IGD值越小時,種群的性能越好。
本文選擇了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ū)別。
本文挑選了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。
本文針對穩(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ù)的研究方向。