張丹麗，曹 錦，高彥杰

（上海電力大學(xué) 電子與信息工程學(xué)院，上海 200090）

多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP），又稱多能性問題[1]?，F(xiàn)實生活中大量的工程問題都屬于MOPs，如柔性作業(yè)車間調(diào)度決策、城市運輸、工期成本問題等。由于多目標(biāo)優(yōu)化問題需要平衡多個目標(biāo)來達(dá)到總目標(biāo)最優(yōu)，具有高緯度、大尺度的特點，優(yōu)化十分困難。針對這一問題，很多研究者提出了解決多目標(biāo)優(yōu)化問題的進(jìn)化算法。根據(jù)選擇機(jī)制的不同，大部分多目標(biāo)進(jìn)化算法（Multi-objective Evolutionary Algorithms，MOEAs）可分為三大類[2]，即基于Pareto支配的MOEAs、基于分解的MOEAs和基于指標(biāo)的MOEAs。

現(xiàn)有的多目標(biāo)進(jìn)化算法的綜述類文章側(cè)重于對經(jīng)典多目標(biāo)進(jìn)化算法的介紹與分析，而沒有涉及解決高維多目標(biāo)優(yōu)化問題（Many-objective Optimization Problems，MaOPs）的研究。對于超過三個以上的高維多目標(biāo)優(yōu)化問題（MaOPs）、結(jié)構(gòu)復(fù)雜的多目標(biāo)優(yōu)化問題以及針對各種不同形狀的Pareto集的具有通用性的MOEAs的研究仍然存在缺陷。

因此，本文的重點側(cè)重于高維多目標(biāo)進(jìn)化算法的研究。針對這些目前仍未很好解決的問題，歸納總結(jié)了近些年提出的最先進(jìn)的MOEAs，分別從基于Pareto支配的MOEAs、基于分解的MOEAs和基于指標(biāo)函數(shù)的MOEAs進(jìn)行歸納總結(jié)。最后，就MOEAs目前仍然存在的問題進(jìn)行分析，并對今后的研究方向進(jìn)行了展望，可對相關(guān)領(lǐng)域?qū)W者開展自己新的研究方向提供參考。

1 多目標(biāo)優(yōu)化的相關(guān)理論

多目標(biāo)優(yōu)化問題（MOPs）可以描述為[3]：

minxf（x）=minx[f1（x），f2（x），...fm（x）]，x∈Ω，

其中，決策向量X=（x1，x2，...xn）屬于非空決策空間Ω，目標(biāo)函數(shù)向量f：Ω→Λ由m（m≥2）個目標(biāo)組成，Λ是目標(biāo)空間。下面簡單地介紹幾個相關(guān)定義：

定義1（可行解）：滿足約束條件的決策空間中的解x∈Ω，即稱為可行解。

定義2（Pareto支配）：給定兩個解x，y∈Ω，以及它們對應(yīng)的目標(biāo)向量f（x），f（y）∈Rm，當(dāng)且僅當(dāng)?i∈{1，2，...m}，fi（x）≤fi（y）且?j∈{1，2，...m}，fj（x）＜fj（y）時，則x支配y（表示x＜y）。

定義3（Pareto最優(yōu)解）：如果一個解不被任何其他解所支配，則它被定義為帕累托最優(yōu)解（Pareto Optimal Solution）。

定義4（Pareto最優(yōu)解集）：一個多目標(biāo)優(yōu)化問題的所有Pareto解構(gòu)成的集合稱為Pareto最優(yōu)解集（Pareto Set，PS）。

定義5（Pareto前沿）：Pareto最優(yōu)解集中的解所對應(yīng)的目標(biāo)向量稱為Pareto前沿（Pareto Front，PF）。

2 多目標(biāo)進(jìn)化算法最新進(jìn)展

針對目前仍未很好解決的多目標(biāo)優(yōu)化問題，下面將研究基于Pareto支配的MOEAs、基于分解的MOEAs和基于指標(biāo)函數(shù)的MOEAs三類算法的最新進(jìn)展。

2.1 基于Pareto支配的MOEAs

基于Pareto支配的MOEAs可以成功地解決具有兩個或三個目標(biāo)的MOPs問題。然而，對于MaOPs時，許多基于Pareto支配的MOEAs可能會遇到朝向真正Pareto前沿的選擇壓力的問題。因為在早期迭代過程中，非支配解的數(shù)量隨著目標(biāo)的數(shù)量呈指數(shù)增長?；赑areto優(yōu)勢的收斂保持機(jī)制（如NSGA-III）失去了驅(qū)動種群向Pareto前沿移動的選擇壓力。因此，基于帕累托優(yōu)勢度的準(zhǔn)則不能區(qū)分個體的收斂程度。

為了提高解的收斂性，K.Praditwong等人[4]率先提出了具有代表性的雙存檔算法，使用兩個獨立的檔案來保留有前途的候選解。當(dāng)兩個存檔文件的總大小溢出時，僅對DA執(zhí)行停止操作，并刪除擁擠候選解。然而，在處理MaOPs時，CA和DA中的數(shù)量可能會顯著增加。接著，B.Li等人[5]在此基礎(chǔ)上提出改進(jìn)的雙存檔算法（ITAA）為CA的大小設(shè)置了一個閾值。然而，由于DA的大小是沒有限制的，ITAA的最終輸出解的多樣性不足。為了解決這個問題，W.Hangding等人[6]提出了改進(jìn)的雙存檔算法（TwoArch2），利用IBEA的更新策略對CA進(jìn)行更新，當(dāng)種群溢出時，DA迭代選擇具有極值目標(biāo)值的邊界解。最后，DA被輸出為TwoArch2的最終解。L.Cai等人[7]使用了兩種基于聚合框架的更新策略來更新CA和DA。然而，對于投影不完全覆蓋單位超平面的部分帕累托前沿的MaOPs，DA的大小可能小于給定的大小，這是因為某些權(quán)向量可能具有相同的最優(yōu)解。顯然，上述算法均未能設(shè)計一個平衡收斂性和多樣性的機(jī)制來解決MaOPs。

針對上述算法存在的缺陷，C.Dai[8]提出了一種改進(jìn)的基于多搜索策略的雙存檔進(jìn)化算法（TwoArchM）。TwoArchM的主要組成部分是對兩個文檔采用兩種更新策略來平衡收斂性和多樣性，提出了一種多搜索策略來增強(qiáng)收斂性，平衡探索和開發(fā)。實驗表明，在大多數(shù)問題上，TwoArchM得到的解的質(zhì)量比其他算法得到的解要好。

不同于上述雙存檔算法，P.Wang等人[9]提出了一種基于維數(shù)收斂的多目標(biāo)進(jìn)化算法DC-MaOEA。在該算法中，提出了基于個體與虛擬理想點距離關(guān)系的維數(shù)收斂函數(shù)DC。當(dāng)候選的選擇過程具有相同的Pareto支配等級，DC值可以進(jìn)一步衡量它們的收斂性。另外，還發(fā)展了交配機(jī)制，以提高交配群體的收斂性能。為了平衡種群的收斂性和多樣性，還設(shè)計了環(huán)境選擇，對種群進(jìn)行綜合評價。實驗結(jié)果表明了所提出的DC-MaOEA算法具有優(yōu)越性。

2.2 基于分解的MOEAs

對于MaOPs，其高維目標(biāo)是造成其高復(fù)雜程度的原因之一。然而，現(xiàn)實生活中一些特殊的MaOPs中的目標(biāo)可能彼此高度相關(guān)，因此有些目標(biāo)是冗余的。這些MaOPs的PFs具有很低的維數(shù)，可以稱之為退化MaOPs。然而，現(xiàn)有的MOEA/D框架中的自適應(yīng)策略不能處理退化問題，其中每個子問題考慮一個單一尺度的目標(biāo)函數(shù)。

針對退化MOPs，H.Liu等人[10]提出了MOEA/D的一個最新變體MOEA/D-M2M。每個子問題的可行域由目標(biāo)空間中的方向向量（或參考向量）定義。因此，不同的目標(biāo)具有同等的重要性。顯然，MaEA/D-M2M未能有效處理退化MOP。針對文獻(xiàn)[10]存在的問題，L.Hui等人[11]在其基礎(chǔ)上提出了一種新的MOEA/D算法，稱為MOEA/DAM2M。該算法利用搜索過程中收集的信息自適應(yīng)地調(diào)整每個子問題的可行域。仿真實驗表明該算法具有良好的魯棒性。

在基于分解的多目標(biāo)進(jìn)化算法中，由于進(jìn)化算子對問題的性質(zhì)非常敏感，在不同的搜索階段往往具有不同的特性。然而，在現(xiàn)有的集成方法中所有的子問題/子空間使用的進(jìn)化算子是相同的。但是，對于復(fù)雜的MOPs，其子問題/子空間的特性是不同的。

基于現(xiàn)有的集成方法忽略了以上這一點，X.Hong等人[2]提出了一種細(xì)粒度集成方法（FGEA），用于在一代中為不同的子空間選擇合適的進(jìn)化算子。定義了每個進(jìn)化算子在每個子問題/子空間中的局部貢獻(xiàn)和全局貢獻(xiàn)，并且設(shè)計了一種自適應(yīng)策略來鼓勵進(jìn)化算子做出更多的貢獻(xiàn)，以獲得更多的機(jī)會來生成更多的后代解。在為子空間選擇進(jìn)化算子時，該自適應(yīng)策略同時考慮了進(jìn)化算子的局部貢獻(xiàn)和全局貢獻(xiàn)。為了驗證所提出的細(xì)粒度集成方法的性能，挑選了多目標(biāo)優(yōu)化中最廣泛使用的基準(zhǔn)作為多目標(biāo)優(yōu)化問題，這些MOPs的決策變量之間的復(fù)雜聯(lián)系給MOEAs帶來了挑戰(zhàn)，這使它們比其他MOPs更難解決。實驗結(jié)果驗證了該算法的有效性，揭示了FGEA具有一定的競爭性。

2.3 基于指標(biāo)函數(shù)的MOEAs

一些研究所指出，MOEAs的性能很大程度上取決于問題的Pareto前沿形狀，而大多數(shù)現(xiàn)有的MOEAs在Pareto前沿形狀不同問題上表現(xiàn)出了較差的通用性?；谥笜?biāo)的MOEAs為了計算各種性能指標(biāo)，需要在帕累托前沿取樣一組參考點。在實踐中真實的帕累托前沿是未知的，一組參考點只能從近似帕累托前沿抽樣獲得。目前，大多數(shù)現(xiàn)有的參考點適應(yīng)方法在具有不規(guī)則帕累托前沿的MOPs上取得了顯著的性能。但相比之下，當(dāng)應(yīng)用于具有規(guī)則帕累托前沿的MOPs時，它們的性能會顯著惡化。

針對這一問題，文獻(xiàn)[12]提出了一種增強(qiáng)型IGD指標(biāo)，稱為無貢獻(xiàn)解檢測（IGD-NS）。通過區(qū)分對指標(biāo)沒有任何貢獻(xiàn)的無貢獻(xiàn)解，IGD-NS能夠?qū)Ψ侵浣馓峁└娴暮饬?。與傳統(tǒng)的IGD指標(biāo)相比，IGD-NS給定的候選解提供了更全面的評估。接著，在IGD-NS算法的基礎(chǔ)上，還提出了一種MOEA/IGD-NS算法，將儲存在外部檔案中的非支配解作為計算IGD-NS的參考點。實驗結(jié)果表明，雖然MOEA/IGD-NS算法在某些具有兩個或三個目標(biāo)的MOP問題上的性能優(yōu)于現(xiàn)有的MOEAs算法，但在對不同類型的Pareto前沿問題的通用性較差。

為了解決這一問題，文獻(xiàn)[13]提出了一種新的基于IGD-NS的MOEA方法，稱為AR-MOEA，該方法采用參考點自適應(yīng)的方法來調(diào)整參考點，以便在每一代計算IGD-NS。為了評估AR-MOEA算法的有效性，將擬議的AR-MOEA與用于解決MOPs的4個MOEA進(jìn)行比較，以及用于處理MAOP的4個MOEAs。然后，通過與兩種最先進(jìn)的參考點自適應(yīng)方法比較。實證結(jié)果表明，所提出的AR-MOEA在具有不同類型帕累托前沿的MOPs和MaOPs上均優(yōu)于8個具有代表性的MOEA，顯示出良好的通用性。通過將參考點自適應(yīng)方法嵌入到NSGA-III中，進(jìn)一步評估了該方法的性能。與另外兩種最新的自適應(yīng)方法相比，該方法在規(guī)則和不規(guī)則Pareto前沿問題上仍然表現(xiàn)出最好的性能。

3 結(jié)束語

盡管現(xiàn)有的MOEA在解決多目標(biāo)問題方面取得了巨大的成功，但仍存在一些挑戰(zhàn)。下面提出一些多目標(biāo)進(jìn)化算法研究中存在的問題以及今后研究方向的一些展望。

首先，現(xiàn)有的MOEAs大多是針對沒有約束的MOPs問題，但是現(xiàn)實生活中的多目標(biāo)優(yōu)化問題多是存在一定的約束，研究帶有約束的多目標(biāo)優(yōu)化問題的成為進(jìn)化算法下一步需要重點研究的方向。然后，大多數(shù)現(xiàn)有MOEAs的性能在大規(guī)模多目標(biāo)優(yōu)化問題上急劇退化。迄今為止，對于具有不規(guī)則Pareto前沿的大規(guī)模多目標(biāo)優(yōu)化問題的研究還很少，解決這些問題將更具挑戰(zhàn)性，因為許多現(xiàn)有的參考向量調(diào)整方法可能會受到維數(shù)災(zāi)難的影響。其次，求解具有不規(guī)則Pareto前沿的昂貴多目標(biāo)優(yōu)化問題是一個極具挑戰(zhàn)性的課題，因為只能提供對目標(biāo)函數(shù)的少量評估。在這種情況下，需要更有效的適應(yīng)方法，能夠在有限的計算預(yù)算下正確地識別帕累托前沿的分布，代理輔助進(jìn)化算法。最后，如果Pareto前沿隨時間變化，即如果多目標(biāo)優(yōu)化問題是動態(tài)的，則具有不規(guī)則Pareto前沿的多目標(biāo)優(yōu)化問題將變得更難求解。在這種情況下，帕累托前沿在位置、形狀以及不規(guī)則性方面可能隨時間而改變。