孫哲人,黃玉劃,陳志遠(yuǎn)

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106)

多目標(biāo)優(yōu)化問題(multi-objective optimization problem,簡(jiǎn)稱MOP)[1]是指包含兩個(gè)或兩個(gè)以上目標(biāo)的優(yōu)化問題,其目標(biāo)之間往往相互沖突且難以相互比較.由于能夠較好地權(quán)衡多目標(biāo)優(yōu)化問題中的多個(gè)目標(biāo),進(jìn)化算法逐漸成為了很多領(lǐng)域中解決多目標(biāo)優(yōu)化問題的一種較為流行的工具[2],如經(jīng)濟(jì)、金融、工程[3-5].

在過去的30 多年里,專家學(xué)者對(duì)多目標(biāo)進(jìn)化算法進(jìn)行了大量的研究,提出了許多先進(jìn)的算法,大體可以分成基于支配、基于分解和基于指標(biāo)這3 種[6]:基于支配的算法主要有Zitzler 等人提出的SPEA2[7]和Deb 等人提出的NSGA-II[8],基于分解的算法主要有Deb 等人提出的NSGA-III[9]和Zhang 等人提出的MOEA/D[10],基于指標(biāo)的算法主要有Zitzler 等人提出的IBEA[11]和Beume 等人提出的SMS-EMOA[12].進(jìn)化算法在解決多目標(biāo)優(yōu)化問題時(shí),需要對(duì)解進(jìn)行大量的真實(shí)評(píng)估,即,使用原始的目標(biāo)函數(shù)評(píng)估解.然而,現(xiàn)實(shí)中存在很多問題需要計(jì)算機(jī)仿真、真實(shí)實(shí)驗(yàn)或數(shù)據(jù)驅(qū)動(dòng)的方式來評(píng)估,因此其評(píng)估過程往往需要花費(fèi)大量時(shí)間、人力、物力和財(cái)力,這類問題被稱為昂貴問題[13],如創(chuàng)傷系統(tǒng)優(yōu)化[14]等.對(duì)于昂貴問題,由于受到評(píng)估時(shí)間的限制,進(jìn)化算法難以在短時(shí)間內(nèi)給出較好的結(jié)果.而代理輔助進(jìn)化算法可以通過廉價(jià)的模型評(píng)估代替昂貴的真實(shí)評(píng)估來加速進(jìn)化算法,大大減少評(píng)估過程的代價(jià),同時(shí)能夠保證較好的優(yōu)化結(jié)果.

目前,常用的代理模型主要有多項(xiàng)式響應(yīng)模型、Kriging 模型、神經(jīng)網(wǎng)絡(luò)模型、徑向基函數(shù)網(wǎng)絡(luò)模型和支持向量回歸模型,但在選擇代理模型方面缺乏理論指導(dǎo)[2].一般來說,在使用插值法的模型中,首選的是Kriging模型,因?yàn)镵riging 模型在評(píng)估解的目標(biāo)值的同時(shí),可以給出解的不確定性,而不需要額外使用其他方法來計(jì)算不確定性.因?yàn)橛写颂匦?Kriging 模型是代理輔助進(jìn)化算法一個(gè)較為流行的選擇,如Knowles 提出的ParEGO[15],Ponweiser 等人提出的SMS-EGO[16],Zhang 等人提出的MOEA/D-EGO[17]和Chugh 等人提出的K-RVEA[18]都使用了Kriging 模型.

以上提到的算法是此領(lǐng)域較為流行且具有代表性的算法,它們選擇解的時(shí)候更多關(guān)注解在模型評(píng)估下的收斂性.但很多情況下,在模型評(píng)估下的好解是偽好解,即在真實(shí)評(píng)估下并不是好解.對(duì)于Kriging 模型來說,訓(xùn)練樣本的分布對(duì)模型評(píng)估的準(zhǔn)確度有很大的影響,訓(xùn)練樣本在需要評(píng)估的解四周分布越廣泛,則模型評(píng)估會(huì)相對(duì)越準(zhǔn)確[19].對(duì)于多目標(biāo)優(yōu)化問題,廣泛分布在帕累托前沿(Pareto front,簡(jiǎn)稱PF)上的解,也會(huì)較為廣泛分布在帕累托最優(yōu)集合(Pareto set,簡(jiǎn)稱PS)上[20].因此,如果能夠在真實(shí)PF 附近得到分布較為廣泛的樣本,Kriging 模型就可以較好地近似真實(shí)PF 附近的局部空間,從而增加找到在真實(shí)PF 附近的解的可能.這就需要更多地考慮多樣性,而不只是收斂性.因此,本文提出了基于多樣性的代理輔助進(jìn)化算法(DSAEA)來解決昂貴多目標(biāo)優(yōu)化問題.

1 背景知識(shí)

1.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題的一般形式如下:

其中,F(x)={f1(x),...,fm(x)}T為m個(gè)目標(biāo)組成的目標(biāo)向量,x={x1,...,xd}T為d個(gè)決策變量組成的決策向量,Rd為d維決策空間,Rm為m維目標(biāo)空間,F 表示從決策空間映射到目標(biāo)空間.當(dāng)且僅當(dāng)?i={1,...,m},fi(xk)≤fi(xl)和?j={1,...,m},fj(xk)＜fj(xl),則稱xk支配xl.如果一個(gè)解在解集中沒有解能夠支配它,則稱為非支配解;反之,則稱為支配解.所有非支配解的決策向量構(gòu)成的集合叫做帕累托最優(yōu)集合PS,對(duì)應(yīng)的目標(biāo)向量構(gòu)成的集合叫做帕累托前沿PF.

1.2 代理輔助進(jìn)化算法

代理輔助進(jìn)化算法中的評(píng)估方式分為兩種.

? 一種為真實(shí)評(píng)估,即用原昂貴問題進(jìn)行評(píng)估,正如引言部分提到的,用原昂貴問題進(jìn)行評(píng)估一般需要仿真計(jì)算、真實(shí)實(shí)驗(yàn)、數(shù)據(jù)驅(qū)動(dòng)的方式,需要巨大的代價(jià).因此,真實(shí)評(píng)估需要被限制使用,不然優(yōu)化時(shí)間會(huì)是難以接受的;

? 另一種為模型評(píng)估,即用訓(xùn)練的代理模型進(jìn)行評(píng)估,這種方式相比真實(shí)評(píng)估只需要非常少的消耗.

本文所涉及到的代理輔助進(jìn)化算法流程如圖1 所示,更多有關(guān)代理輔助進(jìn)化算法的內(nèi)容可以查閱文獻(xiàn)[2,13].圖1 中,初始化是在決策空間內(nèi)隨機(jī)采樣一定數(shù)量的解,并進(jìn)行真實(shí)評(píng)估.這些解作為訓(xùn)練集,用于建立代理模型.候選解生成算子是在模型評(píng)估下迭代優(yōu)化產(chǎn)生候選解.選擇算子是在候選解中選擇部分候選解進(jìn)行真實(shí)評(píng)估,并加入到訓(xùn)練集以更新代理模型.此時(shí),若未達(dá)到真實(shí)評(píng)估上限,則繼續(xù)迭代優(yōu)化;否則輸出真實(shí)評(píng)估過的解,即種群中的非支配解.其中,與一般進(jìn)化算法的選擇過程不同的是:由于受到真實(shí)評(píng)估次數(shù)的限制,同時(shí),模型評(píng)估與真實(shí)評(píng)估的函數(shù)值存在一定的誤差,代理輔助進(jìn)化算法需要選擇更具代表性的解[17].即:在現(xiàn)有種群中對(duì)候選解的收斂性與多樣性進(jìn)行權(quán)衡,而不是直接按照適應(yīng)度值進(jìn)行選擇.另外,新候選解的產(chǎn)生并不是把當(dāng)前種群直接作為父代解,同時(shí),真實(shí)評(píng)估的解較少,因此在代理輔助進(jìn)化算法中,種群并沒有明顯的迭代更新過程,而是用于保存所有真實(shí)評(píng)估過的解.

Fig.1 Flow diagram of the SAEA圖1 代理輔助進(jìn)化算法流程示意圖

1.3 相關(guān)工作

目前有較多研究針對(duì)解決多目標(biāo)昂貴問題的代理輔助進(jìn)化算法,這里簡(jiǎn)要介紹較為流行的算法.

? Knowles 提出的ParEGO[15]拓展了EGO[19],并首次把EGO 用于解決多目標(biāo)優(yōu)化問題.ParEGO 把問題均勻劃分成多個(gè)子問題,即把多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,每次隨機(jī)選取一個(gè)子問題,把預(yù)期改善(EI)[19]作為選擇策略來選擇進(jìn)行真實(shí)評(píng)估的解.此外,ParEGO 還限制了訓(xùn)練集的大小以減少建模時(shí)間;

? Ponweiser 等人提出的SMS-EGO[16]使用下置信界(LCB)[21]來劃分解的支配關(guān)系,把得到的解分成非ε支配解、ε支配解、支配解:對(duì)于非ε支配解,SMS-EGO 計(jì)算其S-metric作為適應(yīng)度;對(duì)于ε支配解和支配解,SMS-EGO 分配一個(gè)懲罰值作為適應(yīng)度,距離非支配解越遠(yuǎn)懲罰越大.基于此選擇策略來選擇進(jìn)行真實(shí)評(píng)估的解.雖然SMS-EGO 表現(xiàn)不錯(cuò),但是由于需要大量計(jì)算S-metric,所以它的運(yùn)行時(shí)間特別長(zhǎng);

? Zhang 等人提出的MOEA/D-EGO[17]先對(duì)進(jìn)化算法得到解聚類,然后把EI 作為選擇策略,在每一簇中選擇一個(gè)解進(jìn)行真實(shí)評(píng)估.此外,它采用模糊聚類的方法建立代理模型,在利用所有真實(shí)評(píng)估的解的同時(shí)減少了建模時(shí)間.與ParEGO 相比,MOEA/D-EGO 運(yùn)行速度相對(duì)更快,因?yàn)樗看闻窟x擇解,而不只是選擇單個(gè)解;

? Chugh 等人提出的K-RVEA[18]更多的貢獻(xiàn)在模型管理策略上.它把本次得到的候選解與上一次得到的候選解分別分配到一組參考向量上:如果不活躍的參考向量在數(shù)量上的變化少于一定的數(shù)量,就采用不確定性作為選解依據(jù);否則采用角度懲罰距離作為選解依據(jù).此外,K-RVEA 在更新模型的時(shí)候會(huì)篩選解來限制訓(xùn)練集的大小,從而減少建模時(shí)間;

? Pan 等人提出的CSEA[22]采用前饋神經(jīng)網(wǎng)絡(luò)(FNNs)模型作為代理模型,其作用不同于以上幾個(gè)算法,這里代理模型是作為分類器使用.迭代開始時(shí),它把真實(shí)評(píng)估的解按比例分成訓(xùn)練集和測(cè)試集,并計(jì)算出分類器在測(cè)試集上非支配解和支配解的錯(cuò)誤率.在選擇過程中,分類器把進(jìn)化算法得到的解分成非支配解和支配解兩類;同時(shí),根據(jù)分類器在測(cè)試集上的錯(cuò)誤率與閾值對(duì)比來確定是選擇非支配解還是選擇支配解進(jìn)行真實(shí)評(píng)估.

2 基于多樣性的代理輔助進(jìn)化算法(DSAEA)

DSAEA 算法框架如算法1 所示.

? 步驟1、步驟2 是初始化部分,該部分先在目標(biāo)空間內(nèi)均勻生成參考向量,再隨機(jī)采樣初始解,并在真實(shí)評(píng)估后加入種群P和訓(xùn)練集A;

? 步驟3～步驟10 是算法的主要迭代過程,在真實(shí)評(píng)估次數(shù)達(dá)到上限后,算法便會(huì)終止并輸出最終解,即種群P中的非支配解.其中:步驟4 是用訓(xùn)練集A來訓(xùn)練代理模型;步驟5 是候選解生成算子,它會(huì)在模型評(píng)估下迭代優(yōu)化候選解,如算法3;步驟6 是選擇算子,它是根據(jù)選擇策略選擇μ個(gè)候選解進(jìn)行真實(shí)評(píng)估,如算法4、算法5;步驟8 是訓(xùn)練集更新,如算法6.訓(xùn)練集A會(huì)在每一次迭代后進(jìn)行更新,以保證下一次迭代時(shí)訓(xùn)練出的模型有較好的精度.

算法1.DSAEA 算法框架.

DSAEA 主要由初始化、代理模型構(gòu)建、最小相關(guān)解集計(jì)算、候選解生成算子、選擇算子、訓(xùn)練集更新這6 個(gè)部分組成,下面分別進(jìn)行詳細(xì)說明.

2.1 初始化

初始化部分主要包括均勻生成參考向量和生成初始解.

(1) 均勻生成參考向量:利用正則單形點(diǎn)陣設(shè)計(jì)方法[23,24]在單位超平面上生成一組均勻分布的參考向量.對(duì)于每個(gè)參考向量,從下面集合中均勻取值:

且滿足:

其中,H用于控制參考向量生成的間隔,m為目標(biāo)數(shù)量.生成參考向量的數(shù)量為;

(2) 生成初始解:利用拉丁超立方隨機(jī)采樣(LHS)[25]方法對(duì)決策空間均勻采樣初始解.如文獻(xiàn)[15,17,18]所述,較為合適的隨機(jī)采樣次數(shù)為11d-1,其中,d為決策變量的數(shù)量.

2.2 代理模型構(gòu)建

本文采用Kriging 模型作為代理模型,即高斯過程來擬合目標(biāo)函數(shù),分別對(duì)每一個(gè)目標(biāo)建模.一方面,Kriging模型在評(píng)估目標(biāo)值的同時(shí)可以給出該目標(biāo)上的不確定性,不需要使用額外的方法評(píng)估解的不確定性;另一方面,Kriging 模型因其有效性而較為流行,很多研究都使用它,方便對(duì)比.下面對(duì)訓(xùn)練Kriging 模型做一個(gè)簡(jiǎn)要說明,更多細(xì)節(jié)見文獻(xiàn)[19,26].

為了建立一個(gè)廉價(jià)的Kriging 模型,我們需要兩點(diǎn)假設(shè).

? 第一,假設(shè)對(duì)于任意x,其目標(biāo)函數(shù)值y都滿足:

其中,μ是回歸模型的預(yù)測(cè)值,ε～N(0,σ2);

? 第二,假設(shè)對(duì)于任意兩個(gè)xi和xj,它們的高斯隨機(jī)過程的協(xié)方差與它們的之間的距離相關(guān),表示如下:

其中,θk和pk為超參數(shù),pk∈[1,2].

在以上假設(shè)的基礎(chǔ)上,對(duì)于NI個(gè)訓(xùn)練樣本,我們可以最大似然,公式(4),來估計(jì)參數(shù)μ和σ2:

其中,y為訓(xùn)練樣本的目標(biāo)函數(shù)值,1 為長(zhǎng)度為NI的單位列向量,det(R)為相關(guān)矩陣R 的行列式.R 表示如下:

為了最大化公式(4),可以得到μ和σ2:

其中,rT是樣本與輸入的相關(guān)矩陣:

2.3 最小相關(guān)解集計(jì)算

因?yàn)楹蜻x解生成算子、選擇算子和訓(xùn)練集更新都需要計(jì)算最小相關(guān)解集,算法2 用于算法3、算法5 和算法6 中,所以這里優(yōu)先對(duì)其進(jìn)行介紹.

把原問題分解為多個(gè)單目標(biāo)子問題來求解,可以較好地權(quán)衡解的收斂性和多樣性[8,9].這里的計(jì)算最小相關(guān)解集也是基于分解的思想,它引入?yún)⒖枷蛄堪言瓎栴}分解為多個(gè)單目標(biāo)子問題,再求得每一個(gè)子問題最小相關(guān)解.所有參考向量的最小相關(guān)解組成的集合即為最小相關(guān)解集.其中的每一個(gè)最小相關(guān)解對(duì)應(yīng)一個(gè)子問題的當(dāng)前最優(yōu)解,因而最小相關(guān)解集的大小與解的多樣性有關(guān).最小相關(guān)解集越大,則越多的子問題存在當(dāng)前最優(yōu)解,即這個(gè)集合的多樣性越好;反之亦然.

DSAEA 是按照解與參考向量的角度來判定它們的相關(guān)性的,并在此基礎(chǔ)上得到參考向量的最小相關(guān)解.

解x 與參考向量w 的角度θ的計(jì)算如下:

最小相關(guān)解集的具體算法見算法2,其中,d(x,z*)為解x 到理想點(diǎn)z*的距離.對(duì)于解集X中的每個(gè)解x,其相關(guān)參考向量是與x 相差角度最小的參考向量.對(duì)于一個(gè)參考向量w,其相關(guān)解為所有相關(guān)參考向量為w 的解,可能沒有也可能很多個(gè).參考向量w 的最小相關(guān)解為w 的相關(guān)解中距離理想點(diǎn)z*最近的一個(gè).所有參考向量的最小相關(guān)解組成的集合即為解集X的最小相關(guān)解集.其中,z*=(min(f1),...,min(fm)),min(fi)為種群P中的解在第i個(gè)目標(biāo)上的最小值.

算法2.最小相關(guān)解集MCS.

2.4 候選解生成算子

候選解生成算子是在模型評(píng)估下迭代優(yōu)化候選解,以得到在現(xiàn)有模型下表現(xiàn)較為優(yōu)秀的候選解,具體見算法3.為了充分利用現(xiàn)有條件,候選解生成算子使用訓(xùn)練集A作為初始解,而不是重新隨機(jī)采樣.每次生成子代解之前,如果|X|小于|A|,就從訓(xùn)練集A中隨機(jī)選擇|A|-|X|個(gè)解加入X.這樣可以使X中解的數(shù)量不會(huì)太少,以提高算法的探索能力和解的多樣性,從而更大機(jī)會(huì)搜索到更多有希望的候選解.在得到初始父代解后,候選解生成算子使用模擬二進(jìn)制交叉(simulated binary crossover)[27]和多項(xiàng)式突變(polynomial mutation)[28]算子生成子代解,并使用Kriging 模型評(píng)估其函數(shù)值.然后計(jì)算父代解和子代解并集的最小相關(guān)解集,把最小相關(guān)解集中的解作為下一代父代解繼續(xù)迭代優(yōu)化.當(dāng)達(dá)到最大迭代次數(shù)時(shí),輸出候選解集.

算法3.候選解生成算子Candidates.

2.5 選擇算子

選擇算子是在候選解集中選擇部分解進(jìn)行真實(shí)評(píng)估,具體見算法4.其先是找到每個(gè)解x∈X的鄰居參考向量,然后根據(jù)是否存在活躍的鄰居參考向量,把x 加入Xa或Xia.這里的活躍與否是看該參考向量在種群P中是否有相關(guān)解,即該子問題上是否存在已經(jīng)真實(shí)評(píng)估的解.接下來,算法對(duì)Xa和Xia進(jìn)行篩選,刪除一些希望渺茫的解,見算法5.然后,對(duì)解集X使用Kmeans 方法聚類,劃分成μ個(gè)簇,并在每個(gè)簇中選擇一個(gè)與理想點(diǎn)z*距離最小的解.與文獻(xiàn)[17,18]中所說明的一致,在本文實(shí)驗(yàn)中,μ設(shè)置為5.

算法4.選擇算子Selection.

算法5.篩選.

由于模型評(píng)估具有一定的誤差,真實(shí)評(píng)估的函數(shù)值相對(duì)模型評(píng)估的函數(shù)值會(huì)發(fā)生一定程度的偏移.這里,我們根據(jù)解的不確定性來確定其鄰居參考向量.算法4 中的閾值θth的計(jì)算如公式(12):

公式(13)中的p是一個(gè)系數(shù),本文實(shí)驗(yàn)取是所有目標(biāo)上不確定性組成的向量,其中,f1對(duì)應(yīng)的不確定性取負(fù).

對(duì)Xa或Xia的篩選見算法5,其主要目的是根據(jù)現(xiàn)有真實(shí)評(píng)估過的解來刪除一些希望渺茫的解,從而提高最終選出的解的質(zhì)量.

其中,Xia為不存在活躍的鄰居參考向量的解,即x∈Xia周圍不存在真實(shí)評(píng)估的解.一方面,考慮到x 周圍沒有真實(shí)評(píng)估的解,需要盡量保留x 以探索其附近;另一方面,保留過差的x 對(duì)模型和種群都沒有任何改善,因此,這里用種群P中所有的解來計(jì)算一個(gè)大體范圍來篩選Xia.這里把d(Xr,z*)的最大值作為閾值dth篩選解Xia,刪除d(x,z*)＞dth的x.其中,d(Xr,z*)為集合Xr中每一個(gè)解到理想點(diǎn)z*的距離.

Xa為存在活躍的鄰居參考向量的解,即x∈Xa周圍存在真實(shí)評(píng)估的解.這里按照其鄰居參考向量的最小相關(guān)解排序后的下四分位篩選Xa,閾值為

下四分位是描述整體樣本前一半的平均指標(biāo),即保留與鄰居參考向量上的最小相關(guān)解相比較好的x,這樣對(duì)x 周圍有較大的改善.

2.6 訓(xùn)練集更新

訓(xùn)練集A在每次迭代后都會(huì)進(jìn)行更新,以保存多樣性較好的解,以提高模型擬合的精度;同時(shí),刪除價(jià)值不大的解以減少建模時(shí)間.本文實(shí)驗(yàn)設(shè)置訓(xùn)練集A大小下限為11d-1,更新過程見算法6.

為了能夠利用選擇算子選出的解,步驟1 從解集X中選出一個(gè)d(x,z*)最小的解加入訓(xùn)練集A.步驟2 計(jì)算所有參考向量在種群P中的最小相關(guān)解集,并解加入訓(xùn)練集A.這樣就可以得到多樣性較好的的訓(xùn)練集,并且隨著算法的迭代,樣本會(huì)越來越靠近真實(shí)PF,從而幫助Kriging 模型較好地?cái)M合真實(shí)PF 附近的空間.步驟4、步驟5從相關(guān)解最少的參考向量的相關(guān)解中選出最好的解加入訓(xùn)練集A.這是為了補(bǔ)充訓(xùn)練樣本,防止訓(xùn)練樣本過少而導(dǎo)致模型準(zhǔn)確度下降.

算法6.訓(xùn)練集更新Update.

3 實(shí) 驗(yàn)

由于使用原昂貴問題評(píng)估需要花費(fèi)大量的時(shí)間,若采用真實(shí)的昂貴問題,那么對(duì)比實(shí)驗(yàn)將會(huì)花費(fèi)巨量的時(shí)間,實(shí)驗(yàn)的時(shí)間花費(fèi)將會(huì)令人難以接受.因此,我們限制測(cè)試問題的真實(shí)評(píng)估次數(shù)來模擬解決昂貴多目標(biāo)優(yōu)化問題的場(chǎng)景,即測(cè)試問題只會(huì)被有限次地用于評(píng)估解.

本文實(shí)驗(yàn)通過在大規(guī)模2 目標(biāo)和3 目標(biāo)優(yōu)化問題上的對(duì)比實(shí)驗(yàn)來證明DSAEA 的有效性.目前提出的基于Kriging 模型且性能較好的代理輔助進(jìn)化算法有ParEGO,MOEA/D-EGO,K-RVEA,SMS-EGO.其中,由于SMS- EGO 需要計(jì)算S-metric來選解,所以運(yùn)行速度非常慢,甚至需要幾個(gè)小時(shí)才能運(yùn)行一次.所以,我們使用另外幾個(gè)算法作為對(duì)比算法.

3.1 測(cè)試問題集

實(shí)驗(yàn)選用ZDT[29]和DTLZ[30]測(cè)試問題作為基準(zhǔn)測(cè)試問題.其中,選用ZDT1-4 和ZDT6 作為2 目標(biāo)基準(zhǔn)測(cè)試問題,選用DTLZ1-7 作為3 目標(biāo)基準(zhǔn)測(cè)試問題.

3.2 度量指標(biāo)

實(shí)驗(yàn)選用反向迭代距離(inverted generational distance,簡(jiǎn)稱IGD)[9]和超體積(hypervolume,簡(jiǎn)稱HV)[31]作為度量指標(biāo).

(1) IGD 計(jì)算公式如下:

其中,P是對(duì)PF 均勻采樣后得到的目標(biāo)向量集合,P*是算法計(jì)算得到的目標(biāo)向量集合,d(v,P)是一個(gè)目標(biāo)向量v∈P*到P中最近的向量的距離.本文實(shí)驗(yàn)在PF 上均勻取10 000 個(gè)點(diǎn)作為參考點(diǎn)來計(jì)算IGD.

(2) HV 計(jì)算公式如下:

其中,P*是算法計(jì)算得到的目標(biāo)向量集合,P′是P*中非支配解的集合,volume是計(jì)算向量到參考點(diǎn)的超體積.本文實(shí)驗(yàn)取點(diǎn)1.1××(max(f1),...,max(fm)),f1,...,fm∈PF 作為參考點(diǎn)來計(jì)算HV.

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

(1) 一般設(shè)置

? 決策變量數(shù)量:ZDT 設(shè)置為12,DTLZ 設(shè)置為10;

? 目標(biāo)變量數(shù)量:ZDT 設(shè)置為2,DTLZ 設(shè)置為3;

? 最大真實(shí)評(píng)估次數(shù):ZDT 設(shè)置為200 次,DTLZ 設(shè)置為300 次;

? 初始采樣數(shù):利用LHS 方法采樣11d-1 個(gè)解,ZDT 問題采樣131 個(gè)解,DTLZ 問題采樣109 個(gè)解;

? 交叉算子:模擬二進(jìn)制交叉(simulated binary crossover)[27],設(shè)置概率為1.0,分布指數(shù)為20;

? 變異算子:多項(xiàng)式突變(polynomial mutation)[28],設(shè)置概率為1/d,分布指數(shù)為20;

? 候選解生成算子的最大評(píng)估次數(shù):20×(11d-1)次模型評(píng)估;

? 參考向量數(shù)量:2 目標(biāo)300 個(gè)(H=299),3 目標(biāo)595 個(gè)(H=33).

? 獨(dú)立運(yùn)行次數(shù):每個(gè)算法對(duì)每個(gè)測(cè)試問題獨(dú)立運(yùn)行30 次.

(2) 其他設(shè)置

DSAEA,MOEA/D-EGO 和K-RVEA 中每次迭代選出的解的數(shù)量設(shè)置為5,即μ=5.其他未說明的參數(shù)設(shè)置與其論文中的一致.

3.4 實(shí)驗(yàn)結(jié)果

IGD 結(jié)果見表1,HV 結(jié)果見表2,算法運(yùn)行時(shí)間如表3.數(shù)字表示該指標(biāo)的平均值,括號(hào)內(nèi)的數(shù)字表示該指標(biāo)的標(biāo)準(zhǔn)差,加粗表示在此測(cè)試問題上該項(xiàng)平均值為最優(yōu)值.另外,我們使用秩和檢驗(yàn)在顯著性水平為0.05 下對(duì)30次獨(dú)立運(yùn)行結(jié)果進(jìn)行分析.“+”表示此算法在此測(cè)試問題上與DSAEA 相比在該指標(biāo)上表現(xiàn)更好,“-”表示此算法在此測(cè)試問題上與DSAEA 相比在該指標(biāo)上表現(xiàn)更差,“≈”表示此算法在此測(cè)試問題上與DSAEA 相比在該指標(biāo)上的表現(xiàn)區(qū)別不大.每個(gè)表格的最后一行還給出了在該指標(biāo)上的+/-/≈結(jié)果的匯總.由于部分測(cè)試問題沒有得到較好的收斂,甚至距離PF 非常遠(yuǎn),如ZDT4,ZDT6,DTLZ1,DTLZ3,DTLZ6.在沒有很好的收斂的情況下,對(duì)比多樣性沒有很大的意義,所以這里不討論以上幾個(gè)測(cè)試問題的HV 指標(biāo).

Table 1 Results of IGD 表1 反向迭代距離結(jié)果

Table 2 Results of HV表2 超體積結(jié)果

Table 3 Results of running time表3 運(yùn)行時(shí)間結(jié)果

圖2、圖3 給出了DSAEA 與對(duì)比算法在ZDT,DTLZ 問題上的收斂曲線,橫坐標(biāo)為真實(shí)評(píng)估次數(shù),縱坐標(biāo)為IGD 指標(biāo).

對(duì)于ZDT 測(cè)試問題:

? IGD 和HV 結(jié)果表明:在實(shí)驗(yàn)設(shè)置一致的情況下,DSAEA 明顯表現(xiàn)更好;

? 而收斂曲線表明:DSAEA 的收斂效果在大多數(shù)情況下要好于對(duì)比算法,只有在 ZDT1-3 問題上,DSAEA 的收斂效果在170 次真實(shí)評(píng)估前不如ParEGO.

由于ZDT1-3 問題較為簡(jiǎn)單,在最初階段,搜索到比現(xiàn)有種群更優(yōu)的解很容易,如果算法根據(jù)收斂性選解,則收斂速度會(huì)很快.但在靠近真實(shí)PF 的區(qū)域內(nèi),搜索到比現(xiàn)有種群更優(yōu)的解相對(duì)不易,需要模型能夠較好地?cái)M合真實(shí)PF 附近的區(qū)域.不同于ParEGO,DSAEA 是基于多樣性選解的,它更傾向于增加解集的多樣性,使代理模型可以較好擬合目前種群最優(yōu)解附近的區(qū)域.因此,DSAEA 的收斂曲線前30 次的收斂效果不如ParEGO,而之后的收斂效果要優(yōu)于它.

對(duì)于DTLZ 測(cè)試問題,IGD,HV 結(jié)果和收斂曲線表明:在實(shí)驗(yàn)設(shè)置一致的情況下,DSAEA 在大多數(shù)的測(cè)試問題上明顯表現(xiàn)更好;只有在DTLZ4 測(cè)試問題上,DSAEA 與K-RVEA 的效果相當(dāng);在DTLZ6 問題上,DSAEA 的表現(xiàn)不如MOEA/D-EGO.

Fig.2 Convergence curve of the algorithms on the ZDT problems圖2 算法在ZDT 問題上的收斂曲線

Fig.3 Convergence curve of the algorithms on the DTLZ problems圖3 算法在DTLZ 問題上的收斂曲線

Fig.3 Convergence curve of the algorithms on the DTLZ problems (Continued)圖3 算法在DTLZ 問題上的收斂曲線(續(xù))

圖4 為DSAEA 和MOEA/D-EGO 的30 次獨(dú)立運(yùn)行中,最接近IGD 平均值的實(shí)驗(yàn)結(jié)果.可以看到:DSAEA大部分的解都集中在內(nèi)部3 個(gè)參考向量附近,且有較多解向這真實(shí)PF 靠攏;而MOEA/D-EGO 大部分的解都集中在邊界的3 個(gè)參考向量附近,其中只有幾個(gè)非常好的解,其余大部分解距離真實(shí)PF 非常遠(yuǎn).

Fig.4 On the DTLZ6 problem,the function evaluated solutions of DSAEA and MOEA/D-EGO are observed from different angles圖4 在DTLZ6 測(cè)試問題上,從不同角度觀察DSAEA 和MOEA/D-EGO 所有真實(shí)評(píng)估的解

在本實(shí)驗(yàn)中,DLTZ6 問題在決策空間內(nèi)存在4 個(gè)不連續(xù)的PS區(qū)域,需要算法具有更高的探索能力.DSAEA是基于多樣性的,在模型評(píng)估下,很好的解可能會(huì)被淘汰,轉(zhuǎn)而保留增加多樣性的解,這樣可能會(huì)錯(cuò)過部分真實(shí)評(píng)估下很好的解.即便如此,DSAEA 的探索的大體趨勢(shì)仍然要優(yōu)于MOEA/D-EGO.

從收斂性和多樣性上來看,DSAEA 要比目前較為流行的算法表現(xiàn)更好.

在運(yùn)行時(shí)間方面,相對(duì)MOEA/D-EGO 和ParEGO,DSAEA 運(yùn)行速度更快.相對(duì)K-RVEA,DSAEA 在大多數(shù)問題上運(yùn)行速度相差不是太多,差異都在3%以下.其中,差異較大的問題為DTLZ1,DTLZ3,DTLZ2,DTLZ6,相比K-RVEA,DSAEA 在前兩個(gè)問題上要慢12%左右,在后兩個(gè)問題上要慢23%左右.對(duì)于以上幾個(gè)問題,因?yàn)槠銹S分布在決策空間中范圍較大,很容易搜索到不同方向的解,即在不同參考向量上的解,這就使訓(xùn)練集A的大小超過11d-1,增加了一定的建模時(shí)間.

從運(yùn)行時(shí)間上來看,DSAEA 運(yùn)行速度不亞于目前較為流行的算法.

由此可見,相比對(duì)比算法,DSAEA 在限制評(píng)估次數(shù)的情況下可以更加有效地解決實(shí)驗(yàn)選用的測(cè)試問題,主要分析有以下幾點(diǎn).

? 首先,DSAEA 引入?yún)⒖枷蛄康淖钚∠嚓P(guān)解來保持多樣性.DSAEA 中,候選解生成算子不是按照支配關(guān)系迭代優(yōu)化候選解,而是按照多樣性,即會(huì)出現(xiàn)淘汰非支配解但保留支配解的情況.例如,x1支配x2,但x1所在參考向量已存在最小相關(guān)解且優(yōu)于x1,而x2所在參考向量不存在相關(guān)解,則x1會(huì)被淘汰,而x2會(huì)被保留.值得一提的是:由于這里是采用模型評(píng)估,而模型評(píng)估總是存在一定的誤差,所以在模型評(píng)估下的非支配解在真實(shí)評(píng)估下可能是支配解;反之亦然.此外,按照多樣性保留解可以增加探索范圍,避免陷入探索單一方向.因此,DSAEA 中候選解生成算子更有可能找到更多有希望的解,即,候選解生成算子迭代優(yōu)化的目標(biāo)是在模型評(píng)估下表現(xiàn)優(yōu)秀的解以及未探索區(qū)域內(nèi)的解;

? 其次,DSAEA 中的選擇算子把解按照周圍是否存在活躍參考向量進(jìn)行劃分篩選.一方面,DSAEA 會(huì)保留相比周圍參考向量的最小相關(guān)解更好的解,以保留在真實(shí)評(píng)估下可能比現(xiàn)有解更好的解,從而提高當(dāng)前解的收斂性;另一方面,DSAEA 會(huì)保留周圍沒有活躍參考向量的解,以對(duì)此未探索區(qū)域進(jìn)行探索,從而提高當(dāng)前解的多樣性.在篩選后,DSAEA 對(duì)保留的解進(jìn)行聚類,選出μ個(gè)代表解進(jìn)行真實(shí)評(píng)估,進(jìn)行批量的真實(shí)評(píng)估大大提升算法運(yùn)行速度.這樣,DSAEA 的選擇算子對(duì)最終解的收斂性和多樣性會(huì)有所幫助;

? 最后,由于測(cè)試問題決策變量數(shù)量較大,屬于大規(guī)模問題,而模型精度有限,所以每次迭代后對(duì)訓(xùn)練集的更新是十分必要的.算法6 先對(duì)所有真實(shí)評(píng)估過的解,即種群P,計(jì)算其最小相關(guān)解加入訓(xùn)練集.若此時(shí)的訓(xùn)練集大小仍小于11d-1,則在剩下的解中按照參考向量上的解的密度繼續(xù)選擇,優(yōu)先選擇密度小的參考向量上的最小相關(guān)解加入訓(xùn)練集.這樣做可以得到在目標(biāo)空間內(nèi)分布較為廣泛且多樣性較好的訓(xùn)練集,在此基礎(chǔ)上,訓(xùn)練的模型會(huì)較好地?cái)M合較大的范圍,并且隨著迭代次數(shù)的增加,訓(xùn)練集會(huì)更加靠近真實(shí)PF 區(qū)域,模型也就可以更好地?cái)M合真實(shí)PF 附近區(qū)域.也就是說,隨著迭代的進(jìn)行,不僅進(jìn)化算法會(huì)朝著真實(shí)PF 附近區(qū)域搜索,而且模型也會(huì)朝著真實(shí)PF 附近區(qū)域靠攏.

4 總 結(jié)

本文提出了基于多樣性的代理輔助進(jìn)化算法(DSAEA)來解決昂貴多目標(biāo)優(yōu)化問題.DSAEA 采用Kriging模型近似每個(gè)目標(biāo).候選解生成算子分配解到對(duì)應(yīng)的參考向量來計(jì)算最小相關(guān)解集,以達(dá)到迭代優(yōu)化候選解的目的.選擇算子篩選出無活躍鄰居參考向量的解,以及表現(xiàn)比大多數(shù)鄰居參考向量的相關(guān)解更好的解.然后對(duì)篩選出的解K-means 聚類,從每個(gè)簇中選擇一個(gè)最好的解進(jìn)行真實(shí)評(píng)估.另外,DSAEA 使用一個(gè)大小下限為11d-1的訓(xùn)練集A作為代理模型的訓(xùn)練集,刪除價(jià)值不大的樣本以降低建模時(shí)間.實(shí)驗(yàn)部分選用大規(guī)模ZDT,DTLZ 測(cè)試問題,與目前流行的MOEA/D-EGO,K-RVEA 和ParEGO 算法進(jìn)行對(duì)比實(shí)驗(yàn).結(jié)果表明:DSAEA 在大多數(shù)選用的測(cè)試問題上,要比以上幾個(gè)算法表現(xiàn)更好.因此,本文的方法是有效可行的.

在實(shí)驗(yàn)中,對(duì)于大規(guī)模問題來說,決策變量的數(shù)量設(shè)置較小,但仍有部分測(cè)試問題沒有很好地收斂.當(dāng)決策變量的量變得更大時(shí),搜索和建模壓力會(huì)隨之上升,這對(duì)進(jìn)化算法的選擇和建模方法是一個(gè)巨大的挑戰(zhàn).另外,由于隨著目標(biāo)數(shù)量的增加,需要更多的解來近似表示PF,而昂貴問題中真實(shí)評(píng)估次數(shù)十分有限,所以如何用有限的點(diǎn)來有效地表示PF,也是一個(gè)嚴(yán)峻的挑戰(zhàn).