大規模多目標進化優化算法研究進展*

謝承旺，龍廣林，程文旗，郭 華

(南寧師范大學計算機與信息工程學院，廣西南寧 530000)

0 引言

現實中存在大量需要同時優化多個目標的問題，它們通常被稱為多目標優化問題 (Multi-objective Optimization Problem,MOP)。 MOP中各目標之間通常是相互沖突的，因此MOP一般不存在能同時優化多個目標的唯一最優解，而往往是一組折中的解，即Pareto解集[1]。因為MOP模型的復雜性使得經典的數學解析方法無法有效地求解，所以研究者嘗試采用一些元啟發方法求解MOP。進化算法(Evolutionary Algorithm，EA)是一類基于群體搜索的隨機優化方法，EA運行一次可以獲得一組解，而且對待解問題的數學性質不做嚴格假設，因而被廣泛地應用于求解各種類型的MOP，并因此產生了許多經典的多目標進化算法(Multi-objective Evolutionary Algorithm，MOEA)。

近年來隨著社會經濟的高速發展，一些更為復雜的MOP不斷涌現，這些MOP通常從兩個方面進行擴展：一方面，MOP的目標數目越來越大，這使得MOP擴展成高維多目標優化問題(Many-objective Optimization Problem，MaOP，一般指目標數目大于等于4)；另一方面，MOP的決策變量數目越來越多，這使得MOP擴展成大規模多目標優化問題(Large-scale Multi-objective Optimization Problem，LSMOP，一般指決策變數的數目超過100)。需要指出的是，國內外學者對高維多目標進化算法(Many-objective Evolutionary Algorithm,MaOEA)及其研究綜述已不少見[2]，但對于大規模多目標進化優化算法(Large-scale Multi-objective Optimization Evolutionary Algorithm，LSMOEA)的研究較少，特別是關于LSMOEA研究綜述的論文更是少見，這種狀況顯然不利于研究者對LSMOP開展深入研究?；诖?，本文系統整理了已有關于LSMOP的文獻，對求解LSMOP的多種方法進行分門別類，概括各類方法的主要思想和技術特點，指出當前研究LSMOP存在的不足，并對今后LSMOP的研究方向給出建議。

1 大規模多目標優化問題相關概念

不失一般性，以最小化問題為例，一個具有n個決策變量和m個目標的MOP可形式化定義如下：

(1)

其中，x=(x1,x2,…,xn)∈Ω?n是n維的決策向量，xi∈[xi,min,xi,max]，i∈(1,2,…,n)，而xi,min和xi,max分別為決策變量xi的下界和上界。對于LSMOP而言，決策向量的維度n通常大于100。F(x) 包含m個相互沖突的目標，且F(x)=(y1,y2,…,ym)∈Λ?m。gi(x)是MOP的第i個不等式約束，q為不等式約束的數目。hj(x)是MOP的第j個等式約束，p為等式約束的數目。

以下在式(1)的基礎上給出與LSMOP密切相關的若干定義：

定義1(Pareto支配) 假設x和y是MOP的可行解，稱xPareto支配y(記作xy)，當且僅當?i∈[1∶m]∶fi(x)≤fi(y)∧?j∈[1∶m]∶fj(x)

定義2(Pareto最優解) 對于決策空間Ω中的任一點x*，若在Ω中不存在Pareto支配x*的解向量，則稱x*為Pareto最優解，即?x∈Ω:

xx*。

定義3(Pareto最優解集) 決策空間Ω中所有Pareto最優解構成的集合稱為Pareto最優解集(PS)，即PS={x*∈Ω|?x∈Ω:xx*}。

定義4(Pareto前沿) Pareto最優解集PS對應的目標向量的集合稱為Pareto前沿(PF)，即PF={F(x*)|x*∈PS}。

定義5(可分離函數[3]) 如果f(x)被稱為可分離函數，當且僅當x中每一個決策變量xi(i=1,…,n)均可獨立優化，即

(2)

否則，f(x)被稱為不可分離函數。

定義6(變量依賴[4]) 設決策變量xi和xj是相互依賴的變量，則存在決策向量x、a1、a2、b1和b2滿足：

f(x)|xi=a2,xj=b1

f(x)|xi=a2,xj=b2>f(x)|xi=a1,xj=b2，

(3)

這里f(x)|xi=a2,xj=b1?f(x1,…,xi-1,a2,…,xj-1,b1,…,xn)。

2 大規模多目標進化優化算法分類

現實中存在大量的LSMOP，例如投資組合優化問題[5]、車輛路徑問題[6]、資源分配問題[7]等，這些應用問題通常具有大量的決策變量，而且決策變量之間尚存在依賴性，這些特征對MOEA的解題能力提出了巨大的挑戰，而有關LSMOP的研究也已成為當前多目標優化領域研究的熱點之一。

迄今為止，研究者根據LSMOP的特征，基于不同的視角和背景提出了若干解決LSMOP的LSMOEA。以下根據LSMOEA的主要思想和技術特點將它們粗略地分成4種類型：1)基于協同進化(Cooperative Coevolution，CC)的方法；2)基于決策變量分析的方法；3)基于問題重構的方法；4)其他方法。

2.1 基于協同進化的LSMOEA

自然界中，協同進化是指不同的物種在進化過程中相互作用、互相適應、共同進化的過程。Potter等[8]首先提出將進化算法與CC相結合的方法，該方法采用固定的分組策略將決策變量分為較小的子種群，然后利用進化算法實施優化。在LSMOP中，由于決策變量的數目眾多，如何對決策變量進行適當分組，將每個組視為一個獨立的種群參與協同進化過程，是這類算法的核心思想。

不難發現，關于決策變量的分組方法是該類算法的重要技術特點。目前經典的變量分組策略主要有如下4種類型：

1)隨機分組(Random Grouping)[9]：將n個決策變量隨機分配到S個規模相等的組中。

2)線性分組(Linear Grouping)[10]：將n個決策變量按自然順序分成S個規模相同的組，即第一組為{x1,x2,…,xn/S}，第二組為{xn/S+1，…,x2n/S}，以此類推。

3)有序分組(Ordered Grouping)[11]：對于一個選定的解，將決策變量按絕對值升序排序，將絕對值最小的n/S個決策變量分成一組，以此類推。

4)差分分組(Differential Grouping)[12]：在執行分組時先檢測決策變量之間的相互作用，將具有相互作用的決策變量分到同一組。

其中，前3種分組機制未使用任何關于目標函數的信息，而差分分組則包含一個基于問題分析的機制。

Antonio等[13]于2013年提出一種基于協同進化策略的大規模多目標優化進化算法CCGDE3，該算法采用隨機分組策略，將決策變量隨機地劃分成多個子種群，利用快速非支配排序方法獲得每個子種群的最優非支配解，由此獲得最終解集。CCGDE3將協同進化方法和廣義差分進化相結合，有效地解決了具有200—500個決策變量的LSMOP。但需指出的是，由于決策變量之間并非都是相互獨立的關系，CCGDE3的分組策略沒有對決策變量進行分析，利用該算法解決一些具有復雜關系變量的LSMOP時，可能無法獲得較好的性能。

2016年，Antonio等[14]提出一種新穎的基于分解的方法解決LSMOP的算法，即MOEA/D2，該算法在CCGDE3的基礎上利用隨機分組和協同進化方法改善MOEA/D在求解LSMOP時的性能。MOEA/D2對LSMOP的目標空間和決策空間進行分解，實驗結果表明，該算法在求解決策變量數目在200—1 200的DTLZ測試問題上具有較好的性能，其效果優于MOEA/D和GDE3。但是這種方法需要進一步考慮如何以較低的計算開銷獲得一組均勻分布的權重向量，以及發展更高效的決策空間分解技術。

Li等[15]利用一種快速識別變量相互依賴關系的方法對決策變量進行分組，提出一種新的基于協同進化的大規模多目標進化優化方法CCLSM，用以解決LSMOP。CCLSM中快速識別相互依賴關系的方法首先識別可分離變量和不可分離變量，其次識別不可分離變量之間的相互依賴信息。CCLSM將協同進化機制和變量分組方法相結合，并且使用交互的分組策略。必須指出，盡管很多算法都利用了協同進化機制和分組策略來解決LSMOP，但一些高效的變量分組策略和協同進化機制等亟待發展。

2019年，Basu等[16]針對LSMOP中決策變量之間具有可分離和不可分離的特點，提出MOEA/D(s&ns)，該算法將協同進化方法和MOEA/D-DE相結合，利用協同進化方法將決策變量劃分成較小規模的子種群，然后利用MOEA/D-DE對各子種群進行優化。

上述LSMOEA的共同特點是利用協同進化的機制，而它們采用的變量分組策略則不盡相同。值得一提的是，CCLSM中利用大規模單目標優化中的快速依賴識別方法，顯著增強了算法的性能。

2.2 基于決策變量分析的LSMOEA

為應對決策空間維度不斷增大帶來的“維數災難”問題，研究者通過對決策變量進行分析，挖掘決策變量與優化問題之間的相關性，即通常意義上的收斂性相關、多樣性相關和收斂性-多樣性相關，然后選擇合適的策略對決策變量進行優化。

Ma等[17]在2016年提出一種基于決策變量分析的大規模多目標進化優化算法MOEA/DVA,該算法進一步研究決策變量的關系以及決策變量對目標函數的影響。在MOEA/DVA中，對決策變量的分析包括控制變量分析和變量關聯性分析。在控制變量分析中，算法將決策變量劃分為位置變量、距離變量和混合變量(即與收斂性和多樣性均相關的變量)；變量關聯性分析則每次通過分析隨機的兩個決策變量之間的相關性，從而進行分組。MOEA/DVA根據決策變量的相關性，以及它們對優化問題的收斂性和多樣性方面的影響對決策變量進行分組，使得該算法在解決某些LSMOP上具有較好的性能。但不可忽視的是，MOEA/DVA需要進行大量的適應度評價，增加了計算開銷，而且該算法在混合變量較多的LSMOP上性能較差，因此如何更好地處理混合變量，以及更有效地分配計算資源是這種算法尚待解決的問題。

Song 等[18]發展了一種隨機的動態分組策略(Random-based Dynamic Grouping,RDG),他們將RDG與MOEA/D框架相結合，提出新算法MOEA/D-RDG。該算法在求解具有800—1 000個決策變量的UF和WFG系列測試問題上表現出較好的性能。RDG方法的主要特點有3個：1)將變量依賴作為局部信息，而非全局信息；2)動態地確定每個分組的變量，而且分組的大小也是根據分解池動態確定；3)利用C-metric計算相對性能改善，并設置一個性能改進表記錄各分組大小引起的性能變化。相比于MOEA/DVA，MOEA/D-RDG采用RDG方法處理LSMOP，而且分組不需要額外的函數評估，所以可以將更多的計算資源用于種群的進化優化，改進算法的性能。值得注意的是，采用動態分組策略是未來設計LSMOEA值得參考的思路。

Zhang等[19]在2016年提出一種大規模高維多目標進化優化算法LMEA，該算法與MOEA/DVA的思想有類似之處，即二者都根據決策變量的控制屬性將它們分成收斂性相關變量和多樣性相關變量，而且都需要大量的函數評估。不同的是，LMEA利用基于角度的聚類分析方法對決策變量的屬性進行分析，并且分別用收斂性優化策略和多樣性優化策略對兩類變量進行優化。雖然LMEA較之MOEA/DVA在決策變量分析上的計算代價有所降低，但它所需的計算資源仍隨決策變量數目的增多而急劇增加，而且對決策變量分類以及變量之間的交互分析亦成為影響該算法時間復雜性的重要因素。

Cao等[20]在2020年提出一種基于圖的多目標帶偏移的差分分組方法，即mogDG-shift，該方法通過分析決策變量的屬性并檢測決策變量之間的相互作用，從而根據變量的屬性和相互作用對決策變量進行分組。與MOEA/DVA的DVA方法相比，mogDG-shift對決策變量分析和分組的方法更為優越，它的分組精度要遠優于DVA。未來mogDG-shift可結合協同進化框架進一步提高算法的優化性能。

2018年，Chen等[21]在協方差矩陣自適應進化策略CMA-ES的基礎上，提出一種可擴展小種群的協方差矩陣自適應進化策略求解LSMOP的新算法，即S3-CMA-ES。與MOEA/DVA類似，S3-CMA-ES將決策變量分為收斂性相關變量和多樣性相關變量，并基于變量的相互作用，進一步將收斂性相關變量分成多個子組。S3-CMA-ES中每個子種群只收斂到一個解，多個子種群同時進化才收斂到一組近似Pareto最優解。與MOEA/DVA和LMEA類似，S3-CMA-ES也依賴于決策變量分析，從而使得計算開銷急劇增加。

在云計算啟發下，Cao等[22]于2017年提出一種基于消息傳遞接口(Message Passing Interface，MPI)的分布式并行協同進化的多目標優化算法DPCCMOEA，該算法利用改進的變量分析方法將決策變量分成若干組，每組由一個子種群進行優化，然后再將每個子種群進一步分成若干組。DPCCMOEA在MPI機制的基礎上，構造了兩層MPI并行結構，相比于CCGDE3和MOEA/DVA，DPCCMOEA減少了時間消耗并獲得較優的解題效果。受DPCCMOEA的啟發，未來可利用分布式方法解決LSMOP，以減少計算開銷。

2018年，Chen等[23]提出一種并行進化算法(Parallel Evolutionary Algorithm，PEA)用于求解LSMOP。PEA設計了一個并行框架，較好地消除進化過程中各個子進程之間的依賴關系，增強算法的并行性。PEA分離收斂性和多樣性，其中當多樣性保持固定時，每個子種群僅優化收斂性相關變量，從而達到在不通信情況下實現收斂?；诓⑿羞M化算法的框架，如何利用“云”的思想自適應地分配計算資源將是一個頗具吸引力的研究課題。

2.3 基于問題重構的LSMOEA

除上述利用協同進化方法和決策變量分析方法處理LSMOP外，近來利用問題重構(Problem Transformation，PT)的方法處理LSMOP成為新的研究熱點。

Zille等[24]在2017年提出一種加權優化框架(Weighted Optimization Framework，WOF)，通過變量分組和加權實施對原始優化問題的轉化(問題重構)。其核心思想在于利用分組策略將變量分成若干組，每一組變量關聯一個權重，即同組內的決策變量具有相同的權重，從而把對大規模決策變量的優化轉換為對較低維度權重向量的優化，實現對搜索空間的降維?；赪OF的問題重構雖然有效降低了決策空間的維度，但其在考慮權重變量相關性方面存在不足，而且在重構策略上比較依賴分組技術。在利用重構方法處理LSMOP中，發展更有效的決策變量分組方法和問題轉換策略需要進一步研究。

由于隨機嵌入(Random Embedding，RE)技術[25,26]在大規模單目標優化問題中的有效性，Qian等[27]提出一種基于隨機嵌入的大規模多目標進化優化算法ReMO，該算法對那些只有少數決策變量對目標函數有貢獻的問題(即低有效維度問題)較為有效，它可以將任意無梯度的多目標優化算法進行擴展，用于求解具有低有效維度的大規模非凸多目標優化問題。值得注意的是，ReMO在保持Pareto前沿、降低時間復雜性和旋轉擾動不變性(即旋轉擾動的魯棒性)等方面具有良好的性質。因為ReMO無需對決策變量進行分析，大幅減少了函數評估的時間開銷，所以該算法成為一種頗具前景的LSMOEA。但需要指出的是，ReMO僅在ZDT測試問題上進行實驗，尚需在更多、更困難的LSMOP上檢驗該算法的性能。

受WOF中轉換策略的啟發，He等[28]在2019年提出一種利用問題重構加速大規模多目標優化的框架LSMOF，其主要思想是利用問題重構直接跟蹤Pareto最優解。LSMOF利用權重向量降低原始問題決策空間的維度，采用指標函數對目標空間進行縮減。具體地，LSMOF首先將候選參考解與一組決策向量相關聯，實現對決策空間的重構，從而確定Pareto最優解集的位置；其次，LSMOF將LSMOP轉化成低維單目標優化問題，并且利用基于性能指標的適應度賦值策略對單目標優化問題進行優化。對比一些代表性LSMOEA，如MOEA/DVA和WOF，LSMOF收斂速度更快，消耗計算資源更少。需要指出的是，將LSMOF與云計算相結合以提高算法的效率亦是一個值得關注的問題。

2.4 其他方法

受SMS-EMOA[29]的啟發，Hong等[30]在2018年提出一種基于雙重局部搜索(Dual Local Search)的多目標進化算法DLS-MOEA。該算法利用局部搜索增加種群多樣性，利用指標方法增強算法的收斂性，該算法在決策變量數目高達8 192個的WFG測試問題上取得顯著較優的性能。一方面，DLS-MOEA并未使用變量分組機制，減少了用于獲取變量交互信息的計算開銷；另一方面，DLS-MOEA比較依賴性能評估指標的選擇。但DLS-MOEA并沒有在較多的LSMOP上進行實驗，其求解更復雜LSMOP的能力尚待進一步驗證。

2016年，Zille等[31]研究變異算子在分組變量中的作用及其對大規模多目標優化的影響，他們在多項式變異的基礎上引入3種新的變異方法，即聯結多項式變異(Linked Polynomial Mutation)、分組多項式變異(Grouped Polynomial Mutation)、分組和聯結多項式變異(Grouped and Linked Polynomial Mutation),實驗結果表明，新的變異算子在大規模WFG測試問題上表現出較好的性能。

Tian等[32]在2019年提出一種用于求解大規模稀疏多目標優化問題的進化算法SparseEA，該算法考慮了LSMOP的Pareto最優解的稀疏性(即最優解的大部分決策變量為0)，設計了一種新的種群初始化方法和新的進化算子，用于保證生成解的稀疏性。需要指出的是，該文獻中精心設計了一組測試問題集SMOP1-8,用于評估算法的性能，實驗表明SparseEA在求解大規模稀疏多目標優化問題時較之其他的算法具有顯著的性能優勢。

鑒于LSMOEA在求解大規模稀疏多目標優化問題時尚有較大的改進空間，Tian等[33]在2020年提出一種通過學習Pareto最優子空間來求解大規模稀疏多目標優化問題的算法，即MOEA/PSL。該算法通過使用受限玻爾茲曼機(Restricted Boltzmann Machine，RBM)和去噪自動編碼器(Denoising Autoencoder，DEA)對Pareto子空間進行學習，其原理在于通過表示RBM和DEA的隱藏層減少決策變量的數目; MOEA/PSL還采用一種參數自適應策略確定在Pareto最佳子空間中生成子代個體的比例和隱藏層的大小。實驗結果表明，在求解大規模稀疏多目標優化問題時學習Pareto最優子空間非常重要[33]。

Liang等[34]在2020年提出一種基于RVEA框架的算法，即MOEA-CSOD,該算法將RVEA與分布式對抗網絡(Distribution Adversarial Networks，DAN)相結合，利用RVEA中的參考向量引導種群進化，利用DAN的分布式神經網絡對抗性訓練框架快速生成收斂性較好的解個體。實驗表明MOEA-CSOD在LSMOP測試上具有較好的性能[34],但該算法在部分測試問題上表現出個體較少以及DAN過擬合的問題，因此MOEA-CSOD尚需進一步完善。

表1列出了近年來具有代表性的LSMOEA類型、提出年份、LSMOP決策變量的數目、LSMOP目標數目以及算法所使用的測試函數等信息。

表1 代表性大規模多目標進化算法

3 展望

LSMOP在現實中廣泛存在，例如電力系統設計問題[35]、投資組合優化問題[5]、車輛路徑問題[6]、資源分配問題[7]、距離最小化問題[36]和軟件項目調度問題[37]等，這些實際應用問題的決策變量數目一般較多，有的甚至高達1 000維以上；另外，決策變量之間通常還存在復雜的依賴關系。由此可見，設計能有效求解LSMOP的算法在理論和應用上具有重要意義。

迄今為止，雖然研究者基于不同的視角提出了多種LSMOEA，且在一些LSMOP測試上進行實驗并取得較好的結果，但有關LSMOEA的研究仍處于起步階段，未來可以從以下6個方面進一步開展深入的研究：

1)設計更加有效的決策變量分組機制。變量分組是LSMOEA中重要的部件，已有決策變量分組的方法有的是從大規模單目標優化中沿用過來，有的是新發展的變量分組方法，但這些分組方法大多需要大量的函數評估用于發現決策變量之間的依賴信息，增加了算法的時間開銷。未來需要進一步發展更加高效的分組策略以提升LSMOEA的性能。

2)LSMOP同時具有高維決策空間和高維目標空間，探索兩個高維空間之間的關聯性以及問題依賴性可能是設計新的LSMOEA的著力點之一。

3)目前用于測試和驗證LSMOEA性能的主要有ZDT[38]、DTLZ[39]、WFG[40]、UF[41]和LSMOP[42]等系列的測試函數，這些測試函數原來大多數是用于測試多目標/高維多目標優化算法的性能，鑒于LSMOP復雜的決策空間，需要精心設計出一系列具有各種類型并且貼合實際應用問題特征的LSMOP基準測試集，以更好地驗證LSMOEA的性能。另外，可以建立LSMOP的實際應用案例庫，用現實問題檢驗LSMOEA的效率與效果。

4)目前研究較多的是靜態LSMOP，而現實中一些復雜的LSMOP搜索空間可能是動態變化的。對于動態LSMOP的研究將是一個有意義且頗具挑戰性的課題。

5)設計出適于評價LSMOEA性能的指標亦是未來需要進一步研究的工作。

6)新的計算模型和學習范式不斷涌現，如云計算和深度學習等，如何在LSMOEA中結合這些新型的計算范式亦是未來值得研究的課題。