結合特征擾動與分配策略的集成輔助多目標優化算法

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

（上海工程技術大學電子電氣工程學院，上海 201620）

0 概述

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

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

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

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

1 相關技術

1.1 多目標優化

多目標優化函數表示如下：

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

1.2 代理模型

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

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

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

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

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

1.3 粒子群優化算法

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

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

2.1 基于擾動與記憶的集成代理模型構建

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

2.1.1 特征擾動

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

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

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

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

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

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

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

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

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

2）根據式（12）求取Hi內存儲的RMSE 的均值。

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

2.1.3 集成代理模型構建

結合特征擾動與分配策略的集成代理模型構建如圖1 所示。

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

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

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

2）使用經過處理的數據集和初始數據集訓練RBFN 和SVR 代理模型。

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

4）輸出集成預測結果。

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

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

2.3 算法步驟

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

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

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

3）進入循環，用S和S′中的樣本點作為訓練數據，針對各目標函數構建集成代理模型。

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

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

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

2.4 算法復雜度分析

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

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

3 實驗設計與結果分析

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

表1 多目標優化測試問題設置Table 1 Setting of multi-objective optimization test problems

3.1 參數設置與性能指標

3.1.1 參數設置

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

3.1.2 性能指標

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

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

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

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

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

3.2 實驗結果對比分析

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

3.2.1 性能指標對比分析

經實驗得到各種算法GD、SP、IGD 指標平均值與標準差，如表2～表4 所示，其中最優結果加粗顯示。

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

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

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

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

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

圖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 個目標函數值，彩色效果見《計算機工程》官網HTML 版。由圖3 可以看出，EA-SMPSO 在ZDT1～ZDT3 以及ZDT6 上逼近效果最好，具有較好的收斂性以及分布性。值得注意的是，ZDT4 是一個具有復雜多模態的測試函數，使用集成模型或者Kriging模型輔助的SMPSO 近似Pareto 前沿的效果稍弱于SMPSO 本身，但對于昂貴多目標優化問題重要的是使用更少評估次數獲得更好的解。在ZDT4 測試問題上：MOEA/D 與NSGAII 都無法很好地逼近Pareto前沿，因此不適合昂貴多目標優化問題；EA-SMPSO相比于K-SMPSO 在Pareto 前沿上找到了更多的解，說明集成代理模型相對Kriging 模型在復雜多模態問題上更具優勢。

圖3 5 種算法求解具有10 個決策變量維數的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模型在昂貴多目標優化問題上的優勢，對具有5、10、20 個決策變量維度的ZDT 系列測試問題使用EA-SMPSO 與K-SMPSO 分別進行求解，記錄其所需的運行時間。如圖4所示，隨著決策變量維度的增加，KSMPSO需增加采樣點保證Kriging模型的精度，計算成本呈指數增加，因此K-SMPSO相比于EA-SMPSO的運行時間增長更快，而EA-SMPSO可使用一組數據構建更為精確的集成模型，加快了尋優速度，節約了計算成本。

圖4 EA-SMPSO 算法和K-SMPSO 算法求解具有5、10、20 個決策變量維數的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 結束語

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