基于網格投影的超多目標進化算法

高智闊,陳未如,彭弗楠

(1.沈陽化工大學 計算機科學與技術學院,遼寧 沈陽 110142;2.遼寧省化工過程工業(yè)智能化技術重點實驗室,遼寧 沈陽 110142)

0 引 言

在社會生產和工程應用等領域,存在著許多的優(yōu)化問題涉及對多個目標進行優(yōu)化,并且絕大多數(shù)目標之間是相互關聯(lián)并相互沖突的。當目標數(shù)為2或3時,這類問題被稱為多目標優(yōu)化問題(multi-objective optimization problem,MOP)[1]。當目標數(shù)大于3時,這類問題被稱為超多目標優(yōu)化問題(many-objective optimization problem, MaOP)[2]。社會實際應用中出現(xiàn)了大量的MaOP例子,如路徑規(guī)劃問題[3]、電力優(yōu)化問題[4]、零件加工問題[5]等。

針對多目標優(yōu)化問題,研究人員結合進化算法提出了很多多目標進化算法(multi-objective evolutionary algorithms,MOEAs),根據(jù)進化機制[6]不同可將MOEAs分為以下三種:基于支配關系的NSGA-II[7]、基于分解的MOEA/D[8]、基于性能評價指標的IBEA[9]。當目標數(shù)量過多時,使用這些算法求解超多目標優(yōu)化問題的性能降低,在超多目標空間中保持解集的分布性和收斂性也很困難[10]。研究人員針對以上問題提出了很多超多目標進化算法(many-objective evolutionary algorithms,MaOEAs):如NSGA-III[11]在NSGA-II的基礎上,引入了參考點針對臨界支配層求解個體;R2-EMOA[12]針對種群采用快速非支配排序方法,針對臨界層使用R2指標篩選個體;MOEA/DP[13]結合MOEA/D思想,針對投影面分解求解個體;KnRVEA[14]為子種群引入拐點自適應策略和參考向量相關聯(lián)協(xié)同進化每一個子種群;NSGA/P[15]結合MOEA/P[16]的投影面思想,對NSGA-II進行投影支配改進;SPEA/R[17]采用目標空間分解為參考向量的策略,使用多樣性優(yōu)先收斂性第二的選擇策略篩選個體。

隨著目標維數(shù)的增加,種群內的個體大都是互不支配的。使用基于支配關系的多目標進化算法和超多目標進化算法求解個體時會存在解集收斂性和分布性不足的情況,如NSGA-II和NSGA-III。為解決上述問題,該文提出了一種基于網格投影的超多目標進化算法。該算法采用MOEA/P算法的投影思想針對目標空間進行降維操作,將目標空間劃分為投影維目標空間和自由維目標空間,降低了對超多目標優(yōu)化問題的求解難度,針對自由維目標空間引入網格適應度選取策略[18],使得算法求得的解集具有良好的收斂性和分布性。

1 背景知識

1.1 基本概念

多目標優(yōu)化問題在一般情況下可以描述為最小化問題,數(shù)學描述如下:

(1)

(2)

其中,Fi(i=1,2,…,M)是需要最小化的第i個目標;Ω是決策空間。在公式(2)中,g是包含J個等式和不等式的約束函數(shù),h是包含K個等式的約束函數(shù);x=(x1,x2,…,xn)是決策空間中的決策向量;當目標個數(shù)M的值大于3時,稱其為超多目標優(yōu)化問題。

定義1 Pareto支配:針對決策空間中的兩個個體x和y,有x支配y(記作xy),當且僅當x和y滿足:

(3)

定義2 Pareto最優(yōu)解:針對決策空間中的一個個體x*,當且僅當x*不被該決策空間中的其他任何個體x支配時,則稱x*為Pareto最優(yōu)解。

定義3 Pareto最優(yōu)解集:由Pareto最優(yōu)解組成的集合稱為Pareto最優(yōu)解集,即:

P*={x*}={x∈Ω|?x'∈Ω,x'x}

(4)

定義4 Pareto前沿:P*中的全部個體映射到目標空間的集合,稱為Pareto前沿,即:

PF*={F(x)=(F1(x),F2(x),…,FM(x))|

x∈P*}

(5)

1.2 MOEA/P算法框架

MOEA/P算法采用投影的思想,根據(jù)決策者的需求將目標空間分解為兩部分,分別是投影面和自由維,以三維目標問題為例,如圖1所示。其中投影面是決策者主要側重的目標集,而自由維的目標集則在劃分投影面的基礎上進一步求解。

圖1 將目標空間分解為投影面和自由維

1.3 GrEA算法思想

GrEA算法采用以個體為中心計算的思想,將個體在目標空間中的目標值計算取代為網格坐標值計算,將網格排序(GR)、網格擁擠距離(GCD)和網格坐標點距離(GCPD)作為個體篩選條件,篩選出目標空間中收斂性和分布性較優(yōu)的個體。

2 GPEA算法

受MOEA/P算法和GrEA算法的啟發(fā),該文針對投影維目標空間引入MOEA/P算法的投影思想,針對自由維目標空間引入GrEA算法中的網格適應度策略篩選個體,設計了一種基于網格投影的超多目標進化算法(GPEA)。

2.1 算法基本思想

GPEA算法的基本思想是使用MOEA/P算法框架,將目標空間分解成投影維目標空間和自由維目標空間兩部分。其中投影維目標空間被劃分成若干個投影格。求解過程中,針對各投影格分別進化。在每代進化中,篩選落入投影格內的個體,再根據(jù)GrEA算法的網格思想將自由維目標空間均勻分段成若干自由格,計算個體相對于自由格的空間屬性,利用個體非支配排序結果和自由維目標空間個體篩選策略對這些個體進行綜合篩選。

2.1.1 自由維目標空間個體篩選策略

自由維目標空間個體選擇策略是以個體在自由維目標空間內的自由格排序(FGR)作為首要篩選條件,自由格擁擠距離(FGCD)作為次要篩選條件,自由格坐標點距離(FGCPD)作為最后的篩選條件。

在對第i個自由維目標分配自由格坐標時,自由格下界、上界對應的目標值lbi和ubi見公式(6)和公式(7)。

lbi=mini(P)-(maxi(P)-mini(P))/(2×g)

(6)

ubi=maxi(P)+(maxi(P)-mini(P))/(2×g)

(7)

其中,mini(P)和maxi(P)是種群P在第i個自由維目標中的最小值和最大值,g是對自由維目標空間中各目標的分段數(shù)。

自由格在第i個自由維目標中的長度為di,計算方法見公式(8)。

di=(ubi-lbi)/g

(8)

這樣,每一自由維的目標都被均勻分割成g個分段,所有自由維上的各個分段組合成自由格。如果把每個自由維各分段標號為0,1,…,g-1,用這些分段標號作為個體的自由格坐標。

定義5 自由格坐標:個體x所落入的自由格的坐標。個體x在第i個自由維上的自由格坐標是該個體所落入自由格在第i自由維上的分段標號。個體x的自由格坐標計算方法見公式(9)。

FGi(x)=?(FFi(x)-lbi)/di」

(9)

其中,lbi是自由格下界,di是自由格長度,它們的計算方法見式(6)和式(8),FF(x)=(FF1(x),FF2(x),…,FFf(x))為個體x在f個自由維組成的空間中對應的各自由維坐標向量,FFi(x)則是該向量在第i自由維上的分量。

定義6 自由格距離:自由格距離FGD用于表示個體x和y在自由維目標空間中的自由格坐標的相對位置關系,自由格距離FGD由公式(10)給出。

(10)

當個體x和y的自由格距離值小于自由維數(shù)f時,將個體y作為個體x的鄰居。在自由維目標空間中,個體x的鄰居組成的集合為FN(x)。

定義7 自由格排序:將個體在各個自由維的自由格坐標值的總和作為個體的自由格排序值。公式(11)為個體在自由維目標空間中的自由格排序計算公式。

(11)

定義8 自由格擁擠距離:將個體x在自由維目標空間上與其所有鄰居之間的距離作為個體x自由格擁擠距離,其中N(x)是個體x的鄰居組成的集合,f是自由維數(shù)。公式(12)為個體在自由維目標空間中的自由格擁擠距離計算公式。

(12)

定義9 自由格坐標點距離:將個體在自由維目標空間上的自由維目標值與自由格邊界點目標值的歐氏距離作為自由格坐標點距離。公式(13)為個體在自由維目標空間中的自由格坐標點距離計算公式。

FGCPD(x)=

(13)

2.1.2 投影格適應度

投影格適應度是指個體x相對于投影格中心點Z的位置關系,個體的投影格適應度計算方法由公式(14)給出。

GP(x)=

(14)

其中,投影格中心點向量Z=(Z1,Z2,…,Zp);FP為歸一化后的投影維目標空間,對應個體x在該空間的歸一量為FP(x)=(FP1(x),FP2(x),…,FPp(x));p為投影維目標空間目標數(shù),k為投影維分段數(shù)。

2.2 算法框架

GPEA算法框架描述如下:

GPEA算法

輸入:

M(目標個數(shù)),

N(種群大小),

E(最大進化代數(shù)),

DS(標決策空間),

g(自由維自由格分段數(shù)),

k(投影維投影格分段數(shù))

輸出:目標解集OP

過程:

步驟1:目標空間劃分。

根據(jù)DS設置將目標空間劃分為投影維目標空間和自由維目標空間,其中投影維目標空間目標數(shù)為p,自由維目標空間目標數(shù)為f;投影維目標空間劃分投影格數(shù)為kp,自由維目標空間的自由格數(shù)為gf;劃分投影格并為投影格分配投影格序號i(i=1,2,…,kp)。

步驟2:初始化種群。

設投影格序號i=1,為其初始化大小為N的種群P1;

步驟3:種群進化。

步驟3.1:對種群Pi內的個體進行交叉變異產生子代個體,合并父代和子代的個體組成新種群CPi;計算種群CPi內所有個體的目標函數(shù)值,對投影維目標空間進行歸一化操作,為所有個體計算投影格適應度;

步驟3.2:從種群CPi中選擇N個良好的個體。

將種群CPi內全部個體投影到投影維目標空間中按照個體的投影格適應度進行分類,將落入投影格內的個體放入列表PL中,將落入投影格外的個體放入列表FL中;如果列表PL內的個體數(shù)大于等于N,則執(zhí)行步驟3.2.1,否則執(zhí)行步驟3.2.2;

步驟3.2.1:針對列表PL內的個體在自由維目標空間中進行非支配排序,生成的R個非支配子集F1,F2,…,FR;將非支配子集內個體依次放入列表LN中并保證LN內個體數(shù)小于N,直到Fr,當Fr放入列表LN時,LN內個體數(shù)剛好大于等于N;計算非支配子集Fr中個體的自由格排序FGR、自由格擁擠距離FGCD、自由格坐標點距離FGCPD,利用自由維目標空間個體篩選策略依次選擇較優(yōu)的個體放入列表LN中,直至列表LN內的個體數(shù)正好等于N。轉步驟3.3;

步驟3.2.2:將列表PL內的所有個體放入到列表LN中,依次選擇列表FL內投影適應度較優(yōu)的個體依次放入到列表LN中,直至列表LN內的個體數(shù)量正好等于N。轉步驟3.3;

步驟3.3:判斷投影格種群Pi是否達到了最大進化代數(shù)E:

若種群Pi未達到最大進化代數(shù),則將列表LN中的個體作為投影格i的新一代種群Pi,繼續(xù)執(zhí)行步驟3的種群進化操作;

若種群Pi達到了最大進化代數(shù),則將列表LN中的個體并入目標解集OP中,并在OP中只保留非支配個體。此時,若i

步驟4:輸出OP。

3 實驗與分析

3.1 測試問題

該文選取DTLZ[19]測試問題集中的DTLZ1-DTLZ4測試問題作為比較的基礎,其中DTLZ1和DTLZ3測試函數(shù)為算法收斂到Pareto前沿創(chuàng)造了很多困難,DTLZ2和DTLZ4測試函數(shù)用于測試算法處理不同形狀問題的能力。這些測試問題都可以擴展到任意個數(shù)的目標和決策向量,用其來驗證所提算法的性能。

3.2 性能指標

為了評價算法的綜合性能,采用了反向迭代距離指標(IGD)[20]來評價算法求得解集的收斂性和分布性。IGD衡量的是算法求得的解集與真實Pareto前沿的個體之間的最小距離的平均值,計算IGD需要預先得到該問題的一組均勻的Pareto前沿真實解集。

IGD指標的計算公式為:

(15)

(16)

其中,S為算法求得的一組Pareto近似解集;P*為一組均勻采樣的Pareto前沿點集;x是P*中的個體;s是S中的個體;|P*|是Pareto前沿點集中個體的數(shù)量;si是Pareto近似解集中個體s在第i個目標中的目標值;xi是Pareto前沿點集中個體x在第i個目標中的目標值;dist(x,s)是個體x到S最近的個體的歐氏距離。IGD的值越小,算法求得的解集越接近Pareto真實前沿,表明算法求得的解集具有較好的收斂性和多樣性。

3.3 實驗設計

為了驗證該算法的性能,實驗選取MOEA/D、GrEA、NSGA-III、NSGA/P、MOEA/DP作為對比,在DTLZ1～DTLZ4測試問題的3、5、7、10目標上進行實驗。

交叉變異參數(shù)設置:為所有算法使用模擬二進制交叉操作和多項式變異操作,其中交叉概率設置為1,變異概率設置為1/n,n是決策變量個數(shù),交叉變異的分布指標都設置為20。

算法自身對比參數(shù)設置:在10目標的DTLZ1～DTLZ4測試問題,決策變量個數(shù)n=12,進化代數(shù)E=6 000,種群大小N=220,性能指標選用IGD的實驗條件下進行算法對比參數(shù)設置。為探究投影維目標空間設置對算法性能的影響,設置投影維目標空間數(shù)p依次為1,2,…,7,投影維分段數(shù)k=2,自由維分段數(shù)g=8;為探究投影維分段數(shù)k對算法性能的影響,設置k的值依次為1,2,…,7,自由維分段數(shù)g=8;為探究自由維分段數(shù)g對算法的影響,設置g的值依次為4,6,8,10,12,14,16,投影維分段數(shù)k=2。以上每組測試獨立運行20次。

不同算法對比參數(shù)設置:設置所有測試問題對應的投影維分段數(shù)k=2,自由維分段數(shù)g=8;針對3目標問題,決策變量個數(shù)n=6,種群大小N=190,進化代數(shù)E=3 000,投影維數(shù)p=1;針對5目標問題,決策變量個數(shù)n=8,種群大小N=210,進化代數(shù)E=4 000,投影維數(shù)p=2;針對7目標問題,決策變量個數(shù)n=10,種群大小N=210,進化代數(shù)E=5 000,投影維數(shù)p=3;針對10目標問題,決策變量個數(shù)n=12,種群大小N=220,進化代數(shù)E=6 000,投影維數(shù)p=4;每組測試獨立運行30次。

3.4 結果與分析

圖2表示在投影維分段數(shù)k和自由維分段數(shù)g不變的情況下,投影維數(shù)p變化對IGD值變化的曲線。從圖中可以看出,當投影維數(shù)小于3時,IGD值逐漸減小,使用投影思想可以提高算法的求解效果,降低了算法在自由維目標空間中求解難度;但是在投影維數(shù)超過3以后,IGD的值開始緩慢增加,在投影維數(shù)過多的時候,個體在自由維目標空間中的收斂性和分布性相對片面地表示個體在目標空間中的收斂性和分布性,此時算法的求解效果較差;當投影維數(shù)約占目標總數(shù)的1/3時,算法的求解效果較好。

圖2 GPEA在DTLZ測試問題上不同 投影維數(shù)的IGD變化曲線

圖3表示在投影維數(shù)p和自由維分段數(shù)g不變的情況下,投影維分段數(shù)k變化對IGD值變化的曲線。從圖中可以看出,隨著投影維分段數(shù)k的增加,IGD的值越好;在投影維分段數(shù)k設置為2及以后,IGD值的變化維持在了一個很小的范圍之內;劃分投影格對種群進化起促進作用,隨著投影維劃分段數(shù)的增加,進化的投影格也就越多,種群進化的時間成本也就越高,從算法求解時間方面考慮,建議將投影維分段數(shù)k設置為2。

圖3 GPEA在DTLZ測試問題上不同投影 分段數(shù)的IGD變化曲線

圖4表示在投影維數(shù)p和投影維分段數(shù)k不變的情況下,自由維分段數(shù)g變化對IGD值變化的曲線。從圖中可以看出,隨著自由維分段數(shù)g的增加,IGD的值越好;在自由維分段數(shù)g設置為8及以后,IGD的值得變化維持在了一個很小范圍內;自由維網格坐標劃分對種群的進化起促進作用,隨著自由維劃分段數(shù)g的增加,單位網格坐標范圍減小,對應個體的網格排序值差異越大,在網格適應度計算中網格排序占據(jù)主導地位。從算法的求解效率方面考慮,建議將自由維分段數(shù)g設置為8。

圖4 GPEA在DTLZ測試問題上不同 網格分段數(shù)的IGD變化曲線

表1給出了所有算法在DTLZ1～DTLZ4測試問題上得到的IGD均值。從實驗結果中可以看出:GPEA在DTLZ1～DTLZ4測試問題上表現(xiàn)良好,在超多目標問題空間中,種群的收斂性和多樣性得到了很好的均衡,以下針對每個DTLZ測試問題詳細分析算法的性能表現(xiàn)。

表1 不同算法在目標數(shù)不同的DTLZ測試問題上獲得的IGD均值

續(xù)表1

DTLZ1和DTLZ3測試問題具有較多的局部帕累托前沿(Pareto Front,PF),為算法求解此類問題創(chuàng)造了更多的障礙。DTLZ2和DTLZ4測試問題具有不同形狀的PF,為算法求解此類問題維持種群多樣性提供了困難。從表1可以看出,GPEA在大多數(shù)目標上取得了很好的結果,原因是投影維目標空間的投影格分解策略可以協(xié)助種群跳出局部PF,網格投影策略可以使種群收斂到Pareto前沿,網格適應度篩選策略可以使種群均勻的覆蓋到PF,提高了算法求解此類問題的魯棒性。

圖5為各算法在7目標DTLZ4測試問題上求得最終解集的平行坐標圖,從圖5可以看出GPEA在收斂性和分布性上取得了較好的結果;MOEA/D存在某目標維解丟失的情況;GrEA和NSGA-III在某目標維上存在局部解集;NSGA/P和MOEA/DP的收斂性和分布性稍弱于GPEA。

4 結束語

針對超多目標優(yōu)化問題使用多目標進化算法難以保證種群的收斂性和多樣性的問題,提出了一種基于網格投影的超多目標進化算法。通過將目標空間拆分,分別構建投影維目標空間和自由維目標空間,使用投影格個體篩選策略和自由維目標空間個體篩選策略保持種群的收斂性和多樣性,解決了MOEA求解超多目標優(yōu)化問題難以平衡種群收斂性和多樣性的問題。通過對標準測試函數(shù)設置不同參數(shù)實驗,與MOEA/D、GrEA、NSGA-III、MOEA/DP和NSGA/P進行對比,實驗結果表明,GPEA能夠很好地處理超多目標優(yōu)化問題。下一步工作是改進投影格個體選擇策略,研究一種新的自由維目標空間適應度函數(shù),并將算法與實際應用更好地結合起來。