基于代理模型估值不確定度的昂貴多目標優化問題研究

張晶 裴東興 馬瑾 沈大偉

摘要：針對代理模型輔助的多目標優化算法中個體不確定度之間相互沖突的問題，本文提出個體每個目標估值不確定的填充準則，同時，為了減少訓練模型消耗的計算資源，提出基于非支配排序的樣本選擇算法。為了驗證該算法的可行性，采用DTLZ和WFG測試函數進行測試，得出結果與近些年發表5種具有代表性的同類型算法進行對比，結果說明該算法可以有效的解決昂貴高維高目標優化問題。

關鍵詞：進化算法；昂貴多目標優化問題；代理模型；填充準則；不確定度

中圖分類號：TP391文獻標志碼：A文獻標識碼

A research for expensive many-objective optimization problem based on uncertainty of surrogate

ZHANG? Jing1，PEI Dongxing2，3，MA? Jin1，SHEN? Dawei2，3*

（1 Department of Internet of Things Technology， Shanxi Vocational & Technical College of Finance & Trade，Taiyuan，

Shanxi 030031， China; 2 Science and Technology on Electric Test and Measurement Laboratory，North University of China，Taiyuan，

Shanxi 030051，China; 3 Key Laboratory of Instrumentation Science and Dynamic Measurement，Ministry of Education，North University

of China，Taiyuan，Shanxi 030051，China）

Abstract： In surrogate assisted many objective optimization， conflicting uncertainties of surrogate between objective is a challenge. Hence， an many objective optimization algorithm with uncertainty of surrogate is proposed called， US-MOEA. The main work of this paper is as follows： first of all， infill criterion based on the uncertainty of predicted value is proposed to select promising solutions for re-evaluating by expensive optimization objective function. Then， in order to reduce the computational resources， a method based on non-dominated sorting is used to select some individual as train sample. In order to verify the effectiveness of proposed algorithm， the DTLZ and WFG test suits problem are applied and compare with five the-state-of-art algorithms proposed in recent years. The experimental results illustrate that the US-MOEA is an effectively method for solving expensive many objective optimization problems.

Key words： evolutionary algorithm; expensive many objective optimization problem;surrogate;infill criterion;uncertainty

0 引 言

多目標優化問題（Multi-objective Optimization Problem， MOP）是一個常見的學術問題，在風能預測［1］，車輛調度優化［2］等工程應用中尤為常見。相較于單目標優化問題，在多目標優化問題中包含多個相互沖突的目標函數，且在優化過程中需同時考慮所有的目標函數。這意味著單個解不能同時使所有目標函數達到最優［3］，故在多目標優化問題中，往往求得的是一組折衷的解集。另外，在工程應用中，一些優化問題的單次評價成本很高或者需要較長的時間成本，稱為昂貴多目標優化問題 （Expensive Many Objective Optimization Problem， EMOP）。當使用普通多目標優化算法［4-5］在求解多目標優化問題時，往往需要數以萬計的評價次數。因此，當使用普通多目標優化算法求解昂貴多目標優化問題時，所需要的優化成本是難以令人承受的。一種有效的方法是先采用計算廉價的代理模型擬合昂貴的目標函數，然后采用普通的進化算法求解代理模型的最優解，隨后依據填充準則選擇合適的解用于真實計算，并將其保存到數據庫來更新模型或輸出最終種群，這類型優化算法稱為代理模型輔助的進化算法（Surrogate-assisted evolution algorithm， SAEA）。

昂貴多目標優化問題由于在解決實際問題中具有廣泛應用價值，因此受到眾多學者的關注，近些年提出許多優秀的代理模型輔助的多目標優化算法，這些算法依據代理模型的使用方法大致分為兩類［6］，分別為通過代理模型預測個體的指標和依據代理模型擬合待優化問題的目標函數。在依據代理模型擬合目標函數的算法中，主要依據代理模型擬合個體的支配關系和切比雪夫函數值等，例如在算法ParEGO［7］中，數據庫中的個體依據參考向量得到個體的切比雪夫值，隨后針對切比雪夫值建立代理模型。在CPS-MOEA［8］中采用分類模型預測個體之間的支配關系，并且選擇初步解進行真實計算。在CSEA［9］中，采用前饋神經網絡作為分類器，預測候選解和參考點之間的支配關系。由于個體的切比雪夫值依據參考向量而得到，但是當解決不規則帕累托面的多目標優化問題時，參考向量往往隨著種群的進化過程發生自適應變化，因此限制了ParEGO算法的應用。另外，由于基于支配的多目標優化算法在解決高維多目標優化問題時效果不理想，因此，采用代理模型預測個體間支配關系的算法并不多。大部分算法為采用代理模型擬合待優化問題的目標函數，例如在KRVEA［10］中，采用高斯過程模型擬合目標函數，在填充準則中依據個體的估值和不確定度選擇合適的個體進行真實計算。在EDNARMOEA［11］中，采用Droupout網絡擬合目標函數，并且提出依據個體的目標函估值和不確定度提出可以平衡種群多樣性和收斂性的填充準則。在KTA2［6］中，采用由3個高斯過程構成的集成模型擬合目標函數，并且提出將種群狀態分為多樣性狀態，收斂性狀態和不確定度狀態，隨后依據個體的估值和不確定度提出相應的填充準則。

在多目標優化算法中，由于個體具有多個目標函數值和不確定度，并且傳統的方法往往將多個不確定度的均值作為個體的不確定度，這種方法并不能很好的反映個體的每個目標的不確定度信息。針對該問題，本文提出估值不確定度的昂貴多目標優化算法（US-MOEA），具體如下：

（1）提出依據估值不確定度的填充準則，與傳統的將個體的所有不確定度的均值作為選擇依據不同，為了充分發揮個體不確定度，本文依據個體每個估值的不確定度選擇個體進行真實計算。為了平衡種群的多樣性和收斂性，在每個目標上隨機選擇估值最大或者最小的個體進行真實計算。另外，在單次優化中，選擇較多的個體進行真實計算會導致計算資源的浪費，因此在解決昂貴高維多目標優化問題時，隨機選擇其中的一半目標函數，并且基于這些目標函數選擇個體。

（2）由于高斯過程模型在給出個體估值的同時提供估值的不確定度，因此在基于代理模型輔助的優化算法中廣泛應用。然而，隨著訓練樣本數量的增多，訓練模型所需要的時間會急劇增加。針對該問題本文提出基于非支配排序的訓練樣本選擇方法。

1 資料與方法

基于代理模型輔助的多目標優化算法是解決昂貴高維多目標優化問題的有效方法，其中，填充準則在基于代理模型輔助的優化算法中起著十分重要的作用［10］。在填充準則中，個體的不確定度是選擇恰當的個體進行真實計算的重要依據。具體為，當選擇不確定度小的個體進行真實計算，有助于增加種群的收斂性；當選擇不確定度大的個體進行真實計算，則有利于改善種群的多樣性，并且經過真實計算的個體往往會保存到數據庫中作為新的訓練樣本更新模型，因此，該類型個體也有助于增加模型的精度［12］。然而，在昂貴高維多目標優化問題中，個體的所有目標函數都通過模型估值獲得，因此，該個體具有多個不確定度值。在傳統的代理模型輔助的多目標優化算法中往往通過個體多個不確定度的均值代表該個體的不確定度，但是均值并不能準確的表示該個體的不確定度信息。圖1給出了3個個體P1，P2和P3分別在3個目標M1，M2和M3的不確定度值，圖2展示了3個個體不確定度的均值。從圖2中可得，個體P2和P3將會被選擇進行真實計算。然而，從圖1中發現，在M1目標上個體P3和P1將會被選擇進行真實計算，在M2目標上P1和P3將會被選擇，在M3目標上P1和P2將會被選擇。綜上可以看出，傳統的基于不確定度均值的填充準則往往不能選擇出恰當的個體進行真實計算，因此本文提出基于單個模型不確定度的昂貴高維多目標優化算法。

1.1 算法框架

在昂貴多目標優化問題中，由于待優化問題評? 價成本昂貴，而傳統的多目標優化算法在尋優時需要數以萬計的評價次數，因此并不適合于解決該類型優化問題。

基于代理模型輔助的多目標優化算法是解決該類型優化問題的有效手段。在該類型優化算法中，常用的代理模型有徑向基函數（Radial basis function， RBF），高斯過程（Gaussian processes， GP），支持向量機（Support vector machines， SVM），多項式回歸（Polynomial regression， PR）等模型擬合目標函數。其中，GP模型在預測時可以同時給出個體的估值以及估值的不確定度，同時在填充準則中，合理的利用估值的不確定度可以選擇出優秀的個體進行真實評價，因此GP模型被廣泛應用。

US-MOEA算法流程如圖3所示，首先依據歷史數據建立代理模型用于擬合昂貴目標函；然后，建立的代理模型輔助算法尋優；最后，通過填充準則策略從優化后的種群中選擇合適的個體進行真實評價。當滿足終止條件時，輸出數據庫中的非支配解，否則，依據數據庫中的樣本更新模型。

1.2 選擇訓練樣本訓練代理模型

在GP模型中，隨著訓練樣本數量的增加，模型的計算復雜度會急劇增加，因此本文提出基于非支配排序的訓練樣本選擇方法，具體步驟如下：

步驟1：將數據庫中的個體依據目標函數進行非支配排序得到F1，F2，…Fl；

步驟2：從第F1層開始，逐層選擇個體直到Fj層（當選擇F1～Fj層的所有個體作為訓練樣本時，樣本數量超過NT （NT表示樣本數量））；

步驟3：從Fj層中隨機選擇NT－|F1～Fj－1|個樣本，其中|F1～Fj－1|表示F1～Fj－1層所有個體的數量；

步驟4：依據選擇出的樣本為每個目標函數建立GP模型。

1.3 填充準則

在基于代理模型輔助的優化算法中，通過填充準則選擇出個體進行真實計算后添加到數據庫中，并且模型訓練樣本和種群尋優的初始父代種群均從數據庫中選擇，因此填充準則在基于代理模型輔助的優化算法中有十分重要的作用。另外由于GP模型在提供個體估值的同時可以提供估值的不確定度，所以，在US-MOEA中采用了GP模型擬合目標函數。

在進化算法中，平衡種群的多樣性和收斂性是十分重要的，具體的講，良好的多樣性可以使得種群跳出局部最優，而尋找到全局最優；優秀的收斂性促使種群快速的尋找到全局最優解。因此，在填充準則中選擇不確定度小的個體可以改善種群的收斂性，選擇不確定度大的個體有利于增強算法的多樣性。此外，由于模型的訓練樣本均從數據庫中選擇，因此，良好的數據庫樣本有助于建立優秀的代理模型。綜上，在填充準則中同時選擇不確定度最大和不確定度最小的個體進行真實計算是合理的，但是，在一次優化中選擇較多的個體進行真實計算會消耗較多的評價次數，不利于算法解決昂貴高維多目標優化問題。

在昂貴多目標優化問題中，由于個體的所有目標函數都是通過模型預測得到，因此該個體具有多個不確定度值，這些不確定度值往往相互沖突。針對該問題，本文提出基于單目標不確定度的昂貴高維多目標進化算法。該算法的填充選擇策略為依據個體在每個目標上不確定度的表現選擇出恰當的個體進行真實計算。例如，圖4展示了3個個體在m個目標上不確定度值，在M1目標上，個體P1和P3在該目標上的不確定度分別為種群中的最大值和最小值，同時，如上所述，在填充準則中一次選擇較多的個體進行真實計算不利于算法解決昂貴多目標優化問題，因此P1或P3個體將會被選擇；同理在M2目標上，P1或P3將會被選擇，在M3目標上個體P1或P2將會被選擇，以此類推。當所有的個體被選擇出來時，刪除其中的重復的個體后，進行真實計算。另外，當待優化目標數較多時，為了避免一次選擇較多的個體，本文提出隨機選擇待優化目標函數中的一半目標函數，并且依據這些目標函數選擇個體進行真實計算。

2 結果與分析

為了驗證US-MOEA算法的性能，采用廣泛用于驗證昂貴多目標優化算法性能的DTLZ［13］測試函數和WFG測試函數，并且和近些年提出的優秀的同類型優化算法進行對比。本節首先介紹實驗參數設置情況，然后通過消融實驗說明該策略的合理性，最后詳細展示了算法US-MOEA在2組測試函數的性能體現并且和同類型的優秀的算法進行對比。

2.1 實驗參數設置

本文實驗參數設置如下：種群數量NP為100，種群迭代次數ω為100，種群尋優過程中通過遺傳算法產生子代，其中交叉概率為1，交叉因子為20，變異概率為1/D，其中D表示決策空間維度，變異因子為20。測試函數的參數設置如表1所示，同時為了實驗的可信度，每個測試問題獨立運行20次，取中位數進行比較，并且采用置信度σ為0.05的Wilcoxon秩和檢驗方法用于檢驗本文算法和對比算法結果之間有無顯著性差異，其中“+”，“-”和“≈”分別表示本文所提算法相較于對比算法結果好、差和沒有顯著性差異。在DTLZ測試函數中采用IGD值評價優化結果的優劣，在WFG中采用HV指標來評價算法的優化結果。

2.2 算法性能度量指標

在DTLZ測試函數中，采用翻轉世代距離（Inverted Generational Distance， IGD）來評價算法優化結果的優劣。公式（1）給出了IGD指標的計算方法，其中S表示經過算法的優化結果，F*表示多目標優化的最優解集，dist（x，S）表示最有解集中點x到集合S的最小距離。IGD值越小則表示算法的優化結果越好。

IGD（S，F*）=∑x∈F*dist（x，S）|F*|。（1）

在WFG測試函數中，采用超體積（Hypervolume， HV）來度量算法優化結果的優劣。公式（2）展示了HV的計算方法，其中，δ表示用來計算體積的測度，S表示算法所得非支配解集的數目，vi表示第i個解構成的超立方體。HV值越大，表示算法的優化結果越好。

HV=δ（∪|S|i=1vi）。（2）

2.3 消融實驗

在進化算法中，平衡種群的多樣性和收斂性是十分重要的，在填充準則中選擇不確定度較小的個體進行真實計算有助于改善種群的收斂性，選擇不確定度較大的個體進行真實計算會增強種群的多樣性。另外在單次選擇出較多的個體進行真實計算時，不利于種群的尋優。因此，消融實驗如表2所示，其中US-MOEA（Min）表示在填充準則中僅選擇不確定度小的個體；US-MOEA（Max）表示在填充準則中僅選擇不確定度大的個體；US-MOEA（All）表示在填充準則中依據所有的目標函數選擇個體。并且選擇測試種群收斂性的DTLZ1函數，測試種群多樣性的DTLZ4函數上進行比較。從中可以看出，US-MOE A（Min）在DTLZ1函數相較于US-MOEA表現較好，在DTLZ4上表現較差，其主要原因為，選擇不確定度小的個體有助于增強種群的收斂性。US-MOEA（Max）在DTLZ4上表現較好，原因為選擇不確定度大的個體進行真實計算增強種群的多樣性。US-MOEA （All）在12和14個目標上表現較差，我們認為其主要原因在單次填充準則中選擇較多的個體進行真實計算不利于算法解決昂貴高維多目標優化問題。

當訓練樣本的數量較多時，高斯過程模型的計算復雜度會變大，因此，在US-MOEA中提出使用基于非支配排序的樣本選擇方法。為了驗證該策略的有效性，設計如下對比試驗，其中US-MOEA（AllData）表示選用數據庫中所有樣本建立模型。表3給出了2種算法在DTLZ1函數上的IGD統計結果和運行時間統計表。從中可以看出US-MOEA（AllData）在3和6個目標上表現較好，在10、12和14個目標上沒有顯著性差異。然而，在運行時間上US-MOEA則有顯著優勢。綜上，當采用非支配排序的樣本選擇方法時，顯著降低算法的計算復雜度，并且算法的優化結果并沒有顯著變差。

2.4 對比算法及US-MOEA在DTLZ函數結果分析

為了驗證本文提出算法在解決昂貴高維多目標優化問題的有效性，在DTLZ測試函數上分別測試3、6、10、12、14個目標函數，并且分別和近些年提出的5個具有代表性的同類型算法進行比較，其中，5個對比算法分別為EF_SAEA、ABSAEA、CSEA、EDNARMOEA、KRVEA。從表4中最后一行可以看出本文提出US-MOEA算法相較于EF_SAEA、ABSAEA、CSEA、 EDNARMOEA、KRVEA表現較好的測試函數個數為10、13、20、25、12，表現較差的函數個數為7、6、4、4、5。通過對比實驗結果可以發現，本文提出的US-MOEA算法在解決昂貴高維多目標優化問題中相較于其他同類型算法更有優勢。另外從表中我們可以看出EF_SAEA算法在DTLZ2函數上表現最好，其主要原因為該算法采用了由3個模型構成的集成模型，且該3個子模型是由待優化問題的不同維度構成的，因此，集成模型可以更加準確的擬合待優化目標函數，有利于種群尋優。US-MOEA算法在相較于其他算法在DTLZ5和DTLZ6上表現更優，其主要原因為本文提出的填充準則可以合理的平衡種群的多樣性和收斂性，更有利于種群的尋優。

2.5 對比算法及US-MOEA在WFG函數結果分析

為了驗證算法在解決昂貴高維多目標優化問題的有效性，選擇測試算法在WFG測試函數12和14個目標函數性能。從表5中可以看出US-MOEA相較于EF_SAEA、ABSAEA、CSEA、EDNARMOEA、KRVEA表現好的函數個數分別為3、11、14、11、8，表現較差的函數個數為0、1、1、0、0。從中可以看出算法US-MOEA在解決昂貴高維多目標優化問題中更有優勢。另外值得注意的是，EF_SAEA在WFG測試函數的表現較好，其主要原因是優秀的建模策略，因此希望提出新的建模策略可以更好的擬合目標函數。

3 結論

本文提出了基于估值不確定度的昂貴多目標優化算法，在該算法中使用高斯過程擬合待優化的昂貴目標函數，采用RVEA算法對高斯過程模型尋優，通過填充準則選擇恰當的解進行真實計算。在填充準則中，常采用個體不確定度均值不能恰當反映該個體的所有估值的不確定度信息。

針對該問題，本文提出依據每個目標不確定度填充采用規則，為了平衡種群多樣性和收斂性，隨機選擇每個目標不確定度估值的最大或者最小的個體。

另外，當解決昂貴高維多目標優化問題時，為了避免單次進化過程中選擇過多的解進行真實評價，可隨機選擇一半的目標函數，并且依據該目標函數選擇解。在DTLZ和WFG測試函數的實驗結果表明，US-MOEA相較于5種同類型算法更適合解決昂貴多目標優化問題。

模型的泛化性能隨著決策空間維度的升高而急劇下降，下一步提出優秀的建模方法用于高維優化問題，如改進適用于高維優化問題的種群進化方法和相應的填充準則。

參考文獻（References）

［1］ DONG Y C， ZHANG H L， WANG C， et al. Wind power forecasting based on stacking ensemble model， decomposition and intelligent optimization algorithm［J］. Neurocomputing， 2021， 462： 169-184.

［2］ 王敏， 陳峰， 張磊石. 具有反向學習能力的串車調度算法研究［J］. 交通運輸系統工程與信息， 2019， 19（2）： 102-107，115.

WANG M，CHEN F，ZHANG L S. Tandem scheduling algorithm on Opposition-learning［J］. Journal of Transportation Systems Engineering and Information Technology， 2019， 19（2）： 102-107，115.

［3］ WANG H， SUN C L， ZHANG G C， et al. Non-dominated sorting on performance indicators for evolutionary many-objective optimization［J］. Information Sciences， 2021， 551： 23-38.

［4］ WANG H， SUN C L， YU H B， et al. A decomposition-based many-objective evolutionary algorithm with optional performance indicators［J］. Complex Intelligent Systems， 2022， 8（6）： 5157-5176.

［5］ ZHOU J J， RAO S J， GAO L， et al. Self-regulated bi-partitioning evolution for many-objective optimization［J］. Information Sciences， 2022， 589： 827-848.

［6］ SONG Z S， WANG H D， HE C， et al. A Kriging-assisted two-archive evolutionary algorithm for expensive many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（6）： 1013-1027.

［7］ KNOWLES J D. ParEGO： A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2006， 10（1）： 50-66.

［8］ ZHANG J Y， ZHOU A M， ZHANG G X. A classification and Pareto domination based multiobjective evolutionary algorithm［C］∥2015 IEEE Congress on Evolutionary Computation （CEC）， 2015.

［9］ PAN L Q， HE C， TIAN Y， et al. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2019， 23（1）： 74-88.

［10］ CHUGH T， JIN Y C， MIETTINEN K， et al. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2018， 22（1）： 129-142.

［11］ GUO D， WANG X L， GAO K L， et al. Evolutionary optimization of high-dimensional multiobjective and many-objective expensive problems assisted by a dropout neural network［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（4）： 2084-2097.

［12］ WANG H， LIANG M N， SUN C L， et al. Multiple-strategy learning particle swarm optimization for large-scale optimization problems［J］. Complex Intelligent Systems， 2021， 7（1）： 1-16.

［13］ DEB K， THIELE L， LAUMANNS M， et al. Scalable multi-objective optimization test problems［C］∥2002 Congress on Evolutionary Computation， 2002.

［14］ HUBAND S， HINGSTON P， BARONE L. While Lyndon A review of multiobjective test problems and a scalable test problem toolkit［J］. IEEE Transactions on Evolutionary Computation， 2006， 10（5）： 477-506.

［15］ ISHIBUCHI H， MASUDA H， TANIGAKI Y， et al. Modified distance calculation in generational distance and inverted generational distance［C］∥proceedings of the International conference on evolutionary multi-criterion optimization， F， 2015. Springer.

（責任編輯：編輯郭蕓婕）