分組策略下的高維目標協同進化算法

王麗萍,俞 維，邱飛岳

1(浙江工業大學 計算機科學與技術學院，杭州 310023)2(浙江工業大學 管理學院，杭州 310023)3(浙江工業大學 教育科學與技術學院，杭州 310023)4(浙江省可視媒體智能處理技術研究重點實驗室，杭州 310023)

1 引 言

在調度優化[1]、路徑規劃[2]等現實問題中，通常存在兩個及兩個以上目標相互沖突，這類問題被稱之為多目標優化問題(Multi-objective optimization problems，MOPs).文獻[3]將目標數大于等于4的MOPs定義為高維目標優化問題(Many-Objective Optimization Problems，MaOPs).

為求解多目標優化問題，國內外研究者通過模擬自然界行為，提出了一系列智能啟發式算法[4].基于支配關系的多目標進化算法是解決多目標優化問題的有效方法之一，但在處理高維目標優化問題時，非支配解在種群中的比例急劇增大，使得原有選擇機制功能退化，選擇壓力急劇下降，阻礙種群收斂至前沿(Pareto Front，PF)，算法性能出現不同程度的下降[5].

這使得越來越多的學者開始關注MaOPs，并提出了一系列改進算法，代表性的算法如下：基于支配關系的高維目標進化算法，在傳統的支配算法基礎上，通過重新定義支配關系，如RPD-NSGA-II[6]、θ-dominance[7],或者引入新的多樣性評價機制，如NSGA-III[8]、SPEA/R[9],以此提高算法性能；基于指標的高維目標進化算法，根據指標值對個體進行排序，如AR-MOEA[10]、MaOEA/IGD[11]等；基于分解的高維目標進化算法，將復雜多目標優化問題分解為多個單目標或多目標優化問題，以此協同優化，如MOEA/D-LWS[12]、MOEA/AD[13]、MOEA/D-AW[14].

近幾年，文獻[15]提出一種偏好引導地協同優化的思想(Preferences-inspired co-evolutionary algorithms,PICEAs).區別于基于個體間非支配關系的選擇機制，PICEAs引入一組隨機偏好集，利用隨機偏好集與個體的支配關系，協同優化偏好集與種群.文獻[16]將此概念進行實例化，提出目標向量引導地協同進化算法(PICEAg),將目標向量(Goal vector)作為偏好集，利用目標向量引導解集收斂.文獻[17]表明PICEAg在高維WFG、DTLZ等測試問題上表現較好.但該算法在搜索過程中存在一定缺陷.在進化前期，基于種群與目標向量集間支配關系的選擇機制能選擇出收斂性較好的解，引導種群快速收斂；但在進化后期，在此機制的選擇下，PICEAg易忽視分布性較好但全局搜索能力較弱的解集，其種群多樣性降低.

在進化過程中，種群收斂性與多樣性間的平衡是制約算法性能的重要因素.文獻[18]從優化分解的角度,提出權重向量引導的協同進化算法，利用權重向量對優化問題進行分解，并將其作為偏好，引導權重向量與候選解協同進化.文獻[19]從適應度評價的角度，引入距離算子，提高算法多樣性.文獻[20]從目標向量集的角度，通過動態調整目標向量集上下界值，引導種群快速收斂.

本文將種群進行分組，劃分成若干個子種群，利用外部存檔集中種群的收斂性與多樣性信息，逐代評估子種群進化潛力，以此動態調整目標向量分布，從而提出一種基于目標向量兩階段分配策略的高維目標協同進化算法，最大化利用有限計算資源，維持種群收斂性與多樣性間的平衡，提高算法性能.

2 研究背景

2.1 高維目標優化問題及相關定義

高維多目標優化問題的表示如下:

(1)

其中，X=(x1,x2,…,xd)表示d維決策變量；F(x)是決策變量到目標空間的映射，m表示目標數；gi(x)表示第i個約束函數，當k=0時，F(x)為無約束高維目標優化問題.

定義1(Pareto占優).假設a與b均為MaOPs的可行解，當且僅當fj(a)

定義2(非支配解).決策空間中不存在b，使得f(b)

定義3(非支配解集).決策空間中所有非支配解構成非支配解集.

定義4(Pareto前沿).所有非支配解映射至目標空間所構成的曲面稱為Pareto前沿.

2.2 PICEA-g

文獻[13]所提算法PICEA-g將目標向量作為偏好集，通過目標向量與候選解之間的支配關系計算其各自適應度值，以此選擇優秀的候選解及目標向量進入下一代，引導目標向量與候選解共同進化.具體流程見算法1，其中適應度值計算公式可見文獻[16].

算法1.PICEA-g

輸入：種群大小N；目標向量大小Ng;最大進化代數maxgen

輸出：種群P

1.P=Initial(N); //初始化產生大小為N的種群

2.G=Generate_Goal(P,Ng); //產生Ng個目標向量

3.FORt=1TOmaxgen

4.PC=Genetic(P,N);//交叉變異產生大小為N的子代種群PC

5.unionP=P∪PC;//子代與父代種群合并

6.GC=Generate_Goal(unionP,Ng);//產生Ng個目標向量

7.unionG=G∪GC;//父子代目標向量合并

8. [fit_unionP,fit_unionG]=Calculate_fitness(unionP,unionG); //計算種群與目標向量適應度值

9. [P,G]=Select(unionP,unionG,fit_unionP,fit_unionG);//選擇適應度值大的N個個體及Ng個目標向量

10.ENDFOR

2.2.1 目標向量分配策略

在算法1中，函數Generate_Goal()表示目標向量的產生.首先在目標空間中尋找各目標上的最大最小值F(P)upper=(maxf1(P),maxf2(P),…,maxfm(P))及F(P)lower=(minf1(P),minf2(P),…,minfm(P))，將其作為目標向量產生的上下界值，如圖1(b)所示，其中P=(X1,X2,…,XN).然后根據公式(2)產生Ng個目標向量，其中rand(0,1)表示[0,1]之間的隨機數.

G=F(P)lower+rand(0,1)*(F(P)upper-F(P)lower)

(2)

圖1 進化前中期DTLZ6問題的解集分布Fig.1 Solution sets obtained by 2-objective DTLZ6 problem in the earlier and middle process of evolutionary

2.2.2 缺陷分析

圖1表示在進化前中期DTLZ6問題的解集分布.從圖1(a)和圖1(b)中可以發現，不同區域上的解收斂至前沿的時間不同，解集在不同區域上的分布也存在差異.處于前沿中心位置的解集分布較稀疏，甚至部分前沿上無解集；而處于前沿邊緣位置的解集分布較密集.而原始的目標向量產生方式忽略了這一特性，等概率地為個體分配目標向量，使得中心區域上的所分配的計算資源是難以滿足該區域上解集的進化，不利于提高算法的收斂性與多樣性.此外，在進化不同階段，種群選擇側重點是不同的[21].在進化前期，種群傾向于選擇收斂性較好的解集，有助于帶動其他解加速收斂；而在進化中后期，當解集基本收斂至前沿時，則傾向于選擇多樣性較好的解集，提高種群多樣性.

綜上所述，在進化過程中，原有目標向量產生策略無法滿足種群進化的需要，不能較好地平衡分布性與收斂性間的關系，降低算法解集質量.因此，需要一種自適應的目標向量分配策略，在進化的不同階段為不同區域上的個體分配目標向量，以此平衡種群收斂性與分布性，提高算法性能.

3 基于分組策略的高維目標協同進化算法

本文結合解集的多樣性及收斂性信息，設計了基于子種群進化潛力的判斷機制，在進化過程中動態調整目標向量分布，提出基于分組策略的高維目標協同進化算法，最大化利用有限計算資源，提高算法性能.

3.1 種群分組策略

對于復雜度不同的測試問題，在同等條件下，所獲得的第一層非支配解數量不同.相較而言，難優化的問題會獲得較少非支配解；相反，簡單問題所獲得的非支配較多.因此本文將歸一化的非支配解數量作為評估子種群進化潛力的指標之一.此外，當解集在目標空間分布較廣時，所求解集的邊界點一般會分布在前沿的邊界上，因此所求解集的邊界點間的歐幾里得距離最大.但是隨著目標維度的增加，歐幾里得距離的計算復雜度也隨之增加，因此計算子種群內個體距離參考向量的最大角度，將歸一化的最大角度作為評估的另一指標，以此衡量子種群分布情況.通常情況下，初始產生的解集往往距離前沿面較遠，在一段時間的搜索后，解集基本能收斂到PF.在此時，多樣性成為制約算法性能的重要因素，當解集多樣性較差時，易產生相似個體，不利于產生收斂性較好的個體，導致搜索停滯甚至后退.算法在進化的不同階段存在搜索傾向.因此，本文將進化代數作為評估子種群進化潛力的影響因子.子種群進化潛力值如公式(3)所示.

(3)

其中，t表示當前進化代數；tmax表示最大進化代數；NDi表示第i個子種群中非支配解數量；NNDmax和NNDmin分別表示NNDi(i=1,2,…,Nspace)中的最大最小值；βi表示第i個子種群中個體距離參考向量的最大角度；βmax和βmin分別表示βi(i=1,2,…,d)中的最大最小值；Nspace表示子種群數.當進化代數t無限趨近于0,PEi主要取決于子種群的收斂性；當進化代數t無限趨近于tmax,PEi主要取決于子種群的分布性.當子種群中非支配解數量NNDi越小時，PEi值越小，則該子種群進化潛力越大；當子種群中βi越小時，PEi值越小，則該子種群進化潛力越大.

以圖2為例,假設存在3個參考向量V1、V2、V3和6個個體P1～P6.θ21、θ22、θ23分別表示個體P2與參考向量的夾角，其中θ21角度最小，因此將個體P2劃分到子種群SP1，并以此類推，將種群進行劃分，個體P1和P2屬于子種群SP1，個體P3、P4和P5屬于子種群SP2，個體P6屬于子種群SP3.對于子種群SP1，其非支配解數量為2，個體P2與向量的角度大于個體P1，則該子種群的最大角度β1=θ21.子種群進化潛力判斷機制如算法2所示.

算法2.種群分組策略

輸入：種群P={P1,P2,…,PN}、子種群數Nspace

輸出：子種群SP={SP1,SP2,…,SPNspace}、子種群進化潛力值PE={PE1,PE2,…,PENspace}

//將種群分組，劃分為若干個子種群SP//

1.初始化產生參考向量V={V1,V2,…,VNspace};

2.θ=;//計算個體與參考向量的角度,θij(i=1,2,…,N;j=1,2,…,Nspace)表示個體Pi到參考向量Vj的角度值

3.FORi=1TON

5.SPk=SPk∪{Pi};//將個體Pi劃分到子種群SPk

6.SP_θk=SP_θk∪{θik};//保留個體Pi與參考向量Vk的角度值

7.ENDFOR

//計算子種群進化潛力值PE//

8.FORj=1TONspace

9. [NDj,NNDj]=Find_best(SPj);//找到子種群中的非支配解集NDj，并計算其個數NNDj

10.βj=max(SP_θj);//在子種群SPj內找到距離參考向量Vj最遠的個體，將該個體與參考向量Vj的角度值記為βj

11.ENDFOR

12.FORj=1TONspace

13.PEj= Potential_evolution(NND,β,t);//根據公式(3)計算子種群進化潛力；

14.ENDFOR

圖2 種群劃分和潛力值計算示意圖Fig.2 Division of the population and calculation of evolutionary potential

3.2 目標向量分配策略

子代目標向量的產生主要分為兩個步驟：首先，根據子種群進化潛力值選擇合適子種群，并為子種群分配一定數量的目標向量，加大此子種群的選擇壓力，實現資源的最大化利用；其次，計算已產生的目標向量數|GC|，在整個目標空間內產生剩余數量的目標向量Ng-|GC|，為剩余子種群一定的選擇壓力，防止未被選擇的剩余子種群產生退化現象,具體如算法3所示.

算法3.目標向量分配策略

輸入：子種群SP={SP1,SP2,…,SPNspace}及其進化潛力PE={PE1,PE2,…,PENspace},混合種群unionP,目標向量產生個數Ng,子種群數Nspace

輸出：子代目標向量集GC

2.FORj=1 TONspace

3.IFPEj

5.ENDIF

6.GC=GC∪GC′;

7.ENDFOR

8.ranGC=Generate_Goal(jointP,Ng-|GC|);

9.GC=GC∪ranGC;

3.3 算法流程

本文在高維目標協同進化算法基礎上，引入一種種群分組策略和目標向量分配策略，具體過程如算法4所示.

算法4.PICEA-g

輸入：種群大小N;目標向量大小Ng;最大進化代數maxgen

輸出：種群P

1.P=Initial(N)

2.G=Generate_Goal(P,Ng);

3.FORt=1TOmaxgen

4.PC=Genetic(P,N);

5.unionP=P∪PC;

6. [SP,PE]=Judge_potention(P,Nspace]);//種群分組策略

7.GC=Twostage_Goal(unionP,SP,PE,Ng,Nspace);//目標向量分配策略

8.unionG=G∪GC;

9. [fit_unionP,fit_unionG]=Calculate_fitness (unionP,unionG);

10. [P,G]=Select(unionP,unionG,fit_unionP,fit_unionG);

11.ENDFOR

4 仿真結果與分析

為驗證基于兩階段資源分配策略的高維目標協同進化算法的有效性，選擇DTLZ1-7系列函數[22]作為測試問題集，將本文所提算法與同類型PICEAg在3、5、7、10及15維DTLZ函數上進行仿真對比實驗.為保證實驗的公平和合理性，兩種算法均在PlatEMO平臺[23]上獨立運行30次，種群規模為100，目標向量數為100，最大進化代數為300，利用運行30后指標方差評估算法穩定性，并采用the Wilcoxon test方法對仿真結果進行顯著性分析，其中，“+”、“=”、“-”分別表示在顯著水平為5%下優于、近似于、劣于改進后算法.

表1 改進前后算法在DTLZ1-7測試問題上的GD與SP指標值Table 1 GD and SP value of algorithms on DTLZ1-7 problems

4.1 性能評價指標

本文采用世代距離(Generation Distance，GD)[24]及空間分布(Spacing，SP)指標[25]對算法所得解集進行收斂性及多樣性評估.

世代距離：所得解集到真實前沿地距離，如公式(4)所示.其中，n表示解集個數，di表示前沿中離第i個個體最近的向量與第i個個體的歐幾里得距離.GD值越小，表明解集離前沿越近，收斂性越佳.

(4)

空間分布：算法所求解集的多樣性，如公式(5)所示.其中，n表示解集個數，di表示前沿中離第i個個體最近的向量與第i個個體的歐幾里得距離.SP值越小，表明算法所得解集在目標空間中均勻分布.

(5)

4.2 算法改進前后對比分析

表1表示各算法在DTLZ系列測試問題上的GD與SP指標對比結果，其中字體加粗表示最優結果，‘M’表示目標數，‘D’表示變量數.DTLZ1和DTLZ3均是具有多模態特性的難優化測試問題，即存在多個局部最優解，其產生的初始種群遠離前沿，較難收斂至PF.對于DTLZ1測試問題，除10維目標外，改進后算法在收斂性及多樣性上均優于對比算法；對于DTLZ3測試問題，除15維目標外，改進后算法在收斂性及多樣性上均優于對比算法，在10維DTLZ3測試上其收斂性優于對比算法.從結果中可以發現，改進后算法在多模態測試問題上取得較好結果，通過動態調整目標向量分布，有目的的增加子種群的選擇壓力，使其快速收斂.

圖3 改進前后算法在3、5、7、10、15維DTLZ1問題上的GD指標BOX圖Fig.3 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ1 problems

圖4 改進前后算法在3、5、7、10、15維DTLZ4問題上的GD指標BOX圖Fig.4 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ4 problems

圖5 改進前后算法在3、5、7、10、15維DTLZ7問題上的GD指標BOX圖Fig.5 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ7 problems

DTLZ4、DTLZ6及DTLZ7均屬于有偏函數，使得分布均勻的決策變量映射到目標空間后不再均勻，該特性增加了維持種群多樣性難度.另外DTLZ7還是一個混合的不連續優化問題.從結果中發現，在DTLZ4測試問題上，改進后算法所求解集的收斂性顯著優于原算法PICEAg,其多樣性略優于對比算法；對于DTLZ6及DTLZ7測試問題，除5維目標空間外，改進后算法在收斂性及多樣性上顯著優于對比算法.尤其在高維目標優化中，相較于PICEAg算法，改進后算法的算法性能并未顯著減弱.這是由于，在進化前期改進后算法根據子種群的收斂性分配目標向量，而在進化后期主要根據其多樣性分配，從而為多樣性較差的子種群提供分配較多計算資源，以此找到多樣性較好的解集，提高種群多樣性.

圖6 改進前后算法在3維DTLZ1-7問題上的前沿對比圖Fig.6 Solution sets obtained by PICEAg and PICEAg-PE on 3-objective DTLZ1-7 problem

圖3-圖5分別表示改進前后算法在DTLZ1、DTLZ4及DTLZ7測試問題上的GD指標box圖.從圖3中可以發現，3、5及7維DTLZ1測試問題上，改進后算法的GD平均線及box圖的長度均低于原算法.表明改進后算法在3、5及7維DTLZ1測試問題上的算法魯棒性優于對比算法.在圖4 中，對于大多數維度的DTLZ4測試問題，改進后算法的GD平均值優于對比算法，但是其魯棒性并未明顯提高.由此可見改進算法不適用于求解DTLZ2這類測試問題.在圖5中，除5維DTLZ7外，改進后算法在其余維度的測試問題上的GD平均值均優于原算法，BOX圖中的上下界值離平均值線較近，產生的異常值個數也遠遠少于原算法.由此可見，對于DTLZ7這類測試問題，改進后算法的收斂性與魯棒性明顯提高.

圖6表示改進前后算法在3維DTLZ1-7測試問題上的前沿對比圖.由圖中可以發現，在DTLZ1、DTLZ6及DTLZ7測試問題上，PICEAg算法所求解集僅收斂至前沿面的部分區域，解集多樣性極差；在DTLZ3測試問題上，PICEAg算法所得解集遠離前沿且多樣性較差；在DTLZ5測試問題上，PICEAg算法所得解集基本收斂至前沿，但部分前沿上解集多樣性較差.相比于對比算法，在以上測試問題中,PICEAg-PE所得解集具有較好的收斂性與多樣性.PICEAg-PE算法根據非支配解集隱含信息，確定子種群進化潛力，調整目標向量分布，平衡種群的收斂與多樣性，提高算法性能.

5 結束語

為平衡進化過程中種群收斂性與多樣性的沖突，本文設計一種基于分組策略的高維協同進化算法，調整目標向量分布，平衡種群收斂與多樣性.根據仿真實驗，結果表明改進后算法所求解集在收斂性及多樣性上有顯著提高.下一步將對參考向量的分布進行調整，以此適應不同優化問題，增強對前沿形狀的敏感性，使目標空間的劃分更加合理.