三階段自適應采樣和增量克里金輔助的昂貴高維優化算法

顧清華，劉思含，王 倩，駱家樂，劉 迪

1.西安建筑科技大學管理學院，西安 710000

2.西安建筑科技大學西安市智慧工業感知計算與決策重點實驗室，西安 710000

3.西安建筑科技大學資源工程學院，西安 710000

在過去的幾十年里，進化算法逐漸應用于解決多目標工程優化問題，各種多目標進化算法也被相繼提出[1]。然而，在現實生活的優化問題中，大多數問題目標函數的計算代價成本昂貴[2]，即昂貴的多目標優化問題，例如創傷系統設計[3]和熔爐優化[4]，多目標進化算法在評估次數有限時求解昂貴問題面臨很大的挑戰。因此，代理輔助的進化算法（surrogate-assisted evolutionary algorithms，SAEAs）應運而生，并成為求解昂貴的多目標優化問題的流行方法[5]。

SAEAs使用代理模型的輸出來評估解，以減少昂貴的函數評估次數，根據代理模型的不同輸出結果，可以將SAEAs分為兩類。第一類是基于分類的SAEAs，其代理模型的輸出是解決方案的合理類型，即好解或壞解。利用k-最近鄰模型[6]、前饋神經網絡模型[7]或裝袋集成模型[8]等作為分類器來判斷解的類型。第二類是基于近似的SAEAs，是最常見的一類，其代理模型的輸出是解的預測值，例如：ParEGO（Pareto optimization efficient global optimization）[9]使用克里金模型作為代理模型來近似目標函數的聚合函數；在K-RVEA（Kriging-assisted reference vector guided evolutionary algorithm）[10]中，構建克里金模型來逼近每個目標函數，以提高收斂性和多樣性；HSMEA（hybrid surrogate-assisted multi-objective evolutionary algorithm）[11]、HE-OMOPSO（heterogeneous ensemble-optimal multi-objective particle swarm optimization algorithm）[12]利用幾種機器學習技術的異質集成來提高對不確定性估計的準確性，其中HE-OMOPSO通過加權平均法將克里金模型和徑向基函數網絡模型結合起來有效的逼近目標函數；CBSAEA[13]對種群進行聚類分析，使用徑向基函數作為代理模型來輔助差分進化算法對個體進行選擇。此類SAEAs使用模型輸出的預測值或不確定性對候選解進行排序，具有較好的預篩選能力。

許多機器學習技術已用在SAEAs 中建立代理模型，其中，克里金模型應用最為廣泛，它能夠在得到預測值的同時提供預測的不確定性，然而，當求解決策變量高維的多目標進化問題時，在低維中表現良好的克里金輔助的SAEAs 將變的難以計算，主要是由于訓練克里金模型的計算復雜度高，為O(n3)，其中n是訓練樣本數[14]，而且在每次面對新樣本時，都需要重新構建模型[15]。針對上述困難，相關學者嘗試將增量學習理論加入克里金模型，使模型在更新時利用上一個模型的信息來降低計算成本，并在單目標優化問題上取得了一定的進展[16]，但僅考慮了單目標優化且模型超參數固定，因此仍存在局限。本文提出了一個基于三階段自適應采樣策略的增量克里金輔助進化算法（incremental Krigingassisted evolutionary algorithm with a three-stage adaptive sampling strategy，TS-ⅠKEA）來求解決策變量高維的昂貴多目標優化問題。本文的主要貢獻可歸納如下：（1）將改進的增量克里金模型應用于SAEA，能夠基于每代種群的不確定性自適應的決定是否更新超參數，在控制計算量的前提下保證模型的精度；（2）設計了一種三階段自適應采樣進行模型管理，將算法的優化狀態分為三種，并根據所處狀態采用不同的策略。

1 基礎知識

1.1 昂貴高維多目標優化算法

在這項工作中，研究問題為以下形式的昂貴高維多目標優化問題：

其中，x是具有d個決策變量的決策向量，X表示決策空間，fm(x)是目標向量F的第m個目標。多目標是指目標的數量m大于2。目標函數是黑盒，要通過耗時的數值模擬或昂貴的物理實驗來評估，因此，為解決此問題，必須基于模擬實驗收集的數據來構建代理[2]。在代理輔助進化優化的背景下，d＞20 的問題被稱為高維問題，現有的大多數SAEA僅可以解決決策變量少于20個的問題。除此之外，對于多目標優化問題，通常沒有唯一的理想解來達到所有目標的最優值，而是存在一組折衷的帕累托最優解，稱為帕累托集（Pareto set，PS），PS在目標空間中的投影稱為帕累托前沿（Pareto front，PF）。

1.2 基于前景區域的進化算法

本算法選擇PREA（promising-region-based evolutionary multi-objective optimization algorithm）[17]作為優化器，其一PREA 能夠很好的適應各種PF，保證TS-ⅠKEA 對具有不同PF 的問題都有更強的魯棒性，其二PREA 是基于指標的多目標進化算法且其指標Ir∞的計算復雜度僅為O(n2)，計算復雜度低更適用于求解高維多目標優化問題。PREA 在目標空間識別出有希望的區域，再使用基于平行距離的多樣性維護機制在有希望的區域內選擇個體，兩個主要組成部分為：（1）有希望區域：使用指標Ir∞來表示每個個體的適應度值并去除種群異常點：

其中，x和y是目標空間Rm中的解，xq和yq分別表示其第q維的目標函數值，Z(x,y)=(max(0,[y1/x1]-1),max(0,[y2/x2]-1),…,max(0,[ym/xm]-1))。根據個體的適應度值標記種群中最好的N個個體，據此在目標空間定義一個有希望區域Rm：

其中，和分別表示N個最好解中第i個目標的最大值和最小值。有希望區域Rm至少包含N個個體，該區域之外的個體被認為是收斂性不足且需要被刪除的解。（2）多樣性維護機制：將候選個體垂直投影到一個由指定的超平面上，平行距離dij是任意兩個個體垂直投影之間的距離，每個個體的擁擠距離Di由平行距離來表示：

依次從Rm中選擇擁擠距離最小的兩個個體并將適應度值較小的個體刪除，重復進行直到種群規模達到N。

2 基于三階段自適應采樣策略的增量克里金輔助進化算法

2.1 算法整體框架

算法構建自適應更新超參數的增量克里金模型作為代理模型，使用PREA 作為優化器，并提出一種三階段自適應采樣準則進行模型管理，整體流程圖如圖1所示。TS-ⅠKEA 每十代輸出由交叉變異操作產生的后代種群Ps，并根據代理模型的預測值進行預選。在每一輪的輸出群體Ps中選擇T個解進行真實函數評估，這些解用來更新種群P和代理模型。以下六個重要步驟組成了TS-ⅠKEA。

圖1 TS-ⅠKEA算法流程圖Fig.1 Flowchart of TS-ⅠKEA algorithm

（1）初始化：使用拉丁超立方體采樣生成大小為N的初始種群P，并使用真實函數對其進行評估。使用種群P對每個目標函數建立原始增量克里金模型。

（2）運行優化器：使用PREA進行種群進化，其中函數評估替換為使用自適應更新超參數的增量克里金模型。在用于采樣之前，將經過10代的演化。

（3）填充采樣：采用三階段自適應采樣策略，分別考慮當前種群的收斂性、多樣性和不確定性，將算法的優化狀態分為三種，并根據所處狀態采用有針對性的采樣策略，詳細過程見2.3節。

（4）更新種群：與PREA 中的思想一致，對于新樣本，P種群由具有無限范數的基于比率的指標Ir∞和基于平行距離的多樣性維護機制來進行更新。

（5）重建自適應更新超參數的增量克里金模型：利用所有訓練數據重建每個目標函數的模型，并根據最大不確定性決定是否更新超參數，詳細說明見2.2節。

（6）重復進行步驟（2）～（5）直到真實函數評估次數耗盡。

2.2 自適應更新超參數增量克里金模型

克里金模型（也被稱為高斯過程）是全局性的近似模型，它提供預測值和預測的不確定性信息。原始克里金模型假設多目標優化問題的目標函數采用以下形式：

其中，μ(x)是高斯過程的預測值，ε(x)是一個平均值為零、標準差為δ的高斯分布。圖2顯示了由四個訓練數據(x(1),y(1))、(x(2),y(2))、(x(3),y(3))、(x(4),y(4))構建的一維克里金模型，圖中陰影部分表示置信范圍。盡管克里金是理想的代理模型，但正如前文中所提到的，對決策變量高維的問題建模非常困難，為了應對這個問題，在克里金模型中引入增量學習，將時間復雜度降低到O(n2)。

假設建立了一個有n個樣本的克里金模型，此時需要用q個新樣本來更新它。增量克里金模型[16]是利用從先前模型獲得的信息來更新模型，并采用θ調整策略[18]來學習初始超參數，而不像原始的克里金模型從頭開始訓練。由于廣泛調整簡化的超參數的效果要優于調整不準確但完整的超參數集，所以θ調整策略將所有的超參數調到相同的值，在一維空間中只優化一個θ值，從而將超參數學習問題的維度降低到一維。

用U表示訓練數據之間的相關矩陣，由舊模型的U-1計算新的U?-1 是建立增量克里金模型最具挑戰性的部分。由于增量模型的超參數是從以前的模型中沿襲的，所以U?-1 的前n行和前n列由U-1組成。新的相關矩陣表示為：

根據分區矩陣的逆向計算，可以得到：

其中，C=B-ATB-1A，是一個q×q矩陣。新樣本的數量q比訓練樣本的數量n小得多，所以公式（10）的整個復雜度為O(n2)。當使用Cholesky 分解時，構建增量克里金模型最困難的部分是由先前克里金模型的E計算新的E?，以滿足U?=E?E?T。由于E?是一個下三角矩陣，E?可以寫為：

其中，E11和E22也是下三角矩陣。因此可得：

比較公式（9）和（12），可以得到：

由于Cholesky分解是獨一無二的，可以從公式（13）中得到E11=E。根據公式（14），計算出ET21=E-1A和E21=AT(ET)-1，將它們代入公式（15），即可得到E22=Chol(B-AT(ET)-1E-1A)。最后，新的相關矩陣E?可以寫為：

其中，(B-AT(ET)-1E-1A)是q×q的矩陣，Cholesky 分解復雜度為O(q3),q遠小于訓練樣本數n，因此可忽略不計，公式（16）的整體復雜度也是O(n2)。

與僅調整一次超參數的模型相比，在整個更新過程中對超參數進行某種形式的再評估可有效利用現有的計算預算[18]；另一方面，更新超參數是克里金模型的主要計算成本。根據上述因素，本算法采用包含兩個基本思想的自適應更新超參數策略，以更好地平衡計算成本和模型精度：（1）克里金模型輸出的不確定性被用來衡量模型的準確性，不確定性越大表明模型的準確性越差。因此，如果此時種群中個體的最大不確定性大于本輪出現的最大不確定性值，超參數就會更新，將每次更新視為新的一輪。（2）為了加快優化過程，此策略在大多數情況下使用增量克里金建立模型，而不更新超參數，將舊模型的超參數視為新模型的起點。

2.3 三階段自適應采樣策略

對于SAEAs 來說，選擇合適的訓練數據來更新代理模型是至關重要的。選取收斂性和多樣性好的有希望解可以提高這兩方面的性能，而選取不確定解則可以提高代理模型的全局精度。為了充分利用有限的函數評估次數更有針對性的進行采樣，本文提出了一種基于優化狀態評估的三階段自適應采樣策略。優化狀態如圖3所示。

圖3 三階段采樣策略流程圖Fig.3 Flowchart of three-stage sampling strategy

優化狀態分為三種情況，若此時增量克里金模型更新超參數，按照更新要求則此時模型預測的不確定性較大，應探索未開發區域以提高模型的精度，則為不確定性需求狀態；若種群Pt的收斂性與上輪的種群Pt-1收斂性有明顯差異，則表明仍有收斂空間，為收斂性需求狀態，反之則為多樣性需求狀態，注意此處使用種群中解到估計理想點的距離來衡量收斂性。

針于每種優化狀態，采用相對照的特制抽樣策略來選擇T個新樣本用于昂貴的函數評估。

（1）收斂性采樣策略：選擇T個適應度值最大的個體，此處的適應度值用指標來衡量，與PREA中一致。

（2）多樣性采樣策略：依次計算每個個體對種群多樣性的貢獻值，多樣性用純多樣性（pure diversity，PD）指標來衡量，選擇貢獻值最大的T個個體。

（3）不確定性采樣策略：首先對當前種群個體的每個目標依次進行不確定性的排序，不確定性為增量克里金模型的對應輸出值，隨后對每個個體每個目標上的排序序號取均值，作為其不確定性排序號碼，選擇排序號碼最大的T個個體進行真實目標函數評價。

由上述三種優化狀態的區分以及三種有針對性的策略的制定，可以看出三階段自適應采樣策略能夠首先保證算法收斂性，且在模型精度較低時，通過選擇不確定性大的解進行再評估，對未開發區域加強探索，避免了模型誤差的累加，同時對多樣性的探索使算法降低陷入局部最優的可能性。

3 實驗與分析

為了驗證所提出的算法TS-ⅠKEA和策略的有效性，本章分別在DTLZ[19]和MaF[20]上進行了數值實驗，并在實例上進行了仿真，驗證了所提出算法的實際意義。

3.1 對比算法

選擇八種最先進的算法進行對比，簡要介紹如下：

（1）NSGA-ⅠⅠⅠ[21]是經典的多目標進化算法，它引入了廣泛分布的參考點以保持種群的多樣性。

（2）PREA[17]是基于指標的多目標進化算法，它首先在目標空間中識別有希望的區域，并采用基于平行距離的多樣性保護策略來選擇有希望區域內的個體。

（3）REMO[22]是代理輔助進化算法，它提出了一種新的基于三類分類器的關系模型來預測候選解與已評估解之間的關系。

（4）ABSAEA[23]使用自適應貝葉斯作為代理模型解決昂貴多目標優化問題，采樣標準在優化過程中自適應切換，以實現勘探和開采之間的平衡。

（5）EDN-ARMOEA[24]提出一種高效輟學神經網絡作為代理模型，在訓練和測試階段都采用退出策略。

（6）HeE-MOEA[25]使用不同機器學習技術的集成作為模型管理和填充標準的代理模型，以有效近似目標函數。

（7）CPS-MOEA[6]使用兩個外部解集來訓練k-最近鄰模型，并以此作為分類器來過濾新生成的個體。

（8）KTA2[26]提出了影響點不敏感模型作為代理模型，并設計了分別考慮收斂性、多樣性和模型不確定性要求的自適應采樣策略。

3.2 參數設置

TS-ⅠKEA中的參數設置如下：

（1）種群大小為N=100。

（2）每個算法在每個測試問題上獨立運行20次。

（3）更新代理模型之前，優化器迭代次數為wmax=10,每次更新代理模型時選擇T=5 個解進行真實函數評估。

下面列出所有比較算法的通用參數設置：

（1）本文使用目標為3，決策變量分別為20、40、60和100的DTLZ和MaF測試集來驗證算法有效性，每個算法的停止條件是達到最大評估次數FEmax，由于評估是昂貴的，當決策變量為20，40，60 時設置為500，決策變量為100時設置為1 000。

（2）在DTLZ 和MaF 測試集中，使用ⅠGD 指標進行評估，ⅠGD 值越小算法的綜合性能越好；在實際工程優化問題中，由于不存在真實的PF，因此，采用HV指標比較優化結果，HV越大則得到的優化結果越好。

（3）初始訓練樣本設置為N1=100。

（4）所有程序均在Matlab R2021b 中編碼，使用進化多目標優化平臺PlatEMO[27]進行對比實驗，每個算法獨立運行20 次，通過置信度為0.05 的Wilcoxon 秩和檢驗比較所提出算法和比較算法的實驗結果，符號“+”和“-”分別表示對比算法顯著優于和劣于TS-ⅠKEA，符號“=”則表示沒有顯著差異；為了保證公平性，所有對比實驗的特定參數設置都嚴格遵循原始文獻中的設置。

3.3 策略有效性實驗

為驗證所提出的兩種策略的有效性，本節設計TS-ⅠKEA 算法的兩個變體，稱為TS-ⅠKEA1 和TS-ⅠKEA2，其中TS-ⅠKEA1除不使用三階段自適應采樣策略來管理代理模型以外，與TS-ⅠKEA保持一致，TS-ⅠKEA2使用增量克里金模型作為代理模型，此模型的超參數不隨算法的更新進行自適應調整，其余與TS-ⅠKEA保持一致。對NSGA-ⅠⅠⅠ、PREA、變體TS-ⅠKEA1、變體TS-ⅠKEA2 以及TS-ⅠKEA五個算法在三個目標和20、40、60、100個決策變量的DTLZ問題上進行20次獨立運行實驗，表1為得到的相應ⅠGD值，并用灰色陰影突出了最佳結果。從實驗結果可看出TS-ⅠKEA取得了最佳的結果。首先，代理模型輔助的TS-ⅠKEA1和TS-ⅠKEA2明顯優于多目標進化算法NSGA-ⅠⅠⅠ和PREA，這表明在有限次函數評估下，代理輔助具有優勢；其次，可觀察到TS-ⅠKEA2 在部分測試實例上與TS-ⅠKEA 取得了相似的性能，但在DTLZ1、DTLZ3和DTLZ6上仍差于TS-ⅠKEA，這是由于變體2舍棄了在運行過程中自適應更新模型超參數，使得算法難以在模型預測產生偏差時及時調整，則模型誤差隨著數據的不斷更新逐漸累加，尤其是針對DTLZ1、DTLZ3 這類多模態難以收斂的問題時，算法精度更加無法保證，因此變體2的算法效果比所提算法差；最后，從TS-ⅠKEA和TS-ⅠKEA1的實驗結果中看出，所提算法在大多數測試問題上優于變體1，變體1 保留了自適應更新超參數的增量克里金模型，保證了代理模型的預測精度，但又因為沒有使用三階段自適應采樣策略來管理代理模型，無法有針對性的選擇更適合算法當前所處狀態的個體，不能有效利用有限計算資源。綜合以上分析，自適應更新模型超參數的增量克里金模型和三階段自適應采樣策略在TS-ⅠKEA算法中缺一不可，求解昂貴的高維多目標優化問題時，該模型和模型管理策略形成的協作機制可以有效平衡種群的收斂性和多樣性。

3.4 DTLZ和MaF上數值實驗

3.4.1 DTLZ測試集上實驗與分析

將六種算法在DTLZ測試集上獨立運行20次，得到的ⅠGD 結果如表2 所示，其最佳平均ⅠGD 值由灰色背景突出顯示。實驗結果顯示，REMO、EDN-ARMOEA、ABSAEA、HeE-MOEA、CPS-MOEA、TS-ⅠKEA 在DTLZ測試集上取得的最佳結果數量分別為10、0、0、0、3、15，其中TS-ⅠKEA表現最優，下面結合每個測試問題的特性進行綜合分析。

表2 算法在三目標不同決策變量的DTLZ上的ⅠGD值Table 2 ⅠGD values of algorithms on DTLZ with different decision variables for three objectives

DTLZ1 和DTLZ3 具有多模態的特性，很難在有限函數評估下收斂到真實PF。REMO在DTLZ1和DTLZ3上效果最好，其次是TS-ⅠKEA。TS-ⅠKEA未能取得最佳結果的原因在于，多模態問題具有多個全局或局部最優解，TS-ⅠKEA 的三階段自適應采樣策略首先保證收斂，但局部最優的出現對算法采樣策略的狀態評估產生了影響，算法錯把尋找到的局部最優當作全局最優進而轉向加強多樣性，從而忽略對其他最優區域的探索。從表2 可以看出六種算法在這兩個測試問題的ⅠGD 值都非常大，說明算法得到的非支配解集都離真實PF 很遠。因此，解決這些問題需要進行更多的函數評估。

DTLZ2 和DTLZ4 相對容易收斂，但它們的困難在于保持種群的多樣性，通常用來檢驗算法保持解決方案均勻分布的能力。DTLZ2是一個具有凹形橢圓的測試問題，TS-ⅠKEA在DTLZ2問題上取得了最好的結果，其次是REMO 和HeE-MOEA、TS-ⅠKEA 的三階段采樣策略對三個狀態的評估和針對性的策略保證了算法的收斂性和多樣性以及模型預測的準確性。DTLZ4是具有偏好特點的測試問題，可以觀察到REMO、ABSAEA 和EDN-ARMOEA均在低維時表現良好，但隨著決策變量維數的增加其性能變差，其中EDN-ARMOEA的代理模型EDN在適應度預測和不確定性估計方面的準確性較低，而且在解決高維問題方面的性能略差，REMO 提出的關系模型更適用于中低規模的決策空間，而本算法TS-ⅠKEA 的自適應更新超參數的增量克里金模型能夠很好的適應高維決策變量。

DTLZ5 問題具有退化的特點，用來測試算法在一條曲線上收斂的能力。從表2可以看出，TS-ⅠKEA在這個問題的每個決策變量上都取得了最好的結果。DTLZ6也具有退化和偏向的特性，CPS-MOEA 在這個問題上取得了最佳結果，其次是REMO和TS-ⅠKEA，CPS-MOEA使用分類器來探索未知區域，在解決這類問題上有較大的優勢，而TS-ⅠKEA利用代理模型輸出的預測值和不確定性進行搜索，在搜索過程中可能被誤導，從而在這一問題上表現較差，雖然TS-ⅠKEA 在DTLZ6 問題上沒有取得最好的結果，但其競爭力也得到了體現。

DTLZ7 測試問題有一組不相連的帕累托最優區域。觀察圖4 可看出TS-ⅠKEA 的ⅠGD 值變化趨勢更快且持續下降，并且圖5可視化了六個算法在三個目標20個決策變量的DTLZ7 上得到的非支配解集，可以看到只有TS-ⅠKEA找到了所有四個不相連的PF且獲得了具有保證收斂和分布的子種群，其余的算法都不能取得滿意的結果，不適合處理這種不連續的問題。這是由于三階段自適應采樣策略在仍有收斂空間時重點保證收斂，使得TS-ⅠKEA 的ⅠGD 變化曲線能夠在初始階段迅速下降，又通過對多樣性和未開發區域的探索以及代理模型在預測精度不高時適時調整超參數，使得ⅠGD能夠穩步持續下降，并最終找到分布均勻的全局最優解。

圖4 在DTLZ7上獲得的ⅠGD變化曲線Fig.4 ⅠGD variation curves obtained on DTLZ7

圖5 在20個決策變量DTLZ7上取得的非支配解Fig.5 Nondominant solutions obtained on 20 decision variables DTLZ7

從DTLZ測試問題實驗結果可以看到，TS-ⅠKEA在處理退化和不連續問題上具有極強的優勢，雖然沒有在每一類問題上都表現的最好，但綜合而言，TS-ⅠKEA 表現出了自身的競爭力。

3.4.2 MaF測試集實驗與分析

六種算法獨立運行MaF基準測試問題20次的ⅠGD統計結果如表3所示，其中將最好的結果進行了灰色陰影突出顯示。實驗結果顯示，REMO、EDN-ARMOEA、ABSAEA、HeE-MOEA、CPS-MOEA、TS-ⅠKEA 在MaF測試集上取得的最佳結果數量分別為7、0、1、0、0、20，可以看出TS-ⅠKEA明顯優于其他算法且整體表現最好。

表3 算法在三目標不同決策變量的MaF上的ⅠGD值Table 3 ⅠGD values of algorithms on MaF with different decision variables for three objectives

在具有反轉PF的MaF1和凹PF的MaF2上，TS-ⅠKEA表現最佳。從ⅠGD 值可以看出，在20、40、60、100 的決策變量上，TS-ⅠKEA 全都具有絕對優勢，通過圖6 算法在MaF1 上ⅠGD 的變化曲線可以明顯看出，TS-ⅠKEA 的ⅠGD下降速度最快，這歸因于三階段采樣策略對于優化狀態的評估中，優先保證種群的收斂，使種群能夠更快速的收斂，且更新模型超參數時對未知區域的探索使算法避免陷入局部最優。

圖6 在MaF1上獲得的ⅠGD變化曲線Fig.6 ⅠGD variation curves obtained on MaF1

對于MaF3和MaF4具有多模態特征的問題，TS-ⅠKEA沒有取得最令人滿意的結果，次于REMO。但是可以從表3 中看出，這兩類問題的ⅠGD 統計結果都很大，說明算法得到的非支配解離真實PF 很遠，只有進行更多的真實函數評估才能解決這類問題。MaF5 是凸PF 的有偏問題，在決策變量為20和40時，REMO取得了最好的結果，但隨著決策變量變大，TS-ⅠKEA優勢凸顯出來，這可能的原因是本算法提出的自適應更新超參數的增量克里金模型在高決策變量時對維持模型精度具有優勢。MaF6 和MaF7 的效果以ⅠK-PREA 最佳，ABSAEA次之。其中，MaF6 具有退化的PF，圖7 可視化了20 個決策變量時MaF6六個算法得到的非支配解與真實PF，可以直觀的看出在有限的函數評估下只有TS-ⅠKEA 找到了真實PF 并取得了一定程度的分布性，ABSAEA 靠近了真實PF但仍沒有找到，其余算法離真實PF還有很遠的距離。TS-ⅠKEA 的采樣策略在未收斂時首先重點保證收斂，因此能夠成為唯一一個找到真實PF 的算法。再次證明了TS-ⅠKEA 在處理退化問題上具有獨有的優勢。

圖7 在20個決策變量MaF6上取得的非支配解Fig.7 Nondominant solutions obtained on 20 decision variables MaF6

3.4.3 算法運行時間對比分析

本小節給出算法的時間對比分析，圖8（a）和（b）分別顯示了六個算法在DTLZ 和MaF 系列測試問題的四個不同決策變量上的平均運行時間，可以看出TS-ⅠKEA時間消耗僅次于CPS-MOEA，顯著優于其他四個對比算法。盡管CPS-MOEA 時間消耗最小，但在56 個測試實例的44 個上性能都差于TS-ⅠKEA，其模型的分類精度比較差；使用原始克里金作為代理模型的ABSAEA，隨著決策變量維度的增高，運行時間成倍激增，而TS-ⅠKEA 使用的增量克里金模型自適應更新超參數，保證模型精度的同時大幅降低算法的時間復雜度，具有實用價值。綜合算法性能和運行時間分析，TS-ⅠKEA具有很強的競爭力。

圖8 各算法在DTLZ和MaF上的運行時間Fig.8 Running time of all algorithms on DTLZ and MaF

3.5 實際工程優化案例

為了驗證算法TS-ⅠKEA在實際問題上的有效性，本節在路徑規劃實際工程[28]案例上進行了仿真實驗，并與多個最先進的算法進行了對比。路徑規劃優化問題是在圖形G=(V,E)中尋找一組最佳路徑P*={p1,p2,…,pL}，路徑N由G=(V,E)中的一組相鄰節點組成，從初始節點nS∈V到預定義端點nEnd∈V，即N=(ni,ni+1,…,nk)=pi,ni=ns,nk=nEnd，該問題包含27 個決策變量，需要在歐氏距離、預期延遲、上升高度、路程時間和路徑平滑度五個目標中尋找最佳結果。用上述五個目標來評估解決方案，解決方案為固定長度的路徑N。七種最新的SAEAs 在500 次評估后得到的HV 和運行時間如表4 所示，其中最佳結果用深灰色標出，排名第二的用淺灰色標出。通過實驗結果可以看出TS-ⅠKEA 獲得的解綜合性能HV最好，運行時間僅次于CPS-MOEA。其原因在于CPS-MOEA 是基于分類的SAEAs，在一次運行后即能篩選出種群大小的“好”解，因此能夠更快達到算法終止條件，但由于選解的粗糙，得到的解的性能較差；本算法采用的自適應更新超參數的增量克里金模型使得算法相比其他SAEAs 運行時間大幅度減少，尤其是與使用原始克里金模型代理的算法相比，例如KTA2、ABSAEA，又有三階段采樣的模型管理策略來保證模型的精度和種群的性能，算法取得了最優的結果。因此，性能的提高和時間的縮短使得TS-ⅠKEA 在實際工程中具有實用價值。

表4 七個算法在實際問題上的HV和運行時間Table 4 HV and runtime of seven algorithms in practical problems

4 結論

本文提出了一種新的可用于求解決策變量高維的SAEA，稱為TS-ⅠKEA。該算法使用根據模型預測精度自適應更新超參數的增量克里金模型作為代理模型，降低時間復雜度的同時保證了模型在高維度時的準確度，并提出了基于優化狀態的三階段采樣策略來自適應的選擇更合適的解進行函數重評估。在DTLZ、MaF兩組測試集以及路徑規劃實際工程案例上與近年提出的最先進的算法進行對比實驗，驗證了所提出算法的競爭力，特別是在處理一些退化和不連續問題上具有獨特優勢，且具有實際應用價值能夠大幅減少優化時間，在解決高維昂貴多目標優化問題具有廣闊的應用前景。

在未來的工作中，將繼續探索更有效的模型管理策略，使用更加精準的優化狀態評估方案來進一步提高模型精度，此外，將TS-ⅠKEA 擴展到解決具有約束的復雜現實問題也是值得研究的。