張佳星，褚曉凱，屈俊峰

（1.湖北文理學(xué)院計算機工程學(xué)院，襄陽 441053；2.河北地質(zhì)大學(xué)信息工程學(xué)院，石家莊 050031；3.河北地質(zhì)大學(xué)人工智能與機器學(xué)習(xí)研究室，石家莊 050031）

0 引言

在現(xiàn)實工程和科學(xué)研究中，許多優(yōu)化問題需要同時滿足多個目標(biāo)，這類問題被稱為多目標(biāo)優(yōu)化 問 題（multi-objective optimization problems，MOPs）［1-2］。近年來，使用進化算法（evolutionary algorithms，EAs）求解MOPs是比較流行且有效的方法。這類方法可以很好地在目標(biāo)空間搜索到完整且分布均勻的Pareto前沿面，從而為決策者提供更合適的選擇。然而，隨著研究的深入和問題的復(fù)雜化，不僅目標(biāo)空間的維度越來越高，而且Pareto最優(yōu)解集（pareto optimal set，PS）和Pareto前沿面之間的映射關(guān)系變得越來越復(fù)雜，PS在決策空間的分布呈多模態(tài)性，即兩個或多個不同的Pareto最優(yōu)解對應(yīng)同一Pareto前沿位置，這樣的問題被稱為“多模態(tài)多目標(biāo)優(yōu)化問題（multi-modal multi-objective optimization problems，MMOPs）”［3］。雖然找到Pareto前沿面就可以滿足優(yōu)化要求，但是獲得更多PS可以為決策者提供更多的備選方案，以便做出更好的選擇。在實際應(yīng)用和科學(xué)研究中存在著許多MMOPs，例如流水車間調(diào)度問題［4］中存在多種優(yōu)化方案同時滿足調(diào)度要求、游戲地圖生成問題［5］中存在多個候選映射空間都符合設(shè)計師的需求、選址優(yōu)化問題［6］中有多個區(qū)域同時滿足選址要求、特征選擇問題［7］中相同的特征個數(shù)同時對應(yīng)多個特征組合，等。因此，研究如何結(jié)合EAs的思想求解MMOPs具有很重要的現(xiàn)實意義。

近年來，研究者們提出了不同的多模態(tài)多目標(biāo)進化算法（multi-modal multi-objective evolution?ary algorithms，MMOEAs）來求解 MMOPs。根據(jù)其算法特征，大致可以將其分為基于Pareto支配、基于目標(biāo)分解、基于新型進化范例三大類。

1 多模態(tài)多目標(biāo)優(yōu)化概述

1.1 相關(guān)概念

MMOPs屬于MOPs，因此用到了MOPs中的一些相關(guān)定義。在一般情況下，最小化多目標(biāo)問題可以定義為：

其中X=(x1,x2,…,xD)T為D維決策向量，Ω∈RD是可行的D維決策空間，F(xiàn)()X定義了m個目標(biāo)函數(shù)(f1(X),f2(X),…,fm(X))。F(X)的所有可能值構(gòu)成的空間為m維的目標(biāo)空間。

在多目標(biāo)優(yōu)化問題中通常通過Pareto支配關(guān)系來比較不同解的優(yōu)劣，定義如下：

在MMOPs中，通常決策空間中會存在兩個或多個相似的PS對應(yīng)目標(biāo)空間中PF的相同區(qū)域。本文采用Rudolph和Preuss［8］提出的松弛等價來定義MMOPs：

定義1一個MMOPs需要找到所有等價于Pareto最優(yōu)解的解。

定義2兩個解X′1和X′2是等價的，如果表示a的任意范數(shù)，μ是決策者給出的一個很小的非負閾值，如果μ=0，MMOPs應(yīng)找出所有等價的Pareto最優(yōu)解。若設(shè)定μ>0，則MMOPs還應(yīng)找出其他質(zhì)量可被接受的解。

1.2 求解要求

求解MMOPs的主流方法依然是進化算法，但與傳統(tǒng)的MOEAs有所不同，這主要是因為與MOPs相比MMOPs具有一定的特殊性。求解MOPs的目的是找到一組收斂性好且分布均勻的Pareto前沿，并不會關(guān)注決策空間的情況。但是在實際生活中，決策者在選擇解決方案時往往需要參考決策向量，因為決策向量代表了最終解決方案的各項實際參數(shù)，所以關(guān)注決策空間的分布性同樣是很有必要的。因此，MMOPs的求解重點是如何提高解集在決策空間的多樣性。

根據(jù)MMOPs的相關(guān)定義可知，其主要特點是決策空間中有兩個或多個Pareto最優(yōu)解集，并且經(jīng)常會出現(xiàn)不同解集上的兩個點在決策空間距離很遠但在目標(biāo)空間距離相近的情況。因此在求解這類MMOPs時通常會遇到兩個挑戰(zhàn)。①如何平衡算法的搜索能力，設(shè)計有效的搜索策略，使算法可以搜索到多個PS的位置，并使每個PS都盡可能完整。②如何設(shè)計有效的個體選擇機制，將同一PF位置上的不同解同時保留下來，同時還要盡可能使決策空間距離很遠但在目標(biāo)空間距離相近的解不被淘汰。為便于理解，下面結(jié)合圖1對這兩個挑戰(zhàn)進行解釋分析。

圖1 具有兩個等價PS的MMOPs示意圖

假設(shè)圖1是一個雙目標(biāo)雙變量的MMOPs，這一問題的PS=PS1∪PS2，其中PS1對應(yīng)了一個完整的PF，PS2同樣對應(yīng)這個完整的PF，當(dāng)算法搜索到PS1時，算法已經(jīng)搜索到了一個完整的PF，繼續(xù)進化只會提高PS1的質(zhì)量，而很難在探索到PS2的鄰域。更具體的說，當(dāng)算法搜索到解決方案A后，很難再搜索到與其等價解決方案B，因此需要算法在前期可以同時搜索到多個PS的大概位置，防止陷入某一個PS。其次，設(shè)置合理的個體選擇機制同樣是很困難的，當(dāng)算法同時搜索到C和D兩個解決方案時，由于這兩個解在目標(biāo)空間中距離很近，當(dāng)非支配解的數(shù)量超過預(yù)定規(guī)模時，為了維持Pareto前沿的多樣性，通常會淘汰解D這種比較擁擠的解，但實際上C和D兩個解決方案在決策空間中距離很遠，也就意味著在實際應(yīng)用中這代表了結(jié)果相近但參數(shù)不同的兩個方案，將其同時保留下來是很有必要的。因此在設(shè)計選擇策略時不能僅依靠解在目標(biāo)空間的擁擠程度，要同時考慮決策空間和目標(biāo)空間解的分布情況。

1.3 評價指標(biāo)

使用EA求解MMOPs最終會得到一組折中的可選方案，不能像單目標(biāo)一樣用最優(yōu)解和真實解的絕對值來進行評價。因此研究者們提出了不同的評價指標(biāo)來客觀展示不同算法之間的性能差距，目前，常見的評價多模態(tài)多目標(biāo)優(yōu)化算法的指標(biāo)，一個是在評估多目標(biāo)優(yōu)化算法時常用的超體積（hypervolume，HV）［9］，另一個是Yue等［10］提出的針對多模態(tài)多目標(biāo)算法的指標(biāo)：帕累托近似性（pareto set proximity，PSP）。

HV指標(biāo)用來評估得到的PF與其參考點構(gòu)成的超體積大小，主要用來驗證解在目標(biāo)空間的分布性，具體如公式（3）所示,

其中，PF是多目標(biāo)算法獲取的Pareto前沿，z*是多目標(biāo)測試函數(shù)的參考點，v(x,z*)是指PF中的一個解與參考點z*圍成的超立體體積。以圖2為例，PF={ }

圖2 超體積（HV）計算示意圖

A,B,C,D，z*為該問題的參考點，則HV(PF,z*)為圖中的陰影面積。這一評價指標(biāo)的優(yōu)勢不需要預(yù)先提供真實的PF作為參考，并且可以同時衡量解集的收斂性和多樣性。

另一指標(biāo)PSP反映了多模態(tài)多目標(biāo)算法獲取的PS與實際PS之間的相似程度，具體如公式（4）。

式中，CR是算法獲取的PS與實際PS之間的覆蓋率；IGDX被稱為決策空間反世代距離，表示算法獲取的PS到實際PS之間的歐式距離。CR的計算方式如下，

D表示決策空間的維數(shù)，表示算法求得的PS在第l維決策變量上的最小值，相應(yīng)的表示最大值，Vminl和Vmaxl分別為真實的PS在第l維上的最小值和最大值。CR越大表示求得的PS越是接近真實PS，當(dāng)CR=1時表示求得的解集與真實解集完全重合。

IGDX是 Zhou 等［11］在指標(biāo)IGD［12］上的擴展，即將IGD應(yīng)用于決策空間，具體公式如下，

其中P*表示在真實PS上選取的一組分布均勻的解，O是求得的真實PS，d(v,O)是P*中的點v到集合O中所有點的歐氏距離的最小值，如果P*在真實PS上的分布足夠均勻，IGDX就可以很好的衡量解在決策空間分布情況，其數(shù)值越小，則表示求得的解集與參考集P*距離越小。

PSP指標(biāo)很好的將兩者進行了結(jié)合，可以同時衡量求得的解在決策空間的收斂性和多樣性，從而有效評價MMOEAs的真實性能。

1.4 測試函數(shù)

MMOPs的相關(guān)研究雖然早在2005年［13-14］就已經(jīng)開始，但是近幾年才被研究者們廣泛關(guān)注。因此，為MMOPs設(shè)計的測試函數(shù)并不多，而且經(jīng)典的多目標(biāo)測試函數(shù)并不符合多模態(tài)問題的特征（具有多個PSs），所以它們并不適合用來對MMOEAs進行測試。目前使用最為廣泛的是2019CEC競賽［15］中的測試集。該測試集包含了22個測試函數(shù)，表1給出了22個測試函數(shù)的一些具體特征，包括函數(shù)名稱、PS的數(shù)目、重疊情況、目標(biāo)數(shù)量、決策空間維度以及本文使用的評價指標(biāo)HV的參考點。

表1 測試函數(shù)的具體特征

其中PS的數(shù)目和重疊情況是影響測試函數(shù)求解難度的重要信息，一般來說，PS數(shù)量越多求解難度越高，如果多個PS存在重疊或者相互連接，同樣會增加求解難度。此外，函數(shù)MMF10-MMF13、MMF14_a和MMF15_a中同時包含了全局PS和局部PS。

2 多模態(tài)多目標(biāo)進化算法最新研究進展

自2005年以來，學(xué)者們就已經(jīng)開始關(guān)注在求解MOPs時決策空間的復(fù)雜性［13-14］，但大多都是獨立進行的，沒有明確使用“多模態(tài)多目標(biāo)優(yōu)化”一詞。Coelho等［16］將其稱為多目標(biāo)多全局優(yōu)化（multi-objective multi-global optimization），而在Zechman等［17］的相關(guān)研究中又被稱為多模態(tài)多目標(biāo)棘手問題（multi-modal multi-objective wicked problems），直至2016年Ling等［18］才明確定義了代表MMOPs的術(shù)語。

在多模態(tài)多目標(biāo)優(yōu)化問題中，目標(biāo)空間的同一個Pareto前沿往往對應(yīng)決策空間中的多個Pareto最優(yōu)解集。傳統(tǒng)的MOEAs的目的是求得收斂性和分布性好的Pareto前沿，即重點關(guān)注解在目標(biāo)空間的收斂性和分布性，而很少關(guān)注解在決策空間的多樣性。因此，在求解多模態(tài)多目標(biāo)優(yōu)化問題時往往不能得到分布性良好的Pareto最優(yōu)解集。近年來，研究者們提出了不同的多模態(tài)多目標(biāo)進化算法（multi-modal multi-objective evolutionary algorithms，MMEAs）來求解MMOPs。根據(jù)其算法特征，大致可以分為基于Pareto支配、基于目標(biāo)分解、基于新型進化范例三類。

2.1 基于Pareto支配的MMOEAs

這類算法同樣采用Pareto支配的方法對個體進行選擇，但這種方法在求解MMOPs時往往無法保證解在決策空間的分布性。為此，研究者們在傳統(tǒng)Pareto支配方法的基礎(chǔ)上又加入了不同的選擇策略作為算法的第二選擇標(biāo)準(zhǔn)，以保持種群的多樣性。

Deb 等［14］提出了 Omni-Optimizer，該算法是在NSGAII基礎(chǔ)上的一個擴展。為增強算法的穩(wěn)定性，該算法在初始化種群時采用了拉丁超立方體采樣的方法。在進化過程中首次引入了決策空間擁擠距離的概念，并結(jié)合非支配排序作為種群進化時的選擇策略，與傳統(tǒng)MOEAs相比，決策空間的多樣性得到了很大的提升。

Ling等［18］提出了 DN-NSGA-II，該算法同樣是在NSGAII上的改進。提出了一種基于決策空間的小生境方法，同時對二選競賽方式進行了改進，增大了決策空間距離遠的解進入交配池的概率，從而使算法能在同一個Pareto前沿上找到多個全局Pareto最優(yōu)解集。

Kim等提出了SPEA2+［19］，該算法是在SPEA2的基礎(chǔ)上進行的擴展，添加了新的交叉機制和存檔機制，采用兩個檔案庫來保持解的收斂性。分別在目標(biāo)空間和決策空間根據(jù)解的密度進行更新以進行環(huán)境選擇，以此來同時維持解在目標(biāo)空間和決策空間的多樣性。

Liu等［20］提出了一種雙峰小生境進化算法，種群在非支配排序后，在目標(biāo)空間和決策空間中同時采用生態(tài)位共享方法進行種群多樣性維護，從而使求解MMOP的解多樣化。

Pareto支配的方法在求解MMOPs時應(yīng)用依然廣泛，其主要優(yōu)勢在于該方法適用性強、操作簡單、收斂速度快等。除此之外，這類算法具有很強的可擴展性，可以針對MMOPs的特性對算法本身的選擇策略、進化范式等方面進行設(shè)計和改進，從而提高算法的收斂性和多樣性。

2.2 基于目標(biāo)分解的MMOEAs

目標(biāo)分解的核心思想是將多目標(biāo)問題分解為多個簡單的單目標(biāo)問題進行求解，這一方法在求解MOPs時表現(xiàn)良好，因此，研究者們針對MMOPs的特性對此進行改進，使算法能夠同時維持解集在決策空間和目標(biāo)空間的多樣性。

Hu等［21］在MOEA/D中引入了決策空間多樣性維護機制，環(huán)境選擇是基于目標(biāo)空間中的PBI函數(shù)值和決策空間中的擁擠距離值相結(jié)合來進行的。通過這種方式，可以將多個不同的解決方案關(guān)聯(lián)到一個子問題，這有助于擴展解決MMOPs問題的多樣性。

Tanabe等［22］提出了 MMOEA/D-AD，該算法在其決策空間中設(shè)置一個了相對鄰域，根據(jù)子問題在目標(biāo)空間的位置，將子問題與其決策空間中的相鄰子問題進行比較，在搜索過程中自動調(diào)整種群的大小，每個子代只更新決策空間鄰域內(nèi)的個體中與同一子問題相關(guān)的原始解。因此，可以為每個子問題保留多個Pareto最優(yōu)解集。

Tanabe等［23］針對這類分解的方法提出了一種基于三個操作的框架：分配、刪除和添加操作，給同一子問題分配多個解，以處理多個等效的解決方案。這類方法可以在一定程度上同時兼顧解在目標(biāo)空間和決策空間的多樣性，但也增加了算法的計算成本，而且，這類算法一般使用均勻分布的權(quán)重向量來維持多樣性，過于依賴參數(shù)的設(shè)置和搜索空間的復(fù)雜程度。因此，合理的劃分子問題，以及設(shè)計更簡便的資源分配方式是目前這類算法的主要研究方向。

2.3 基于新型進化范例的MMOEAs

許多新型進化范例在求解MOEAs時可以取得很好的表現(xiàn)，因此，研究者們將適用于多目標(biāo)優(yōu)化問題求解的進化算法移植到多模態(tài)多目標(biāo)優(yōu)化問題的求解中，用性能優(yōu)越的新型進化算法來求解MMOPs。代表性算法簡述如下。

Yue等［10］提出了MO_Ring_PSO_SCD，這是基于環(huán)形拓撲結(jié)構(gòu)的粒子群進化算法。粒子群進化算法在MOPs和MMOPs中應(yīng)用都非常廣泛。在MO_Ring_PSO_SCD中，作者提出了一種結(jié)合非支配排序和特殊擁擠距離的選解方式，同時考慮了帕累托解集在目標(biāo)空間和決策空間的擁擠距離，有效維護了解集的多樣性。同時還提出了多模態(tài)多目標(biāo)優(yōu)化問題測試函數(shù)和新的評價指標(biāo)。

Zhang等［24］在MO_Ring_PSO_SCD的基礎(chǔ)上提出了MMOCLRPSO，該算法同樣采用了環(huán)形拓撲結(jié)構(gòu)，以非支配排序和特殊擁擠距離相結(jié)合的方式進行選解。并且在此基礎(chǔ)上設(shè)計了一種基于歐幾里德距離的聚類方法對決策空間進行聚類，以此增強算法在決策空間的搜索能力。

Liang等［25］提出了MMODE，采用差分進化算法求解MMOPs。該算法采用非支配排序進行進化種群的第一選擇，引入決策空間擁擠距離進行第二選擇，通過個體預(yù)選擇機制和改進的變異算子來增加解的多樣性。同時對解的越界處理方式進行了改進。

Hu等［26］提出了MMOPIO，采用了基于合并參數(shù)的改進鴿群優(yōu)化算法（PIO）求解MMOPs。該算法提出了一種自組織映射（self-organizing map，SOM）來控制決策空間，從而為PIO建立良好的鄰域關(guān)系。利用精英學(xué)習(xí)策略和特殊的擁擠距離計算機制獲得均勻分布的解集。

Jza等［27］提出了CNMM，該算法采用粒子群優(yōu)化算法來得到下一代進化群體，采用改進的差分進化策略來擴大搜索范圍，并用近鄰移動策略讓粒子向最優(yōu)解逼近，在局部范圍內(nèi)進化，從而達到優(yōu)化的目的。

這類基于新型進化范例的優(yōu)化算法具有較強的搜索能力，可以探索到更多的Pareto最優(yōu)解集，在處理多模態(tài)多目標(biāo)問題時取得了很好的效果。并且這類算法同樣具有很強的可擴展性，為研究者們提供了許多新的思路。

2.4 其他

此外，還有一些其他研究很難歸為上述幾類，Liu等［28］提出了TriMOEA-TA＆R，該算法是一種使用雙存檔和重組策略的新型MOEAs。通過分析決策變量之間的關(guān)系來指導(dǎo)搜索，采用雙重檔案的通用框架協(xié)同維護種群，使用聚類思想保證目標(biāo)空間的多樣性，使用小生境的清除策略來促進決策空間的多樣性。Fan等［29］還提出了一種基于分區(qū)搜索的框架，將決策空間劃分為多個子空間，從而實現(xiàn)對種群的劃分。但其在一定程度上限制了種群初期的全局搜索能力。Li等［30］提出了DE-RLFR，該算法是一種基于適應(yīng)度排序強化學(xué)習(xí)的進化算法，基于Q-Learning框架自適應(yīng)的選擇變異策略產(chǎn)生下一代。

3 結(jié)語

盡管目前的MMOEAs在求解MMOPs時取得了一定的成果，但仍然存在一些挑戰(zhàn)。目前，MMOEAs存在如下三個典型問題及研究方向。首先，現(xiàn)有的大多數(shù)MMOEAs雖然在決策空間取得了很好的分布，但同時犧牲了一部分目標(biāo)空間的性能，因此，如何同時維持目標(biāo)空間和決策空間的多樣性依舊是研究的重點。然后，大多數(shù)算法采用小生境技術(shù)來維持種群多樣性，但在算法初期沒有任何先驗知識的情況下，很難準(zhǔn)確地對種群進行劃分，特別是在MMOPs問題中，使用小生境方法在算法前期無法同時準(zhǔn)確的捕獲到多個PS，若強行對種群進行劃分則有可能會影響算法在前期的全局搜索能力，從而對最終結(jié)果產(chǎn)生不好影響。因此，如何平衡算法搜索能力可以作為未來的研究方向。其次，用于測試函數(shù)的評價指標(biāo)僅能單獨評價決策空間或者目標(biāo)空間的性能，而多模態(tài)多目標(biāo)優(yōu)化問題注重的是同時維護決策空間和目標(biāo)空間的多樣性，因此設(shè)計一些針對問題特性的綜合評價指標(biāo)同樣是很有意義的研究方向。最后，目前有關(guān)多模態(tài)多目標(biāo)問題的實際應(yīng)用相對較少，因此將多模態(tài)多目標(biāo)優(yōu)化算法應(yīng)用于更多的實際優(yōu)化問題中，使算法研究更有意義同樣是未來的目標(biāo)。