面向多目標優化的多樣性代理輔助進化算法*

孫哲人,黃玉劃,陳志遠

(南京航空航天大學 計算機科學與技術學院,江蘇 南京 211106)

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

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

目前,常用的代理模型主要有多項式響應模型、Kriging 模型、神經網絡模型、徑向基函數網絡模型和支持向量回歸模型,但在選擇代理模型方面缺乏理論指導[2].一般來說,在使用插值法的模型中,首選的是Kriging模型,因為Kriging 模型在評估解的目標值的同時,可以給出解的不確定性,而不需要額外使用其他方法來計算不確定性.因為有此特性,Kriging 模型是代理輔助進化算法一個較為流行的選擇,如Knowles 提出的ParEGO[15],Ponweiser 等人提出的SMS-EGO[16],Zhang 等人提出的MOEA/D-EGO[17]和Chugh 等人提出的K-RVEA[18]都使用了Kriging 模型.

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

1 背景知識

1.1 多目標優化問題

多目標優化問題的一般形式如下:

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

1.2 代理輔助進化算法

代理輔助進化算法中的評估方式分為兩種.

? 一種為真實評估,即用原昂貴問題進行評估,正如引言部分提到的,用原昂貴問題進行評估一般需要仿真計算、真實實驗、數據驅動的方式,需要巨大的代價.因此,真實評估需要被限制使用,不然優化時間會是難以接受的;

? 另一種為模型評估,即用訓練的代理模型進行評估,這種方式相比真實評估只需要非常少的消耗.

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

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

1.3 相關工作

目前有較多研究針對解決多目標昂貴問題的代理輔助進化算法,這里簡要介紹較為流行的算法.

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

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

? Zhang 等人提出的MOEA/D-EGO[17]先對進化算法得到解聚類,然后把EI 作為選擇策略,在每一簇中選擇一個解進行真實評估.此外,它采用模糊聚類的方法建立代理模型,在利用所有真實評估的解的同時減少了建模時間.與ParEGO 相比,MOEA/D-EGO 運行速度相對更快,因為它每次批量選擇解,而不只是選擇單個解;

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

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

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

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

? 步驟1、步驟2 是初始化部分,該部分先在目標空間內均勻生成參考向量,再隨機采樣初始解,并在真實評估后加入種群P和訓練集A;

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

算法1.DSAEA 算法框架.

DSAEA 主要由初始化、代理模型構建、最小相關解集計算、候選解生成算子、選擇算子、訓練集更新這6 個部分組成,下面分別進行詳細說明.

2.1 初始化

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

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

且滿足:

其中,H用于控制參考向量生成的間隔,m為目標數量.生成參考向量的數量為;

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

2.2 代理模型構建

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

為了建立一個廉價的Kriging 模型,我們需要兩點假設.

? 第一,假設對于任意x,其目標函數值y都滿足:

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

? 第二,假設對于任意兩個xi和xj,它們的高斯隨機過程的協方差與它們的之間的距離相關,表示如下:

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

在以上假設的基礎上,對于NI個訓練樣本,我們可以最大似然,公式(4),來估計參數μ和σ2:

其中,y為訓練樣本的目標函數值,1 為長度為NI的單位列向量,det(R)為相關矩陣R 的行列式.R 表示如下:

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

其中,rT是樣本與輸入的相關矩陣:

2.3 最小相關解集計算

因為候選解生成算子、選擇算子和訓練集更新都需要計算最小相關解集,算法2 用于算法3、算法5 和算法6 中,所以這里優先對其進行介紹.

把原問題分解為多個單目標子問題來求解,可以較好地權衡解的收斂性和多樣性[8,9].這里的計算最小相關解集也是基于分解的思想,它引入參考向量把原問題分解為多個單目標子問題,再求得每一個子問題最小相關解.所有參考向量的最小相關解組成的集合即為最小相關解集.其中的每一個最小相關解對應一個子問題的當前最優解,因而最小相關解集的大小與解的多樣性有關.最小相關解集越大,則越多的子問題存在當前最優解,即這個集合的多樣性越好;反之亦然.

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

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

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

算法2.最小相關解集MCS.

2.4 候選解生成算子

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

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

2.5 選擇算子

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

算法4.選擇算子Selection.

算法5.篩選.

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

公式(13)中的p是一個系數,本文實驗取是所有目標上不確定性組成的向量,其中,f1對應的不確定性取負.

對Xa或Xia的篩選見算法5,其主要目的是根據現有真實評估過的解來刪除一些希望渺茫的解,從而提高最終選出的解的質量.

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

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

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

2.6 訓練集更新

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

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

算法6.訓練集更新Update.

3 實 驗

由于使用原昂貴問題評估需要花費大量的時間,若采用真實的昂貴問題,那么對比實驗將會花費巨量的時間,實驗的時間花費將會令人難以接受.因此,我們限制測試問題的真實評估次數來模擬解決昂貴多目標優化問題的場景,即測試問題只會被有限次地用于評估解.

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

3.1 測試問題集

實驗選用ZDT[29]和DTLZ[30]測試問題作為基準測試問題.其中,選用ZDT1-4 和ZDT6 作為2 目標基準測試問題,選用DTLZ1-7 作為3 目標基準測試問題.

3.2 度量指標

實驗選用反向迭代距離(inverted generational distance,簡稱IGD)[9]和超體積(hypervolume,簡稱HV)[31]作為度量指標.

(1) IGD 計算公式如下:

其中,P是對PF 均勻采樣后得到的目標向量集合,P*是算法計算得到的目標向量集合,d(v,P)是一個目標向量v∈P*到P中最近的向量的距離.本文實驗在PF 上均勻取10 000 個點作為參考點來計算IGD.

(2) HV 計算公式如下:

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

3.3 參數設置

(1) 一般設置

? 決策變量數量:ZDT 設置為12,DTLZ 設置為10;

? 目標變量數量:ZDT 設置為2,DTLZ 設置為3;

? 最大真實評估次數:ZDT 設置為200 次,DTLZ 設置為300 次;

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

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

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

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

? 參考向量數量:2 目標300 個(H=299),3 目標595 個(H=33).

? 獨立運行次數:每個算法對每個測試問題獨立運行30 次.

(2) 其他設置

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

3.4 實驗結果

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

Table 1 Results of IGD 表1 反向迭代距離結果

Table 2 Results of HV表2 超體積結果

Table 3 Results of running time表3 運行時間結果

圖2、圖3 給出了DSAEA 與對比算法在ZDT,DTLZ 問題上的收斂曲線,橫坐標為真實評估次數,縱坐標為IGD 指標.

對于ZDT 測試問題:

? IGD 和HV 結果表明:在實驗設置一致的情況下,DSAEA 明顯表現更好;

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

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

對于DTLZ 測試問題,IGD,HV 結果和收斂曲線表明:在實驗設置一致的情況下,DSAEA 在大多數的測試問題上明顯表現更好;只有在DTLZ4 測試問題上,DSAEA 與K-RVEA 的效果相當;在DTLZ6 問題上,DSAEA 的表現不如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 問題上的收斂曲線(續)

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

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

在本實驗中,DLTZ6 問題在決策空間內存在4 個不連續的PS區域,需要算法具有更高的探索能力.DSAEA是基于多樣性的,在模型評估下,很好的解可能會被淘汰,轉而保留增加多樣性的解,這樣可能會錯過部分真實評估下很好的解.即便如此,DSAEA 的探索的大體趨勢仍然要優于MOEA/D-EGO.

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

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

從運行時間上來看,DSAEA 運行速度不亞于目前較為流行的算法.

由此可見,相比對比算法,DSAEA 在限制評估次數的情況下可以更加有效地解決實驗選用的測試問題,主要分析有以下幾點.

? 首先,DSAEA 引入參考向量的最小相關解來保持多樣性.DSAEA 中,候選解生成算子不是按照支配關系迭代優化候選解,而是按照多樣性,即會出現淘汰非支配解但保留支配解的情況.例如,x1支配x2,但x1所在參考向量已存在最小相關解且優于x1,而x2所在參考向量不存在相關解,則x1會被淘汰,而x2會被保留.值得一提的是:由于這里是采用模型評估,而模型評估總是存在一定的誤差,所以在模型評估下的非支配解在真實評估下可能是支配解;反之亦然.此外,按照多樣性保留解可以增加探索范圍,避免陷入探索單一方向.因此,DSAEA 中候選解生成算子更有可能找到更多有希望的解,即,候選解生成算子迭代優化的目標是在模型評估下表現優秀的解以及未探索區域內的解;

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

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

4 總 結

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

在實驗中,對于大規模問題來說,決策變量的數量設置較小,但仍有部分測試問題沒有很好地收斂.當決策變量的量變得更大時,搜索和建模壓力會隨之上升,這對進化算法的選擇和建模方法是一個巨大的挑戰.另外,由于隨著目標數量的增加,需要更多的解來近似表示PF,而昂貴問題中真實評估次數十分有限,所以如何用有限的點來有效地表示PF,也是一個嚴峻的挑戰.