連續(xù)昂貴多目標優(yōu)化問題綜述

張 峰，陳新中

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

0 引言

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

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

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

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

1 相關基礎知識

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

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

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

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

定義2假設存在解集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］、神經網絡［13-16］等，都可用來作為代理模型。算法通常都會從已評估過的解中挑選部分解來訓練代理模型。

1.3 效用準則

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

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

1.4 評價指標

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

2 代理輔助進化算法簡介

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

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

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

3 代理輔助進化算法分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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