陳萬芬，王宇嘉，林煒星

上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620

近年來，進化算法由于其解決復(fù)雜多目標(biāo)優(yōu)化問題的優(yōu)勢被廣泛應(yīng)用于科學(xué)和工程的各個領(lǐng)域。但是為了達到所需的收斂效果，進化算法需要進行大量的適應(yīng)度評估。例如，在汽車工業(yè)中進行一次防撞分析需要36～160個小時，若要求解兩變量工程問題，至少需要50次迭代，每次迭代至少需要一次仿真模擬，那么整個求解設(shè)計過程至少要耗費2個月的時間[1]，在實際工程優(yōu)化問題中顯然是難以接受的。為了緩解上述問題，通常使用計算廉價的代理模型代替昂貴的實際適應(yīng)度評估。

代理模型是指近似的數(shù)學(xué)模型，它可以代替更復(fù)雜、更耗時的數(shù)值分析。在樣本數(shù)據(jù)集上構(gòu)建代理模型以逼近候選解的適應(yīng)度值的計算，這類方法稱為代理輔助進化算法（Surrogate-Assisted Evolutionary Algorithm，SAEA）。許多分類或回歸技術(shù)都可以用作代理模型，如徑向基函數(shù)網(wǎng)絡(luò)（Radial Basis Functions Network，RBFN）[2]、響應(yīng)面方法（Response Surface Methodology，RSM）[3]、Kriging[4]和支持向量回歸（Support Vector Regression，SVR）[5]。不同的代理模型可以針對性地解決不同問題[6]，如RBFN模型用于高階非線性問題，Kriging模型用于高維空間中的低階非線性問題。然而對于大多數(shù)實際問題，其特征是未知的，難以通過單一代理模型解決，通常使用代理集成來提高模型的近似性和預(yù)測的準(zhǔn)確性[7-8]。

集成模型通過使用多個代理模型來減少計算時間，通常有兩種集成模型方法。一種是Singh等人[9]提出的選擇一個在不同代理模型中具有最高準(zhǔn)確性的代理模型來評估個體。另一種是Lim和Jin[10]提出的使用不同的代理模型評估具有不同權(quán)重系數(shù)的個體，將代理模型的集成與提出的廣義代理多目標(biāo)模因算法結(jié)合使用。Singh等人[9]提出了代理模型輔助模擬退火算法，使用集成的代理模型與受約束的Pareto模擬退火作為進化算法框架，根據(jù)均方根誤差選擇代理模型對個體進行評估。Martinez和Coello[11]提出了使用代理模型輔助分解的多目標(biāo)進化算法，將徑向基函數(shù)用作集成模型，算法中為每個目標(biāo)函數(shù)建立了代理模型。還有一些研究使用多個代理模型作為集成來近似函數(shù)，實驗結(jié)果表明，在集成機器學(xué)習(xí)模型中，集成基礎(chǔ)學(xué)習(xí)者輸出的預(yù)測方差可用于近似適應(yīng)性預(yù)測中的不確定性程度[6]。盡管在集成代理方面研究者已經(jīng)作了大量的工作[6，11-12]，但是大多數(shù)都使用集成來提高適應(yīng)度近似的準(zhǔn)確性，很少關(guān)注集成的不確定性信息[13]。因此，研究集成的不確定性信息，對提高代理模型的預(yù)測能力具有重要意義。

為了使集成代理輔助進化算法獲得滿意的優(yōu)化結(jié)果，需要不斷提高集成代理模型的預(yù)測精度，通常是選擇新的樣本點并將其添加到樣本集中來更新代理模型以提高擬合精度。但是，添加點的過程需要大量的采樣點，例如廣義回歸神經(jīng)網(wǎng)絡(luò)（Generalized Regression Neural Network，GRNN）和RBF集 成 的SAEA需 要3 000個采樣點[14]。對創(chuàng)傷系統(tǒng)設(shè)計問題的單個函數(shù)評估需要處理40 000個緊急事件記錄樣本點[15]。但是，在許多實際的優(yōu)化問題中，訓(xùn)練集中的數(shù)據(jù)通常很少。在機翼減阻優(yōu)化設(shè)計中，僅給出了70組數(shù)據(jù)作為初始采樣點[16]。當(dāng)采用添加點的方法來解決這些問題時，預(yù)測精度急劇下降，因此不適用解決樣本數(shù)據(jù)少的問題。

如上所述，大多數(shù)現(xiàn)有的SAEA是基于大數(shù)據(jù)樣本集的，關(guān)于基于小樣本數(shù)據(jù)集對SAEA的研究相對較少。對于小樣本數(shù)據(jù)集，不僅可用數(shù)據(jù)量很小，而且在數(shù)值噪聲和高維優(yōu)化方面仍然存在問題[17-18]。因此，如何最大程度地利用樣本數(shù)據(jù)來構(gòu)建高質(zhì)量的代理模型成為急需解決的問題。本文提出了異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法，當(dāng)訓(xùn)練集中的數(shù)據(jù)較小時，將訓(xùn)練集劃分為幾個子集，然后在每個子集上訓(xùn)練代理模型，最后將它們組合成高精度的代理集成。同時，為了在收斂質(zhì)量和效率之間取得平衡，將全局優(yōu)化與局部優(yōu)化相結(jié)合。使用Kriging和RBFN建立代理模型，前者用于全局優(yōu)化，后者用于局部優(yōu)化，這將在一定程度上緩解高維優(yōu)化的耗時問題。

1 多目標(biāo)粒子群優(yōu)化算法和代理模型

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

通常情況下，多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problems，MOP）包含多個相互沖突的目標(biāo)，以最小化目標(biāo)為例，一般MOP可以描述如下：

其中，x=(x1,x2,…,xn)T∈Ω為n維決策變量（向量），為決策空間，由m個相互矛盾的目標(biāo)函數(shù)組成，?m為目標(biāo)空間，fi(x)表示第i個目標(biāo)函數(shù)。

若決策變量x(1)∈Ω和x(2)∈Ω滿足：

則稱決策變量x(1)支配決策變量x(2)，記為x(1)?x(2)。在MOP中，當(dāng)一個解不受任何其他解支配時，則可以稱為Pareto最優(yōu)解。在搜索空間中，所有Pareto最優(yōu)解的集合形成的權(quán)衡曲面，稱為Pareto前沿。

1.2 粒子群算法

粒子群（Particle Swarm Optimization，PSO）算法是一種基于鳥群的隨機搜索算法[19]。PSO算法利用個體最優(yōu)和全局最優(yōu)引導(dǎo)整個群體的尋優(yōu)，其位置和速度更新公式如下：

由于粒子群算法具有設(shè)置參數(shù)少、運行效率高、易于實現(xiàn)等優(yōu)點，近年來在群智能優(yōu)化領(lǐng)域中被廣泛使用。但是粒子群算法存在易陷入局部最優(yōu)和算法后期收斂速度慢等問題，所以出現(xiàn)了很多改進的粒子群算法。如為了提高算法的搜索能力，采用反向?qū)W習(xí)策略來增強算法的全局搜索能力[20-21]；通過構(gòu)造動態(tài)子空間并隨機對其單維進行變異增強粒子精細搜索的能力[22]。

1.3 代理模型

（1）Kriging模型。Kriging是在高斯過程（Gaussian Process，GP）理論基礎(chǔ)上進行建模的有效插值方法[4]，該方法不僅能預(yù)測未知點的函數(shù)值，還可以提供預(yù)測不確定性的程度，提高模型的搜索能力。Kriging模型不僅能找到最佳的線性無偏估計值，同時還能使預(yù)測的均方誤差最小。Kriging模型由用于全局趨勢預(yù)測的多項式項和用于局部偏差回歸的高斯過程項組成，可以表示為：

其中，x={x1,x2,…,xn}為n維設(shè)計空間的設(shè)計矢量，y(x)為預(yù)測函數(shù)值，線性回歸反映了原始函數(shù)的整體趨勢，hi(x)為回歸模型的基函數(shù)，β={β1,β2,…,βk}代表相應(yīng)的回歸系數(shù)向量，k是基函數(shù)hi(x)的數(shù)量，高斯過程z(x)服從均值為0，方差為σ2的正態(tài)分布。

（2）RBFN模型。RBFN是常用的代理模型之一，可以用作代理模型的局部搜索[2]。RBFN是具有單個隱藏層的前饋神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)由輸入層、隱含層和輸出層組成。隱藏層節(jié)點的激活函數(shù)為徑向基函數(shù)，包括高斯函數(shù)、反射Sigmoid函數(shù)和逆多二次函數(shù)，徑向基函數(shù)的基本形式為：

其中，xi={xi1,xi2,…,xin}表示第i個訓(xùn)練樣本，n和N分別是變量數(shù)和訓(xùn)練樣本數(shù)，α={α1,α2,…,αN}表示權(quán)重系數(shù)，‖·‖為歐幾里德范數(shù)即待測點x與數(shù)據(jù)中心ci之間的歐氏距離，φ(·)為核函數(shù)即徑向函數(shù)，內(nèi)核的典型選擇包括線性樣條、三次樣條、多二次方、薄板樣條和高斯函數(shù)[23]。

2 異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法

2.1 算法框架

代理模型廣泛應(yīng)用于群智能計算中，許多不同適應(yīng)度形態(tài)特性的優(yōu)化問題的實驗結(jié)果表明，RBFN在訓(xùn)練數(shù)據(jù)小的情況下，各類非線性度不同的問題表現(xiàn)最好[24]。并且隨著搜索維度及規(guī)模的增加，RBFN也能有較好的表現(xiàn)。Kriging作為一類統(tǒng)計學(xué)習(xí)模型，非常適合于捕捉復(fù)雜優(yōu)化問題的全局場景，并能獲得與RBFN相媲美的結(jié)果。

為了能夠快速有效地解決不同形態(tài)的優(yōu)化問題，本文提出了異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法，其結(jié)合了Kriging與RBFN的優(yōu)點，構(gòu)建能解決不同形態(tài)問題的異構(gòu)集成模型，并采用多目標(biāo)粒子群優(yōu)化算法作為搜索算法，提高種群對未知解的搜索能力。本文所提算法框架如圖1所示。

圖1 異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法框架圖Fig.1 Framework diagram of heterogeneous ensemble surrogate-assisted multi-objective particle swarm optimization algorithm

從數(shù)據(jù)庫中選取需要的樣本形成樣本子集，根據(jù)采樣得到的樣本子集構(gòu)建所需的代理模型，分別為Kriging模型和RBFN模型，再將其通過平均加權(quán)法進行異構(gòu)集成。對建立的異構(gòu)集成模型進行誤差分析，若不滿足要求，則需要增加樣本點，然后利用整個設(shè)計空間中的樣本點更新代理模型。最后利用多目標(biāo)粒子群優(yōu)化算法對異構(gòu)集成模型進行優(yōu)化，得出目標(biāo)函數(shù)最優(yōu)解集，這在一定程度上減少了多目標(biāo)粒子群算法的評價次數(shù)，降低了計算成本。

異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法具體步驟如下：

步驟1使用最優(yōu)拉丁超立方設(shè)計[25]（Optimal Latin Hypercube Design，OLHD）方法從設(shè)計空間中選取初始樣本點，并將這些設(shè)計樣本點保存到樣本點數(shù)據(jù)庫中，所選的樣本點個數(shù)為11D-1，其中D為決策變量個數(shù)，計算樣本點所對應(yīng)的目標(biāo)函數(shù)值并保存到目標(biāo)函數(shù)樣本數(shù)據(jù)庫。

步驟2由決策變量樣本點和目標(biāo)函數(shù)樣本數(shù)據(jù)集構(gòu)造各個優(yōu)化目標(biāo)關(guān)于決策變量的異構(gòu)集成模型。

步驟3對構(gòu)造的異構(gòu)集成模型進行誤差分析，若不滿足要求，則需要再次使用OLHD方法來增加樣本點，重新建立異構(gòu)集成模型；若滿足要求，則進入下一步。

步驟4初始化種群中各個粒子的位置和速度，并設(shè)置群體大小、慣性權(quán)重、加速度系數(shù)和迭代次數(shù)等參數(shù)值。

步驟5采用步驟1～步驟3構(gòu)造的異構(gòu)集成近似模型計算各個粒子的適應(yīng)度值，并把非支配解存儲到外部存檔中。

步驟6根據(jù)式（3）和式（4）更新各個粒子的位置和速度，重新計算各個粒子的適應(yīng)度值，進而更新它們的個體極值、全局極值以及外部存檔。

步驟7以所得粒子是否接近全局最優(yōu)解作為收斂條件，若未達到收斂，對種群進行更新，并返回步驟5；若收斂，則得出Pareto最優(yōu)解集。

在算法運行過程中，構(gòu)造Kriging模型和RBFN模型的計算復(fù)雜度都是O(n3)，n是訓(xùn)練樣本的大小，所以集成模型的計算復(fù)雜度為O(n3)。多目標(biāo)粒子群優(yōu)化算法的計算復(fù)雜度為O(N×D)，其中N為初始化種群的大小，D為決策變量個數(shù)。因此所提算法的整體計算復(fù)雜度為O(n3)+O(N×D)。

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

在機器學(xué)習(xí)策略中，集成學(xué)習(xí)通過靈活地組合多個學(xué)習(xí)器來獲得更好的泛化能力[26]，集成學(xué)習(xí)一般結(jié)構(gòu)是先產(chǎn)生一組同種類型或不同類型的個體學(xué)習(xí)器，再用某種策略將它們結(jié)合起來，其結(jié)構(gòu)如圖2所示。理論上已經(jīng)證明，當(dāng)多樣性和準(zhǔn)確性之間達到適當(dāng)?shù)钠胶鈺r，集成模型可以提供比單個模型更準(zhǔn)確的預(yù)測[27]。

圖2 集成學(xué)習(xí)示意圖Fig.2 Schematic diagram of ensemble learning

本文使用加權(quán)平均法作為集成代理模型的結(jié)合策略。加權(quán)平均法是集成學(xué)習(xí)中計算簡單、可行性較高且易于理解的模型融合方法，該方法將多個模型按照一定規(guī)則加權(quán)平均后輸出融合結(jié)果[6]，具體如下：

式中，ei是第i個代理模型的均方根誤差。由公式（9）可以看出，預(yù)測誤差較小的代理模型被分配的權(quán)重較大。在本算法中，用均方根誤差作為誤差的測量方法，每個代理模型的均方根誤差如下：

式中，m是樣本數(shù)目，e(xi)是點xi的預(yù)測誤差。

本文選用兩種不同類型的學(xué)習(xí)算法作為集成模型的個體學(xué)習(xí)器，稱為異構(gòu)集成模型，即通過兩種不同的建模方法形成兩種代理模型，然后通過加權(quán)平均法將兩種代理模型組合成為一個高精度、魯棒性強的異構(gòu)集成代理模型。異構(gòu)集成代理模型只需要一個搜索種群，因此所需的數(shù)據(jù)量較少，適用于數(shù)據(jù)量少的情況。在許多代理模型中，Kriging模型具有很好的非線性函數(shù)近似性，并且在中低維度上具有良好的性能。RBFN模型在建模過程中遍歷所有訓(xùn)練數(shù)據(jù)，因此非常適合探索局部適應(yīng)度場景并在高維問題上表現(xiàn)出色。因此，本文選擇Kriging和RBFN來構(gòu)建代理模型并通過加權(quán)平均法將兩者結(jié)合形成異構(gòu)集成代理模型，其中Kriging模型用于全局優(yōu)化，RBFN模型用于局部優(yōu)化，以獲取收斂性并能緩解高維優(yōu)化的耗時問題。異構(gòu)集成代理模型的形成方法如圖3所示。

圖3 異構(gòu)集成代理模型的形成方式Fig.3 Formation of heterogeneous ensemble surrogate model

在圖3中，集成代理模型通過一個種群中的數(shù)據(jù)產(chǎn)生了兩個不同的代理模型，分別是Kriging模型和RBFN模型，將兩個代理模型通過加權(quán)平均法相集成。加權(quán)平均法本身不需要其他背景理論知識，可以直接使用，簡單方便，但是在模型集成過程中會依賴其成員的權(quán)重，所以有一些不依賴于權(quán)重的改進方法[26]，例如投票法（Voting）、堆疊法（Stacking），雖然它們不需要權(quán)重來進行模型融合，但其計算復(fù)雜度較高，特別是Stacking方法需要進行多輪模型融合，這將會使訓(xùn)練時間加長。

異構(gòu)集成代理模型的構(gòu)造方法如下：

（1）對種群用精確適應(yīng)度函數(shù)求出其適應(yīng)度值。

（2）根據(jù)種群位置及適應(yīng)度值構(gòu)建Kriging模型與RBFN模型。

（3）求出兩個代理模型的均方誤差，根據(jù)加權(quán)平均法更新各個代理模型的權(quán)重。

（4）將Kriging模型與RBFN模型按各自的權(quán)重組合成異構(gòu)集成代理模型。

異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法的基本步驟如下：

步驟1初始化。初始化階段包括種群的初始化與兩個代理模型的初始化。種群的初始化是基于樣本數(shù)據(jù)庫，樣本數(shù)據(jù)庫中的數(shù)據(jù)是通過在待優(yōu)化區(qū)域用OLHD方法隨機采樣產(chǎn)生。對種群初始化時，隨機選取數(shù)據(jù)庫中11D-1個樣本點構(gòu)成初始化的種群。根據(jù)種群中粒子的信息，用Kriging模型及RBFN模型構(gòu)建初始化的兩個代理模型。

步驟2異構(gòu)集成代理模型的構(gòu)建。根據(jù)加權(quán)平均法求出兩個代理模型各自的權(quán)重，并根據(jù)權(quán)重將兩個代理模型組成為異構(gòu)集成代理模型。

步驟3種群的更新。根據(jù)多目標(biāo)粒子群優(yōu)化算法更新種群中各個粒子的位置與速度。

步驟4代理模型更新。在不滿足代理模型精度要求時，需要更新異構(gòu)集成代理模型，其更新方法參見以上異構(gòu)集成代理模型的構(gòu)造策略，在滿足代理模型精度要求時，利用異構(gòu)集成代理模型對新更新的候選解作評價，并選出預(yù)測結(jié)果最好的粒子對其用精確適應(yīng)度函數(shù)評價。

步驟5終止條件的判斷。若滿足終止條件，停止算法，否則，轉(zhuǎn)至步驟3。

3 實驗分析

本文將使用5個具有不同復(fù)雜程度的常用數(shù)值函數(shù)ZDT1～ZDT4和ZDT6來測試所提算法的適用性和效率[28]。測試實例ZDT1的決策變量為4個，ZDT2～ZDT4和ZDT6的決策變量為10個，而目標(biāo)函數(shù)數(shù)量為2個。使用非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm II，NSGAII）[29]和基于擁擠距離和epsilon占優(yōu)的多目標(biāo)粒子群優(yōu)化算法（Optimal Multi-Objective Particle Swarm Optimization algorithm，OMOPSO）[30]分別與異構(gòu)集成代理模型結(jié)合并進行比較，分別稱為HE-NSGAII和HE-OMOPSO；使用NSGAII和OMOPSO分別與單個代理模型Kriging結(jié)合并進行比較，分別稱為K-NSGAII[31]和K-OMOPSO[32]；將異構(gòu)集成代理模型與單個代理模型進行比較。此外還將新提出的HEOMOPSO與OMOPSO和NSGAII進行了比較，從而證明使用異構(gòu)集成代理模型在優(yōu)化昂貴問題中的重要性。計算了解決這些基準(zhǔn)函數(shù)時的覆蓋率度量，并將其與未使用代理模型的OMOPSO和NSGAII的覆蓋率度量進行比較，為了減少隨機誤差的影響，每個測試函數(shù)都進行了10次實驗。

3.1 基準(zhǔn)測試

實驗選用了ZDT系列測試函數(shù)，分別是ZDT1、ZDT2、ZDT3、ZDT4和ZDT6。由于ZDT5是一個二進制問題，對于Kriging模型來說很難估計，所以不適合所提出的方法?；鶞?zhǔn)測試問題具有多種特征，例如凸、非凸、不連續(xù)和多邊問題。ZDT1是具有簡單邊界的凸函數(shù)，ZDT2～ZDT4和ZDT6是高維測試問題，其中ZDT2是連續(xù)的非凸函數(shù)，ZDT3是由非連續(xù)的Pareto前沿組成，ZDT4是高度多模態(tài)函數(shù)，包含了219個局部極值，而ZDT6位于Pareto前沿的解密度較低，并且其Pareto最優(yōu)解分布不均勻，Pareto前沿是非凸的。這些基準(zhǔn)測試函數(shù)具有不同程度的復(fù)雜性，因此可以有效地說明所提出的HE-OMOPSO算法的適用性。

3.2 性能指標(biāo)

本文選擇世代距離指標(biāo)（Generational Distance，GD）[33]、間距指標(biāo)（Spacing，SP）[34]和超體積指標(biāo)（Hyper-Volume，HV）[35]分別評價算法的性能。

GD指標(biāo)由Pareto最優(yōu)解集中的每個點到參考集中的平均最小距離表示，GD值越小，說明算法的收斂性越好，也表明了近似Pareto前沿解集有較好的收斂性。GD指標(biāo)的計算公式如下：

其中，P是由算法獲得的近似Pareto解集，P*是從目標(biāo)空間真實Pareto前沿上采樣的一組均勻分布的參考集，是到目前為止找到的非支配解的數(shù)量，而dis(x,y)表示解集P中的點y和參考集P*中的點x之間的歐氏距離。

SP指標(biāo)可以用來測量解集分布的均勻性，該指標(biāo)通過計算解集中每個解到其他解的最小距離的標(biāo)準(zhǔn)差獲得，SP值越小，說明解集越均勻，算法的多樣性越好，也表明了近似Pareto前沿解集有較好的多樣性。SP指標(biāo)的計算公式如下：

其中，di表示第i個解到解集P中其他解的最小距離，dˉ表示所有di的均值。

HV指標(biāo)可以捕獲一組非支配解的收斂性和多樣性，因此本文將其用作評價多目標(biāo)優(yōu)化算法的綜合性能。該性能指標(biāo)用于度量一個目標(biāo)空間的體積，即算法獲得的非支配解集與參考點圍成的目標(biāo)空間中區(qū)域的體積，HV指標(biāo)值越大，說明算法的綜合性能越好，也表明了近似Pareto前沿解集有較好的收斂性和多樣性。HV指標(biāo)的計算公式如下：

其中，δ表示Lebesgue測度，用來測量體積，||S表示非支配解集的數(shù)目，vi表示參考點與解集中第i解構(gòu)成的超體積。在本文中，所有比較算法均用于指定HV的參考點得出了非支配解的最大和最小目標(biāo)值，即最小參考點和最大參考點分別為[0，0]和[11，11]，HV值均歸一化為[0，1]。

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

假設(shè)目標(biāo)函數(shù)的計算在實驗過程中是昂貴的，M、D分別代表所有測試實例中的目標(biāo)數(shù)、決策變量數(shù)（維度數(shù)），算法參數(shù)設(shè)置如表1所示，對于所有比較算法，獨立運行次數(shù)為10次，在每次運行中，初始訓(xùn)練數(shù)據(jù)都是新生成的。

表1 算法參數(shù)設(shè)置Table 1 Algorithm parameter settings

為了比較常規(guī)的NSGAII、OMOPSO、K-NSGAII、K-OMOPSO和HE-NSGAII與新提議的HE-OMOPSO，所有實驗均使用相同的初始種群。在10次實驗中，記錄了每種算法的實際仿真成本數(shù)量以及通過這些方法獲得的非支配點。然后，針對每次實驗計算GD、SP和HV三個性能指標(biāo)，實驗仿真結(jié)果如圖4～圖8所示。

圖4 測試函數(shù)ZDT1的Pareto前沿Fig.4 Pareto front of test function ZDT1

圖5 測試函數(shù)ZDT2的Pareto前沿Fig.5 Pareto front of test function ZDT2

圖6 測試函數(shù)ZDT3的Pareto前沿Fig.6 Pareto front of test function ZDT3

圖7 測試函數(shù)ZDT4的Pareto前沿Fig.7 Pareto front of test function ZDT4

測試結(jié)果表明，與OMOPSO、NSGAII、K-NSGAII、K-OMOPSO和HE-NSGAII相比，新提出的方法在ZDT1、ZDT2、ZDT3和ZDT6測試函數(shù)上表現(xiàn)較好，除ZDT4外。從圖4～圖6中可以看出，新提出的方法在真實的Pareto前沿上的分布性和均勻性比K-NSGAII、K-OMOPSO和HE-NSGAII的效果更好，在收斂性上與OMOPSO和NSGAII相比，效果較差，但是該方法使用了較少的適應(yīng)度函數(shù)評估次數(shù)獲得了更好的近似值。從圖7中可以看出，新提出的方法與HE-NSGAII相比，收斂性較差，與K-NSGAII和K-OMOPSO相比，收斂效果較好，這是由于ZDT4函數(shù)的復(fù)雜性使得單個代理模型更難于近似真實函數(shù)，這體現(xiàn)出了異構(gòu)集成代理模型的優(yōu)勢，而與OMOPSO和NSGAII相比，生成的近似值更接近真實的Pareto前沿。從圖8中可以看出，新提出的方法在收斂性和分布性上比其他算法表現(xiàn)都好，除了生成更接近真實的Pareto前沿的點外，還生成沿其更好分布的點。

圖8 測試函數(shù)ZDT6的Pareto前沿Fig.8 Pareto front of test function ZDT6

以測試函數(shù)ZDT1為例，分別從GD、SP和HV三個性能指標(biāo)說明算法的有效性。從圖9和圖10中可以看出，隨著迭代次數(shù)的增加，本文所提方法能較快地收斂，并且解集分布也較均勻，算法在收斂性和多樣性方面取得較好效果，這是因為所提方法使用異構(gòu)集成模型，加快了收斂速度，而在異構(gòu)集成模型中加入RBFN模型用于局部搜索優(yōu)化，提高了算法的多樣性。從圖11中可以看出，隨著迭代次數(shù)的增加，HE-OMOPSO的HV值雖然多次陷入局部最優(yōu)，但是能夠很快地跳出，然后繼續(xù)迭代到HV值收斂，這是因為加入了RBFN模型用于局部搜索優(yōu)化，而Kriging模型用于全局搜索優(yōu)化，兩者相結(jié)合，加快了收斂速度。從圖12中可以看出，隨著評估次數(shù)的增加，HE-OMOPSO能較快地收斂，在達到相同的收斂指標(biāo)時，OMOPSO的評估次數(shù)是本文所提算法的10倍。

圖9 GD值收斂性比較Fig.9 Comparison of GD value convergence

圖10 SP值多樣性比較Fig.10 Comparison of SP value diversity

圖11 綜合指標(biāo)HV值比較Fig.11 Comparison of comprehensive metric HV value

圖12 算法評估次數(shù)比較Fig.12 Comparison of algorithm evaluation times

由于ZDT2和ZDT6的Pareto前沿的特殊性，可以用來測試算法的收斂性能。從表2和表3中可以看出，本文所提方法在ZDT2、ZDT6中取得了最小的GD值，這說明使用異構(gòu)集成模型可以提高算法的收斂性。因為異構(gòu)集成中的Kriging模型可以使預(yù)測誤差減小，從而使算法的全局搜索能力增強。而在分布性方面，HEOMOPSO在ZDT6中的SP值接近于0，與其他算法相比，多樣性較好，這說明使用異構(gòu)集成模型可以提高算法的多樣性，異構(gòu)集成模型中的RBFN模型能使算法的局部搜索能力增強，從而提高算法的多樣性；HE-OMOPSO在ZDT4中的SP值差于其他測試函數(shù)的SP值，但是與單個Kriging代理模型算法相比，多樣性較好，說明異構(gòu)集成模型與單個代理模型相比，能夠獲得更好的局部搜索優(yōu)化，增強算法處理不確定信息的能力，從而提高算法的多樣性。

表2 不同測試方法的GD和SP平均值Table 2 Average value of GD and SP of different test methods

表3 不同測試方法的GD和SP標(biāo)準(zhǔn)偏差Table 3 Standard deviation of GD and SP for different test methods

表4和表5的實驗結(jié)果表明，與ZDT4和ZDT6相比，本文所提方法在ZDT1、ZDT2和ZDT3中的優(yōu)勢更明顯，這是因為ZDT4和ZDT6比ZDT1、ZDT2和ZDT3更復(fù)雜，并且這種復(fù)雜性使代理模型更難于適應(yīng)真實函數(shù)。因此，ZDT4和ZDT6中的代理模型精度相對較低，這導(dǎo)致HE-OMOPSO算法性能較差。在求解ZDT1函數(shù)時，HE-OMOPSO和HE-NSGAII的HV值與NSGAII和OMOPSO的HV值相接近，這是因為ZDT1是低維問題，異構(gòu)集成代理模型可利用較少的樣本點構(gòu)建更精確的代理模型，在提高收斂速度的同時能較好地逼近Pareto前 沿；與K-NSGAII和K-OMOPSO相 比，HEOMOPSO獲得的HV值較好。對于ZDT2和ZDT3高維問題，HE-OMOPSO所獲得的解在收斂性和多樣性方面均劣于NSGAII和OMOPSO所獲得的解，而HEOMOPSO所獲得的解在收斂性和多樣性方面略優(yōu)于HE-NSGAII；HE-OMOPSO的HV值與K-NSGAII和KOMOPSO相比，收斂性和多樣性較好，這是由于Kriging模型不適合高維問題，構(gòu)建的代理模型精度和準(zhǔn)確率較差，而HE-OMOPSO因為加入了RBFN模型，形成了異構(gòu)集成代理模型，用于彌補Kriging的不足，因此獲得的非支配解更接近于真實的Pareto前沿。由于ZDT4和ZDT6函數(shù)的復(fù)雜性，導(dǎo)致HE-OMOPSO算法性能較差，但是HE-OMOPSO獲得的HV值與K-NSGAII和KOMOPSO相比，綜合性能較好，說明HE-OMOPSO構(gòu)建的異構(gòu)集成代理模型在精度和效率方面優(yōu)于單個代理模型。

表4 不同測試方法的HV平均值Table 4 Average HV of different test methods

表5 不同測試方法的HV標(biāo)準(zhǔn)偏差Table 5 HV standard deviation of different test methods

需要注意的是，在每次迭代中，將在HE-OMOPSO中解決由Kriging模型和RBFN模型構(gòu)成的近似多目標(biāo)優(yōu)化問題，因此，新方法對數(shù)值函數(shù)的計算時間成本比常規(guī)OMOPSO方法和NSGA-II方法要大。但是對于計算量大的多目標(biāo)優(yōu)化問題，通常需要幾十個小時甚至更長時間來執(zhí)行目標(biāo)函數(shù)的仿真，因此可以忽略通過處理Kriging模型和RBFN模型而花費的時間。HE-OMOPSO的實際仿真成本要比所比較的算法少得多，因此，在解決昂貴的多目標(biāo)優(yōu)化問題時，HE-OMOPSO的整體計算成本要比傳統(tǒng)的OMOPSO方法和NSGA-II方法好得多。

4 結(jié)語

本文提出了使用異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法來解決耗時的多目標(biāo)優(yōu)化問題，將所提出的方法與HE-NSGAII、K-OMOPSO、K-NSGAII、OMOPSO和NSGAII進 行 了 基 準(zhǔn) 測 試 函 數(shù)ZDT1、ZDT2、ZDT3、ZDT4和ZDT6的比較，使用GD、SP和HV三個指標(biāo)來評估算法的性能。實驗結(jié)果表明，本文所提出的方法獲得的非支配解分布良好，并且解的均勻性不比傳統(tǒng)的優(yōu)化算法獲得的解差。盡管提出的方法在ZDT4上的性能較差，這是因為目標(biāo)函數(shù)難以擬合（模型精度差或目標(biāo)函數(shù)的復(fù)雜性），但可以用更少的實際適應(yīng)度函數(shù)評估生成更好的近似值。因此，與傳統(tǒng)的優(yōu)化算法相比，所提方法的計算成本更低，并且算法的搜索能力也令人滿意，對于昂貴的多目標(biāo)優(yōu)化問題非常有效。未來的工作將進行代理模型的管理優(yōu)化并用具有兩個以上目標(biāo)的問題來測試所提的方法。