一種適應(yīng)度排序的高維多目標(biāo)粒子群優(yōu)化算法

楊五四，陳 莉，王 毅，張茂省

(1.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710021；2.中國地質(zhì)調(diào)查局西安地質(zhì)調(diào)查中心 自然資源部黃土地質(zhì)災(zāi)害重點實驗室，陜西 西安 710054)

多目標(biāo)優(yōu)化問題是一類復(fù)雜的最優(yōu)化問題。常規(guī)多目標(biāo)優(yōu)化算法雖能夠有效解決2或3個目標(biāo)的多目標(biāo)優(yōu)化問題，但求解高維多目標(biāo)優(yōu)化問題(n≥4)的效果并不理想。其主要原因有：隨著問題目標(biāo)維數(shù)的增加，采用常規(guī)帕累托(Pareto)支配關(guān)系將有可能導(dǎo)致算法對非支配解的選擇壓力不足，使得非支配解難以有效逼近真實帕累托前沿；另外，由于高維多目標(biāo)優(yōu)化問題的帕累托最優(yōu)前沿為超曲面，導(dǎo)致帕累托最優(yōu)解集及對應(yīng)可行解搜索空間的規(guī)模呈指數(shù)級增長，從而使算法收斂速度大幅下降。如何有效求解高維多目標(biāo)優(yōu)化問題，研究更優(yōu)的高維多目標(biāo)優(yōu)化方法是目前進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域所面臨的難題之一?，F(xiàn)有的方法，如在搜索過程中結(jié)合偏好信息以縮小帕累托前沿區(qū)域[1-2]，通過寬松的帕累托支配關(guān)系來增強算法選擇壓力，如格支配[3]、K支配[4]、直覺模糊支配[5]、α支配[6]、模糊支配[7]等，以及采用新的比較準(zhǔn)則對個體收斂性能的優(yōu)劣進(jìn)行比較與排序，以實現(xiàn)非支配個體之間的性能比較[8-9]。

針對高維多目標(biāo)優(yōu)化問題，考慮到集成適應(yīng)度排序[8]是一種非帕累托支配排序方式，文中提出了一種集成適應(yīng)度排序的高維多目標(biāo)粒子群優(yōu)化算法。即通過獲取種群中個體與參考點最近的確定維度向量，其中向量維度參數(shù)設(shè)為K，首先使用基于懲罰的邊界交叉方法(PBI)作為適應(yīng)度函數(shù)來對種群中的個體進(jìn)行排序，然后對較差的個體進(jìn)行剔除，并將精英個體保存到外部檔案中；同時，雖然粒子優(yōu)化算法[10]具有較強的局部和全局搜索功能，以及收斂速度較快、算法參數(shù)較少等優(yōu)良特性，但其易落入局部最優(yōu)，影響算法效果，因而采用雙搜索策略的粒子群優(yōu)化算法[11]對種群進(jìn)行尋優(yōu)搜索。

1 集成適應(yīng)度排序

集成適應(yīng)度排序方法在文獻(xiàn)[8]中是這樣描述的：對種群P每個個體與預(yù)先定義的均勻分布參考點W進(jìn)行關(guān)聯(lián)，據(jù)此求出每個個體的最近權(quán)向量L，并選出前K個(其中K遠(yuǎn)遠(yuǎn)小于N)權(quán)向量，其中K為提前定義的常數(shù)。將已選權(quán)向量與N個適應(yīng)度函數(shù)相關(guān)聯(lián)，這里采用基于懲罰的邊界交叉函數(shù)作為適應(yīng)度函數(shù)，具體數(shù)學(xué)形式如式(1)所示。每個適應(yīng)度函數(shù)對部分個體進(jìn)行非遞減排序，并根據(jù)個體的優(yōu)劣進(jìn)行編號，得到每個個體排序向量R。與文獻(xiàn)[8]不同之處在于沒有直接計算出每個個體最大排序序號，而是通過向量R結(jié)合參考點W對種群進(jìn)行選擇，并將精英個體保存在檔案中，同時，采用算法NSGA-Ⅲ[12]的歸一化方法對種群進(jìn)行處理，集成適應(yīng)度排序的算法流程見算法1。

算法1集成適應(yīng)度排序(Ensemble Fit Ranking)。

輸入：種群P，參考點W，控制參數(shù)K。

輸出：每個解的全局排序序數(shù)RankNumber。

① [N，M]←size(P)

②NW←size(W)

③P←Normalization(P)

④rank←AssociationSort(P，W)

⑤L←GetClosestWeightVectors(K)

⑥D(zhuǎn)istance←GetPBIValue(L，K)

⑦r←GetSortNumber(Distance)

⑧Distance←Distance(Distance≠inf)=1

⑨RankNumber←r*Distance

基于懲罰的邊界交叉方法[13]的數(shù)學(xué)形式如下：

mingpbi(x|λi，z*)=d1+θd2，

(1)

z*為理想點，θ為罰參數(shù)，λi為權(quán)重向量，x為決策向量。

2 基于集成適應(yīng)度排序的高維多目標(biāo)粒子群優(yōu)化算法MaPSO-EFR

2.1 算法描述

基于帕累托支配的高維多目標(biāo)優(yōu)化算法在求解高維多目標(biāo)優(yōu)化問題時具有一定的局限性，而基于非帕累托支配的排序方法的主要優(yōu)勢在于放棄了帕累托支配方法中較為嚴(yán)格的個體優(yōu)劣衡量標(biāo)準(zhǔn)，通過新的比較準(zhǔn)則對個體收斂性能的優(yōu)劣進(jìn)行比較與排序，以實現(xiàn)非支配個體之間的性能比較，可有效提升對精英個體的選擇壓力，提高了算法的收斂精度，而且使得算法選擇壓力的提升不受目標(biāo)維數(shù)增加的影響，從根本上解決了目標(biāo)維數(shù)增多時精英個體選擇壓力退化的問題。基于此，提出一種集成適應(yīng)度排序的高維多目標(biāo)粒子群優(yōu)化算法(MaPSO-EFR)，其算法流程如算法2和算法3所示。

算法2高維多目標(biāo)粒子群優(yōu)化算法(MaPSO-EFR)。

輸入：種群大小N，控制參數(shù)K，最大迭代次數(shù)Gmax。

輸出：種群P。

① 初始種群P，產(chǎn)生一組均勻分布的參考點W

②Archive←UpdateArchive(P，W，N，K)

③ whileG

④P←Operator(P，Archive)

⑤Archive←UpdateArchive([P，Archive]，W，N，K)

⑥Offspring←DE_Operator(Archive)

⑦Archive←UpdateArchive([Offspring，Archive]，W，N，K)

⑧ end while

算法3外部檔案更新(UpdateArchive)。

輸入：種群P，參考點W，種群大小N，控制參數(shù)K。

輸出：更新后種群Archive。

①RankNumber←EnsembleFitRanking(P，W，K)

②RP←1：length(P)

③RR←1：length(W)

④ While length(RP)>length(P)-N

⑤ [temp，imin]=min(RankNumber(RP，RR))

⑥RP←Delete disadvantaged individuals(temp，imin)

⑦ end while

⑦Archive←P(RP)

算法MaPSO-EFR的總流程：首先初始化種群P，并在目標(biāo)空間中產(chǎn)生一組均勻分布的參考點W，并初始化外部檔案，在while循環(huán)中，使用雙搜索策略的粒子群優(yōu)化算法對種群P進(jìn)行更新，得到新種群P，然后更新檔案，利用差分進(jìn)化算子對檔案中的個體進(jìn)行交叉、變異等操作，得到子群，最后再次更新檔案，直到循環(huán)迭代滿足結(jié)束條件。外部檔案更新流程如算法3所示，首先通過集成適應(yīng)度排序獲取各向量排序后的序號，計算出當(dāng)前種群的大小，以及參考點數(shù)量，進(jìn)入while循環(huán)中，通過種群與參考點的關(guān)系對最小的序號進(jìn)行選擇，刪除較差的個體，直到滿足循環(huán)終止條件，最后將精英個體保存在外部檔案中。

2.2 計算復(fù)雜度分析

算法MaPSO-EFR的計算時間復(fù)雜度主要在于排序，其中歸一化操作的時間復(fù)雜度為O(m2N)，而全局排序序號的計算的時間復(fù)雜度為max{O(mN2)，O(N2logN)}，綜合考慮算法MaPSO-EFR的計算復(fù)雜度為max {O(mN2)，O(N2logN)}。

3 實驗結(jié)果與分析

仿真實驗在Intel Core i7-6500u 、8 GB內(nèi)存、2.50 GHz 主頻的雙核CPU與Windows 1064位操作系統(tǒng)的個人電腦上運行。為了測試算法MaPSO-EFR的性能，選取性能先進(jìn)的4種高維多目標(biāo)進(jìn)化優(yōu)化算法進(jìn)行對比，分別為EFRRR[8]、NSGA-III[12]、MOEA/D[14]、MaOEAIGD[15]，所有算法在多目標(biāo)進(jìn)化算法開源平臺PlatEMO[16]上進(jìn)行對比驗證。

3.1 測試函數(shù)與評價指標(biāo)

選取標(biāo)準(zhǔn)測試問題DTLZ1-4和WFG的部分測試實例，分別在5，8，10，15目標(biāo)上進(jìn)行仿真實驗。測試問題決策變量的設(shè)置如表1所示。其中，m為目標(biāo)數(shù)，n為決策變量數(shù)，k為位置變量，l為距離變量。采用綜合性能指標(biāo)反世代距離(IGD)對算法性能進(jìn)行評價。

表1 測試問題的決策變量設(shè)置

3.2 實驗參數(shù)設(shè)置

表2 目標(biāo)數(shù)、種群數(shù)與進(jìn)化次數(shù)設(shè)置

每個算法在測試用例上分別獨立運行30次，并取均值作為最終結(jié)果；所有對比算法的參數(shù)設(shè)置均采用原文獻(xiàn)中的數(shù)值，變異算子采用多項式變異，其中ηm=20，pm=1/n；集成適應(yīng)度排序參數(shù)K設(shè)置為目標(biāo)數(shù)，根據(jù)目標(biāo)數(shù)的增加而變化。測試實例的目標(biāo)數(shù)，采用的種群數(shù)以及算法進(jìn)化次數(shù)如表2所示。

3.3 實驗結(jié)果與分析

為了更客觀地評估實驗結(jié)果，采用Wilcoxon秩和檢驗對所有對比算法進(jìn)行兩兩比較，顯著性水平設(shè)為0.05，其中“+”、“-”和“=”分別表示對比算法性能優(yōu)于、劣于和相似于提出的算法，其中最優(yōu)值用灰色背景進(jìn)行標(biāo)注。

表3 統(tǒng)計了5種對比算法的最終實驗結(jié)果。從表中可以直觀地看到，算法MaPSO-EFR在大部分測試問題上的表現(xiàn)優(yōu)于其他對比算法。其中，在測試問題DTLZ上，以略微的優(yōu)勢領(lǐng)先于其它算法，而在測試問題WFG上，算法MaPSO-EFR的性能表現(xiàn)明顯優(yōu)于其它算法，比同樣采用集成適應(yīng)度排序的EFRRR獲得的最佳測試實例的數(shù)量多一些。但是算法MaPSO-EFR的集成適應(yīng)度的方式與算法EFRRR還是有很大的不同，前者采用基于懲罰的邊界交叉方法作為適應(yīng)度函數(shù)，而后者使用切比雪夫函數(shù)作為適應(yīng)度函數(shù)；基于懲罰的邊界交叉方法分為兩部分，一部分強調(diào)收斂性，另一部分強調(diào)多樣性，使得其在某些測試用例上的表現(xiàn)優(yōu)于切比雪夫方法。但這不是說基于懲罰的邊界交叉方法在所有問題上都優(yōu)于切比雪夫方法。另外，算法MaPSO-EFR沒有采用EFRRR中的最大排序模式選擇個體，而是通過參考點對標(biāo)記序號的個體進(jìn)一步選擇，并保存最優(yōu)個體進(jìn)入下一代，這樣可以避免在某一方向上重復(fù)選擇個體，在保證種群收斂性的同時，保證種群的多樣性。

表4對表3中各對比算法在測試實例上所獲得Wilcoxon秩和檢驗的最佳、較好(+)、相似(=)、較差(-)等進(jìn)行了統(tǒng)計。其中，算法MaPSO-EFR獲得了23個最佳性能表現(xiàn)的測試實例，占總數(shù)的57.5%；算法NSGA-III在6個測試實例上的性能最優(yōu)，而且在21個測試實例上的性能與算法MaPSO-EFR的相似，在4個對比算法中性能綜合表現(xiàn)最好。

為了更直觀地評價算法MaPSO-EFR性能表現(xiàn)，以5種對比算法在實例DTLZ3的15目標(biāo)上的測試為例，采用折線圖、盒圖等可視化工具進(jìn)行說明。其中，圖1(a)描繪出了各對比算法的反世代距離指標(biāo)隨著迭代次數(shù)的增加而變化的折線，可以明顯地看出對比算法NSGA-III，MaOEA-IGD的收斂性不如算法MaPSO-EFR和EFRRR；算法MaPSO-EFR收斂性表現(xiàn)幾乎和算法EFRRR是一樣的，但還是稍遜于算法EFRRR。雖然MOEA/D的收斂性表現(xiàn)比算法MaPSO-EFR和EFRRR都要好，但從表3中的數(shù)據(jù)容易發(fā)現(xiàn)，算法MOEA/D在DTLZ3的15目標(biāo)上表現(xiàn)不穩(wěn)定。圖1(b)將各對比算法在DTLZ3的15目標(biāo)上的30次實驗數(shù)據(jù)用盒圖的方式進(jìn)行了說明。直觀上可以看出，算法NSGA-III的表現(xiàn)最差，算法EFRRR和算法MaPSO-EFR的性能表現(xiàn)相似。

表3 算法MaPSO-EFR與四種對比算法在DTLZ和WFG的不同目標(biāo)維數(shù)上獲得的IGD平均值和標(biāo)準(zhǔn)差

(a) 5種對比算法的收斂性能曲線對比

(b) 5種對比算法收斂性能的盒圖對比

表4 所有對比算法實驗結(jié)果總結(jié)

綜上分析，算法MaPSO-EFR在采用的大多數(shù)測試問題上獲得了比對比算法更好的表現(xiàn)，表明提出的算法具有較好的收斂性和多樣性，具有一定的競爭性。

3.4 參數(shù)K的討論

參數(shù)K是一個平衡算法收斂性與多樣性的控制參數(shù)。為了討論其對算法評價結(jié)果的影響，除了上述反世代距離指標(biāo)，另外還采用世代距離指標(biāo)(GD)、空間評價指標(biāo)(SP)這兩個指標(biāo)。其中，世代距離指標(biāo)用于評價算法的收斂性能，所得解集的世代距離評價指標(biāo)值越小越好；空間評價指標(biāo)用于反映算法所得解集分布的均勻性，空間評價指標(biāo)值越小，解集的分布越均勻。在測試實例DTLZ3的5，8，10，15目標(biāo)上，分別取[1，15]之間的整數(shù)來對參數(shù)K進(jìn)行實驗，對于每個K值，算法程序運行30次并取平均值。最終結(jié)果如圖2所示。

(a) 參數(shù)K對世代距離指標(biāo)的影響

(b) 參數(shù)K對空間評價指標(biāo)的影響

(c) 參數(shù)K對指標(biāo)反世代距離的影響

從圖2(a)和(b)可以看出，算法MaPSO-EFR在DTLZ3的不同目標(biāo)數(shù)上的世代距離和空間評價指標(biāo)隨著參數(shù)K的增加呈下降趨勢，說明參數(shù)K的取值對算法的收斂性和多樣性有較大影響。而在圖2(c)中，參數(shù)K在取值3以后，反世代距離指標(biāo)變化幅度趨于穩(wěn)定，也就是說，參數(shù)K對綜合指標(biāo)反世代距離的影響比較小。從而說明了針對不同目標(biāo)維數(shù)，需要設(shè)定不同的K值，才可以使得算法性能表現(xiàn)更佳。

4 結(jié)束語

針對高維多目標(biāo)優(yōu)化問題，考慮集成適應(yīng)度排序是一種非帕累托支配排序方式，提出了一種集成適應(yīng)度排序的高維多目標(biāo)粒子群優(yōu)化算法。首先，對種群P每個個體與預(yù)先定義的均勻分布參考點W進(jìn)行關(guān)聯(lián)，求出每個個體的最近權(quán)向量L，并選出前K個權(quán)向量，采用基于懲罰的邊界交叉方法作為適應(yīng)度函數(shù)，對部分個體進(jìn)行非遞減排序，并根據(jù)個體的優(yōu)劣進(jìn)行排序編號。然后，對較差的個體進(jìn)行剔除，并保存精英個體到外部檔案中進(jìn)入下一次迭代更新。最后，討論了參數(shù)K值對算法性能的影響。與4種先進(jìn)的高維多目標(biāo)進(jìn)化優(yōu)化算法在標(biāo)準(zhǔn)測試集DTLZ和WFG的實驗表明，算法MaPSO-EFR在大多數(shù)測試實例上的性能表現(xiàn)優(yōu)于對比算法，具有較好的收斂性與多樣性。但是算法MaPSO-EFR在一些退化的多目標(biāo)測試問題上表現(xiàn)不理想，接下來工作將繼續(xù)改善算法MaPSO-EFR的性能。