基于聚類的代理模型構建策略

陳 彧，楊媛媛

(武漢理工大學 理學院，湖北 武漢 430070)

0 引 言

代理模型輔助的進化算法(surrogate-assisted evolutionary algorithm，SAEA)在昂貴單目標和多目標優化問題中得到了廣泛的應用[1,2]，代理模型的選擇、構建和管理是SAEA的設計和應用中的關鍵技術問題[3]。為克服單一代理模型的缺陷和不足，Sun等[4]采用多代理模型提高代理模型的評價精度。為減少多代理模型導致的計算量的增加，Shu等[5]采用多精度模型來實現迭代過程的探索和開發需求，Yu等[6]則通過動態模型選擇策略構建低復雜度的面向搜索需求的代理模型。在訓練數據集的擴展方法方面，Tian等[7]采用多目標加點準則進行訓練數據選擇，可以在互相矛盾的需求中取得較好的折衷。Wang等[8]根據進化算法的全局探索和局部開發需求分別構建代理模型，但未對訓練數據進行篩選，從而導致了模型訓練過程時間復雜度的無限增長。

針對SAEA研究中的技術難題，本文提出了一種基于聚類的代理模型構建策略(clustering-based construction strategy of surrogate models，CCS-SM)。該策略采用了多代理集成模型的動態選擇技術，利用聚類方法選擇多精度模型的訓練數據，并設計了面向搜索需求的加點準則。數值實驗結果表明，基于CCS-SM策略的代理模型輔助粒子群優化算法(particle swarm optimization assisted by surrogates based on clustering，PSO-ASC)時間復雜度低，收斂速度快；另外，以基于CCS-SM的粒子群優化(particle swarm optimization，PSO)搜索作為一種加速策略，可以大大提高混合變量多目標進化算法(mixed-variable multiobjective evolutionary algorithm，MV-MOEA)的收斂性能。

1 基于聚類的代理模型構建策略(CCS-SM)

為實現基于代理模型的全局搜索和局部開發，需要構建全局代理模型和局部代理模型。本文提出了一種基于聚類的代理模型構建策略(CCS-SM)。

首先，通過聚類算法實現對搜索空間的自適應劃分。本文采用K-means聚類算法來將已經得到的所有數據點分為N個數據類C1,C2,…,CN。

其次，基于聚類結果來構建全局代理模型。考慮到數據集中數據點的分布存在不確定性且代理模型本身存在近似誤差，為得到能夠刻畫優化問題全局走勢的全局代理模型，分別從C1,C2,…,CN中隨機選擇一個數據點來構成訓練全局模型的訓練數據集，試圖通過數據點位置的隨機性來削弱代理模型近似誤差對全局搜索的不利影響。

同時，基于聚類結果構建局部代理模型。考慮到全局最優解以較大的概率存在于當前所搜索到的數據點中適應值較好的數據類附近，以Ci(i=1,…,N)中各數據點的最佳適應值作為類Ci的適應值，通過輪盤賭方式選擇Ci0類數據所在的區域作為局部搜索區域。若Ci0類中的數據點個數M大于等于N，則選擇適應值最好的N個數據點訓練代理模型；否則，再從其它N-1個類中選擇適應值最好的N-M個點，并在此基礎上構建局部代理模型。

CCS-SM策略基于已有數據的聚類結果來構建全局和局部代理模型，對構建模型的數據集合規模進行了控制，降低了代理模型的訓練和評價過程的時間復雜度；通過采樣不同類的數據來構建的全局模型可以較好刻畫待優化問題的全局適應值地形，而基于同一類的數據來構建的局部代理模型則具有較好的局部近似精度，能夠實現低復雜度的高精度局部開發。因此，CCS-SM在對時間復雜度進行精確控制的前提下提高了全局代理模型和局部代理模型的構建效率，有望大大提高SAEA的收斂效率。

2 基于聚類的代理模型輔助粒子群優化算法(PSO-ASC)

基于CCS-SM策略的代理模型構建和管理模式，本文提出了一種基于聚類的代理模型輔助粒子群優化算法(PSO-ASC)。

2.1 PSO-ASC的集成代理模型

由于每一種代理模型具有各自的優缺點，PSO-ASC中采用3個典型的異構模型進行集成[8]：

2.2 PSO-ASC的搜索策略

對于最小化問題minf(x)，PSO-ASC通過在3種不同的搜索模式之間進行切換來實現基于代理模型的啟發式搜索。

2.2.1 搜索模式一

(1)

作為最大化的目標函數，利用PSO尋找集成代理模型評價的不確定性較大的點。對PSO搜索得到的最優結果進行精確評價，并將其加入數據集中。

2.2.2 搜索模式二

利用代理模型加速收斂，構建能夠較好刻畫優化函數的全局適應值地形的全局代理模型。通過CCS-SM的全局策略選擇構建全局代理模型的N個數據點，并從3個代理模型中隨機選擇一種作為全局代理模型

(2)

式中：j為1-3的隨機整數。基于所建立的全局代理模型(2)，利用PSO尋找全局代理模型評價目標函數值較小的點。對PSO算法得到的結果進行精確評價，將其加入數據集中。

2.2.3 搜索模式三

利用局部代理模型進行局部開發，建立盡可能精確的局部代理模型。通過CCS-SM策略的局部策略選擇構建局部代理模型的N個數據點，以模型(2)作為最小化的目標函數，利用PSO進行基于代理模型的局部搜索。對PSO搜索到的最終結果進行精確評價，并將其加入數據集中。

2.3 PSO-ASC算法的迭代過程

基于上述3種搜索模式，本文提出了一種基于聚類的代理模型輔助粒子群優化算法(PSO-ASC)。基于圖1所示的算法框架，PSO-ASC的具體迭代過程如下：

圖1 PSO-ASC算法框架

(1)采用拉丁超立方抽樣(Latin hypercube sampling，LHS)生成種群規模P=P0的初始種群，并對其進行精確評價；將其加入檔案數據集Dt，其中P表示數據集的規模。

(2)根據模式一從Dt中選擇N個數據點訓練全局代理模型；采用LHS重新產生N個數據點生成初始種群，以式(1)的函數最大化作為優化目標，采用PSO算法進行迭代優化；對PSO優化的結果進行精確的個體評價，并將其加入Dt中，得到新的數據集Dt+1；

(3)根據模式二的策略從Dt+1中選擇N個數據點訓練全局代理模型；采用LHS重新產生N個數據點生成初始種群，以式(2)中的函數最小化作為優化目標，采用PSO算法進行迭代優化；對PSO搜索得到的結果進行精確的個體評價，并將其加入Dt+1，得到新的數據集Dt+2；

(4)令t=t+2；如果t≥tmax，算法結束；否則，如果Dt中的最佳適應值得到改進，則轉到(2)；如果Dt中的最佳適應值未得到改進，則轉到(5)；

(5)根據模式三的策略從Dt中選擇N個數據點訓練全局代理模型。采用LHS重新產生N個數據點作為初始種群，以式(2)中的函數最小化作為優化目標，采用PSO算法進行迭代優化；對PSO搜索得到的結果進行精確的個體評價，并將其加入Dt中得到新的數據集Dt+1；

(6)令t=t+1；如果t≥tmax，算法結束；如果Dt的種群適應值得到改進，則轉到(5)，否則轉到(2)。

2.4 數值實驗

2.4.1 參數設置

為驗證本文所提出的PSO-ASC算法的有效性，我們通過表1所示的5個標準測試函數將其與CAL-SAPSO的實驗結果進行了比較。兩個算法都采用了同樣的參數設置：對于問題規模為d的測試問題，初始數據集規模設為N=5d，個體精確評價次數上限為11d；在基于代理模型的PSO搜索中，種群規模為50，迭代次數為100。為了對比兩個算法在不同規模的測試問題的求解效率，對于每個測試問題都對比了d=10，20，30這3種情況。

表1 測試問題

2.4.2 結果分析

為驗證算法PSO-ASC的有效性，本文通過數值實驗將其與4種有代表性的經典SAEAs進行了比較。其中，GPEME[9]和MAES-ExI[10]均以Kriging模型作為代理模型，分別采用置信下界(lower confidence bound，LCB)和期望改進量(expected improvement，ExI)作為精確評價及加點準則；WTA1[11]和GS-SOMA[12]均采用了多項式回歸(polynomial regression，PR)、徑向基函數(radial basis function，RBF)網絡和Kriging模型構成的集成模型，而GS-SOMA還額外采用了一個PR模型來對數據進行光滑處理。對每一個測試問題獨立運行PSO-ASC 20次，5種算法所得到的目標函數平均值與標準差見表2，其中黑體表示所有算法比較的最佳結果。除了Rosenbrock函數外，PSO-ASC的平均結果大多優于其它算法，但運行結果的標準差卻往往略差，特別是對于Rosenbrock函數的優化結果平均值與標準差均高于GS-SOMA。考慮到Rosenbrock函數的適應值地形具有狹長的平緩波谷，對優化算法的種群多樣性的要求更高，而GS-SOMA能夠更好的在收斂過程中保持種群多樣性，故在Rosenbrock函數的優化問題上表現更好。

表2 PSO-ASC與GPEME、MAES-ExI、WTA1和GS-SOMA的運行結果(平均值±標準差)比較

需要注意的是，由于PSO-ASC的設計初衷是對精確評價尤其困難的數據驅動優化問題進行高效優化，故采用了與以上算法不同的基于代理模型評價結果的連續多次迭代模式。為了更進一步發掘PSO-ASC中的CCS-SM策略的優勢和不足，我們將其與CAL-SAPSO算法[8]進行了比較。CAL-SAPSO采用了與PSO-ASC類似的迭代模式，但其采用集成模型對個體進行近似評價，且將所有已有的數據點作為訓練數據來構建代理模型。

對每個測試問題獨立運行20次，分別計算20次迭代過程中每一代的目標函數平均值，可以得到算法的收斂曲線。將PSO-ASC和CALS-SAPSO分別求解d=10，20，30的5種測試問題，可以得到圖2所示的Ackley函數的收斂曲線、圖3所示的Ellipsoid函數收斂曲線、圖4所示的Griewank函數收斂曲線、圖5所示的Rastrigin函數收斂曲線及圖6所示的Rosenbrock函數收斂曲線。由于兩種算法采用了相同的初始化模式，在1～5d次個體評價的收斂曲線大致相同。從第5d+1次精確評價開始，CAL-SAPSO算法的收斂曲線瞬間發生了大幅下降，在迭代中期的快速收斂以后，迭代后期迭代曲線趨于平穩，收斂過程出現停滯；相對而言，PSO-ASC算法的下降過程則是連續的，在迭代中期下降速度比CAL-SAPSO算法慢，但卻能夠在迭代后期保持適應值的持續下降，最終得到比CAL-SAPSO算法更好的收斂結果。由于CAL-SAPSO算法采用所有的數據點來構建代理模型，可以在迭代中期引導算法的快速收斂；然而，倘若迭代前期所得到的數據點的分布具有局限性，則可能導致CAL-SAPSO在中期所得到的數據點大多集中于某個區域附近。到了迭代后期，處于這個區域的數據點規模較大時，在代理模型的構建過程中就會處于主導地位，導致迭代后期算法一直在這一區域進行搜索。倘若這一區域是局部最優解的吸引區域，則會出現圖3和圖4中所示的停滯現象。而PSO-ASC算法在迭代搜索過程中總是根據聚類結果來選擇數據構建代理模型，在迭代中期聚類結果隨著迭代過程的推進變化較大，因此基于代理模型的搜索過程主要關注于全局探索，最佳適應值的變化速度較慢；因此，PSO-ASC算法得到的數據集具有更好的多樣性，在迭代后期則能更好的克服局部最優解的吸引，最終得到更加精確的近似最優解。

圖2 CAL-SAPSO、PSO-ASC優化d=10,20,30的Ackley函數的收斂曲線

圖3 CAL-SAPSO、PSO-ASC優化d=10,20,30的Ellipsoid函數的收斂曲線

圖4 CAL-SAPSO、PSO-ASC優化d=10,20,30的Griewank函數的收斂曲線

圖5 CAL-SAPSO、PSO-ASC優化d=10,20,30的Rastrigin函數的收斂曲線

圖6 CAL-SAPSO、PSO-ASC優化d=10,20,30的Rosenbrock函數的收斂曲線

考慮兩種算法獨立運行20次所得到的最終狀態，其運行結果平均值、中位數、標準差，以及兩種算法的平均運行時間見表3。表3中的對比結果表明，PSO-ASC算法求解測試問題的最終結果的平均值和中位數均優于CAL-SAPSO算法。由于PSO-ASC在迭代中期的全局搜索過程得到了分布更好的數據點集，算法能更好地克服全局最優解的吸引，從而可以得到更精確的全局最優解。因此，PSO-ASC算法需要更多的迭代預算來實現種群的收斂，在迭代次數還不能達到其種群收斂要求的情況下，PSO-ASC算法求解結果的標準差會略高于CAL-SAPSO。然而PSO-ASC算法對代理模型的構建數據集規模進行了控制，在搜索模式二和模式三中均隨機采用集成模型中的一種模型進行評價，與CAL-SAPSO算法相比雖然所構建的代理模型精度略微下降，但基于代理模型的搜索過程的時間復雜度卻大大降低。因此，PSO-ASC最終結果以標準差略大的代價，獲得了更低的時間復雜度，其整體性能優于CAL-SAPSO。

表3 PSO-ASC與CAL-SAPSO對測試問題的運行結果比較

3 代理模型輔助的混合變量進化算法(SaMV-MOEA)及其在S-系統推斷中的應用

3.1 非線性S-系統及其雙目標優化模型

非線性S-系統是一種能夠較好地刻畫生化反應的非線性動力學性質的微分方程模型。有N種物質參與反應的生化網絡S-系統如下

式中：Xi為第i中反應物的濃度，αi,βi,gij,hij為模型參數。然而，S-系統中的模型參數較多，變量Xi對模型參數的適應度地形非常復雜，而在最優參數值附近反應物Xi的濃度對參數又極不敏感，因此對稀疏S-系統的推斷非常困難。文獻[13]采用二進制變量刻畫生化網絡的網絡連接關系，構建了推斷S-系統的N個方程進行逐個推斷的雙目標優化模型

minF(θi)=(err(θi),L0(θi))

(3)

式中：θi=(αi,βi,gi1,…,giN,hi1,…,hiN)為第i個方程的參數向量，err(θi)為根據參數向量θi所計算出的數據擬合誤差，L0(θi)為參數向量θi的L0范數。為了更加容易得到稀疏的網絡連接，采用二進制向量表示網絡連接，實數變量表示具體的參數值，并設計了混合變量的多目標進化算法(mixed-variable multiobjective evolutionary algorithm，MV-MOEA)對S-系統來進行求解。在對表4中的S-系統的每個微分方程進行逐個推斷的數值實驗中，MV-MOEA在2000次個體評價以后得到了更精確的推斷結果[13]。

表4 5維S-系統的模型參數

3.2 代理模型輔助的混合變量進化算法(SaMV-MOEA)

由于MV-MOEA在迭代過程中生成了大量的候選解并對其進行了精確評價，充分利用已搜索到的歷史結果來構建代理模型，可以提高MV-MOEA的全局收斂速度和局部開發能力。為此，本文將CCS-SM策略引入MV-MOEA，得到一種代理模型輔助的混合變量多目標進化算法(SaMV-MOEA)。

由于MV-MOEA采用了不同的方式來生成候選解中的二進制串和實數向量，在通過變異生成二進制串以后，可以采用代理模型來提高實數向量的生成效率。首先，在MV-MOEA中增加檔案集A，保存所搜索到的所有候選解。對于檔案集A中的任意一個解x=(bx,rx)，bx為N維二進制串，rx為N+2維實數向量。令

θ=(rx(1∶2),bx),bx?rx(3∶N+2)

(4)

式中：bx?rx(3∶N+2)表示bx與rx(3∶N+2)逐個分量相乘。于是可以得到由參數向量θ構成的代理模型訓練數據集Dt。

在SaMV-MOEA的新個體生成策略中，根據CCS-SM策略構建全局或局部代理模型，并基于此代理模型進行小種群規模，低迭代次數的PSO搜索。最后，將PSO得到的實數解向量與MV-MOEA中的變異策略生成的實數解向量分別通過式(4)和MV-MOEA的二進制變量生成策略得到的二進制串進行結合，從而得到優化模型(3)中的參數向量θ。通過err(θi)對兩個實數向量串進行比較，將對應的適應值較好的實數向量作為新個體的實數向量，從而提高實數解向量的生成效率。

考慮到基于代理模型的迭代搜索過程也具有一定的時間復雜度，我們將代理模型輔助的迭代搜索的種群規模設為20，迭代次數設為50。另外，為進行公平的比較，SaMV-MOEA和MV-MOEA的種群均設為100。對于表4中S-系統進行數值實驗，SaMV-MOEA經過1000次迭代和MV-MOEA經過2000次迭代的數值結果見表5。

表5 SaMV-MOEA與MV-MOEA對S-系統的推斷結果比較

數值實驗結果表明，通過引入代理模型能夠提高實數向量的生成效率，雖然SaMV-MOEA的迭代次數只有MV-MOEA的一半，但卻得到了與其相似的推斷結果。需要特別說明的是，對于第3個方程，SaMV-MOEA得到了比MV-MOEA更接近真實模型參數的推斷結果。這說明在代理模型的輔助下，SaMV-MOEA對于具有平坦的適應值地形的優化模型具有更強的全局搜索能力，能夠更快地收斂到全局最優解附近。

4 結束語

目前，對SAEA的研究工作主要集中于如何降低昂貴優化問題的精確評價次數，卻較少關注如何利用低復雜度的代理模型來提高進化算法的收斂效率。本文提出了一種基于聚類的代理模型構建策略CCS-SM，并由此提出了CCS-SM策略的PSO-ASC和通過CCS-SM策略來加速收斂的SaMV-MOEA。數值實驗結果表明，基于CCS-SM策略進行迭代搜索的PSO-ASC和將其作為加速策略的SaMV-MOEA的優化性能均優于已有的算法，表明該策略是一種高效的代理模型構建和管理策略，可以在各類代理模型輔助的進化算法中進行推廣應用。