孫超利 李 貞 金耀初

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

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

雖然代理模型在單目標(biāo)計算費時問題的優(yōu)化中獲得了較多關(guān)注,但其在計算費時多目標(biāo)優(yōu)化問題中的應(yīng)用還處于起步階段,目前還有很多亟待解決的問題.

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 高斯過程

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

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

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

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

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

1.2 RVEA 算法

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

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

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

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

2 代理模型輔助的計算費時進化高維多目標(biāo)優(yōu)化

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

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

2.1 模型最優(yōu)解集的搜索

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

2.2 改進的填充準(zhǔn)則

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

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

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

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

算法3.改進的填充準(zhǔn)則

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

3 實驗驗證

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

3.1 參數(shù)設(shè)置

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

3.2 性能指標(biāo)

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

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

3.3 實驗結(jié)果及分析

3.3.1 搜索模型最優(yōu)解集的最大評價次數(shù)L

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

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

3.3.2 不同算法中的實驗結(jié)果

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

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

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

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

4 結(jié)束語

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

目前,高斯過程模型面臨最大的問題是當(dāng)決策空間維度增加時,訓(xùn)練時間會呈現(xiàn)指數(shù)級增長,導(dǎo)致在決策空間高維上很難使用.為此,如何求解決策空間高維的多目標(biāo)計算費時優(yōu)化問題,需要進一步展開研究.