張丹麗，曹 錦，高彥杰

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

多目標(biāo)優(yōu)化問(wèn)題（Multi-objective Optimization Problem，MOP），又稱多能性問(wèn)題[1]?，F(xiàn)實(shí)生活中大量的工程問(wèn)題都屬于MOPs，如柔性作業(yè)車間調(diào)度決策、城市運(yùn)輸、工期成本問(wèn)題等。由于多目標(biāo)優(yōu)化問(wèn)題需要平衡多個(gè)目標(biāo)來(lái)達(dá)到總目標(biāo)最優(yōu)，具有高緯度、大尺度的特點(diǎn)，優(yōu)化十分困難。針對(duì)這一問(wèn)題，很多研究者提出了解決多目標(biāo)優(yōu)化問(wèn)題的進(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è)重于對(duì)經(jīng)典多目標(biāo)進(jìn)化算法的介紹與分析，而沒(méi)有涉及解決高維多目標(biāo)優(yōu)化問(wèn)題（Many-objective Optimization Problems，MaOPs）的研究。對(duì)于超過(guò)三個(gè)以上的高維多目標(biāo)優(yōu)化問(wèn)題（MaOPs）、結(jié)構(gòu)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題以及針對(duì)各種不同形狀的Pareto集的具有通用性的MOEAs的研究仍然存在缺陷。

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

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

多目標(biāo)優(yōu)化問(wèn)題（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)空間。下面簡(jiǎn)單地介紹幾個(gè)相關(guān)定義：

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

定義2（Pareto支配）：給定兩個(gè)解x，y∈Ω，以及它們對(duì)應(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)化問(wèn)題的所有Pareto解構(gòu)成的集合稱為Pareto最優(yōu)解集（Pareto Set，PS）。

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

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

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

2.1 基于Pareto支配的MOEAs

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

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

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

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

2.2 基于分解的MOEAs

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

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

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

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

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

一些研究所指出，MOEAs的性能很大程度上取決于問(wèn)題的Pareto前沿形狀，而大多數(shù)現(xiàn)有的MOEAs在Pareto前沿形狀不同問(wèn)題上表現(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í)，它們的性能會(huì)顯著惡化。

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

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

3 結(jié)束語(yǔ)

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

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