張 峰，陳新中

（中國電子科技集團公司第二十八研究所，江蘇 南京 210007）

0 引言

許多實際工程優(yōu)化問題，通常涉及同時優(yōu)化多個相互沖突的目標，此類問題可稱為多目標優(yōu)化問題（Multiobjective Optimization Problem，MOP）［1-4］。在多目標優(yōu)化問題基礎(chǔ)上，存在一類特殊的問題，其目標函數(shù)很難使用公式進行簡單計算，而是主要依賴大量耗時的仿真實驗進行計算，因而導致優(yōu)化的時間成本過于昂貴，此類問題可稱為昂貴的多目標優(yōu)化問題（Expensive Multiobjective Optimization Problem，EMOP）［5］。

盡管在最近20 年間，研究者提出大量多目標優(yōu)化算法以高效地求解各類MOP，但由于多目標優(yōu)化算法需要進行大量的目標函數(shù)評估才能達到理想的求解效果，EMOP每次計算目標函數(shù)卻比較耗時。另外在求解EMOP 問題時，算法往往只能進行少量的目標函數(shù)評估，使得多目標優(yōu)化算法難以高效地求解EMOP。

為了高效地求解EMOP，許多相關(guān)工作開始嘗試在多目標優(yōu)化算法框架基礎(chǔ)上，使用機器學習建立代理模型來輔助算法進行評估。在此基礎(chǔ)上，涌現(xiàn)出不少專門為高效求解EMOP 而設(shè)計的代理輔助進化算法［6］。

目前很少有相關(guān)工作回顧該領(lǐng)域的最新技術(shù)，現(xiàn)有工作大多根據(jù)代理模型對代理輔助進化算法進行分類，通常將相關(guān)算法分為基于高斯過程的算法和基于非高斯過程的算法。雖然不同代理模型的特性不一樣，在預測不同類型問題的目標值時，預測質(zhì)量存在一定差異，但都可以用來求解相關(guān)類型的問題。在基于代理模型種類的算法分類下，通常難以直觀地了解不同類型問題的研究進展。本文按連續(xù)昂貴多目標優(yōu)化問題的規(guī)模大小對相關(guān)算法進行分類梳理，說明每類問題的特點，分析每個算法的優(yōu)缺點，以便人們能夠直觀地了解不同規(guī)模的連續(xù)昂貴多目標優(yōu)化問題研究進展，方便后續(xù)開展研究工作，或者選擇適合的算法求解相關(guān)問題。

1 相關(guān)基礎(chǔ)知識

1.1 連續(xù)多目標優(yōu)化問題定義

EMOP 是在MOP 的基礎(chǔ)上，計算目標函數(shù)比較耗時的一類MOP 問題。為了方便理解，本文主要介紹MOP。為了更具有普遍性，給出最小化連續(xù)MOP 的數(shù)學定義如下：

其中，Ω ∈Rn稱為n維決策空間，x=(x1，x2，...，xn)T稱為一組決策變量，F(xiàn)(x)：Ω →Rm則表示需要優(yōu)化的m個目標函數(shù)，Rm為目標空間。下面給出一些關(guān)于MOP 的相關(guān)定義：

定 義1假 設(shè)x1，x2∈Ω，當且僅當?i∈1，...，m和?j∈1，...，m，都有fi(x1) ≤fi(x2)和fj(x1) ＜fj(x2)成立，則稱x1Pareto 支配x2［7］。

定義2假設(shè)存在解集P，非支配解集PN是所有不被P中的解Pareto 支配的解集。

定義3?x*∈Ω，若不存在一個解能夠使Pareto 支配x*，則稱x*是Pareto 的最優(yōu)解。

定義4在一個MOP 中，所有Pareto 的最優(yōu)解組成Pareto最優(yōu)解集（Pareto set，PS）。

定義5Pareto 最優(yōu)解集對應的目標向量稱為Pareto 前沿（Pareto Front，PF）。

1.2 代理模型

一般來說，許多機器學習方法，例如高斯過程［8-10］、多任務高斯過程［11-12］、神經(jīng)網(wǎng)絡［13-16］等，都可用來作為代理模型。算法通常都會從已評估過的解中挑選部分解來訓練代理模型。

1.3 效用準則

在通常情況下，許多代理模型對候選解的目標值進行預測時，不僅會給出一個預測目標均值，而且會給出一個預測目標的方差。貝葉斯優(yōu)化［17］中的效用準則不僅考慮到代理模型的預測目標值，而且考慮到模型預測的不確定性，可用來更好地評估候選解，這對于提升算法的優(yōu)化性能有著重要意義。

常用的效用準則有EI（Expected Improvement）效用準則、LCB（Lower Confidence Bounder）效用準則和 UCB（Upper Confidence Bounder）效用準則。

1.4 評價指標

EMOP 問題的評價指標［18］主要通過收斂性和多樣性來體現(xiàn)。算法在優(yōu)化EMOP 后，會得到一組解集與解集對應的目標向量。收斂性是指解集對應的目標向量距離Pareto Front 的遠近程度，多樣性是指解集對應的目標向量覆蓋Pareto Front 的完整程度。

2 代理輔助進化算法簡介

不同于多目標優(yōu)化算法對產(chǎn)生的大量解進行目標函數(shù)評估，代理輔助進化算法在多目標優(yōu)化算法框架基礎(chǔ)上，使用機器學習建立代理模型來輔助算法評估大量的候選解。候選解可以理解為不經(jīng)過真實目標函數(shù)評估的，由代理模型評估過的中間解。算法最后挑選出少量最有價值的候選解（最佳候選解）進行目標函數(shù)評估。反復迭代以上流程，滿足算法終止條件后，針對所有進行目標函數(shù)評估后的解集執(zhí)行非支配操作，將得到的結(jié)果作為EMOP的近似解集。代理輔助進化算法工作流程如圖1所示。

首先，算法根據(jù)實際需要對相應參數(shù)進行初始化。接下來對算法進行采樣，并對采樣得到的解進行目標函數(shù)評估。然后，在訓練代理模型過程中，算法根據(jù)設(shè)計的策略，從已評估過的解中挑選出部分解作為訓練樣本，以決策變量作為輸入，根據(jù)算法設(shè)計的需要選擇合適的目標作為輸出，以訓練代理模型。之后，算法將會產(chǎn)生大量候選解，并用代理模型進行評估。算法先產(chǎn)生候選父代，根據(jù)父代產(chǎn)生候選子代，使用代理模型評估候選子代中的每個候選解。許多算法通常都會結(jié)合貝葉斯優(yōu)化中的效用準則以更好地評估候選解。上面的過程通常會反復迭代，滿足終止條件后則進行下一步驟。最后，挑選最佳候選解主要是從代理模型評估過的大量候選解中，根據(jù)算法設(shè)計的選解策略，挑選出少量最有價值的候選解進行目標函數(shù)評估。反復以上流程，直到滿足終止條件（通常指當前目標函數(shù)的評估次數(shù)達到最大允許值）則停止。

由于代理輔助進化算法的目標函數(shù)評估次數(shù)一般很少，算法通常對所有評估過的解進行取非支配操作，得到一組非支配解集，這組解集則作為EMOP 的求解結(jié)果。

3 代理輔助進化算法分類

本文根據(jù)EMOP 的規(guī)模大小，將相關(guān)算法分成處理小規(guī)模EMOP 的代理輔助進化算法和處理中大規(guī)模EMOP 的代理輔助進化算法。EMOP 的規(guī)模大小主要由決策變量數(shù)決定，代理模型雖然對于不同類型問題的預測質(zhì)量存在差異，但這并不意味著代理模型只適合求解某一類問題。

3.1 處理小規(guī)模EMOP的代理輔助進化算法

Fig.1 Workflow of surrogate-assisted evolutionary algorithm圖1 代理輔助進化算法工作流程

一般稱決策變量數(shù)較少的EMOP 為小規(guī)模EMOP（如決策變量數(shù)小于10），通常求解此類問題的目標函數(shù)評估次數(shù)也較少（如目標函數(shù)評估總次數(shù)一般在300 次以內(nèi)）。在小規(guī)模EMOP 問題上，高斯過程作為代理模型會擁有比較高的預測質(zhì)量，并且高斯過程不但可以提供預測目標均值，而且可以提供預測目標方差，能夠結(jié)合貝葉斯優(yōu)化的效用準則提升優(yōu)化性能。因此，選擇高斯過程作為代理模型來求解此類問題成為當前的一種流行方法。下面介紹一些主要用來求解小規(guī)模EMOP 的算法。

NSGA-II 雖然屬于多目標優(yōu)化算法，但在解決目標變量數(shù)較少的EMOP 上有著良好效果，NSGA-II 也經(jīng)常出現(xiàn)在求解EMOP 的對比算法中［19］。NSGA-II 主要通過對當前種群進行交叉變異產(chǎn)生子代，再通過非支配排序和計算擁擠距離來更新種群，借此不斷逼近EMOP 的Pareto Front。

Knowles［20］提出的ParEGO 主要使用一組均勻的權(quán)重向量將EMOP 劃分成多個單目標子問題，通過優(yōu)化每個子問題的最優(yōu)解來近似得出一組EMOP 的最優(yōu)解。ParEGO實現(xiàn)過程簡單，并對許多類型的EMOP 都能取得良好效果，但ParEGO 在一次子問題優(yōu)化過程中，更多地考慮優(yōu)化一個子問題聚合函數(shù)本身，而不是優(yōu)化整個EMOP 問題。此外，ParEGO 一次迭代只能產(chǎn)生一個最佳候選解，從而導致ParEGO 求解EMOP 的時間過長。

Ponweiser 等［21］提出的SMS-EGO 采用協(xié)方差矩陣自適應進化策略優(yōu)化一種超體積指標，以決定挑選哪個候選解進行評估，以此不斷逼近EMOP 的真實Pareto Front。SMS-EGO 一次迭代同樣只能產(chǎn)生一個最佳候選解，并且隨著EMOP 優(yōu)化目標數(shù)的上升，超體積指標的計算會變得十分復雜，從而導致算法求解EMOP 的時間過長。因此，SMS-EGO 在求解優(yōu)化目標數(shù)較少的EMOP 時能取得良好效果，而不適合用來求解優(yōu)化目標數(shù)過多的EMOP 問題。

針對一次優(yōu)化只能評估一個最佳候選解的缺點，在MOEA/D-DE［22］基 礎(chǔ)上，Zhang 等［23］提出MOEA/D-EGO。MOEA/D-EGO 通過一組均勻的權(quán)重向量把EMOP 劃分成多個子問題，MOEA/D-EGO 通過同時優(yōu)化全部子問題的最佳候選解，并將所有子問題聚類成多個簇，挑選出每個簇的最佳候選解來逼近EMOP 的Pareto Front。MOEA/DEGO 在一次優(yōu)化中會得到多個最佳候選解，支持使用并行技術(shù)同時評估多個最佳候選解，能有效縮短算法求解EMOP 的時間。在優(yōu)化子問題時，子問題的鄰居間進行相互協(xié)作，有助于提升最佳候選解的質(zhì)量。MOEA/D-EGO在求解大多數(shù)EMOP 時都能取得比較理想的效果，但在一些特殊問題上，算法效果欠佳，比如優(yōu)化目標數(shù)超過3 的EMOP 等。

針對目標數(shù)超過3 的EMOP 優(yōu)化，在RVEA［24］基礎(chǔ)上，Chugh 等［25］提出了K-RVEA。K-RVEA 采用一組自適應權(quán)重向量將一個EMOP 劃分成多個子問題，K-RVEA 同時優(yōu)化所有子問題的最佳候選解，并根據(jù)代理模型預測結(jié)果的不確定性、權(quán)重向量分布情況和候選解分布情況，以權(quán)衡算法的收斂性和多樣性。此外，K-RVEA 還提出一種挑選部分解來訓練代理模型的策略，該策略不僅能保證代理模型的預測精度，而且能對代理模型的訓練時間進行限制。實驗結(jié)果表明，K-RVRA 在優(yōu)化目標數(shù)超過3 的EMOP 問題上取得了理想效果。

同樣的，針對目標數(shù)大于3 的EMOP 優(yōu)化，Pan 等［26］提出了CSEA。Pan 等認為隨著優(yōu)化目標數(shù)的增加，代理模型近似目標函數(shù)的計算成本將會變高，因此使用代理模型預測解之間的支配關(guān)系會比較適合。CSEA 最終采用神經(jīng)網(wǎng)絡建立代理模型，并使用代理模型預測候選解與參考解之間的支配關(guān)系。算法根據(jù)代理模型預測的不確定性和支配關(guān)系挑選候選解進行評估，最終不斷逼近EMOP 的Pareto Front。在求解優(yōu)化目標數(shù)3 及其以上的EMOP 時，CSEA能夠取得理想效果。

由于一次優(yōu)化產(chǎn)生多個最佳候選解可以結(jié)合并行技術(shù)同時進行評估，從而顯著減少求解EMOP 的時間，對于求解時間要求高的應用場景具有比較重要的意義。Lin等［27］提出的MOBO/D 首先通過一組均勻的權(quán)重向量把一個EMOP 分解成一組子問題，隨后采用MOEA/D-DE 優(yōu)化出一個候選種群，并進一步使用IGD 指標［28］批量挑選出多個最佳候選解進行評估。通過這些方法可保證算法的收斂性和多樣性，因此MOBO/D 在多數(shù)EMOP 問題上都能夠取得良好效果。隨后，Zhang 等［29］在網(wǎng)格約束分解基礎(chǔ)上提 出BCDG（A Batched Constrained Decomposition with Grids）。BCDG 采用CDG-MOEA［30］優(yōu)化出一個候選種群，隨后根據(jù)hypervolume 指標［31］批量挑選出一些最佳候選解進行評估，通過hypervolume 指標可有效引導搜索方向。BCDG 在求解一些Pareto Front 形狀比較復雜的EMOP 時存在一定優(yōu)勢。

隨著機器學習技術(shù)的快速發(fā)展，一部分現(xiàn)有工作開始借鑒遷移學習的一些方法和思想，并將這些方法或思想應用到代理輔助進化算法設(shè)計中，借此提升算法的優(yōu)化性能。

Le 等［32］提出一種交叉代理輔助模因算法CSAMA，CSAMA 首先訓練其他目標函數(shù)上的代理模型，然后使用訓練樣本在其他代理模型上的預測結(jié)果構(gòu)建將要進行目標函數(shù)預測的目標代理模型，借此提升目標代理模型的預測質(zhì)量。CSAMA 在求解目標函數(shù)相關(guān)的EMOP 時可取得比較理想的效果，然而許多EMOP 的目標函數(shù)間普遍缺乏相關(guān)性，因此CSAMA 不具有普遍性。

針對EMOP 目標函數(shù)缺乏普遍的相關(guān)性的問題，Luo等［33］提出的GCS-MOE 同樣使用一組均勻的權(quán)重向量將一個EMOP 劃分成許多相關(guān)子問題，并進一步將一些相關(guān)子問題劃分成一個任務組。由于從同一個EMOP 分解出的子問題具有普遍的相關(guān)性，因此可更好地結(jié)合多任務學習方法優(yōu)化EMOP。針對多個相關(guān)任務組，GCS-MOE 采用多任務高斯過程建立代理模型，算法同時優(yōu)化多個相關(guān)任務組的最佳候選解，以不斷逼近整個EMOP 的Pareto Front。此外，GCS-MOE 還提出一種組合效用準則，并為每個任務組的訓練樣本提供一種選擇和維護策略。在求解目標數(shù)小于4 且決策變量數(shù)不多的EMOP 上，算法取得了理想效果。

針對現(xiàn)有算法將分解后的子問題劃分成多個固定任務，未能充分體現(xiàn)任務間相關(guān)性的問題，蔡昕燁等［34］提出了AMMCS。AMMCS 同樣使用一組均勻的權(quán)重向量，把一個EMOP 劃分成許多相關(guān)的子問題后，通過一種相關(guān)性度量指標將這些子問題動態(tài)劃分成多個相關(guān)任務目標。AMMCS 同樣采用多任務高斯過程作為代理模型，并使用多種群協(xié)作搜索技術(shù)同時優(yōu)化出多個相關(guān)任務目標的最佳候選解，不斷逼近EMOP 的Pareto Front。AMMCS 在簡單、常規(guī)的EMOP 上能取得理想效果，但由于預先設(shè)置固定的方向向量和代理模型預測質(zhì)量問題，AMMCS 在一些Pareto Front 形狀不規(guī)則或者比較復雜的EMOP 上效果不夠理想。

3.2 處理中大規(guī)模EMOP的代理輔助進化算法

一般稱決策變量數(shù)較多的EMOP 為中大規(guī)模EMOP，此類問題通常需要較多的目標函數(shù)評估次數(shù)才能進行有效求解（如目標函數(shù)評估總次數(shù)通常超過300）。隨著決策變量數(shù)的增加，高斯過程的預測質(zhì)量會受到影響，并且由于能夠獲取較多已評估過的解，訓練樣本相應變得更為豐富。在中大規(guī)模EMOP 的目標值預測上，一些機器學習模型的預測質(zhì)量比高斯過程的預測質(zhì)量更有競爭力。因此，現(xiàn)有部分算法嘗試使用一些非高斯過程的機器學習模型作為代理模型，或者尋找別的方法彌補高斯過程的不足。目前能夠高效求解中大規(guī)模EMOP 的相關(guān)方法較少，主要有以下方法：

針對決策變量數(shù)較多的中規(guī)模EMOP，Lin 等［35］提出一種可拓展的代理輔助進化算法BS-MOBO。BS-MOBO采用貝葉斯神經(jīng)網(wǎng)絡建立代理模型，并在monte carlo 抽樣和sobolov 訓練的支持下，能夠輕松訓練貝葉斯神經(jīng)網(wǎng)絡來輔助算法評估。BS-MOBO 使用MOEA/D 優(yōu)化出一個候選種群，并根據(jù)一種貪婪策略和超體積指標批量挑選出多個最佳候選解進行評估，以此保證算法的收斂性和多樣性［36］。值得一提的是，在求解小規(guī)模EMOP 問題上，BSMOBO 也可以選用高斯過程作為代理模型，可獲得理想的效果。BS-MOBO 的算法性能依賴于一個批量評估最佳候選解的參數(shù)，該參數(shù)在不同優(yōu)化問題中，或者在一個完整優(yōu)化過程的不同優(yōu)化階段很可能是不固定的，固定的參數(shù)設(shè)置很可能會影響B(tài)S-MOBO 的算法性能。

針對中規(guī)模的EMOP，Ruan 等［37］在高斯過程基礎(chǔ)上提出了SAEA/ME。SAEA/ME 挑選相關(guān)的決策變量而非全部決策變量參與構(gòu)建代理模型，并將原來的EMOP 轉(zhuǎn)換為基于代理模型的新問題，同時開發(fā)出一種子集選擇方法挑選出最佳候選解進行評估，并更新訓練樣本集。SAEA/ME 在求解決策變量數(shù)較多（如決策變量數(shù)在10～50 之間）的EMOP 時有著理想效果。由于SAEA/ME 使用NSGA-II 來優(yōu)化EMOP，在面對優(yōu)化目標數(shù)超過3 的EMOP 時，SAEA/ME 存在一定的爭議，并且研究其他降維技術(shù)來減輕代理模型構(gòu)建中的維數(shù)災難，對SAEA/ME 也有著較重要的意義。

4 結(jié)語

代理輔助進化算法使用機器學習方法建立代理模型來輔助算法評估候選解，成為求解昂貴多目標優(yōu)化問題的一種流行方法。因此，對代理輔助進化算法的最新研究進展進行分類總結(jié)是一個很有必要的工作。本文根據(jù)問題規(guī)模大小將相關(guān)算法分成兩類進行闡述，并分析與比較相應算法的優(yōu)缺點，希望人們能夠從中直觀地了解不同規(guī)模的連續(xù)昂貴多目標優(yōu)化問題研究現(xiàn)狀，方便后續(xù)研究工作的開展。