基于最小距離和聚合策略的分解多目標進化算法

李二超，李康偉

（蘭州理工大學電氣工程與信息工程學院，蘭州 730050）

0 引言

進化算法是一種基于群體智能的啟發式優化算法，它通過對生物進化的繁殖、變異、重組和選擇等過程的模擬來達到優化的效果。這種算法對于求解多目標優化問題具有很好的效果，基于進化算法，研究者們相繼提出了很多解決不同多目標優化問題（Many-objective Optimization Problem,MOP）［1］的優化算法。

以非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm，NSGA）［2］為代表的第一代進化算法，基于Pareto 支配關系以及多樣性保留策略對個體進行選擇，該算法在選擇解之前先將種群根據支配關系進行分層，以便能夠有更大的機會選擇出更好的個體遺傳到下一代，并且在選擇解的過程中加入了適應度共享策略，保持了解的多樣性。但是，NSGA無法很好地保證高質量的解遺傳到下一代，而使一些好的解丟失，并且需要指定共享參數使其依賴于共享的概念。因此，在非支配排序遺傳算法（NSGA）、向量評估遺傳算法（Vector Evaluated Genetic Algorithm，VEGA）［3］、小生境Pareto 遺傳算法（Niched Pareto Genetic Algorithm，NPGA）［4］等基礎上引入精英保留策略提出了第二代進化算法，例如強度帕累托進化算法（Strength Pareto Evolutionary Algorithm，SPEA）［5］、改進的強度帕累托進化算法（Strength Pareto Evolutionary Algorithm Two，SPEA2）［6］、基于非支配排序的多目標進化算法（Nondominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ）［7］等。第二代進化算法的代表算法NSGA-Ⅱ與NSGA 類似，首先將整個種群根據Pareto 非支配排序進行分層，其中前一層的解支配后一層的解，而同層的解之間互不支配；在選擇解時使用精英解保留策略逐層選擇解以保證收斂性，在最后一層采用擁擠距離的選擇方法以保證解的多樣性。Cai 等［8］為了評估超多目標優化問題的最優前沿逼近真實前沿的程度，提出了一種基于參考向量的多樣性指標（Diversity Indicator based on Reference vectors，DIR）。在DIR 中，首先生成一組均勻分布的參考向量，然后根據每個解關聯的參考向量數量計算解的覆蓋率，最后由所有解的覆蓋率的標準差決定解的多樣性。DIR 的值越小，多樣性越好。將DIR 與NSGA-Ⅱ結合提出了DIR 增強的NSGA-Ⅱ（DIR-enhanced NSGA-Ⅱ，d-NSGA-Ⅱ）。這種第二代多目標進化算法得到的近似解不能均勻地分布在Pareto 最優前沿上。為了提高多樣性，Deb 等［9］在NSGA-Ⅱ算法中引入參考點，將每個解關聯在相應的參考向量上，提出了基于參考點的多目標遺傳算法——NSGA-Ⅲ（Nondominated Sorting Genetic Algorithm Ⅲ），NSGA-Ⅲ為第三代進化算法的代表算法，它結合了非支配排序和基于參考點選擇的優點，在保證收斂性的基礎上提高了種群的分布性［10-11］。Bi 等［12］在NSGA-Ⅲ的基礎上加入了基于消元算子的新的選擇機制，提出了基于消元算子的加強NSGA-Ⅲ多目標進化算法——NSGA-Ⅲ-EO（NSGA-Ⅲbased on Elimination Operator），此算法增加了解的選擇壓力，并且提高了種群的多樣性，但是上述這類基于支配的多目標進化算法在解決高維問題時由于各目標之間互不支配［13-14］，從而使選擇壓力降低。

基于參考點分解的多目標進化算法設置了一組參考向量，將目標空間分成若干個子區域來求解［15-16］。在算法當中每個子區域相當于一個子問題，通過對每個子種群同時進行優化來達到優化的效果。Zhang 等［17］通過將一個多目標優化問題分解成一組單目標優化問題，提出了一種基于分解的多目標進化算法（Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D）。MOEA/D 算法在多目標優化問題尤其是高維多目標優化問題的收斂性和分布性等方面表現出了很好的效果，但是這種算法依然存在一些不足，比如在更新鄰域子問題時會使其相鄰子問題以外表現較好的解丟失，一個解同時出現在多個鄰域當中而降低了解的多樣性［18］，為此近年來許多學者在此算法上做了更多的研究。Liu 等［19］將均勻分布的參考向量分解成多個子空間，提出將一個多目標優化問題分解為若干個簡單多目標子問題的多目標進化算法MOEA/D-M2M（MOEA/D based on decomposing MOP into a number of simple Multi-objective subproblems），其中，每個子空間對應一定大小的子種群，明顯增加了解的多樣性，而在解的選擇過程中加入了Pareto 非支配排序方法使其均勻性有所下降。Li 等［20］將MOEA/D 與NSGA-Ⅱ結合，并且加入了差分進化（Differential Evolution，DE）的策略，另外，為了改善MOEA/D 的收斂性能，將局部搜索的思想融入MOEA/D 算法中，提出了解決復雜Pareto 解集的多目標進化算法——MOEA/D-DE（MOEA/D based on Differential Evolution），此算法使用聚合的方法選擇解的過程雖然提高了解的均勻性但是多樣性仍有不足。本文針對基于支配的多目標進化算法選擇壓力不高和均勻性差以及MOEA/D 多樣性不足的問題，將均勻分布的參考向量根據角度分解成多個子空間來增加多樣性，并且引入分兩階段基于最小距離和聚合方法選擇解的策略（Two-stage selection strategy based on minimum Distance and Aggregation method，TDA）來平衡收斂性、多樣性以及均勻性，提出了基于最小距離和聚合策略的分解多目標進化算法——MOEATDA。

1 問題描述

1.1 多目標優化

多目標優化問題的各目標之間相互沖突，并且隨著目標個數的增加問題的復雜度越高，且越不易求解［21-22］。多目標優化通常用于生產調度和路徑規劃等實際問題當中，通常情況下優化過程不能使每個目標同時達到最優，而只能找到一組折中解來表示最優解，因此多目標優化的目的是如何用特定的算法來找到一組最優解。一般情況下，將兩目標和三目標的問題稱為多目標優化問題，將三目標以上的問題稱為超多目標優化問題［23］。

多目標優化算法有最大化目標函數值和最小化目標函數值兩種［24］，此處以最小化目標函數值為例：

其中：Ω代表決策空間，x=(x1，x2，…，xn)T∈Ω為n維決策變量；Θ代表目標空間，F(x) ∈Θ為M個目標函數；gi(x) ≤0(i=1，2，…，p)為p個不等式約束條件；hi(x)=0(i=1，2，…，q)為q個等式約束條件。以下是幾個關于Pareto支配［25-26］的定義。

Pareto 支配對于任意兩個解x，y∈Ω，若?i∈{1，2，…，M} 有fi(x) ≤fi(y)，且?j∈{1，2，…，M} 滿足fj(x) ＜fj(y)，則x支配y（記為x?y）。

Pareto 最優解 如果x∈Ω，不存在y∈Ω使得y?x成立，則稱x是Pareto最優解。

Pareto 最優解集 所有Pareto 最優解組成的解集，即P={x|x∈Ω∧??y∈Ω，y?x}。

Pareto 最優前沿 Pareto 最優解對應的目標函數值所組成的解集稱為Pareto 最優前沿，即：PF={F(x)=(f1(x)，f2(x)，…，fM(x))T|x∈P}。

1.2 分解方法

在高維多目標優化算法中通常采用分解的方法將一個多目標優化問題分解為一組單目標問題進行求解，在本文中采用常用的基于懲罰的邊界交叉法（Penalty-based Boundary Intersection，PBI）作為分解方法。第i個子問題定義如式（2）所示：

其中：θ為懲罰因子；‖ · ‖為L2范數；wi=(w1，w2，…，wm)T為分解后第i個子問題的權重向量。

1.3 權重向量的生成

在多目標優化算法中常用比較成熟的Das 和Dennis 系統方案［27］分解技術，在單位超平面上生成一組均勻分布的參考點，參考點的數目N和每維目標上的劃分份數H的關系如式（3）所示：

其中m表示目標的維數，每一個參考向量wi(i=1，2，…，m)中的所有元素之和為1，并且每一維元素都取值于{0/H，1/H，…，H/H}。圖1 表示3 目標問題參考點生成的示意圖，r1、r2和r3為目標的維數。

圖1 權重向量的生成Fig.1 Generation of weight vectors

2 本文算法

2.1 基本思想和主要框架

基于分解的多目標進化算法對于解的分布性有很大的提升，但是在使用聚合方法選擇解的過程中降低了解的多樣性。本文在基于參考向量分解技術的基礎上根據角度將種群分解成一組特定大小的子種群，然后分兩階段在每個子種群內使用最小距離和聚合的方法選擇解，這種分解技術可以有效提高種群的多樣性。為了提高進化效率，在生成新解的過程中引入鄰域，由于鄰域中的最優解較為相似，所以在交叉變異的過程中能夠促進進化，并且能夠降低計算復雜度和提高局部搜索能力。

MOEA-TDA 主要分為5 個步驟：1）初始化種群Pop、權重向量集W；2）求解交叉鄰域A；3）生成新解；4）根據角度分解子種群；5）根據TDA 策略選擇解。MOEA-TDA 總框架偽代碼如算法1所示。

算法1 MOEA-TDA總框架。

2.2 基于聚合的交叉鄰域

在MOEA/D 中采用均勻分布的權重向量生成了不變的鄰域，使得每個子問題都含有很多鄰近的子問題，鄰域內的子問題具有相似的最優解，所以對子問題的進化有一定的幫助。為了進一步提高算法的進化效率和局部搜索能力，提出基于聚合的鄰域選擇策略。在MOEA/D 等經典的多目標優化算法中每個子問題的鄰域都是根據相鄰的權重向量所確定的，這樣使得進化前期每個權重向量所對應的子問題都不是離其最近的，所以在差分進化的過程當中局部搜索能力不高，本算法中提出的基于聚合的交叉鄰域策略不再是將離權重向量的歐氏距離最近的個體作為鄰域解，而是計算出權重向量與每個個體之間的PBI 值，然后選出PBI 值最小的T個解為鄰域，這時鄰域隨著每一代的進化而發生自適應變化，有利于提高種群的局部搜索能力。偽代碼如算法2所示。

算法2 基于聚合的交叉鄰域。

在進化過程中對于每個權重向量除了原本與其相關聯的最優解外，再找出與權重向量的PBI 值最小的兩個解來進行差分進化。本文使用MOEA/D-DE 中提出的差分進化和多項式變異來產生子代個體，差分進化中有交叉、變異和選擇幾個主要的步驟，這種進化算法比較適合解決連續的優化問題，它能引導新解產生的方向。

2.3 基于角度的目標空間分解策略

首先在目標空間中產生N個均勻分布的參考向量，再根據參考向量將目標空間劃分為指定數量的子區間，每一個子區間對應唯一的子種群，其中每一代的種群采用基于角度的劃分方式將目標空間劃分為N個子區間{Ω1，Ω2，…，ΩN} 以提高所求最優解集的多樣性，對于每一個子區間：

基于角度的目標空間分解策略原理如圖2 所示，如圖選出任意兩個權重向量wi和wj，在其周圍分布著6 個不同的個體。在傳統的多目標優化算法當中一般使用基于歐氏距離的計算方法找出與權重向量相關聯的個體，例如，在分解過程中根據歐氏距離只會將x2和x4劃分到同一區間內，這種分解方法使算法的收斂性有所提高，但是在維持多樣性方面有一定的缺陷。而使用基于角度的目標空間的分解策略劃分子空間時，在同一子區間內不僅包含x2和x4，而且也包含x6，這樣在選擇解的過程中會很大程度上維持種群的多樣性。

圖2 基于角度的目標空間的分解策略Fig.2 Decomposition strategy of target space based on angle

2.4 基于最小距離和聚合策略選擇解

根據角度分解目標空間之后會使每個權重向量關聯到一個子區間，因此可以在每個子區間內分兩階段基于最小距離和聚合策略單獨選擇解。由于在分解完子區間后有一些區間內關聯不到個體，所以根據此策略選擇解時，需要分以下兩種情況進行：

1）子區間內有關聯個體。

在這種情況下，當進化代數達到臨界代數之前基于最小距離選擇解，以提高算法的收斂性；當進化代數達到臨界代數之后基于PBI 聚合的策略選擇解，以提高解的分布性。在本算法中基于距離和基于角度選擇解的臨界代數是根據多次實驗結果測試出來的。這里的距離由式（6）給出，公式當中的各參數與式（2）中相同。

2）子區間內無關聯個體。

當子區間內無關聯個體時，不能直接選擇解，此時需要計算子代和父代組成的混合種群在該區間對應的權重向量下的PBI值，然后選擇出混合種群中最小的PBI值所對應的個體作為該區間的最優解。兩種情況下的算法流程如圖3所示。

圖3 基于最小距離和聚合策略的解選擇Fig.3 Solution selection based on minimum distance and aggregation strategy

圖3 中：gen為當前運行代數，Cgen為臨界代數，nC為第i個子種群中的個體數，subpop（i）為第i個子種群，w（i）為第i個子種群相關聯的權重向量，Mixpop為子代和父代的混合種群，Pop為最終輸出種群。

3 實驗和結果分析

為了測試MOEA-TDA 的性能，分別選取了ZDT［28］和DTLZ［29］系列測試問題。其中：ZDT 系列測試問題主要選取具有代表性的ZDT1～ZDT4 和ZDT6；而DTLZ 系列測試問題選取DTLZ1～DTLZ5，主要測試算法在高維情況下的性能。

ZDT1 和ZDT4 為連續凸型測試函數，但前者的偏約束個數大于后者；ZDT2為連續凹型測試函數；而ZDT3為前沿斷續的測試函數；以上均為基因型均勻的測試函數。ZDT6為連續凸型但基因型非均勻的測試函數。對于DTLZ1，目標函數值位于一個線性超平面上，并且難以收斂到最優解；DTLZ2 的Pareto 最優解集位于單位球的第一象限，它可用于探測一個MOEA 對高維目標的進化搜索能力；DTLZ3 不僅包含局部Pareto 最優解集還包含一個全局Pareto 最優解集，可測試全局收斂能力；DTLZ4 測試MOEA 維持一個良好的分布解集的能力［30］；DTLZ5 的Pareto 最優解集聚集于一條曲線上，用于測試MOEA 收斂到一條曲線的能力。本文主要研究收斂性和多樣性問題，因此使用以上測試函數進行實驗。

為了驗證可行性，本算法與4 種經典的算法MOEA/D、MOEA/D-DE、NSGA-Ⅲ和基于網格的多目標進化算法GrEA［31］進行了比較。

3.1 參數設置

為了公平比較，所有算法的種群規模和運行代數均保持一致，對于GrEA算法，由于自身的機制限制，將種群規模設置為4的倍數。各測試問題的參數設置如表1所示。

表1 DTLZ測試問題的參數設置Tab.1 Parameter setting of DTLZ test problem

對于3、6、8 以及10 維問題，所有算法的種群規模分別設置為300、252、120 以及220；而對于5 維問題，GrEA 算法的種群規模設置為212，其他算法設置為210，GrEA算法的div設為10。ZDT 系列測試問題的迭代次數設為100，DTLZ 系列測試問題的迭代次數設為1 000，交叉指數mu=30，變異指數mum=20，變異概率Pm=1/D，交叉概率CR=1.0，懲罰因子θ=5，差分進化參數F=0.5，所有算法在每個測試函數上獨立運行20次。

3.2 性能指標

為了能夠更精確地比較算法的性能優劣，通常需要做定量的對比，在本文中使用較為廣泛的綜合性能指標反世代距離（Inverted Generational Distance，IGD）［32-33］和超體積（HyperVolume，HV）［34］作為評估指標。

反世代距離（IGD）兼顧了近似解集的收斂性和多樣性，其通過真實前沿上均勻采樣的一組參考點與求得的近似最優解集之間的平均距離來計算。P*為Pareto 真實前沿上均勻采樣得到的一組參考點，P為使用優化算法求出的一組近似最優解集。則IGD指標的計算如式（7）所示：

其中：|P*|表示P*的基數，即解集P*中解的個數；dist(v，P)表示v∈P*到其最近解的歐氏距離。若IGD 值越小，則所求得的近似最優解集的性能越好，即更接近于真實前沿PF。

另一個指標超體積HV 也用來同時評估所得近似最優解集的收斂性和多樣性，其不需要真實Pareto 真實前沿而通過在目標空間設定一個參考點來求得。假設ur=為目標空間中被所有的Pareto 最優解支配的一個參考點，則超體積表示目標空間中以ur為邊界被最優解集P中的解所支配的區域的大小，HV 指標的計算如式（8）所示：

其中，VOL(·)表示勒貝格計量。HV 越大說明最優前沿P的性能越好。

3.3 實驗結果分析

為了更客觀地顯示出所提算法的優越性，分別對所有算法的IGD 和HV 指標獨立計算20 次，所有算法在ZDT 測試問題下的IGD 和HV 指標的均值和標準差如表2 所示，在DTLZ測試問題下的IGD 和HV 指標均值和標準差分別如表3～4 所示，并且在表中用粗體標出了最好的值。

表2 5種算法在ZDT測試集上的平均IGD和HV均值以及標準差Tab.2 Average IGD，average HV mean and standard deviation of five algorithms on DTLZ test set

表3 5種算法在DTLZ測試集上的平均IGD均值及標準差Tab.3 Average IGD mean and standard deviation of five algorithms on DTLZ test set

對于二維多目標優化問題，由表2中的反世代距離（IGD）和超體積（HV）可以看出，MOEA-TDA 與其他4 種經典算法相比在收斂性和多樣性方面有很大的提升，尤其對于ZDT4測試問題，其效果較為顯著，但是對于ZDT1 測試問題效果沒有ZDT4 效果明顯，這說明MOEA-TDA 對于解決偏約束個數較小的優化問題性能有很大的提升，這是由于第一階段基于最小距離的選擇策略能夠有效提高解集的收斂能力。對于ZDT2，所提算法的效果優于其他算法，因此該算法對連續凹型測試問題也同樣適用。對于非均勻的ZDT6，該算法也均優于其他對比算法，說明該算法能夠有效地解決非均勻系列的測試函數。但是對于ZDT3這類不連續的測試問題而言，盡管該算法能夠提高收斂性和多樣性，但是它不能完全收斂到真實前沿上。因為在該算法中生成的權重向量都是均勻分布的，在利用角度分解目標空間的過程中會使前沿斷續地方的權重向量也會參與到分解目標空間的過程中，從而使這些權重向量也匹配到解，因此對于前沿斷續的問題效果并不好。從標準差可以看出，算法的魯棒性也有所提高，所以算法MOEA-TDA在ZDT測試集上明顯優于其他4類經典算法。

對于DTLZ 系列測試函數，使用性能指標反世代距離IGD和超體積HV 表示其結果如表3 和表4。同樣，由表3 可以看出，算法MOEA-TDA 在高維問題上也有較大的優勢，對于DTLZ1 測試問題而言，雖然收斂性提升較小，而且相對于NSGA-Ⅲ和GrEA 最優解集分布更加均勻，但是MOEA/D-DE對DTLZ1 的8、10 目標效果比MOEA-TDA 好。說明該算法對難以收斂到最優解集的測試問題性能有一定的提升，但是此策略對于DTLZ1 問題隨著目標維數的增加效果逐漸減弱。由表3～4 可以看出，對于DTLZ2，不管是高維問題還是低維問題MOEA-TDA 的優化效果均優于其他算法，說明基于最小距離和聚合策略的選擇方法對于高維目標的進化搜索能力有較大的提升。對于同時包含局部Pareto 最優解集和全局Pareto最優解集的DTLZ3 測試函數，從性能指標可以看出，維數較低時優化效果明顯，但是維數增加到10 維時優化效果顯著降低，而MOEA/D-DE 效果較好，說明當維數較低時MOEA-TDA能有效提高全局搜索能力，維數較高時MOEA/D-DE的全局搜索能力較強。DTLZ4 主要測試解集的分布能力，在此算法中基于角度的目標空間分解策略主要用于提高最優解集的分布性，從實驗結果看出該算法在目標數較低時效果較好，此外GrEA 算法也能夠很好地保持解集的分布性，因為在GrEA 算法中使用到了基于網格的策略，對分布性也有較大的提升。而對于DTLZ5 而言實驗MOEA-TDA 結果較差，這是由于使用了基于角度分解目標空間的策略，使其在高維空間中很難保證前沿退化問題的最優解集聚集到真實前沿上。

表4 5種算法在DTLZ測試集上的平均HV及標準差Tab.4 Average HV and standard deviation of five algorithms on DTLZ test set

NSGA-Ⅲ為非常經典的多目標優化算法，它結合了非支配排序和基于參考點選擇的優點，在保證收斂性的基礎上提高了種群的多樣性，MOEA/D 和MOEA/D-DE 通常使用加權和法、Tchebycheff 法和PBI 的聚合方法，PBI 的聚合方法比Tchebycheff 法得到的最優解集更加均勻，主要用來求解非凸優化問題，在本文中為了與提出的算法保持一致采用PBI 的聚合方法。從實驗結果來看，與其他幾個對比算法相比，MOEA/D-DE 的結果較優，這是由于加入差分進化的原因。而基于網格的多目標優化算法GrEA 在收斂性和多樣性上表現也較為突出，不僅更加適合處理復雜的優化問題，而且對Pareto 前沿的形狀有很強的魯棒性。MOEA-TDA 在基于權重向量分解的基礎上加入了基于角度的分解策略，進一步提高了種群的多樣性并且保證了分布性；為了提高收斂性，在算法的前期使用基于最小距離的選擇策略。綜上，根據實驗結果得出，提出的MOEA-TDA 不僅能夠提高收斂性和多樣性，并且能夠提高維持一個良好分布解集的能力。

4 結語

本文提出了一種分兩階段基于最小距離和聚合策略選擇解的多目標進化算法——MOEA-TDA。首先，使用根據角度分解子空間的策略，有效地提高了解的多樣性；其次，使用基于聚合的交叉鄰域，提高了局部搜索能力；最后，分兩階段在每個子種群中分別根據最小距離和PBI 聚合策略選擇解，提高了解的收斂性。從實驗結果可以得出，所提出的MOEATDA 與其他4 種經典的多目標優化算法相比在本文中的測試問題上綜合性能都有明顯的提高。