多模態多目標進化算法研究綜述

張佳星，褚曉凱，屈俊峰

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

0 引言

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

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

1 多模態多目標優化概述

1.1 相關概念

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

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

在多目標優化問題中通常通過Pareto支配關系來比較不同解的優劣，定義如下：

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

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

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

1.2 求解要求

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

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

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

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

1.3 評價指標

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

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

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

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

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

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

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

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

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

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

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

1.4 測試函數

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

表1 測試函數的具體特征

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

2 多模態多目標進化算法最新研究進展

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

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

2.1 基于Pareto支配的MMOEAs

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

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

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

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

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

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

2.2 基于目標分解的MMOEAs

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

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

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

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

2.3 基于新型進化范例的MMOEAs

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

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

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

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

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

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

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

2.4 其他

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

3 結語

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