基于最小距離和聚合策略的分解多目標(biāo)進(jìn)化算法

李二超，李康偉

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

0 引言

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

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

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

1 問題描述

1.1 多目標(biāo)優(yōu)化

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

多目標(biāo)優(yōu)化算法有最大化目標(biāo)函數(shù)值和最小化目標(biāo)函數(shù)值兩種［24］，此處以最小化目標(biāo)函數(shù)值為例：

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

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

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

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

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

1.2 分解方法

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

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

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

在多目標(biāo)優(yōu)化算法中常用比較成熟的Das 和Dennis 系統(tǒng)方案［27］分解技術(shù)，在單位超平面上生成一組均勻分布的參考點(diǎn)，參考點(diǎn)的數(shù)目N和每維目標(biāo)上的劃分份數(shù)H的關(guān)系如式（3）所示：

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

圖1 權(quán)重向量的生成Fig.1 Generation of weight vectors

2 本文算法

2.1 基本思想和主要框架

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

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

算法1 MOEA-TDA總框架。

2.2 基于聚合的交叉鄰域

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

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

在進(jìn)化過程中對于每個(gè)權(quán)重向量除了原本與其相關(guān)聯(lián)的最優(yōu)解外，再找出與權(quán)重向量的PBI 值最小的兩個(gè)解來進(jìn)行差分進(jìn)化。本文使用MOEA/D-DE 中提出的差分進(jìn)化和多項(xiàng)式變異來產(chǎn)生子代個(gè)體，差分進(jìn)化中有交叉、變異和選擇幾個(gè)主要的步驟，這種進(jìn)化算法比較適合解決連續(xù)的優(yōu)化問題，它能引導(dǎo)新解產(chǎn)生的方向。

2.3 基于角度的目標(biāo)空間分解策略

首先在目標(biāo)空間中產(chǎn)生N個(gè)均勻分布的參考向量，再根據(jù)參考向量將目標(biāo)空間劃分為指定數(shù)量的子區(qū)間，每一個(gè)子區(qū)間對應(yīng)唯一的子種群，其中每一代的種群采用基于角度的劃分方式將目標(biāo)空間劃分為N個(gè)子區(qū)間{Ω1，Ω2，…，ΩN} 以提高所求最優(yōu)解集的多樣性，對于每一個(gè)子區(qū)間：

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

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

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

根據(jù)角度分解目標(biāo)空間之后會使每個(gè)權(quán)重向量關(guān)聯(lián)到一個(gè)子區(qū)間，因此可以在每個(gè)子區(qū)間內(nèi)分兩階段基于最小距離和聚合策略單獨(dú)選擇解。由于在分解完子區(qū)間后有一些區(qū)間內(nèi)關(guān)聯(lián)不到個(gè)體，所以根據(jù)此策略選擇解時(shí)，需要分以下兩種情況進(jìn)行：

1）子區(qū)間內(nèi)有關(guān)聯(lián)個(gè)體。

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

2）子區(qū)間內(nèi)無關(guān)聯(lián)個(gè)體。

當(dāng)子區(qū)間內(nèi)無關(guān)聯(lián)個(gè)體時(shí)，不能直接選擇解，此時(shí)需要計(jì)算子代和父代組成的混合種群在該區(qū)間對應(yīng)的權(quán)重向量下的PBI值，然后選擇出混合種群中最小的PBI值所對應(yīng)的個(gè)體作為該區(qū)間的最優(yōu)解。兩種情況下的算法流程如圖3所示。

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

圖3 中：gen為當(dāng)前運(yùn)行代數(shù)，Cgen為臨界代數(shù)，nC為第i個(gè)子種群中的個(gè)體數(shù)，subpop（i）為第i個(gè)子種群，w（i）為第i個(gè)子種群相關(guān)聯(lián)的權(quán)重向量，Mixpop為子代和父代的混合種群，Pop為最終輸出種群。

3 實(shí)驗(yàn)和結(jié)果分析

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

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

為了驗(yàn)證可行性，本算法與4 種經(jīng)典的算法MOEA/D、MOEA/D-DE、NSGA-Ⅲ和基于網(wǎng)格的多目標(biāo)進(jìn)化算法GrEA［31］進(jìn)行了比較。

3.1 參數(shù)設(shè)置

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

表1 DTLZ測試問題的參數(shù)設(shè)置Tab.1 Parameter setting of DTLZ test problem

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

3.2 性能指標(biāo)

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

為了更客觀地顯示出所提算法的優(yōu)越性，分別對所有算法的IGD 和HV 指標(biāo)獨(dú)立計(jì)算20 次，所有算法在ZDT 測試問題下的IGD 和HV 指標(biāo)的均值和標(biāo)準(zhǔn)差如表2 所示，在DTLZ測試問題下的IGD 和HV 指標(biāo)均值和標(biāo)準(zhǔn)差分別如表3～4 所示，并且在表中用粗體標(biāo)出了最好的值。

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

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

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

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

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

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

4 結(jié)語

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