大規(guī)模多目標(biāo)進(jìn)化優(yōu)化算法研究進(jìn)展*

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

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

0 引言

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

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

1 大規(guī)模多目標(biāo)優(yōu)化問題相關(guān)概念

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

(1)

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

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

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

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

xx*。

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

定義4(Pareto前沿) Pareto最優(yōu)解集PS對(duì)應(yīng)的目標(biāo)向量的集合稱為Pareto前沿(PF)，即PF={F(x*)|x*∈PS}。

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

(2)

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

定義6(變量依賴[4]) 設(shè)決策變量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 大規(guī)模多目標(biāo)進(jìn)化優(yōu)化算法分類

現(xiàn)實(shí)中存在大量的LSMOP，例如投資組合優(yōu)化問題[5]、車輛路徑問題[6]、資源分配問題[7]等，這些應(yīng)用問題通常具有大量的決策變量，而且決策變量之間尚存在依賴性，這些特征對(duì)MOEA的解題能力提出了巨大的挑戰(zhàn)，而有關(guān)LSMOP的研究也已成為當(dāng)前多目標(biāo)優(yōu)化領(lǐng)域研究的熱點(diǎn)之一。

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

2.1 基于協(xié)同進(jìn)化的LSMOEA

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

不難發(fā)現(xiàn)，關(guān)于決策變量的分組方法是該類算法的重要技術(shù)特點(diǎn)。目前經(jīng)典的變量分組策略主要有如下4種類型：

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

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

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

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

其中，前3種分組機(jī)制未使用任何關(guān)于目標(biāo)函數(shù)的信息，而差分分組則包含一個(gè)基于問題分析的機(jī)制。

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

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

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

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

上述LSMOEA的共同特點(diǎn)是利用協(xié)同進(jìn)化的機(jī)制，而它們采用的變量分組策略則不盡相同。值得一提的是，CCLSM中利用大規(guī)模單目標(biāo)優(yōu)化中的快速依賴識(shí)別方法，顯著增強(qiáng)了算法的性能。

2.2 基于決策變量分析的LSMOEA

為應(yīng)對(duì)決策空間維度不斷增大帶來的“維數(shù)災(zāi)難”問題，研究者通過對(duì)決策變量進(jìn)行分析，挖掘決策變量與優(yōu)化問題之間的相關(guān)性，即通常意義上的收斂性相關(guān)、多樣性相關(guān)和收斂性-多樣性相關(guān)，然后選擇合適的策略對(duì)決策變量進(jìn)行優(yōu)化。

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

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

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

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

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

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

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

2.3 基于問題重構(gòu)的LSMOEA

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

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

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

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

2.4 其他方法

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

2016年，Zille等[31]研究變異算子在分組變量中的作用及其對(duì)大規(guī)模多目標(biāo)優(yōu)化的影響，他們?cè)诙囗?xiàng)式變異的基礎(chǔ)上引入3種新的變異方法，即聯(lián)結(jié)多項(xiàng)式變異(Linked Polynomial Mutation)、分組多項(xiàng)式變異(Grouped Polynomial Mutation)、分組和聯(lián)結(jié)多項(xiàng)式變異(Grouped and Linked Polynomial Mutation),實(shí)驗(yàn)結(jié)果表明，新的變異算子在大規(guī)模WFG測試問題上表現(xiàn)出較好的性能。

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

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

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

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

表1 代表性大規(guī)模多目標(biāo)進(jìn)化算法

3 展望

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

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

1)設(shè)計(jì)更加有效的決策變量分組機(jī)制。變量分組是LSMOEA中重要的部件，已有決策變量分組的方法有的是從大規(guī)模單目標(biāo)優(yōu)化中沿用過來，有的是新發(fā)展的變量分組方法，但這些分組方法大多需要大量的函數(shù)評(píng)估用于發(fā)現(xiàn)決策變量之間的依賴信息，增加了算法的時(shí)間開銷。未來需要進(jìn)一步發(fā)展更加高效的分組策略以提升LSMOEA的性能。

2)LSMOP同時(shí)具有高維決策空間和高維目標(biāo)空間，探索兩個(gè)高維空間之間的關(guān)聯(lián)性以及問題依賴性可能是設(shè)計(jì)新的LSMOEA的著力點(diǎn)之一。

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

4)目前研究較多的是靜態(tài)LSMOP，而現(xiàn)實(shí)中一些復(fù)雜的LSMOP搜索空間可能是動(dòng)態(tài)變化的。對(duì)于動(dòng)態(tài)LSMOP的研究將是一個(gè)有意義且頗具挑戰(zhàn)性的課題。

5)設(shè)計(jì)出適于評(píng)價(jià)LSMOEA性能的指標(biāo)亦是未來需要進(jìn)一步研究的工作。

6)新的計(jì)算模型和學(xué)習(xí)范式不斷涌現(xiàn)，如云計(jì)算和深度學(xué)習(xí)等，如何在LSMOEA中結(jié)合這些新型的計(jì)算范式亦是未來值得研究的課題。