劉子怡，王宇嘉，孫福祿，賈 欣，聶方鑫

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

0 概述

在科學(xué)研究及工程應(yīng)用中存在很多多目標優(yōu)化問題（Multi-objective Optimization Problem，MOP）［1-2］，且這些優(yōu)化問題呈現(xiàn)出規(guī)模越來越大、復(fù)雜性越來越高的特征。進化算法是一種模擬自然進化過程的隨機優(yōu)化算法，采用群體搜索策略，無需分析目標函數(shù)或約束，單次運行即可獲得一組非主導(dǎo)的解，適用于求解多目標優(yōu)化問題［3］。但是多數(shù)多目標進化算法通常需要上萬次適應(yīng)度評估才能得到令人滿意的解［4］，比如進氣通風(fēng)系統(tǒng)設(shè)計問題需要計算流體動力學(xué)模擬來優(yōu)化目標，一次適應(yīng)度評估就需數(shù)小時，整體評估則需耗費幾小時甚至幾天［5］，因此此類多目標優(yōu)化問題通常被稱為昂貴多目標優(yōu)化問題［6］。

近年來，針對昂貴多目標優(yōu)化問題，CHUGH 等［7］提出一種采用代理模型替代部分昂貴評估的方法，能夠有效解決計算開銷大的問題。還有一些研究人員分別將徑向基函數(shù)網(wǎng)絡(luò)（Radial Basis Function Network，RBFN）［8］、支持向量回歸（Support Vector Regression，SVR）［9］、Kriging［10］和人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）［11］用于求解非線性問題。LI 等［12］結(jié)合自我改進的新預(yù)篩選策略提出一種RBF 輔助的多種群協(xié)同進化算法。LIU 等［13］提出一種置信下界輔助的差分進化算法，該算法在優(yōu)化過程中使用Kriging 代理模型在候選后代粒子群中篩選粒子。TIAN 等［14］提出一種高斯過程（Gaussian Process，GP）輔助的進化算法，該算法采用多目標填充準則的方式選擇真實適應(yīng)度評估的個體。然而，隨著決策變量維數(shù)的增加，構(gòu)建Kriging代理模型的計算成本成指數(shù)級增加，且單一代理模型只能解決少數(shù)問題，評估精度與多樣性較差。

為提高代理模型的質(zhì)量與多樣性：GOEL 等［15］提出一種結(jié)合多個代理模型的模型集成方法，在集成過程中個體的準確性與多樣性達到適當平衡時，可提供比單個模型更高的預(yù)測準確率；TANG 等［16］提出一種基于二次多項式模型和RBFN 組成的混合全局代理模型的代理輔助進化算法；WANG 等［17］使用Kriging、PR和RBFN 不同代理模型集成了全局與局部模型，強化算法搜索性能并輔助低維優(yōu)化；HABIB 等［18］使用Kriging、RBFN 和兩種不同功能的RSM 代理模型對每個目標進行近似，并在昂貴多目標優(yōu)化問題上進行了驗證；ROSALES-PéREZ 等［19］結(jié)合模型選擇策略確定SVR 超參數(shù)，集成一組SVR 代理模型解決多目標優(yōu)化問題。值得注意的是，在模型管理中采樣不確定的個體可有效地提高模型質(zhì)量，并促進搜索空間中潛在有前途區(qū)域的探索［17］。Kriging 代理模型可為每個解提供近似的不確定信息，還能通過集合成員輸出之間的方差提供不確定信息，但以上有關(guān)集成代理模型方面的研究專注于提高集成的近似評估準確性，忽略了集成過程中的不確定信息［15］。

為利用不確定信息構(gòu)造準確性較高的代理模型，本文提出一種基于擾動與記憶的集成輔助多目標優(yōu)化（Ensemble-Assisted Multi-objective Optimization based on Disturbance and Memory，EAMO-DM）算法。該算法對訓(xùn)練集進行特征擾動產(chǎn)生新數(shù)據(jù)集并共同訓(xùn)練RBFN 和SVR 代理模型，生成多樣性強且準確性高的集成代理模型，在適應(yīng)度評估次數(shù)有限的情況下找到較好解，同時在模型管理中通過考慮不確定信息以更好地平衡種群多樣性與收斂性。

1 相關(guān)技術(shù)

1.1 多目標優(yōu)化

多目標優(yōu)化函數(shù)表示如下：

其中：x=(x1，x2，…，xD)為決策變量，D為決策變量維數(shù)；M為目標數(shù)量；Ω為可行的決策空間；RM為目標空間。由于多個目標彼此沖突，因此通常存在一組最佳折衷解決方案。在目標空間中，由最佳折衷解（稱為Pareto 最優(yōu)解）形成的圖像稱為Pareto 前沿（Pareto Front，PF），D中相應(yīng)的解構(gòu)成的集合稱為Pareto 最優(yōu)集。

1.2 代理模型

RBFN 代理模型在代理輔助進化算法中具有較強擬合能力，可用于構(gòu)建局部或全局代理模型，建模計算成本低，問題維度的增加對其擬合效果影響較小［8］。RBFN 是具有單個隱藏層的前饋神經(jīng)網(wǎng)絡(luò)，結(jié)構(gòu)由輸入層、隱含層和輸出層組成。給定i個訓(xùn)練樣本xi={xi，1，xi，2，…，xi，n}，RBFN 代理模型表示如下：

其中：τ={τ1，τ2，…，τn}為RBFN 輸出權(quán)重；||·||表示樣本x與RBFN 函數(shù)中心ci的歐氏距離；φ(·)為徑向基核函數(shù)。常用的核函數(shù)有高斯、線性、多重二次曲面和立方等核函數(shù)［20］。

SVR 代理模型是一種基于支持向量機的機器學(xué)習(xí)模型，計算成本低且泛化能力好，對小樣本問題也有較好的擬合能力［9］。給定i個訓(xùn)練樣本xi={xi，1，xi，2，…，xi，n}，SVR 問題可看作如下優(yōu)化問題：

其中：ω為超平面法向量；b為偏置項。SVR 的優(yōu)化目標為最小化訓(xùn)練樣本與不敏感損失函數(shù)ε之間的誤差，獲得最優(yōu)超平面，使預(yù)測偏差最小化［9］，具體如下：

其中：α與α*為拉格朗日乘子；C為懲罰參數(shù)，即超出ε的程度；K(hi，hj)為核函數(shù)。SVR 代理模型表示如下：

1.3 粒子群優(yōu)化算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是一種基于鳥群的群智能優(yōu)化算法［21］。在PSO中，搜索空間上的一個粒子為一個潛在解，每個粒子的速度決定其飛行方向和位置，所有粒子跟隨當前最優(yōu)粒子在解空間中搜索，每個粒子的速度和位置計算如下：

2 基于擾動與記憶的集成輔助多目標優(yōu)化算法

2.1 基于擾動與記憶的集成代理模型構(gòu)建

機器學(xué)習(xí)相關(guān)理論證明集成模型中個體的準確性與多樣性達到適當平衡時，可以提供比單個模型更精準的預(yù)測結(jié)果［22］。因此，本文對數(shù)據(jù)樣本引入特征擾動，使模型間樣本數(shù)據(jù)不同，以提升集成個體間的多樣性，在模型融合過程中加入基于記憶的影響因子分配策略，以提高集成的準確性。

2.1.1 特征擾動

采用主成分分析（Principal Component Analysis，PCA）［23］對種群引入特征擾動，生成全新的樣本集。PCA是機器學(xué)習(xí)中廣泛使用的數(shù)據(jù)處理方法，計算成本低、簡單易行，主要思想是在減少數(shù)據(jù)集維數(shù)的同時保留最主要的特征，具體步驟如下：

1）給定初始樣本集X={x1，x2，…，xi}，設(shè)新生成的樣本集Z={z1，z2，…，zi}，對i個樣本組成的矩陣X進行零均值化處理，得到樣本協(xié)方差矩陣：

2）對XXT進行特征值分解，求得對應(yīng)特征值降序排列，并取前l(fā)行構(gòu)成降維后目標矩陣G=(g1，g2，…，gl)，則新生成的樣本可表示如下：

3）在使用PCA 對種群進行處理后，得到一組新訓(xùn)練數(shù)據(jù)，兩組數(shù)據(jù)共同用于訓(xùn)練不同模型。

2.1.2 基于記憶的影響因子分配策略

集成模型中的融合策略用于平衡不同基模型的輸出，削弱不完美模型的影響，確保代理預(yù)測精度［15］。為提高集成預(yù)測的精確度，結(jié)合集成模型中各代理的預(yù)測輸出值，提出一種基于記憶的影響因子分配策略，具體定義如下：

其中：f′(x)為集成對粒子x進行近似適應(yīng)度評估的結(jié)果；Ns為集成中的基代理個數(shù)；fi′(x)為集成中第i個代理的預(yù)測結(jié)果；Ii為fi′(x)的影響因子。Ii定義如下：

基于記憶的影響因子分配策略的具體步驟如下：

1）更新Hi。當t≤ξ時，只執(zhí)行存入操作；當t>ξ時，則執(zhí)行存入與淘汰操作。

2）根據(jù)式（12）求取Hi內(nèi)存儲的RMSE 的均值。

本文在對基模型預(yù)測結(jié)果進行融合的過程中加入基于記憶的影響因子分配策略，誤差小的代理模型被分配的權(quán)重大，有效避免了代理模型在采樣數(shù)據(jù)點處表現(xiàn)良好但在未勘探區(qū)域表現(xiàn)較差而引起的誤差，保證了集成穩(wěn)定性，提高了算法準確性。

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

結(jié)合特征擾動與分配策略的集成代理模型構(gòu)建如圖1 所示。

圖1 EAMO-DM 算法中集成代理模型的構(gòu)建Fig.1 Construction of ensemble surrogate model in EAMO-DM algorithm

在集成過程中的基模型選用RBFN 代理和SVR代理，其中：RBFN 模型建模計算成本低，非線性擬合能力強，在高維搜索空間也有很好表現(xiàn)；SVR 模型在小樣本問題上占據(jù)優(yōu)勢，模型簡單并且在中低維搜索空間表現(xiàn)出良好的泛化能力。因此，在集成代理模型構(gòu)建過程中，將特征擾動及影響因子分配策略分別應(yīng)用于模型訓(xùn)練和模型融合，結(jié)合RBFN 模型與SVR 模型的優(yōu)勢，提高了集成預(yù)測的準確性，更好地逼近不同形態(tài)的Pareto 前沿并具有高維可拓展性。集成代理模型構(gòu)建步驟具體如下：

1）使用特征擾動方式對訓(xùn)練集S進行處理得到新訓(xùn)練集S′。

2）使用經(jīng)過處理的數(shù)據(jù)集和初始數(shù)據(jù)集訓(xùn)練RBFN 和SVR 代理模型。

3）結(jié)合影響因子分配策略將兩代理模型組合成集成代理模型。

4）輸出集成預(yù)測結(jié)果。

2.2 基于不確定信息的加點準則

通過增加采樣點可提高模型準確性，但這一過程因其隨機性浪費了計算資源。為提升模型精度同時節(jié)約計算成本，采用基于不確定信息的加點準則，用于選擇個體進行昂貴適應(yīng)度評估，并將其加入訓(xùn)練集更新模型。在EAMO-DM 算法中，訓(xùn)練集S中的數(shù)據(jù)用于構(gòu)建集成，并通過以下策略管理訓(xùn)練集S：采用Kriging 輔助進化算法中廣泛使用的置信下界準則［13］將最小LCB 值作為目標，選擇最優(yōu)的個體進行昂貴適應(yīng)度評估，并放入訓(xùn)練集S中更新集成代理。LCB 評價函數(shù)表示如下：

2.3 算法步驟

EAMO-DM 算法的具體步驟如下：

1）使用拉丁超立方設(shè)計方法，采樣種群規(guī)模為N的初始種群，以保證初始種群均勻分布。使用真實函數(shù)評估樣本點（即計算其對應(yīng)目標函數(shù)值），將非支配解存入外部檔案A，更新訓(xùn)練集S。

2）初始化種群中粒子的速度和位置。

3）進入循環(huán)，用S和S′中的樣本點作為訓(xùn)練數(shù)據(jù)，針對各目標函數(shù)構(gòu)建集成代理模型。

4）使用多目標粒子群優(yōu)化算法進行種群更新，利用集成代理對各粒子進行近似適應(yīng)度評估，篩選用于真實函數(shù)評估的個體，評估后放入訓(xùn)練集S更新集成代理。

5）更新各粒子的個體極值、全局極值以及外部檔案A，輸出Pareto 最優(yōu)解集。

在EAMO-DM 算法運行過程中，訓(xùn)練集S存放真實函數(shù)評估的所有個體，并作為構(gòu)建或更新集成代理的訓(xùn)練數(shù)據(jù)集。

2.4 算法復(fù)雜度分析

EAMO-DM 算法的計算復(fù)雜度T由真實適應(yīng)度評估次數(shù)F、構(gòu)建集成代理模型TE以及其他額外成本Tother的計算時間確定，具體公式如下：

其中：γ為適應(yīng)度評估系數(shù)。在構(gòu)建集成模型的過程中，通過特征擾動處理訓(xùn)練樣本的計算復(fù)雜度為O(λM)，對各代理進行影響因子分配時的計算復(fù)雜度為O(λM)，訓(xùn)練RBFN 代理與SVR 代理的計算復(fù)雜度均為O(λ2M)，λ為構(gòu)建代理模型的樣本數(shù)量，在產(chǎn)生新種群以及選取真實評估粒子過程中的計算復(fù)雜度為O(NM)，N為初始種群規(guī)模。因此，EAMODM 算法的計算復(fù)雜度為O(λ2M)+O(γF)。對于昂貴多目標優(yōu)化問題，真實適應(yīng)度評估相當耗時，構(gòu)建模型所需的時間可忽略不計。

3 實驗設(shè)計與結(jié)果分析

將ZDT 系列測試函數(shù)作為多目標優(yōu)化測試問題，如表1 所示。在EAMO-DM 算法框架中，使用SMPSO［24］作為多目標粒子群優(yōu)化算法，稱為EASMPSO；將EA-SMPSO 算法框架中的集成代理模型替換成單個Kriging 模型，稱為K-SMPSO；將EAMO-DM 算法與SMPSO［24］結(jié)合，稱為EA-SMPSO；將單個Kriging模型與SMPSO結(jié)合，稱為K-SMPSO。使用EA-SMPSO 與SMPSO、NSGAII［25］、MOEA/D［26］以及K-SMPSO 進行實驗對比。

表1 多目標優(yōu)化測試問題設(shè)置Table 1 Setting of multi-objective optimization test problems

3.1 參數(shù)設(shè)置與性能指標

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

為保證公平性，每種算法進行20 次獨立實驗，評估次數(shù)設(shè)為1 000。對于每個測試問題，目標數(shù)量M為2，種群規(guī)模為50；對ZDT1～ZDT3 測試問題，決策變量維數(shù)D為5、10、20；由于ZDT4 及ZDT6 默認決策變量維數(shù)有限，決策變量維數(shù)D為10。按照文獻［27］，將式（12）中參數(shù)ξ設(shè)為5、式（13）中參數(shù)μ設(shè)為2。值得注意的是，EA-SMPSO 與K-SMPSO 使用相同的模型管理策略。

3.1.2 性能指標

選用GD、SP、IGD 3 個指標定量評價算法性能：

其中：ψ為P中解的數(shù)目；dis為P中個體函數(shù)值與中最近個體之間的歐氏距離。GD 越小，解集收斂性越好。

2）SP 指標用于評價算法多樣性，其值由最鄰近距離的方差表示，計算公式如下：

其中：di是解集中兩相鄰個體的歐氏距離；為di的均值。SP 越小，解集分布性越好。

3）IGD 指標可用于綜合評價解集的綜合性能，即收斂性和多樣性，計算公式如下：

3.2 實驗結(jié)果對比分析

實驗從性能指標、Pareto 前沿逼近效果以及算法運行時間三方面對比EA-SMPSO 與K-SMPSO、NSGAII、SMPSO 及MOEA/D 在求解ZDT 系列測試問題上的性能表現(xiàn)。

3.2.1 性能指標對比分析

經(jīng)實驗得到各種算法GD、SP、IGD 指標平均值與標準差，如表2～表4 所示，其中最優(yōu)結(jié)果加粗顯示。

表2 5 種算法GD 性能指標的平均值和標準差Table 2 Average and standard deviation of GD performance indicators of 5 algorithms

表3 5 種算法SP 性能指標的平均值和標準差Table 3 Average and standard deviation of SP performance indicators of 5 algorithms

表4 5 種算法IGD 性能指標的平均值和標準差Table 4 Average and standard deviation of IGD performance indicators of 5 algorithms

由表2～表4 可以看出：

1）在決策變量維數(shù)為5 的ZDT1、ZDT2 測試問題上，EA-SMPSO 與單個Kriging 輔助的K-SMPSO相比，GD 值稍差（在ZDT2 測試問題上相差不到0.01）；在決策變量維數(shù)為10 的復(fù)雜ZDT3、ZDT4 測試問題及不均勻的ZDT6 測試問題上，EA-SMPSO的GD 值比K-SMPSO 更好；在決策變量維數(shù)為20 的ZDT 測試問題上，EA-SMPSO 在各指標上優(yōu)勢明顯。這是算法使用不同的代理模型所致，Kriging 代理模型能對低維非線性問題進行更精確的擬合，RBF 與SVR 代理模型更擅長處理高維小樣本問題。

2）在ZDT1～ZDT3測試問題上，隨著決策變量維數(shù)的增加，EA-SMPSO的SP值較K-SMPSO優(yōu)勢更明顯。這表明EAMO-DM 算法的多樣性更好，同時探索能力更好，并且驗證了Kriging 模型在高維問題上存在對于不確定信息估計不準確的問題［13］，導(dǎo)致算法勘探能力下降。

3）對于不同決策變量維數(shù)下的ZDT 測試問題，EA-SMPSO 相比于沒有代理輔助的SMPSO、NSGAII及MOEA/D，在ZDT1～ZDT3 測試問題上各指標均更具優(yōu)勢，但在ZDT4 測試問題上GD 值與SP 值稍遜于SMPS 與MOEA/D，這是由于ZDT4 測試問題有多個局部Pareto前沿，多模態(tài)特征使得其用集成代理難以近似。

可見，EA-SMPSO 相比于K-SMPSO、NSGAII、SMPSO 及MOEA/D 搜索所得解集的收斂性與分布性更好，綜合優(yōu)勢明顯。

為進一步分析多目標優(yōu)化算法的有效性，以ZDT1～ZDT3 測試問題為例，給出EA-SMPSO、K-SMPSO、SMPSO 的IGD 指標變化趨勢，如圖2 所示。從圖2 可以看出：SMPSO、K-SMPSO 與EA-SMPSO 的IGD 值都隨評估次數(shù)增加較為平穩(wěn)下降。雖然K-SMPSO 與EASMPSO 均能收斂到較好指標，但集成代理輔助條件下指標下降更快，因為EA-SMPSO 比單個Kriging 代理更為精確，能更快地搜索到更好的解，同時驗證了集成代理提供的不確定信息的有效性。另外，對于相同IGD指標，EA-SMPSO 與SMPSO 相比，使用集成代理的EA-SMPSO 約減少90%的評估次數(shù)，這對于昂貴多目標優(yōu)化問題具有重要意義。

圖2 EA-SMPSO、K-SMPSO 和SMPSO 算法求解ZDT1～ZDT3 測試問題時的IGD 指標變化趨勢Fig.2 Variation trend of IGD when EA-SMPSO，K-SMPSO and SMPSO algorithms solve ZDT1～ZDT3 test questions

3.2.2 近似Pareto 前沿對比分析

圖3 給出了各算法在求解ZDT 系列測試問題時獲得的近似Pareto 前沿，其中f1、f2代表ZDT 系列測試問題中的2 個目標函數(shù)值，彩色效果見《計算機工程》官網(wǎng)HTML 版。由圖3 可以看出，EA-SMPSO 在ZDT1～ZDT3 以及ZDT6 上逼近效果最好，具有較好的收斂性以及分布性。值得注意的是，ZDT4 是一個具有復(fù)雜多模態(tài)的測試函數(shù)，使用集成模型或者Kriging模型輔助的SMPSO 近似Pareto 前沿的效果稍弱于SMPSO 本身，但對于昂貴多目標優(yōu)化問題重要的是使用更少評估次數(shù)獲得更好的解。在ZDT4 測試問題上：MOEA/D 與NSGAII 都無法很好地逼近Pareto前沿，因此不適合昂貴多目標優(yōu)化問題；EA-SMPSO相比于K-SMPSO 在Pareto 前沿上找到了更多的解，說明集成代理模型相對Kriging 模型在復(fù)雜多模態(tài)問題上更具優(yōu)勢。

圖3 5 種算法求解具有10 個決策變量維數(shù)的ZDT1～ZDT4 和ZDT6 測試問題時獲得的近似Pareto 前沿Fig.3 Pareto front of 5 algorithms solve the ZDT1～ZDT4 and ZDT6 test questions with 10 decision variable dimensions

3.2.3 算法運行時間對比分析

為進一步分析本文提出的集成代理模型較單個Kriging模型在昂貴多目標優(yōu)化問題上的優(yōu)勢，對具有5、10、20 個決策變量維度的ZDT 系列測試問題使用EA-SMPSO 與K-SMPSO 分別進行求解，記錄其所需的運行時間。如圖4所示，隨著決策變量維度的增加，KSMPSO需增加采樣點保證Kriging模型的精度，計算成本呈指數(shù)增加，因此K-SMPSO相比于EA-SMPSO的運行時間增長更快，而EA-SMPSO可使用一組數(shù)據(jù)構(gòu)建更為精確的集成模型，加快了尋優(yōu)速度，節(jié)約了計算成本。

圖4 EA-SMPSO 算法和K-SMPSO 算法求解具有5、10、20 個決策變量維數(shù)的ZDT1～ZDT3 測試問題的運行時間Fig.4 Running time of EA-SMPSO algorithm and K-SMPSO algorithm to solve the ZDT1～ZDT3 test questions with 5，10，and 20 decision variable dimensions

4 結(jié)束語

本文提出一種基于擾動與記憶的集成輔助多目標優(yōu)化算法，使用RBFN 和SVR 代理模型，并結(jié)合特征擾動與影響因子分配策略構(gòu)建集成代理模型，同時考慮了不確定信息以選擇進行適應(yīng)度評估的個體。實驗結(jié)果表明，該算法在處理具有凹、凸、非連續(xù)、非均勻特性的多目標問題時，得到解集的分布性與收斂性相比經(jīng)典算法更好，并且當決策變量維數(shù)增加時，使用集成代理模型可獲得比Kriging 代理模型更準確的預(yù)測結(jié)果，同時計算成本較低。下一步將設(shè)計更高效的模型管理策略，并通過充分利用并行仿真資源，將本文算法應(yīng)用于求解更多的昂貴多目標優(yōu)化問題。