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

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

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

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

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

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

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

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

輸出：每個(gè)解的全局排序序數(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*為理想點(diǎn)，θ為罰參數(shù)，λi為權(quán)重向量，x為決策向量。

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

2.1 算法描述

基于帕累托支配的高維多目標(biāo)優(yōu)化算法在求解高維多目標(biāo)優(yōu)化問(wèn)題時(shí)具有一定的局限性，而基于非帕累托支配的排序方法的主要優(yōu)勢(shì)在于放棄了帕累托支配方法中較為嚴(yán)格的個(gè)體優(yōu)劣衡量標(biāo)準(zhǔn)，通過(guò)新的比較準(zhǔn)則對(duì)個(gè)體收斂性能的優(yōu)劣進(jìn)行比較與排序，以實(shí)現(xiàn)非支配個(gè)體之間的性能比較，可有效提升對(duì)精英個(gè)體的選擇壓力，提高了算法的收斂精度，而且使得算法選擇壓力的提升不受目標(biāo)維數(shù)增加的影響，從根本上解決了目標(biāo)維數(shù)增多時(shí)精英個(gè)體選擇壓力退化的問(wèn)題。基于此，提出一種集成適應(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)生一組均勻分布的參考點(diǎ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，參考點(diǎn)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)生一組均勻分布的參考點(diǎn)W，并初始化外部檔案，在while循環(huán)中，使用雙搜索策略的粒子群優(yōu)化算法對(duì)種群P進(jìn)行更新，得到新種群P，然后更新檔案，利用差分進(jìn)化算子對(duì)檔案中的個(gè)體進(jìn)行交叉、變異等操作，得到子群，最后再次更新檔案，直到循環(huán)迭代滿足結(jié)束條件。外部檔案更新流程如算法3所示，首先通過(guò)集成適應(yīng)度排序獲取各向量排序后的序號(hào)，計(jì)算出當(dāng)前種群的大小，以及參考點(diǎn)數(shù)量，進(jìn)入while循環(huán)中，通過(guò)種群與參考點(diǎn)的關(guān)系對(duì)最小的序號(hào)進(jìn)行選擇，刪除較差的個(gè)體，直到滿足循環(huán)終止條件，最后將精英個(gè)體保存在外部檔案中。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 測(cè)試函數(shù)與評(píng)價(jià)指標(biāo)

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

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

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

為了更直觀地評(píng)價(jià)算法MaPSO-EFR性能表現(xiàn)，以5種對(duì)比算法在實(shí)例DTLZ3的15目標(biāo)上的測(cè)試為例，采用折線圖、盒圖等可視化工具進(jìn)行說(shuō)明。其中，圖1(a)描繪出了各對(duì)比算法的反世代距離指標(biāo)隨著迭代次數(shù)的增加而變化的折線，可以明顯地看出對(duì)比算法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)將各對(duì)比算法在DTLZ3的15目標(biāo)上的30次實(shí)驗(yàn)數(shù)據(jù)用盒圖的方式進(jìn)行了說(shuō)明。直觀上可以看出，算法NSGA-III的表現(xiàn)最差，算法EFRRR和算法MaPSO-EFR的性能表現(xiàn)相似。

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

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

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

表4 所有對(duì)比算法實(shí)驗(yàn)結(jié)果總結(jié)

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

3.4 參數(shù)K的討論

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

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

(b) 參數(shù)K對(duì)空間評(píng)價(jià)指標(biāo)的影響

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

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

4 結(jié)束語(yǔ)

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