面向高維優(yōu)化的記憶引導(dǎo)信任域貝葉斯優(yōu)化（MG-TuRBO）

面向高維優(yōu)化的記憶引導(dǎo)信任域貝葉斯優(yōu)化（MG-TuRBO）

Memory-Guided Trust-Region Bayesian Optimization (MG-TuRBO) for High Dimensions

https://arxiv.org/pdf/2604.08569

摘要

交通仿真與數(shù)字孿生標(biāo)定是一個(gè)在有限仿真預(yù)算下具有挑戰(zhàn)性的優(yōu)化問題。每次試驗(yàn)都需要一次成本高昂的仿真運(yùn)行，且校準(zhǔn)輸入與模型誤差之間的關(guān)系通常是非凸且含噪的。隨著校準(zhǔn)參數(shù)數(shù)量的增加，該問題變得更加困難。我們將一種常用的自動(dòng)標(biāo)定方法——遺傳算法（GA），與貝葉斯優(yōu)化方法（BOMs）進(jìn)行了比較：包括經(jīng)典貝葉斯優(yōu)化（BO）、信任域貝葉斯優(yōu)化（TuRBO）、Multi-TuRBO，以及本文提出的記憶引導(dǎo)型TuRBO（MG-TuRBO）方法。我們在兩個(gè)具有14和84個(gè)決策變量的真實(shí)交通仿真標(biāo)定問題上對比了性能，分別代表低維與高維（14D和84D）設(shè)置。針對BOMs，我們研究了兩種采集策略：湯普森采樣與一種新穎的自適應(yīng)策略。我們采用最終標(biāo)定質(zhì)量、收斂行為以及多次運(yùn)行間的一致性來評(píng)估性能。結(jié)果表明，在低維問題中，BOMs達(dá)到良好標(biāo)定目標(biāo)的速度遠(yuǎn)快于GA。MG-TuRBO在我們的14D設(shè)置中表現(xiàn)相當(dāng)，但在84D問題中展現(xiàn)出顯著優(yōu)勢，尤其是在與我們的自適應(yīng)策略結(jié)合時(shí)。我們的結(jié)果表明，MG-TuRBO特別適用于高維交通仿真標(biāo)定，并可能普遍適用于一般的高維問題。

I. 引言

隨著傳感技術(shù)、網(wǎng)聯(lián)基礎(chǔ)設(shè)施和數(shù)據(jù)管線的持續(xù)改進(jìn)，交通仿真模型在交通運(yùn)行、規(guī)劃與安全分析中變得日益重要[1]。其價(jià)值取決于模型反映現(xiàn)實(shí)的程度，即針對實(shí)際觀測交通條件進(jìn)行校準(zhǔn)的匹配程度。若未知交通流入量、轉(zhuǎn)向比或行為相關(guān)參數(shù)等關(guān)鍵輸入未得到妥善校準(zhǔn)，數(shù)字孿生將產(chǎn)生存在偏差的網(wǎng)絡(luò)狀態(tài)與不可靠的決策。在此，我們將交通仿真校準(zhǔn)視為一項(xiàng)計(jì)算成本高昂的黑盒優(yōu)化問題展開研究。

交通微觀仿真校準(zhǔn)之所以困難，是因?yàn)槠淠繕?biāo)函數(shù)具有隨機(jī)性、非凸性，且評(píng)估成本高昂。在實(shí)踐中，校準(zhǔn)通常采用適應(yīng)度指標(biāo)，通過其與觀測交通流量及速度的吻合程度來進(jìn)行評(píng)估[2]。既往研究與實(shí)踐指南已為主流仿真平臺(tái)確立了校準(zhǔn)工作流程，同時(shí)也表明：隨著網(wǎng)絡(luò)規(guī)模、擁堵程度及參數(shù)維度的增加，校準(zhǔn)難度亦隨之上升[3]。有限的仿真預(yù)算使得搜索效率成為一項(xiàng)關(guān)鍵挑戰(zhàn)。

元啟發(fā)式方法在交通仿真校準(zhǔn)中仍被廣泛使用，因其在梯度不可獲取時(shí)具備靈活性、魯棒性與實(shí)用性[4], [5]。其中，遺傳算法（GA）尤為常見，并在多種校準(zhǔn)場景中展現(xiàn)出實(shí)際應(yīng)用價(jià)值[4]。然而，由于這些方法未對響應(yīng)面進(jìn)行顯式建模，通常需要大量的仿真器評(píng)估調(diào)用。這促使學(xué)界針對此類高成本校準(zhǔn)問題，對樣本效率更高的方法產(chǎn)生興趣。貝葉斯優(yōu)化方法（BOMs）在此類設(shè)定中頗具吸引力，因其利用高斯過程（GP）結(jié)合采集函數(shù)，引導(dǎo)評(píng)估向搜索空間內(nèi)更具潛力的區(qū)域推進(jìn)[6]。BOMs在交通仿真校準(zhǔn)領(lǐng)域亦已展現(xiàn)出良好潛力[7]。

然而，隨著維度升高，標(biāo)準(zhǔn)的全局貝葉斯優(yōu)化（BO）往往效果下降，原因在于在大范圍搜索空間內(nèi)構(gòu)建代理模型與優(yōu)化采集函數(shù)愈發(fā)困難[8]。信任域貝葉斯優(yōu)化（TuRBO）通過將搜索限制于局部信任域內(nèi)提升了算法的可擴(kuò)展性；Multi-TuRBO則通過并行運(yùn)行多個(gè)信任域擴(kuò)展了這一思想，以增強(qiáng)搜索多樣性[9]。此類方法采用湯普森采樣（基于后驗(yàn)樣本的候選點(diǎn)選擇）作為采集策略[10]。它們非常契合交通仿真校準(zhǔn)的場景，因?yàn)樵搱鼍跋碌哪繕?biāo)函數(shù)具有噪聲與多峰特性，且評(píng)估預(yù)算有限。盡管如此，在信任域收縮（collapse）后，重啟決策仍可能使搜索返回至存在相似局部極小值的區(qū)域，從而在高維設(shè)定下降低搜索效率。

我們提出了記憶引導(dǎo)型TuRBO（MG-TuRBO）與一種自適應(yīng)采集策略，兩者以互補(bǔ)的方式對TuRBO進(jìn)行了擴(kuò)展。MG-TuRBO利用評(píng)估歷史，將歸一化設(shè)計(jì)空間中的采樣點(diǎn)聚類為候選吸引盆（basins），基于觀測目標(biāo)值計(jì)算各吸引盆的質(zhì)量與訪問頻次統(tǒng)計(jì)量，并據(jù)此從有潛力但探索不足的吸引盆中選取重啟中心，同時(shí)剔除明顯較弱的吸引盆。這種具備吸引盆感知的重啟策略，有效減少了信任域收縮后對相似局部最優(yōu)值的重復(fù)發(fā)現(xiàn)。我們的自適應(yīng)策略采用改進(jìn)量與預(yù)測不確定性隨時(shí)間動(dòng)態(tài)變化的加權(quán)組合形式。該策略在搜索過程中實(shí)現(xiàn)了對探索-利用權(quán)衡的顯式控制。

II. 作為黑盒優(yōu)化問題的交通仿真校準(zhǔn)

A. 問題表述

我們將交通仿真校準(zhǔn)表述為一個(gè)計(jì)算代價(jià)高昂的黑盒優(yōu)化問題。校準(zhǔn)質(zhì)量是通過使用 Geoffrey E. Havers (GEH) 統(tǒng)計(jì)量比較仿真交通流量與觀測流量來評(píng)估的，這是一種廣泛使用的交通模型校準(zhǔn)指標(biāo) [11]。令表示觀測計(jì)數(shù)，表示在仿真器實(shí)現(xiàn) ω （例如給定的隨機(jī)種子）下，對應(yīng)于候選參數(shù)向量 x 的仿真計(jì)數(shù)。對于每個(gè)目標(biāo)，GEH 的計(jì)算公式如下：

在每次迭代中，我們在歸一化搜索空間中使用有限 Sobol 候選集 [14] 來近似公式 (4)，在該集合上評(píng)估采集策略，并選擇得分最高的候選點(diǎn)進(jìn)行評(píng)估。在進(jìn)行 GP 擬合之前，校準(zhǔn)參數(shù)和目標(biāo)值被標(biāo)準(zhǔn)化為均值 0、方差 1，以提高數(shù)值穩(wěn)定性。

D. 記憶引導(dǎo)型 TuRBO (Memory-Guided TuRBO)

MG-TuRBO 通過僅修改重啟步驟來擴(kuò)展 Multi-TuRBO。在正常搜索期間，每個(gè)信任域遵循與 Multi-TuRBO 相同的基于局部采集的更新和信任域自適應(yīng)規(guī)則。區(qū)別出現(xiàn)在當(dāng)信任域收縮至其最小尺寸時(shí)。MG-TuRBO 并非從隨機(jī)位置重啟，而是利用歷史評(píng)估來識(shí)別有希望的吸引盆，并在那些既具有高質(zhì)量又探索不足的區(qū)域進(jìn)行重啟。算法 1 總結(jié)了該過程。

即在該吸引盆中發(fā)現(xiàn)的最佳目標(biāo)函數(shù)值，以及吸引盆規(guī)模 n k = ∣ B k ∣ ，用于統(tǒng)計(jì)當(dāng)前有多少個(gè)已評(píng)估點(diǎn)屬于吸引盆 k 。

當(dāng)信任域收縮時(shí)，MG-TuRBO 首先剔除明顯較差的吸引盆。它僅保留滿足以下條件的吸引盆：

因此，公式 (7) 和 (10) 定義了算法 1 中的記憶引導(dǎo)重啟邏輯。

與 TuRBO 和 Multi-TuRBO 相比，MG-TuRBO 增加了三個(gè)基于記憶的組件：周期性吸引盆發(fā)現(xiàn)（periodic basin discovery）、質(zhì)量感知吸引盆過濾（quality-aware basin filtering）以及規(guī)模感知重啟選擇（population-aware restart selection）。Multi-TuRBO 通過多個(gè)信任域提高了多樣性，但仍然采用隨機(jī)重啟。相比之下，MG-TuRBO 利用累積的搜索歷史來引導(dǎo)重啟，使其朝向那些有希望但尚未被大量采樣的區(qū)域。該設(shè)計(jì)旨在減少對相似局部最優(yōu)值的重復(fù)發(fā)現(xiàn)，并提高多模態(tài)高維校準(zhǔn)問題中的預(yù)算效率。

E. 采集策略

本研究中的貝葉斯優(yōu)化方法（BOMs）使用兩種采集策略：自適應(yīng)策略和湯普森采樣（Thompson sampling）。

F. 實(shí)驗(yàn)設(shè)計(jì)概覽

對于 14D Chattanooga 問題，總預(yù)算為 B = 100 次評(píng)估。所有方法也都從相同的 Sobol 初始 20 次運(yùn)行開始，用于代理模型初始化。我們使用不同的隨機(jī)種子將每種算法運(yùn)行 10 次，以考察多次運(yùn)行間的一致性。對于 84D Nashville 問題，總預(yù)算為 B = 1500 次評(píng)估，其中包含用于代理模型初始化的 200 次初始運(yùn)行。由于計(jì)算成本較高，我們對每種方法僅運(yùn)行一次。

IV. 結(jié)果

A. 14 維校準(zhǔn)優(yōu)化

圖 2 展示了 14D 網(wǎng)絡(luò)優(yōu)化階段的收斂情況，報(bào)告為 10 次運(yùn)行中的中位數(shù)最佳觀測 GEH 及四分位距（IQR）。共享的初始化階段（評(píng)估 1-20）被排除，以突出引導(dǎo)優(yōu)化期間的差異。GA 顯示出初始下降，在評(píng)估 40 時(shí)達(dá)到約 3.4，然后繼續(xù)緩慢改進(jìn)，在評(píng)估 50-60 時(shí)達(dá)到接近 3.1-3.2 的平臺(tái)期，此后改進(jìn)極小。所有 BOMs 均大幅優(yōu)于 GA。標(biāo)準(zhǔn) BO 穩(wěn)步提升但仍然受限，在評(píng)估 100 時(shí)達(dá)到 1.28（自適應(yīng)）和 1.37（湯普森）的中位數(shù) GEH。

TuRBO 方法收斂更快，并以明顯更低的 GEH 值結(jié)束。在所有方法中，采用湯普森采樣的 TuRBO 表現(xiàn)出最強(qiáng)的性能，在評(píng)估 100 時(shí)達(dá)到 1.01 的中位數(shù) GEH，且具有最緊致的方差，表明跨運(yùn)行的一致性。采用湯普森采樣的 Multi-TuRBO 以 1.05 的中位數(shù)排名第二，隨后是采用湯普森采樣的 MG-TuRBO，為 1.06。自適應(yīng)變體表現(xiàn)稍差：TuRBO（自適應(yīng)）達(dá)到中位數(shù) 1.11，MG-TuRBO（自適應(yīng)）達(dá)到 1.13，Multi-TuRBO（自適應(yīng)）達(dá)到 1.16。在這個(gè) 14D 問題中，MG-TuRBO 的多引導(dǎo)策略（原文為 many-guide，疑為 memory-guided 筆誤）并未顯示出相對于更簡單的信任域方法的明顯優(yōu)勢。自適應(yīng)采集使 BO 和 Multi-TuRBO 在早期獲得更快的進(jìn)展，特別是在評(píng)估 30 到 50 之間。然而，對于 TuRBO，湯普森采樣實(shí)現(xiàn)了最佳的最終性能。對于 MG-TuRBO，自適應(yīng)策略給出了比湯普森采樣更低且更穩(wěn)定的最終中位數(shù)，后者在多次運(yùn)行中顯示出較高的變異性。采集策略以依賴于方法的方式影響性能。對于所有信任域方法，湯普森采樣優(yōu)于自適應(yīng)策略：TuRBO 提升了 9%，Multi-TuRBO 提升了 9%，MG-TuRBO 提升了 6%。這種一致的模式表明，湯普森采樣的激進(jìn)利用（exploitation）在 14D 下與信任域框架有效地結(jié)合。相反，標(biāo)準(zhǔn) BO 表現(xiàn)出相反的行為：自適應(yīng)策略明顯優(yōu)于湯普森采樣 7%，表明全局采集函數(shù)受益于自適應(yīng)策略平衡的探索 - 利用權(quán)衡。

圖 3 展示了在湯普森采樣下評(píng)估點(diǎn)的主成分分析（PCA）投影。前兩個(gè)主成分解釋了總方差的 32.5%（PC1：20.9%，PC2：11.6%）。來自 10 次運(yùn)行的所有評(píng)估點(diǎn)被投影到一個(gè)共享的 PCA 空間中。圖 3 和圖 2 具有一致的結(jié)果。GA 將評(píng)估廣泛散布在可行區(qū)域內(nèi)，但在高質(zhì)量解附近表現(xiàn)出很少的集中。標(biāo)準(zhǔn) BO 形成幾個(gè)主要簇，表明部分集中但局部優(yōu)化較弱。TuRBO 產(chǎn)生緊密、密集的簇，與信任域內(nèi)的集中局部搜索一致。Multi-TuRBO 形成幾個(gè)截然不同的簇，反映跨多個(gè)信任域的并行探索。MG-TuRBO 顯示出類似結(jié)構(gòu)的聚類，但在區(qū)域之間有更明顯的移動(dòng)。在 14D 案例中，這種附加的結(jié)構(gòu)并未轉(zhuǎn)化為相對于 TuRBO 的明顯性能提升。圖 4 總結(jié)了所有方法在評(píng)估 100 時(shí)的最終最佳 GEH。

圖 4 確認(rèn)采用湯普森采樣的 TuRBO 是最強(qiáng)的 14D 方法，中位數(shù) GEH 為 1.01，且在所有方法中方差最低。采用湯普森采樣的 Multi-TuRBO 以 1.06 的中位數(shù)排名第二，隨后是采用湯普森采樣的 MG-TuRBO，為 1.08。對于 MG-TuRBO，湯普森采樣也以 4% 的優(yōu)勢優(yōu)于自適應(yīng)策略，且一致性相當(dāng)。自適應(yīng)變體顯示出始終較高的中位數(shù)和較寬的分布。BO 在 BOMs 中具有最高的中位數(shù)，分別為 1.29（自適應(yīng)）和 1.38（湯普森），具有更寬的變異性，但所有運(yùn)行仍低于 1.7。

B. 84 維校準(zhǔn)優(yōu)化

84D Nashville 走廊是一個(gè)比 14D Chattanooga 案例困難得多的校準(zhǔn)問題。由于搜索空間更大，BOMs 在引導(dǎo)優(yōu)化開始之前使用 200 個(gè)初始樣本。圖 5 在優(yōu)化階段（評(píng)估 201+）比較了采用湯普森采樣（Thompson Sampling）和自適應(yīng)（Adaptive）采集的方法，以一次具有代表性的單次運(yùn)行為例。在這個(gè)更高維度的設(shè)置中，方法的相對排名發(fā)生了明顯變化。采用自適應(yīng)采集的 MG-TuRBO 表現(xiàn)最佳，在評(píng)估 1500 時(shí)達(dá)到約 3.1 的最終 GEH。

采用自適應(yīng)采集的 TuRBO 排名第二，約為 3.2，而采用湯普森采樣的 TuRBO 達(dá)到 3.6。Multi-TuRBO 在兩種采集策略下表現(xiàn)中等，在評(píng)估 1500 時(shí)達(dá)到約 3.6–3.7。這些信任域方法均大幅優(yōu)于標(biāo)準(zhǔn) BO 和 GA。標(biāo)準(zhǔn) BO 在兩種采集策略下，初始化后的進(jìn)展都很有限。GA 收斂到約 4.8，在這個(gè)高維單次運(yùn)行比較中表現(xiàn)優(yōu)于標(biāo)準(zhǔn) BO——盡管兩者都遠(yuǎn)遜于信任域方法。信任域方法與非信任域方法之間巨大的性能差距，強(qiáng)調(diào)了在 84D 中局部化搜索的關(guān)鍵重要性。MG-TuRBO 從自適應(yīng)采集中獲得了最明顯的收益（3.1 對比湯普森采樣的 3.5），而 TuRBO 也偏好自適應(yīng)策略（3.2 對比 3.6）。其他方法對采集策略表現(xiàn)出很少的敏感性。這種模式表明，自適應(yīng)采集特別有利于在高維空間中采用激進(jìn)的多區(qū)域探索策略的方法。

圖 6 通過可視化所有三種信任域方法在具有代表性的 84D 運(yùn)行中使用自適應(yīng)采集的信任域行為，解釋了這些性能差異。TuRBO 有 20 次重啟，發(fā)生在信任域收縮且沒有足夠改進(jìn)之后——這表明其持續(xù)陷入局部吸引盆（local basins）。由于只有一個(gè)活躍的信任域，TuRBO 在重啟前將許多評(píng)估用于局部優(yōu)化。這證明在廣闊的 84D 搜索空間中是低效的。Multi-TuRBO 通過并行維護(hù)多個(gè)信任域，將重啟頻率顯著降低至 4 次主要重啟事件。活躍區(qū)域（以不同顏色顯示）同時(shí)探索空間的不同部分，與 TuRBO 的順序方法相比提高了搜索效率。然而，如果初始區(qū)域放置次優(yōu)，Multi-TuRBO 仍可能將大量預(yù)算用于優(yōu)化中等有希望的區(qū)域。MG-TuRBO 的重啟次數(shù)最多（21 次）。這些并不表示失敗，而是發(fā)揮著根本性的戰(zhàn)略作用。MG-TuRBO 有意為每個(gè)局部區(qū)域分配較小的預(yù)算，在提取足夠的梯度信息后主動(dòng)轉(zhuǎn)移。然后，它使用更新的全局代理模型來選擇下一個(gè)有希望的區(qū)域進(jìn)行局部優(yōu)化。這種系統(tǒng)的快速循環(huán)允許 MG-TuRBO 在 84D 空間中采樣更多的吸引盆，而不是過度承諾于任何單一區(qū)域，最終實(shí)現(xiàn)了最佳性能。

總體而言，84D 的結(jié)果與 14D 案例有根本的不同。在 14D 中，使用 TuRBO（湯普森采樣）的聚焦單區(qū)域搜索表現(xiàn)最佳。在 84D 中，使用 MG-TuRBO（自適應(yīng)策略）的更廣泛的多吸引盆探索取得了優(yōu)越的性能，表明維度縮放從根本上改變了最優(yōu)搜索策略。

V. 結(jié)論

我們在兩個(gè)真實(shí)問題上比較了用于交通仿真校準(zhǔn)的優(yōu)化方法：14D Chattanooga 網(wǎng)絡(luò)和 84D Nashville 網(wǎng)絡(luò)。結(jié)果表明，算法性能取決于問題維度。在 14D 中，采用湯普森采樣的 TuRBO 表現(xiàn)最佳，取得了最低且最一致的 GEH 值。在這種較低維度的設(shè)定下，聚焦的單一信任域已足夠，而更復(fù)雜的多區(qū)域策略帶來的收益有限。在 84D 中，采用自適應(yīng)采集策略的 MG-TuRBO 表現(xiàn)最佳，Multi-TuRBO 也展現(xiàn)出強(qiáng)勁的性能。在這種更高維度的設(shè)定下，跨多個(gè)區(qū)域的更廣泛探索變得更為重要，而在相同預(yù)算下，單區(qū)域 TuRBO、標(biāo)準(zhǔn) BO 和 GA 的效果則相對較弱。總體而言，結(jié)果表明低維問題可通過 TuRBO 等較簡單的單區(qū)域方法得到良好處理，而高維問題則受益于更廣泛的多區(qū)域搜索策略，其中 MG-TuRBO 展現(xiàn)出最強(qiáng)的性能。

原文鏈接：https://arxiv.org/pdf/2604.08569