分組策略下的高維目標(biāo)協(xié)同進(jìn)化算法

王麗萍,俞 維，邱飛岳

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

1 引 言

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

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

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

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

在進(jìn)化過程中，種群收斂性與多樣性間的平衡是制約算法性能的重要因素.文獻(xiàn)[18]從優(yōu)化分解的角度,提出權(quán)重向量引導(dǎo)的協(xié)同進(jìn)化算法，利用權(quán)重向量對優(yōu)化問題進(jìn)行分解，并將其作為偏好，引導(dǎo)權(quán)重向量與候選解協(xié)同進(jìn)化.文獻(xiàn)[19]從適應(yīng)度評價的角度，引入距離算子，提高算法多樣性.文獻(xiàn)[20]從目標(biāo)向量集的角度，通過動態(tài)調(diào)整目標(biāo)向量集上下界值，引導(dǎo)種群快速收斂.

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

2 研究背景

2.1 高維目標(biāo)優(yōu)化問題及相關(guān)定義

高維多目標(biāo)優(yōu)化問題的表示如下:

(1)

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

定義1(Pareto占優(yōu)).假設(shè)a與b均為MaOPs的可行解，當(dāng)且僅當(dāng)fj(a)

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

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

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

2.2 PICEA-g

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

算法1.PICEA-g

輸入：種群大小N；目標(biāo)向量大小Ng;最大進(jìn)化代數(shù)maxgen

輸出：種群P

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

2.G=Generate_Goal(P,Ng); //產(chǎn)生Ng個目標(biāo)向量

3.FORt=1TOmaxgen

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

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

6.GC=Generate_Goal(unionP,Ng);//產(chǎn)生Ng個目標(biāo)向量

7.unionG=G∪GC;//父子代目標(biāo)向量合并

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

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

10.ENDFOR

2.2.1 目標(biāo)向量分配策略

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

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

(2)

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

2.2.2 缺陷分析

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

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

3 基于分組策略的高維目標(biāo)協(xié)同進(jìn)化算法

本文結(jié)合解集的多樣性及收斂性信息，設(shè)計了基于子種群進(jìn)化潛力的判斷機制，在進(jìn)化過程中動態(tài)調(diào)整目標(biāo)向量分布，提出基于分組策略的高維目標(biāo)協(xié)同進(jìn)化算法，最大化利用有限計算資源，提高算法性能.

3.1 種群分組策略

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

(3)

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

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

算法2.種群分組策略

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

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

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

1.初始化產(chǎn)生參考向量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

//計算子種群進(jìn)化潛力值PE//

8.FORj=1TONspace

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

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

11.ENDFOR

12.FORj=1TONspace

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

14.ENDFOR

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

3.2 目標(biāo)向量分配策略

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

算法3.目標(biāo)向量分配策略

輸入：子種群SP={SP1,SP2,…,SPNspace}及其進(jìn)化潛力PE={PE1,PE2,…,PENspace},混合種群unionP,目標(biāo)向量產(chǎn)生個數(shù)Ng,子種群數(shù)Nspace

輸出：子代目標(biāo)向量集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 算法流程

本文在高維目標(biāo)協(xié)同進(jìn)化算法基礎(chǔ)上，引入一種種群分組策略和目標(biāo)向量分配策略，具體過程如算法4所示.

算法4.PICEA-g

輸入：種群大小N;目標(biāo)向量大小Ng;最大進(jìn)化代數(shù)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);//目標(biāo)向量分配策略

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 仿真結(jié)果與分析

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

表1 改進(jìn)前后算法在DTLZ1-7測試問題上的GD與SP指標(biāo)值Table 1 GD and SP value of algorithms on DTLZ1-7 problems

4.1 性能評價指標(biāo)

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

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

(4)

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

(5)

4.2 算法改進(jìn)前后對比分析

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

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

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

圖5 改進(jìn)前后算法在3、5、7、10、15維DTLZ7問題上的GD指標(biāo)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均屬于有偏函數(shù)，使得分布均勻的決策變量映射到目標(biāo)空間后不再均勻，該特性增加了維持種群多樣性難度.另外DTLZ7還是一個混合的不連續(xù)優(yōu)化問題.從結(jié)果中發(fā)現(xiàn)，在DTLZ4測試問題上，改進(jìn)后算法所求解集的收斂性顯著優(yōu)于原算法PICEAg,其多樣性略優(yōu)于對比算法；對于DTLZ6及DTLZ7測試問題，除5維目標(biāo)空間外，改進(jìn)后算法在收斂性及多樣性上顯著優(yōu)于對比算法.尤其在高維目標(biāo)優(yōu)化中，相較于PICEAg算法，改進(jìn)后算法的算法性能并未顯著減弱.這是由于，在進(jìn)化前期改進(jìn)后算法根據(jù)子種群的收斂性分配目標(biāo)向量，而在進(jìn)化后期主要根據(jù)其多樣性分配，從而為多樣性較差的子種群提供分配較多計算資源，以此找到多樣性較好的解集，提高種群多樣性.

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

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

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

5 結(jié)束語

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