基于小生境聚類的改進MOEA-D 算法*

湯愷祥，許 峰

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

2006年，Deb[1]和 Brockhoff[2]指出，現實中的許多優化問題是多目標優化問題（Multi-objective Optimization Problem，MOP），而其中的高維多目標優化問題（Many-dimensional Multi-objective Optimization Problem，MaOP）的比重越來越高。多目標進化算法（Multi-objective Evolutionary Algorithm，MOEA）在如今的研究領域中是公認處理MOP 的有效優化方法，但MOEA 在處理MaOP 時就顯得能力不足，其表現在處理問題時性能的低下，對真實的Pareto 前沿表示不準確，結果分布性不均勻和穩定性不理想等問題。

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

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

在MOEA-D-AWA 中并沒有考慮優化種群替換方法，本文提出在MOEA-D-AWA 基礎上引入小生境與聚類思想來優化種群替換，以達改進算法分布性的目的。利用標準測評函數對改進算法進行了性能測試，并與相關算法進行了比較。

1 MOEA-D 算法

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

1.1 權重向量的生成

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

1.2 構建聚合函數的TCH 分解方法

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

1.3 鄰域的選取與作用

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

MOEA-D 基本步驟如下：

步驟1 初始化。得到初始種群P，權重向量λ，各個權重向量鄰域內T 個向量等。

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

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

2 MOEA-D-AWA 算法

MOEA-D 的結構模塊主要有：（1）優化問題分解；（2）演化算子；（3）子代更新；（4）權重向量，許多改進研究就以這些模塊為基礎進行。從文獻[9]中的大量數值實驗顯示，MOEA-D 在求解大規模高維多目標優化問題時性能欠佳。因此，Qi[5]與Ma 提出了基于分解的動態調節權重向量的多目標進化算法（MOEA-D-AWA）用于改進以上問題。

動態調節權重向量在MOEA-D 框架的基礎上進行改進的，其基本原理并不復雜。基本思路為：利用目前解集和一個非支配解集動態調節權重向量。主要過程為：已知當前種群P 及種群大小為N，計算P 中每個個體的擁擠度，擁擠度計算方法見文獻[5]。當種群P 中有過于擁擠的群（超出自定義數值）時，刪除擁擠度最高的一個個體解并重新計算P 中每個個體的擁擠度。如果種群P

動態調節的權重向量生成公式如下：

動態調節權重向量的方法可以對MOEA-D 算法獲得的解起到提高分布性和保持種群多樣性的作用。

3 基于小生境聚類的改進MOEA-D-AWA

文獻[5]中研究了MOEA-D-AWA 算法對MOEA-D算法的改進效果，并將其改進的算法與其他相關的多目標進化算法的結果進行了比較。

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

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

定義清除算法（小生境）相關距離：

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

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

DBSCAN 聚類密度算法[11]中的相關定義：

參數：（1）epsilon 表示點的鄰域半徑；（2）minPts 鄰域內至少包含個體的數量。

根據參數，樣本中的個體將分成三類：

（1）NBHD（p,epsilon）>=minPts 為核點；（2）NBHD（p,epsilon）

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

步驟1 初始化。得到初始種群P，權重向量λ，各個權重向量的鄰域內T 個向量等。

步驟2 更新操作。

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

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

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

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

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

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

4 數值實驗與算法性能評測

4.1 算法性能評測指標

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

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

4.2 數值實驗結果

下面用基于小生境聚類的MOEA-D 算法對Osyczka2 和Viennet4 兩個標準測試函數進行優化仿真，并將結果與經典的MOEA-D 算法的結果進行比較，從而檢驗改進算法的性能。

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

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

表1 Osyczka2 的MOEA-D/NC-MOEA-D 性能指標

圖1 Osyczka2 的 Pareto 最優前沿（NC-MOEA-D）

圖2 Osyczka2 的 Pareto 最優前沿（MOEA-D）

圖3 Viennet4 的 Pareto 最優前沿（NC-MOEA-D）

圖4 Viennet4 的 Pareto 最優前沿（MOEA-D）

表2 Viennet4 的MOEA-D/NC-MOEA-D 性能指標

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