模型輔助的計算費時進化高維多目標優化

孫超利 李 貞 金耀初

在復雜的工程優化問題中,通常有多個目標需要同時優化,而這些目標之間往往相互沖突和影響,即一個目標的改善會導致至少一個其他目標的惡化,這些問題被稱為多目標優化問題[1].一般多目標優化問題[2]的數學模型可表示為:

其中,M是目標個數,x是D維決策空間 RD中的一個決策向量.在優化問題中,進化算法(Evolutionary algorithm,EA)[3]由于其不需要假設任何目標函數的凹凸性,可微性或約束性,且有更多的機會獲得全局最優解,因而獲得了工業界和科學界的關注,并且在實際工程中得到了很多應用.求解多目標優化問題的進化算法(Multi-objective evolutionary algorithm,MOEA)[4]通常分為4 大類:1)基于支配關系的進化多目標算法:如快速非支配排序的遺傳算法(Nondominated sorting genetic algorithm II,NSGA-II)[5-6]、提升強度的Pareto 進化算法[7];2) 基于分解的進化多目標算法:如基于分解的多目標進化算法(Multiobjective evolutionary algorithm based on decomposition,MOEA/D)[8]、參考向量引導進化算法(Reference vector guided evolutionary algorithm,RVEA)[9];3) 基于指標的進化多目標算法:基于指標的進化算法[10]、基于超體積估計的算法[11];4) 其他算法:如基于分解和支配的高維多目標進化算法(Many-objective optimization algorithm based on dominance and decomposition,MOEA-DD)[12]、基于雙目標優化的進化算法(Bi-goal evolution,BiGE)[13].然而,不管哪一類現有的多目標優化進化算法,在搜尋最優解集的過程中都需要耗費大量的性能評估次數,而在許多實際的多目標優化問題中其目標函數的評價非常昂貴,如:航空發動機管路卡箍布局優化[14]中,一臺典型的航空發動機通常包含上百根管路,而涉及計算一根管路震動頻率的模擬函數評估可能需要大量的時間,因此很大程度地限制了多目標進化算法在這類問題中的應用.目前求解昂貴的多目標優化問題常用的方法之一是引入代理模型,使用模型代替昂貴多目標計算的進化算法通常稱為代理模型輔助的進化多目標算法(Surrogate-assisted evolutionary multi-objective optimization,SAEMO).常見的求解多目標優化問題的SAEMO 算法通常分為三類.第1 類是在多目標優化過程中直接用代理模型代替費時的目標函數計算來進行環境選擇.如Akhtar等[15]為每個目標建立一個徑向基函數模型,并提出用多個準則來選擇具有代表性的點進行真實的目標函數評價.如Zhang 等[16]提出了高斯過程隨機模型輔助的算法,該算法對每個目標建立高斯過程模型,基于分解策略將多目標問題轉換成多個單目標優化問題,根據個體每個目標的高斯過程模型估值計算切比雪夫函數值,并利用獲取函數進行環境選擇.Chugh 等[17]提出對每個目標函數建立高斯過程模型,并通過目標函數估值的角度懲罰距離指標值和估值的不確定度來選擇真實計算的個體,稱為克里金模型輔助 的RVEA 算法(Kriging-assisted RVEA,K-RVEA).為了提高計算費時多目標問題的優化 性能,Wang 等[18]在為每個目標函數建立代理模型的基礎上引入一種自適應獲取函數指標,從而提出了一種新的采樣選擇標準.Yang 等[19]提出了離線數據驅動的多目標優化,在進化算法中使用了粗代理模型和細代理模型兩種模型,粗代理模型用于引導算法快速地定位到較好的搜索空間,同時細代理模型主要關注平衡粗代理模型知識遷移過來的好解.文獻[20]構建了一個正確模型和多個輔助模型作為多個優化問題,然后利用多任務優化方法來求解這些問題,實現了從輔助模型到正確模型的遷移.Zhao 等[21]對多目標問題的每個目標建立了若干代理模型,并基于目標空間和決策空間個體的距離提出了一種新的不確定度計算方法.求解多目標優化問題的第2 類SAEMO 算法是對多目標問題的聚合函數建立代理模型,即通過聚合函數將多目標轉換為單目標,對單目標建立代理模型,從而輔助多目標優化.Knowles[22]基于求解單目標問題的有效全局優化算法(Efficient global optimization,EGO),提出使用切比雪夫函數將多目標優化問題轉換成單目標優化問題,并對單目標問題建立高斯過程模型,利用獲取函數選擇個體進行真實計算,從而實現了基于EGO 的Pareto 面尋優算法(Pareto optimization with the efficient global optimization,ParEGO).代理模型輔助的多目標優化算法中第3 類是根據支配關系訓練分類模型,將代理模型作為分類器輔助多目標優化算法.如Pan 等[23]引入人工神經網絡來預測參考點與候選解之間的優劣關系來選擇好的候選解進行真實計算,為一種基于分類的代理模型輔助進化算法(A classification based surrogate-assisted evolutionary algorithm,CSEA).Zhang 等[24]提出利用個體間的支配關系訓練支持向量機分類模型來預測后代個體的質量,從而選擇好的個體作為下一個父代.

雖然代理模型在單目標計算費時問題的優化中獲得了較多關注,但其在計算費時多目標優化問題中的應用還處于起步階段,目前還有很多亟待解決的問題.

1) 模型的選擇.目前常見的代理模型有多項式回歸模型[25],徑向基函數[26-27],高斯過程[28],人工神經網絡[29]和支持向量機[30]等.在進化過程中選擇哪一種模型對目標函數進行估值會很大程度影響算法的尋優能力.

2) 模型的用途選擇.通常情況下,全局代理模型用于輔助提高算法的探索能力,局部代理模型用于輔助提高算法的開發能力.而在多目標優化問題中,由于有多個目標,確定模型的用途更是進化多目標算法能否快速找到Pareto 非支配解集的重要因素.

3) 填充標準.如何選擇個體進行真實目標函數計算并且更新模型在代理模型輔助的單目標和多目標進化優化中起著至關重要的作用,其選擇的好壞會直接影響模型更新后的準確度.

在SAEMO 中,模型估值的不確定度會影響算法的搜索方向,從而影響算法的求解性能,因此在優化過程中,估值的不確定度往往和估值同時考慮.與多項式回歸、徑向基函數和人工神經網絡等模型相比,高斯過程代理模型不僅能夠提供個體估值,同時還能提供估值的不確定度,因此本文選擇高斯過程模型用來作為原目標函數的估值模型,并通過對高斯過程模型最優解集的搜索,探索最優解集可能存在的不同領域,從而提高算法的開發能力.另外,模型搜索獲得的最優解集是原優化問題的潛在非支配解,因此從中選擇真實計算的個體能夠加快算法對原問題的求解效率.然而,由于高斯過程的獲取函數是針對單目標優化問題的建模提出來的,隨著目標數的增加,對每個目標分別建立高斯過程模型時個體估值的不確定度會隨之增大.因此,針對多目標優化問題,考慮到個體的收斂性、種群的多樣性以及估值的不確定性,本文對高斯過程模型的期望提高(Expected improvement,EI)獲取函數進行了改進.使用角度懲罰距離函數值作為個體的收斂性指標,所有目標估值的不確定度均值作為個體的估值不確定度,從而使算法在選擇個體進行真實計算時在開發和開采能力上達到平衡.

本文主要貢獻包含以下兩個方面:

1) 通過對模型最優解集的搜索提高算法的開發能力,使其能夠引導種群向具有較好目標函數值的區域進化,并從獲得的最優解集中選擇個體進行真實的目標函數評價,從而加快收斂速度.

2) 考慮個體的收斂性、種群的多樣性以及估值的不確定性,針對計算費時多目標優化問題提出一種新的填充準則.

1 相關工作

1.1 高斯過程

高斯過程(Gaussian process,GP)是基于統計理論提出的機器學習方法[28],其性質由均值函數μ(x) 和協方差函數k(xi,xj)唯一確定,

其中,xi,xj代表決策空間R 中2 個任意的D維向量,μ(x)和k(x)分別為均值函數和協方差函數.因此,給定數據集 D S={(xi,f(xi)),i=1,2,···,n},假設訓練集X=[x1;x2;···;xn],Y=f(x1);f(x2);···;f(xn)],則高斯過程模型可定義如下:

其中,K為n×n階對稱的正定協方差矩陣,每個元素kij表示xi和xj之間的相關性.則

式中,K(X,X*) 表示測試輸出樣本X*和訓練輸出樣本X之間的協方差矩陣,K(X*,X*)為測試輸出樣本X*自身的協方差矩陣.

隨后,通過最大似然估計方法尋找最優的超參數,從而最終確定高斯過程模型.當給定輸入X*,其通過訓練集中的輸入X和其觀測目標輸出值Y,預測出概率最大的預測后驗分布,即

1.2 RVEA 算法

RVEA 算法[9]是2016 年Cheng 等針對高維多目標優化問題提出的基于分解的進化算法.不同于最初提出的基于分解的多目標進化算法MOEA/D[8],RVEA 中使用一組自適應的參考向量,同時提出了角度懲罰距離(Angle penalized distance,APD)作為環境選擇策略.在RVEA 中,參考向量根據目標函數值范圍的不同調整其分布,

其中,dt,i,j表示第i個個體在第t代時在第j個參考向量上的APD 值,θt,i,j表示第t代個體i的目標函數值與第j個參考向量之間的夾角.P(θt,i,j)為懲罰函數,其計算公式為

M和N分別表示目標數和參考向量數,tmax為種群最大進化代數,γvt,j表示參考向量Vt,i與其他參考向量之間的最小角度,α是控制懲罰函數速率的參數.式(11) 中,F′(xi(t)) 表示第t代的第i個解歸一化之后的目標函數值,其歸一化方法為:

式中,F(xi(t)) 是個體i在t代的一個目標函數值,F*表示由每個目標最小值組成的向量.

2 代理模型輔助的計算費時進化高維多目標優化

模型的用途以及選擇個體真實計算的模型填充準則對于代理模型輔助的進化算法在計算資源有限的情況下尋找計算費時問題的最優解集是非常重要的[31-33].隨著目標空間維度的增加,對計算費時問題的求解算法在搜索效率上有了更高的要求.由于常見的求解高維多目標的優化算法需要大量的目標函數評價次數,使其在求解這類費時問題時受到了很大地限制.使用計算廉價的代理模型代替計算費時的目標函數評價是求解計算費時多目標優化問題的常見方法.然而,模型的使用方法會極大地影響算法的搜索效率,特別是當目標空間維度增加時,由于各個目標均為估值,一個目標估值錯誤將會導致優化算法朝著錯誤的方向進行搜索,從而嚴重影響最優解集的尋找.另一方面,在搜索最優解集的過程中,選擇若干個體進行真實評價也是非常重要的.這些真實計算的個體不僅用于更新模型,以提高模型的估值準確度,同時也是潛在的非支配候選解.鑒于高斯過程模型不僅能夠提供估值還能夠提供估值不確定度,本文提出使用高斯過程模型來估計目標函數值,以輔助計算費時的高維多目標問題的優化(Surrogate-assisted expensive evolutionary many-objective optimization,SAExp-EMO).在該方法中,為了提高搜索效率,首先將各個代理模型作為優化目標,使用對求解高維多目標問題具有較好優化性能的RVEA 算法對代理模型進行最優解集的搜索,找到具有較好收斂性能的解,從而能夠提供較好的供真實計算個體選擇的候選解集.算法1 給出了本文方法的偽代碼.算法1 分為3 個部分:第1 部分為初始化階段(1～ 3 行),主要是用拉丁超立方抽樣方法采樣若干個體以供初始代理模型的訓練,同時獲得目前的非支配解集.第2 部分是訓練代理模型并對其進行最優解集的搜索(5～ 6 行),第3 部分是通過填充準則策略從搜索到的代理模型最優解集中選擇個體進行真實計算.第2 部分和第3 部分交替運行,直到滿足停止條件,即達到最大評價次數為止.

算法1.代理模型輔助的計算費時進化多目標優化 (SAExp-EMO)

2.1 模型最優解集的搜索

當模型能夠很好地擬合原目標函數時,搜索代理模型得到的最優解集即為原優化問題的最優解集,并且能夠大量地節省求解問題的計算時間.因此,為了提高對費時高維多目標優化問題的求解效率,在SAExp-EMO 中,通過對高斯過程模型進行最優解集的搜索使種群能夠落到目標函數值較好的潛在區域,以供真實計算個體的選擇.任何求解高維多目標優化問題的算法都可以用來實現對代理模型最優解集的搜索.RVEA[9]是Cheng 等在2016年提出的基于分解的求解高維多目標優化問題的有效方法,其提供了角度懲罰距離用于在高維目標空間更好地選擇下一代父代種群.同時,自適應參考向量可以更均勻的取到最優解集.因此,本文選用RVEA 對高斯過程模型進行非支配最優解集的搜索.|pop(t)|表示當前t代種群大小,算法2 給出了搜索模型最優解集的偽代碼.

2.2 改進的填充準則

模型管理是代理模型輔助的優化算法中最重要的環節,由于真實計算的個體不僅要用于模型的更新以提高模型的估值準確度,同時其也是潛在的最優非支配解集中的候選解,所以填充準則的選擇,將直接影響最終獲得的優化結果好壞.常見的針對高斯過程模型提出的填充準則是針對單目標優化問題的,不能直接用于多目標優化問題.考慮到RVEA中角度懲罰距離指標可以同時衡量一個個體的收斂性和多樣性,故本文考慮將目標函數估值的角度懲罰距離值作為個體的性能指標.其角度懲罰距離期望值提高越大,說明個體的整體性能提高較大,因此選擇這類個體進行真實的目標函數計算有利于加快費時優化問題最優解集的搜索.另一方面,若個體估值的總體不確定度較大,即各個目標估值不確定的累加和較大時,表明該個體的估值不可信.因此,對這類個體進行真實的目標函數計算并用于模型的更新將有利于代理模型準確度的提高.基于以上分析,本文針對高維多目標優化問題,提出一種改進的期望提高獲取函數,以選擇具有較高價值的個體進行真實計算.式(15) 給出了改進的期望提高獲取函數.

其中,dt,i,j為第i個個體在t代相對于 第j個參考向量的APD 值,d*表示Arc中所有個體具有的最小的APD 值,即

s(xi) 為個體i各個目標估值不確定度的平均值,即

其中,sk(xi) 表示第i個個體在第k個目標上的估值不確定度.

算法3.改進的填充準則

算法3 給出了改進的填充準則的偽代碼 . 在算法3 中,將模型搜索最優解集的最后一代種群個體分配給其最近的參考向量,并計算相應的角度懲罰距離值.同時根據各個目標估值的不確定計算個體的整體估值不確定度(所有目標估值不確定度的平均).隨后根據個體的角度懲罰距離和平均不確定度計算其期望提高值,從種群中選擇期望值最大的個體進行真實計算.

3 實驗驗證

為驗證本文方法的有效性,本文在7 個DTLZ基準問題[34]上進行了測試,每個問題分別測試了3、4、6、8、10 個目標.并和沒有代理模型輔助的進化算法RVEA 以及具有代表性的用于求解計算費時多目標優化問題的代理模型輔助算法,K-RVEA[17],CSEA[23]和ParEGO[22]進行了對比.其中K-RVEA同樣為每個目標建立代理模型并搜索模型的最優,和本文不同的是,在K-RVEA 中優化模型的最后一代種群進行了聚類,并根據和固定參考向量相關聯的個體數差異選擇APD 最小或者不確定度最大的若干個體進行真實評價.CSEA 是基于神經網絡的求解費時問題的多目標優化問題,通過對個體的分類選擇若干有前途的個體進行真實計算.ParEGO使用切比雪夫函數將多目標優化問題轉換成單目標優化問題,并對單目標優化問題建立高斯過程模型,利用獲取函數選擇個體進行真實計算.

3.1 參數設置

實驗中,所有算法的最大目標函數評價次數均設置為300 次.根據文獻[34]給出的DTLZ 測試函數的定義,問題的維度為K+M-1,M為目標數,DTLZ1 和DTLZ7 測試函數K的取值分別為5 和20,DTLZ2-6 測試函數K取值為10.所有算法都獨立運行20 次,本文對比算法的結果都在PlatEMO上運行得到.為了公平比較,除了初始樣本大小,對比算法中搜索算法的參數均采用原文給出的參數,即交叉ηc和變異ηn算子均為20,交叉概率pc設為1.0,變異概率pn設為 1/D,其中D為決策變量的維度.在K-RVEA、CSEA、ParEGO 中,初始采樣大小均為 11D-1,其測試問題維度為固定的10 維.而本文測試問題維度是不固定的,決策空間大小由目標函數個數決定,因此當目標維度增高,決策空間維度也隨之增大.由于 11D-1 占用大量評價次數,優化代數減少不利于算法的尋優.故本實驗中K-RVEA、CSEA、ParEGO 和SAExp-EMO 初始樣本設置都為Ns=5D-1 .利用置信度σ=0.05的Wilcoxon 秩和檢驗方法來判斷本文算法和其他算法獲得的解集之間的差異性.符號+、-和≈分別表示所比較的算法性能比本文SAExp-EMO 算法好、差和沒有明顯的差異.

3.2 性能指標

反轉世代距離評價指標(Inverted generational distance,IGD)[35]是一個綜合性能評價指標,通常被用作衡量求解多目標優化問題方法的性能指標.它主要通過計算每個在真實Pareto 前沿面上的點(個體)到算法獲取的非支配面上個體之間的最小歐式距離和,來評價算法的收斂性能和分布性能.值越小,算法的綜合性能越好.IGD 的計算公式如下:

其中,P和Q分別為均勻分布在真實 Pareto 面上的點集和算法獲得的最優Pareto 面.dist(v,Q)為P中個體v到Pareto 面Q的最小歐幾里得距離.因此,IGD 是通過計算真實Pareto 面上點集到獲取的非支配面的最小歐氏距離的平均值來評價算法的綜合性能.當P中個體數足夠多時,其解就會均勻的覆蓋真實Pareto 面,本文中|P|設置為10 000.

3.3 實驗結果及分析

3.3.1 搜索模型最優解集的最大評價次數L

搜索模型最優解集的評價次數會影響算法對計算費時問題的尋優能力,評價次數過少,算法還沒找到模型的最優解集,評價次數過多,搜索可能會偏離真實的問題最優.為此,本文分別使用L=0,L=500×M,L=1 000×M,L=1 500×M,L=2 000×M,L=2 500×M和L=3 000×M模型評價次數對DTLZ1 和DTLZ2 測試問題上進行了算法性能進行了測試,其中M為問題的目標數.在實驗中,目標函數分別設置為3、6、8、10 進行了測試.圖1 給出了不同L值下獲得的IGD 值.由圖1可以看出,當搜索模型的最大評價次數為L=1 000×M時算法在這兩個函數上的性能最好.為此,在本文的方法中,搜索模型最優的停止條件為模型評價次數達到L=1 000×M.

圖1 不同模型評價次數下算法的性能結果對比圖Fig.1 Performance comparison of the proposed method with different number of evaluations on surrogate model

3.3.2 不同算法中的實驗結果

為了驗證本文算法的有效性,本文算法和RVEA,ParEGO,K-RVEA 以及CSEA 在3、4、6、8、10 個目標的DTLZ1～7 測試問題上進行了實驗結果對比.需要注意的是ParEGO 算法是針對目標函數個數不超過4 個的多目標優化問題提出的,因此本文單獨將ParEGO 和SAExp-EMO 方法在3個和4 個目標的DTLZ1～ 7 測試函數上進行了對比.表1 給出了SAExp-EMO 和ParEGO 獲得的IGD 平均值的結果,其中最好結果以粗體表示.由表1 可以看出,本文提出的SAExp-EMO 方法能夠在3 個目標和 4 個目標的DTLZ1～ 7 測試函數集上獲得更好或者一樣的IGD值,說明SAExp-EMO 算法在收斂性和多樣性上具有更好的性能.

表1 SAExp-EMO 和ParEGO 在3 個和4 個目標函數的DTLZ 測試問題上獲得的平均IGD 統計結果Table 1 Average IGD statistical results of SAExp-EMO and ParEGO on DTLZ test problems of 3 and 4 objective functions

RVEA、K-RVEA 和CSEA 均是針對高維多目標提出的優化算法,其中RVEA 無代理模型輔助,而K-RVEA 和CSEA 均為代理模型輔助的高維多目標優化方法.表2 給出了不同算法在3、4、6、8、10 個目標的DTLZ 上的測試結果,其中最好結果以粗體表示.由表2 可以看出,相比于無代理模型輔助的RVEA,本文的SAExp-EMO 在所有DTLZ 測試函數上均獲得了性能較好的解,只有在4 個目標的DTLZ4 上獲得的結果和RVEA 無差別.相比于代理模型輔助的K-RVEA,本文方法在25 個問題上獲得了較好解,在測試問題DTLZ1～7中,除DTLZ4 外,本文算法的結果都優于K-RVEA.這是因為 DTLZ4的Pareto 前沿是一條退化的覆蓋在目標空間中一個子空間曲線,而SAExp-EMO 在使用參考向量搜索模型最優解集的過程中,有大量沒有分配到解的空參考向量,這使得收斂到Pareto前沿的求解過程緩慢,而CSEA 算法在DTLZ4 上取得了最好的效果,主要歸因于CSEA 中基于徑向空間劃分的更新參考點的策略.從表2 可以看出,SAExp-EMO 算法在10 個目標的DTLZ1、DTLZ2、DTLZ3 和DTLZ7 的結果明顯優于K-RVEA,這歸因于K-RVEA 模型最優解集搜索的頻率是固定的,在高維的決策空間中,會導致種群搜索陷入局部某塊區域,不利于找到有前途的候選解.與CSEA 相比,SAExp-EMO 在26 個問題上獲得了較好解,只有在3 個問題上沒有比過CSEA,表明了本文算法在求解高維多目標優化問題上具有較好的性能.

表2 SAExp-EMO、RVEA、K-RVEA 和CSEA 得到的平均IGD 值Table 2 Average IGD values obtained by SAExp-EMO,RVEA,K-RVEA and CSEA

為進一步查看最后非支配解集的分布,圖2(a)給出了各個算法在3 個目標的DTLZ1 測試問題上找到的最優非支配解集.三角形、正方形、菱形分別表示算法K-RVEA、CSEA 和SAExp-EMO 所獲得最優非支配解集.由圖2(a)可知,SAExp-EMO所獲得非支配解的目標函數值比K-RVEA 和CSEA都小.在相同的評價次數下,相比于K-RVEA,CSEA算法SAExp-EMO 獲得的種群更靠近真實的Pareto前沿,說明SAExp-EMO 算法有更快和更好的收斂性,同時從解的分布看,SAExp-EMO 所找到的目標空間具有更好解的分布性.圖2(b)為K-RVEA,CSEA,以及SAExp-EMO 在3 個目標DTLZ1 上獨立運行20 次獲得的IGD 均值的收斂圖.由圖2(b)可以看出,在相同的評價次數下,SAExp-EMO獲得了比K-RVEA 和CSEA 更好的IGD 值,同時SAExp-EMO 算法具有更快的收斂速度.

圖2 不同算法在DTLZ1 上的性能結果對比Fig.2 Performance comparison of different methods on three-objective DTLZ1 problem

4 結束語

針對代理模型輔助的計算費時多目標問題的優化,本文提出了一種新的填充準則,基于角度懲罰距離以及目標估值的平均不確定度,改進期望提高計算方式,用于選擇使用真實目標函數計算的個體.算法在3、4、6、8 和10 個目標的DTLZ 基準測試問題上進行了測試,和其他有代表性的代理模型輔助的多目標進化算法的實驗結果相比,本文所提方法具有更好的求解性能.

目前,高斯過程模型面臨最大的問題是當決策空間維度增加時,訓練時間會呈現指數級增長,導致在決策空間高維上很難使用.為此,如何求解決策空間高維的多目標計算費時優化問題,需要進一步展開研究.