組合加點準則的代理輔助多目標粒子群優(yōu)化

陳萬芬，王宇嘉，林煒星

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

多目標進化算法已被應(yīng)用于許多現(xiàn)實世界中的復(fù)雜優(yōu)化問題，但是當將其應(yīng)用于求解耗時的多目標優(yōu)化問題時，優(yōu)化過程通常需要進行大量的適應(yīng)度函數(shù)評估才能找到Pareto最優(yōu)解。為了解決計算量大的多目標優(yōu)化問題，代理輔助進化算法(Surrogate Assisted Evolutionary Algorithms， SAEAs)被廣泛采用[1]，以便采用計算廉價的代理模型來代替昂貴的實際適應(yīng)度函數(shù)評估。

代理模型通常指代替更復(fù)雜耗時的數(shù)值分析的近似數(shù)學模型，任何具有預(yù)測能力的模型都可以被用作代理模型[2-7]。提高模型的準確度以及模型管理是SAEAs領(lǐng)域中目前急需解決的問題。模型管理又稱為加點準則，通過代理模型產(chǎn)生新的樣本點，達到提高代理模型精度的目的[8]。建立有效的代理模型，并使用加點準則的模型管理策略加速收斂和改善優(yōu)化中的多樣性，對提高代理模型的預(yù)測能力具有重要意義[9]。

模型管理是SAEAs中更新代理模型的重要步驟，國內(nèi)外研究人員陸續(xù)提出多種加點準則，例如改善期望準則(Expected Improvement， EI)[10]、改善概率準則(Probability of Improvement， PI)[11]、最小化代理模型預(yù)測準則(Minimize Surrogate Prediction， MSP)[12]、置信下界準則(Lower Confidence Bound， LCB)[13]等。文獻[14]使用EI準則來選擇精度較高的候選解以更新代理模型，使算法在評估昂貴或數(shù)量有限的多目標優(yōu)化問題上表現(xiàn)出較好的性能。文獻[15]建立代理模型后，為每個子問題計算EI值，并求解EI的最大值，以減少問題的計算復(fù)雜性和適應(yīng)度函數(shù)評估的數(shù)量。文獻[16]使用高斯過程代理模型的LCB準則來選擇適應(yīng)度較好的后代，用以解決進化多目標優(yōu)化問題。文獻[17]提出代理輔助的模擬退火算法，該算法通過使用均方根誤差計算得出代理模型的準確性來評估種群中的個體，提高了代理模型的精度并減少了計算成本。這些基于單一加點準則的代理模型輔助多目標優(yōu)化算法的效率雖有所提高，但在每次迭代中均只添加了1個新增樣本點來更新代理模型，導(dǎo)致整個Pareto 前沿無法在一次迭代中得到充分的探索。

基于以上問題，文獻[18]使用EI準則和PI準則選擇要重新評估的個體進行多目標優(yōu)化，獲得了當前近似Pareto解集，結(jié)果表明該方法優(yōu)于NSGAII算法。文獻[19]提出一種多目標加點準則，該準則將加點采樣視為一個雙目標問題，同時使預(yù)測的適應(yīng)度和其方差最小。該方法選擇第一個和最后一個非支配前沿的解作為新的加點樣本，使得所提出的多目標加點準則對于高維優(yōu)化問題有較好的優(yōu)化效果。上述算法能夠在一次迭代中同時添加多個樣本點，提高優(yōu)化效率，但是其較少關(guān)注集成模型提供的不確定信息。已有研究表明，集成模型成員輸出的方差不確定性信息對于模型管理是有效的[20-21]，因此代理模型中的不確定信息應(yīng)得到更多的關(guān)注。

為了建立精度和效率都較高的代理模型，提高適應(yīng)度近似的準確性，增強代理模型的預(yù)測性能，本文提出了組合加點準則的代理輔助多目標粒子群優(yōu)化算法。該算法將Kriging模型與徑向基函數(shù)網(wǎng)絡(luò)模型加權(quán)集成為預(yù)測穩(wěn)定性較強的異構(gòu)集成模型，利用集成代理提供的不確定性信息提高模型預(yù)測能力，并使用組合加點準則進行模型管理，實現(xiàn)了勘探與開發(fā)之間的平衡。

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

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

通常情況下，多目標優(yōu)化問題(Multi-Objective Optimization Problems，MOPs)包含多個相互沖突的目標。以最小化目標為例， MOPs可以被描述為

(1)

式中，m是目標函數(shù)的數(shù)目；x是決策變量；fi(x)是第i個目標函數(shù)。若決策變量x1完全支配另一個決策向量x2，則表示為x1x2，所需滿足的條件如式(2)所示。

(2)

在MOPs中，當一個解不受任何其他解支配時，則可以稱其為Pareto最優(yōu)解。在搜索空間中，將所有Pareto最優(yōu)解的集合形成的權(quán)衡曲面稱為Pareto前沿。

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

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法是一種模擬鳥類群體智能行為的隨機搜索算法[22]。該算法中，將每只鳥都視為一個粒子，粒子與粒子之間通過相互協(xié)作和信息共享完成尋優(yōu)過程，進而找到符合優(yōu)化問題的最優(yōu)解。PSO算法的位置和速度更新式為

vi(k+1)=w×vi(k)+c1r1(pbesti-xi(k))+

c2r2(gbest-xi(k))

(3)

xi(k+1)=vi(k+1)+xi(k)

(4)

式中，i=1，2，…，N是粒子的個數(shù)；N表示種群的大??；vi(k)表示粒子i在第k維的速度；xi(k)表示粒子i在第k維中的位置；w是慣性權(quán)重；常數(shù)c1和c2是加速系數(shù)，其中c1表示向自身學習的能力，c2表示粒子向整個種群學習的能力；r1和r2是均勻分布在[0，1]中的隨機值；pbesti表示粒子i所經(jīng)歷的最優(yōu)位置，其所在的和項表示向自身學習的機制；gbest表示種群中最好粒子的位置，其所在的和項表示粒子向整個種群學習的機制。

1.3 代理模型

代理模型是真實函數(shù)的近似值，可用來構(gòu)建更為簡單且計算成本更低的模型，主要包括Kriging模型、徑向基函數(shù)網(wǎng)絡(luò)(Radial Basis Function Network，RBFN)模型、多項式回歸模型、支持向量回歸模型等。下面主要介紹本文使用的Kriging模型和RBFN模型。

1.3.1 Kriging模型

Kriging也被稱為高斯過程(Gaussian Process)[23]。與其他代理模型相比，Kriging模型不僅能給出估計值，還可以生成估計值的均方誤差，用于指導(dǎo)添加新的采樣點，以更新代理模型并提高模型的準確性。Kriging模型本質(zhì)上是一種插值模型，將目標函數(shù)視為高斯隨機過程的具體實現(xiàn)，表示為

Y(x)=f(x)+Z(x)

(5)

式中，f(x)為全局趨勢，代表近似函數(shù)Y(x)的數(shù)學期望；Z(x)為局部偏差，數(shù)學期望為0。

1.3.2 RBFN模型

徑向基函數(shù)(Radial Basis Function，RBF)方法[24]是一個實值函數(shù)，其值取決于從輸入x到神經(jīng)元中心c的距離。RBF的典型選擇包括：線性函數(shù)、三次函數(shù)、多二次函數(shù)或高斯函數(shù)。

RBFN通常具有3層，即包含識別函數(shù)的輸入層、具有非線性RBF激活函數(shù)的隱藏層以及線性輸出層。網(wǎng)絡(luò)的輸出為

(6)

式中，φ(x)表示RBFN的輸出結(jié)果；N是樣本點大小；φ(‖x-ci‖)表示徑向基函數(shù)，為了使RBFN模型適應(yīng)特定任務(wù)，需要微調(diào)3個參數(shù)：權(quán)重wi、中心向量ci和RBF寬度參數(shù)βi。

2 組合加點準則的代理輔助多目標粒子群優(yōu)化

2.1 算法框架

目前，大量的代理模型方法被用于解決許多不同適應(yīng)度形態(tài)特性的優(yōu)化問題，其中RBFN模型在訓練數(shù)據(jù)小的情況下，對于各類非線性度不同的問題表現(xiàn)最好。隨著搜索維度以及規(guī)模的增加，RBFN模型也能有較好的表現(xiàn)。Kriging模型作為一類統(tǒng)計學習模型，適合于捕捉復(fù)雜優(yōu)化問題的全局場景，并能獲得與RBFN模型相媲美的結(jié)果。為了能夠快速有效地解決不同形態(tài)的優(yōu)化問題，本文提出了組合加點準則的代理輔助多目標粒子群優(yōu)化算法。該算法將Kriging模型與RBFN模型加權(quán)集成為預(yù)測穩(wěn)定性較強的異構(gòu)集成模型，利用EI準則和MSP準則結(jié)合的組合加點準則在每一次迭代中同時添加多個樣本點更新代理模型，其算法流程圖如圖1所示。

圖1 組合加點準則的代理輔助多目標粒子群優(yōu)化算法流程圖

首先對目標函數(shù)進行采樣，使用采樣的樣本點訓練由Kriging模型和RBFN模型組成的異構(gòu)集成模型；然后，使用實際目標函數(shù)評估組合加點準則產(chǎn)生的多個新樣本點。將包括新數(shù)據(jù)樣本點的擴展訓練集用于代理模型的訓練，以此更新代理模型；最后，使用多目標粒子群優(yōu)化算法對異構(gòu)集成模型進行優(yōu)化，得出Pareto最優(yōu)解集。

組合加點準則的代理輔助多目標粒子群優(yōu)化算法的具體步驟如下：

步驟1初始化種群?；跇颖军c數(shù)據(jù)庫進行種群的初始化，通過最優(yōu)拉丁超立方采樣(Optimal Latin Hypercube Sampling，OLHS)[25]方法從決策變量空間內(nèi)抽取樣本點X，并將這些樣本點用于評估目標函數(shù)值Y，得出樣本點對應(yīng)的優(yōu)化目標樣本數(shù)據(jù)集，并使用[X，Y]作為訓練數(shù)據(jù)；

步驟2初始化代理模型。根據(jù)種群中粒子的信息，使用樣本點數(shù)據(jù)集初始化兩個代理模型，并訓練Kriging模型和RBFN模型；

步驟3構(gòu)建異構(gòu)集成模型。根據(jù)加權(quán)平均法求出兩個代理模型的權(quán)重，其中權(quán)重由代理模型的均方根誤差得出。通過模型預(yù)測誤差來調(diào)整權(quán)重大小，預(yù)測誤差較小的模型，其權(quán)重較大[26]；

步驟4代理模型的更新。對構(gòu)造的異構(gòu)集成模型進行誤差分析，在不滿足代理模型精度要求時，使用EI準則和MSP準則結(jié)合的加點準則來增加樣本點，重新建立異構(gòu)集成模型；在滿足代理模型精度要求時，利用異構(gòu)集成模型對更新的候選解進行評估，選出預(yù)測結(jié)果最好的粒子進行精確適應(yīng)度函數(shù)評估；

步驟5利用更新后的異構(gòu)集成近似模型計算各個粒子的適應(yīng)度值，并將非支配解存儲到外部存檔中；

步驟6種群的更新。根據(jù)多目標粒子群優(yōu)化算法更新種群中各個粒子的位置和速度，重新計算各個粒子的適應(yīng)度值，更新個體極值、全局極值以及外部存檔；

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

2.2 模型管理

2.2.1 EI準則

(7)

(8)

式中，σ2是方差；p是單位向量；R是樣本點x的相關(guān)函數(shù)。通過求解maxEI(x)的子優(yōu)化問題，可得出新的樣本點x*。

2.2.2 MSP準則

在代理輔助優(yōu)化算法中，最小化代理模型預(yù)測準則是最簡單、最直接，也是最早被采用的方法，其原理是直接在代理模型上尋找目標函數(shù)的最小值，然后加入樣本數(shù)據(jù)集來更新代理模型。子優(yōu)化問題的數(shù)學模型為

(9)

2.2.3 組合加點準則

EI準則理論上是一種全局優(yōu)化算法，但優(yōu)化后期收斂速度較慢。MSP準則通常用于局部優(yōu)化，但在優(yōu)化空間十分復(fù)雜或者選取初始樣本點較少時，其容易陷入局部最優(yōu)而無法找到全局最優(yōu)解。本文將EI準則和MSP準則結(jié)合成組合加點準則，該方法既能克服單一加點準則的缺陷，還可以加快收斂速度，能夠在一次迭代中同時獲得多個樣本點，用于更新代理模型，提高模型的準確性和優(yōu)化效率。組合加點準則的模型管理過程如圖2所示。

圖2 組合加點準則的模型管理過程

圖2中，本文使用的異構(gòu)集成模型由具有不同輸入函數(shù)的Kriging模型和RBFN模型組成。集成成員輸出的預(yù)測方差可估計適應(yīng)度函數(shù)預(yù)測中的不確定性程度，用于模型管理。在優(yōu)化中，集成模型代替了真實的目標函數(shù)，以評估由多目標進化算法找到的候選解，而組合加點準則用于計算這些解的最優(yōu)值。

3 實驗分析

本文使用具有不同復(fù)雜度的數(shù)值函數(shù)DTLZ[28](除DTLZ5和DTLZ6外)來測試所提出的方法，算法比較結(jié)果如表1所示。

表1 多種算法比較

為了減少隨機誤差的影響，每個測試函數(shù)都進行了10次實驗。本文所使用的多目標粒子群優(yōu)化算法的參數(shù)設(shè)置為：種群大小為100，領(lǐng)導(dǎo)者大小為100，變異概率為0.1，變異擾動為0.5，迭代次數(shù)為100。

3.1 測試函數(shù)

本文選擇的數(shù)值測試函數(shù)是DTLZ1、DTLZ2、DTLZ3、DTLZ4和 DTLZ7，這些函數(shù)具有不同程度的復(fù)雜性，可有效說明所提方法的適用性。測試函數(shù)的性能如表2所示。

表2 測試函數(shù)特性

3.2 性能指標

本文使用3個評價指標來評估算法的性能，分別是世代距離(Generational Distance，GD)[31]、間距(Spacing，SP)[32]和超體積(Hyper-Volume，HV)[33]。GD指標和SP指標分別用來評價算法的收斂性和多樣性。HV指標提供了一組非支配解的收斂性和多樣性的組合信息，并且HV值越高，非支配解的質(zhì)量越好。在本文中，沿著Pareto前沿采樣了1 000個均勻分布的參考點組成參考集以計算GD指標、SP指標和HV指標。

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

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

表3 算法參數(shù)設(shè)置

為了將本文所提算法與NSGAIII、OMOPSO、HE-OMOPSO和HE-OMOPSO-EI進行比較，所有實驗均使用相同的初始種群。在10次實驗中，記錄每種算法的實際仿真成本數(shù)量以及通過這些方法獲得的非支配點。針對每次實驗計算GD指標、SP指標和HV指標，其均值和標準偏差如表4～表7所示，實驗結(jié)果如圖3所示。

表7 HV的標準偏差

實驗結(jié)果表明，與NSGAIII、OMOPSO、HE-OMOPSO和HE-OMOPSO-EI相比，本文所提方法在測試函數(shù)DTLZ1、DTLZ2、DTLZ3和DTLZ7上表現(xiàn)較好。從圖3(a)～圖3(c)中可以看出，本文所提方法在真實Pareto前沿上的分布性和均勻性與NSGAIII、OMOPSO、HE-OMOPSO和HE-OMOPSO-EI等算法效果相似，但是所提方法與傳統(tǒng)方法相比使用了更少的適應(yīng)度函數(shù)評估次數(shù)，也獲得了更好的近似值；與HE-OMOPSO和HE-OMOPSO-EI相比，所提方法的模型準確率更高。從圖3(d)中可以看出，所提方法在真實Pareto前沿上的分布性和均勻性與HE-OMOPSO和HE-OMOPSO-EI相比效果相似，而與NSGAIII和OMOPSO相比收斂性較差，這是由于測試函數(shù)DTLZ4的復(fù)雜性使得代理模型難于近似真實函數(shù)，導(dǎo)致算法性能變差。從圖3(e)中可以看出，所提方法在分布性和多樣性上比HE-OMOPSO和HE-OMOPSO-EI好，除了可生成更接近真實的Pareto前沿的點外，還生成了沿其分布更好的點。

(a)

本文以測試函數(shù)DTLZ2為例，分別從GD、SP和HV共3個性能指標來說明算法的有效性。從圖4(a)和圖4(b)中可以看出，隨著迭代次數(shù)的增加，本文所提方法能較快地收斂，并且解集分布也較均勻，算法在收斂性和多樣性方面取得了較好的效果，這是因為所提方法使用組合加點準則用于模型管理，而在代理模型中又引入MSP準則用于局部搜索優(yōu)化，提高了算法的多樣性。從圖4(c)中可以看出，隨著迭代次數(shù)的增加，HE-OMOPSO-CIP的HV值雖然多次陷入局部最優(yōu)，但是能夠很快跳出，然后繼續(xù)迭代到HV值收斂。這是因為EI準則被用于全局搜索優(yōu)化，而MSP準則被用于局部搜索優(yōu)化，兩者相結(jié)合，加快了收斂速度。從圖4(d)中可以看出，隨著評估次數(shù)的增加，HE-OMOPSO-CIP能較快地收斂，在達到相同的收斂指標時，OMOPSO的評估次數(shù)是本文所提算法的10倍。

(a)

由于測試函數(shù)DTLZ4和DTLZ7的Pareto前沿具有多個局部最優(yōu)解，因此適用于測試算法的收斂性能。從表4和表5中可以看出，在測試函數(shù)DTLZ4和DTLZ7中，本文所提方法與HE-OMOPSO和HE-OMOPSO-EI相比取得了較小的GD值，證明EI準則和MSP準則都能夠提高非支配解的質(zhì)量，將兩者結(jié)合起來可以進一步提高算法的收斂性，從而提高算法性能；而異構(gòu)集成模型中的Kriging模型可以使預(yù)測誤差減小，增強全局搜索能力，進而提高算法的收斂性。HE-OMOPSO-CIP在測試函數(shù)DTLZ3中取得了較小的GD值和SP值，說明該算法能夠獲得收斂良好且分布均勻的最優(yōu)解。使用組合加點準則可以避免算法陷入局部最優(yōu)，而異構(gòu)集成模型中的RBFN模型可以增強局部搜索能力，提高算法的多樣性。在DTLZ2函數(shù)中，所提方法取得了較小的SP值，說明算法獲得的非支配解在真實的Pareto前沿上分布較均勻，算法的多樣性較好。

表4 GD和SP的平均值

表5 GD和SP的標準偏差

從表6和表7中可以看出，本文方法在全部測試函數(shù)中的HV值與其他算法相當或更好，說明HE-OMOPSO-CIP獲得的HV值與所比較的算法相比，算法的收斂性和多樣性都較好，也表明近似Pareto前沿解集有較好的收斂性和多樣性。在測試函數(shù)DTLZ2上，所提方法的HV值比單一加點準則和無加點準則的HV值更好，說明所提方法能夠在勘探與開發(fā)之間實現(xiàn)更好的平衡。所提方法在測試函數(shù)DTLZ4中獲得的標準偏差幾乎為0，其均方誤差也接近于0，說明所提方法在DTLZ4中優(yōu)于其他算法。上述結(jié)果證明組合加點準則可以根據(jù)適應(yīng)度估計值和方差來評估解的質(zhì)量，提高代理模型的準確性和預(yù)測能力，從而獲得近似Pareto最優(yōu)解集。

表6 HV的平均值

4 結(jié)束語

本文提出組合加點準則的代理輔助多目標粒子群優(yōu)化算法來解決耗時的多目標優(yōu)化問題，并將所提方法與其他基于代理模型的方法進行了基準測試函數(shù)的比較。實驗結(jié)果表明，對于高維問題，組合加點準則的代理模型充分利用了異構(gòu)集成模型的預(yù)測能力，較好地平衡了算法的多樣性和收斂性，能夠有效優(yōu)化計算量大的多目標優(yōu)化問題。