多目標(biāo)進(jìn)化算法研究綜述

張丹麗，曹 錦，高彥杰

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

多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP），又稱多能性問題[1]?，F(xiàn)實(shí)生活中大量的工程問題都屬于MOPs，如柔性作業(yè)車間調(diào)度決策、城市運(yùn)輸、工期成本問題等。由于多目標(biāo)優(yōu)化問題需要平衡多個(gè)目標(biāo)來達(dá)到總目標(biāo)最優(yōu)，具有高緯度、大尺度的特點(diǎn)，優(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）的研究。對于超過三個(gè)以上的高維多目標(biāo)優(yōu)化問題（MaOPs）、結(jié)構(gòu)復(fù)雜的多目標(biāo)優(yōu)化問題以及針對各種不同形狀的Pareto集的具有通用性的MOEAs的研究仍然存在缺陷。

因此，本文的重點(diǎn)側(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）個(gè)目標(biāo)組成，Λ是目標(biāo)空間。下面簡單地介紹幾個(gè)相關(guān)定義：

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

定義2（Pareto支配）：給定兩個(gè)解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）時(shí)，則x支配y（表示x＜y）。

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

定義4（Pareto最優(yōu)解集）：一個(gè)多目標(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可以成功地解決具有兩個(gè)或三個(gè)目標(biāo)的MOPs問題。然而，對于MaOPs時(shí)，許多基于Pareto支配的MOEAs可能會遇到朝向真正Pareto前沿的選擇壓力的問題。因?yàn)樵谠缙诘^程中，非支配解的數(shù)量隨著目標(biāo)的數(shù)量呈指數(shù)增長?；赑areto優(yōu)勢的收斂保持機(jī)制（如NSGA-III）失去了驅(qū)動種群向Pareto前沿移動的選擇壓力。因此，基于帕累托優(yōu)勢度的準(zhǔn)則不能區(qū)分個(gè)體的收斂程度。

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

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

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

2.2 基于分解的MOEAs

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

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

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

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

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

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

針對這一問題，文獻(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算法，將儲存在外部檔案中的非支配解作為計(jì)算IGD-NS的參考點(diǎn)。實(shí)驗(yàn)結(jié)果表明，雖然MOEA/IGD-NS算法在某些具有兩個(gè)或三個(gè)目標(biāo)的MOP問題上的性能優(yōu)于現(xiàn)有的MOEAs算法，但在對不同類型的Pareto前沿問題的通用性較差。

為了解決這一問題，文獻(xiàn)[13]提出了一種新的基于IGD-NS的MOEA方法，稱為AR-MOEA，該方法采用參考點(diǎn)自適應(yīng)的方法來調(diào)整參考點(diǎn)，以便在每一代計(jì)算IGD-NS。為了評估AR-MOEA算法的有效性，將擬議的AR-MOEA與用于解決MOPs的4個(gè)MOEA進(jìn)行比較，以及用于處理MAOP的4個(gè)MOEAs。然后，通過與兩種最先進(jìn)的參考點(diǎn)自適應(yīng)方法比較。實(shí)證結(jié)果表明，所提出的AR-MOEA在具有不同類型帕累托前沿的MOPs和MaOPs上均優(yōu)于8個(gè)具有代表性的MOEA，顯示出良好的通用性。通過將參考點(diǎn)自適應(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)實(shí)生活中的多目標(biāo)優(yōu)化問題多是存在一定的約束，研究帶有約束的多目標(biāo)優(yōu)化問題的成為進(jìn)化算法下一步需要重點(diǎn)研究的方向。然后，大多數(shù)現(xiàn)有MOEAs的性能在大規(guī)模多目標(biāo)優(yōu)化問題上急劇退化。迄今為止，對于具有不規(guī)則Pareto前沿的大規(guī)模多目標(biāo)優(yōu)化問題的研究還很少，解決這些問題將更具挑戰(zhàn)性，因?yàn)樵S多現(xiàn)有的參考向量調(diào)整方法可能會受到維數(shù)災(zāi)難的影響。其次，求解具有不規(guī)則Pareto前沿的昂貴多目標(biāo)優(yōu)化問題是一個(gè)極具挑戰(zhàn)性的課題，因?yàn)橹荒芴峁δ繕?biāo)函數(shù)的少量評估。在這種情況下，需要更有效的適應(yīng)方法，能夠在有限的計(jì)算預(yù)算下正確地識別帕累托前沿的分布，代理輔助進(jìn)化算法。最后，如果Pareto前沿隨時(shí)間變化，即如果多目標(biāo)優(yōu)化問題是動態(tài)的，則具有不規(guī)則Pareto前沿的多目標(biāo)優(yōu)化問題將變得更難求解。在這種情況下，帕累托前沿在位置、形狀以及不規(guī)則性方面可能隨時(shí)間而改變。