基于小生境聚類的改進(jìn)MOEA-D 算法*

湯愷祥，許 峰

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001）

2006年，Deb[1]和 Brockhoff[2]指出，現(xiàn)實(shí)中的許多優(yōu)化問題是多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP），而其中的高維多目標(biāo)優(yōu)化問題（Many-dimensional Multi-objective Optimization Problem，MaOP）的比重越來越高。多目標(biāo)進(jìn)化算法（Multi-objective Evolutionary Algorithm，MOEA）在如今的研究領(lǐng)域中是公認(rèn)處理MOP 的有效優(yōu)化方法，但MOEA 在處理MaOP 時就顯得能力不足，其表現(xiàn)在處理問題時性能的低下，對真實(shí)的Pareto 前沿表示不準(zhǔn)確，結(jié)果分布性不均勻和穩(wěn)定性不理想等問題。

目前有兩大類可以較好的處理MaOP 的MOEA。一類是基于精英選擇的多目標(biāo)進(jìn)化算法，另一類是基于多目標(biāo)分解的多目標(biāo)進(jìn)化算法。

2007年，Zhang[3]提出了一種基于分解的演化多目標(biāo)進(jìn)化算法；2010年，GU[4]提出一種新的權(quán)重向量設(shè)計(jì)機(jī)制；2014年，Qi[5]提出了一種基于分解的動態(tài)調(diào)節(jié)權(quán)重向量的多目標(biāo)進(jìn)化算法（MOEA-D-AWA）；2016年，Blasco[6]在進(jìn)行高維Pareto 前沿分析時引入了相似距離；2017年，Bi[7]在一種多目標(biāo)進(jìn)化算法中引入了小生境方法；2018年，Monalisa[8]在一種多目標(biāo)進(jìn)化算法中引入了聚類思想。

在MOEA-D-AWA 中并沒有考慮優(yōu)化種群替換方法，本文提出在MOEA-D-AWA 基礎(chǔ)上引入小生境與聚類思想來優(yōu)化種群替換，以達(dá)改進(jìn)算法分布性的目的。利用標(biāo)準(zhǔn)測評函數(shù)對改進(jìn)算法進(jìn)行了性能測試，并與相關(guān)算法進(jìn)行了比較。

1 MOEA-D 算法

MOEA-D 算法主要用于解決MaOP，其思路是將多目標(biāo)優(yōu)化問題分解成若干個單目標(biāo)子問題，然后利用多目標(biāo)進(jìn)化算法處理這些若干個子問題。其主要概念及步驟如下[3]：

1.1 權(quán)重向量的生成

MOEA-D 使用單格子算法生成較均勻的權(quán)重向量，且滿足以下條件：

1.2 構(gòu)建聚合函數(shù)的TCH 分解方法

TCH 方法（Tchebycheff）：權(quán)重向量 λi中子問題表示為：

1.3 鄰域的選取與作用

在MOEA-D 中，計(jì)算權(quán)重向量間的歐式距離獲取子問題的鄰域。算法利用鄰域定義，獲取父代解，繁殖子代解，且保證解的多樣性。

MOEA-D 基本步驟如下：

步驟1 初始化。得到初始種群P，權(quán)重向量λ，各個權(quán)重向量鄰域內(nèi)T 個向量等。

步驟2 更新操作，隨機(jī)選取第i 個體，在第i 個體的鄰域中隨機(jī)選取兩個個體進(jìn)行交叉變異操作，獲得新個體y。更新z*即參考點(diǎn)和鄰域中的解：判斷新個體的適應(yīng)度是否優(yōu)于第i 個體鄰域中個體的適應(yīng)度，優(yōu)于則替代鄰域個體，劣于則不更新。

步驟3 終止，滿足條件則輸出非支配解集；否則轉(zhuǎn)到步驟2。

2 MOEA-D-AWA 算法

MOEA-D 的結(jié)構(gòu)模塊主要有：（1）優(yōu)化問題分解；（2）演化算子；（3）子代更新；（4）權(quán)重向量，許多改進(jìn)研究就以這些模塊為基礎(chǔ)進(jìn)行。從文獻(xiàn)[9]中的大量數(shù)值實(shí)驗(yàn)顯示，MOEA-D 在求解大規(guī)模高維多目標(biāo)優(yōu)化問題時性能欠佳。因此，Qi[5]與Ma 提出了基于分解的動態(tài)調(diào)節(jié)權(quán)重向量的多目標(biāo)進(jìn)化算法（MOEA-D-AWA）用于改進(jìn)以上問題。

動態(tài)調(diào)節(jié)權(quán)重向量在MOEA-D 框架的基礎(chǔ)上進(jìn)行改進(jìn)的，其基本原理并不復(fù)雜?；舅悸窞椋豪媚壳敖饧鸵粋€非支配解集動態(tài)調(diào)節(jié)權(quán)重向量。主要過程為：已知當(dāng)前種群P 及種群大小為N，計(jì)算P 中每個個體的擁擠度，擁擠度計(jì)算方法見文獻(xiàn)[5]。當(dāng)種群P 中有過于擁擠的群（超出自定義數(shù)值）時，刪除擁擠度最高的一個個體解并重新計(jì)算P 中每個個體的擁擠度。如果種群P

動態(tài)調(diào)節(jié)的權(quán)重向量生成公式如下：

動態(tài)調(diào)節(jié)權(quán)重向量的方法可以對MOEA-D 算法獲得的解起到提高分布性和保持種群多樣性的作用。

3 基于小生境聚類的改進(jìn)MOEA-D-AWA

文獻(xiàn)[5]中研究了MOEA-D-AWA 算法對MOEA-D算法的改進(jìn)效果，并將其改進(jìn)的算法與其他相關(guān)的多目標(biāo)進(jìn)化算法的結(jié)果進(jìn)行了比較。

從權(quán)重向量選擇的方向分析，該算法的優(yōu)點(diǎn)是動態(tài)調(diào)節(jié)權(quán)重向量的方法可以在PF 復(fù)雜（如不連續(xù)的PF 或具有尖峰的PF）的情況下，很大程度上保證權(quán)重向量的均勻性和確保解集均勻分布在PF 上。但是從種群替換的方向分析，該算法中，交叉變異產(chǎn)生一個好子代可以取代大部分差的子代，這就導(dǎo)致種群多樣性變差，即種群替換方向存在缺陷。因此，在利用該算法時，合理的方式是動態(tài)調(diào)節(jié)權(quán)重向量和優(yōu)化種群替換這兩種策略合理互補(bǔ)。在滿足原優(yōu)點(diǎn)的同時，盡可能確保種群多樣性和解的分布性。

在文獻(xiàn)[5]的基礎(chǔ)上，本文提出一種基于小生境中聚類的改進(jìn)MOEA-D-AWA 算法，具體如下：

定義清除算法（小生境）相關(guān)距離：

個體 i=（x1，x2，...，xn）與個體 j=（y1，y2，...，yn）的距離公式為：

小生境中心點(diǎn)為 X1，X2，...，Xm其余個體為 Y1，Y2，...YM，D（Xm，YM）表示中心點(diǎn)與個體間的相關(guān)距離。相關(guān)距離越大，個體與中心點(diǎn)越近。

DBSCAN 聚類密度算法[11]中的相關(guān)定義：

參數(shù)：（1）epsilon 表示點(diǎn)的鄰域半徑；（2）minPts 鄰域內(nèi)至少包含個體的數(shù)量。

根據(jù)參數(shù)，樣本中的個體將分成三類：

（1）NBHD（p,epsilon）>=minPts 為核點(diǎn)；（2）NBHD（p,epsilon）

基于小生境聚類的改進(jìn)MOEA-D（NC-MOEA-D）步驟如下：

步驟1 初始化。得到初始種群P，權(quán)重向量λ，各個權(quán)重向量的鄰域內(nèi)T 個向量等。

步驟2 更新操作。

（1）對父代種群Pt，根據(jù)MOEA-D-AWA 交叉變異方式得到U。

（2）對U 采取清除算法（小生境）操作，即首先對U中個體根據(jù)適應(yīng)度值進(jìn)行降序排列，將第一個個體作為第一個小生境中心。其次利用上述相關(guān)距離方法判斷當(dāng)前個體到所有小生境中心的最短距離是否大于自定義數(shù)值，是則形成新的小生境，不是則加入最近的小生境中。最后小生境生成完畢，多出的個體降低其適應(yīng)值。

（3）將生成的每個小生境進(jìn)行DBSCAN 聚類操作，即首先在小生境中任選一個點(diǎn)，計(jì)算其NBHD（p，epsilon）值并判斷是否為核點(diǎn)。是則建立類，不是則成為外圍點(diǎn)。其次，處理其余點(diǎn)直到將density-reachable 點(diǎn)也加入類中（當(dāng)外圍點(diǎn)加入類中時狀態(tài)改為邊緣點(diǎn)）。最后重復(fù)上述操作直到遍歷完所有點(diǎn)。

（4）在每個小生境中只保留聚類中心（即核點(diǎn)）和外圍點(diǎn)，得到子代種群Qt。

（5）將Pt和Qt合并且根據(jù)聚合函數(shù)更新父代種群Pt+1。

步驟3 若滿足終止條件，則輸出最終的解，否則重復(fù)步驟2。

4 數(shù)值實(shí)驗(yàn)與算法性能評測

4.1 算法性能評測指標(biāo)

MOEA 性能評測指標(biāo)分為四種[10]，具體為容量指標(biāo)、收斂性指標(biāo)、多樣性指標(biāo)、收斂性和多樣性綜合指標(biāo)。根據(jù)本文新算法的優(yōu)化點(diǎn)為分布性的改進(jìn)，考慮采用分布性指標(biāo)（S）與綜合指標(biāo)（IGD）。定義如下：

其中P*表示理想PF，P 表示算法求得的近似PF，d（v，P）表示個體v 到P 中個體的最小歐幾里德距離。IGD指標(biāo)越小，算法分布性越好。

4.2 數(shù)值實(shí)驗(yàn)結(jié)果

下面用基于小生境聚類的MOEA-D 算法對Osyczka2 和Viennet4 兩個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行優(yōu)化仿真，并將結(jié)果與經(jīng)典的MOEA-D 算法的結(jié)果進(jìn)行比較，從而檢驗(yàn)改進(jìn)算法的性能。

圖1、圖2 和圖3、圖4 分別給出了用 NC-MOEA-D和 MOEA-D 得到的 Osyczka2 和 Viennet4 的 Pareto 最優(yōu)前沿。

表1 和表2 分別給出了用NC-MOEA-D 和MOEAD 得到的Osyczka2 和Viennet4 的性能評測指標(biāo)。

表1 Osyczka2 的MOEA-D/NC-MOEA-D 性能指標(biāo)

圖1 Osyczka2 的 Pareto 最優(yōu)前沿（NC-MOEA-D）

圖2 Osyczka2 的 Pareto 最優(yōu)前沿（MOEA-D）

圖3 Viennet4 的 Pareto 最優(yōu)前沿（NC-MOEA-D）

圖4 Viennet4 的 Pareto 最優(yōu)前沿（MOEA-D）

表2 Viennet4 的MOEA-D/NC-MOEA-D 性能指標(biāo)

從圖1～圖4 及表1 和表2 可以清楚地看出，基于小生境聚類的MOEA-D 算法與常規(guī)MOEA-D 算法相比，在分布性和均勻性指標(biāo)上有了一定程度的改善，能夠有效地處理復(fù)雜的多目標(biāo)優(yōu)化問題。