面向高維優化的記憶引導信任域貝葉斯優化（MG-TuRBO）

面向高維優化的記憶引導信任域貝葉斯優化（MG-TuRBO）

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

https://arxiv.org/pdf/2604.08569

摘要

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

I. 引言

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

交通微觀仿真校準之所以困難，是因為其目標函數具有隨機性、非凸性，且評估成本高昂。在實踐中，校準通常采用適應度指標，通過其與觀測交通流量及速度的吻合程度來進行評估[2]。既往研究與實踐指南已為主流仿真平臺確立了校準工作流程，同時也表明：隨著網絡規模、擁堵程度及參數維度的增加，校準難度亦隨之上升[3]。有限的仿真預算使得搜索效率成為一項關鍵挑戰。

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

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

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

II. 作為黑盒優化問題的交通仿真校準

A. 問題表述

我們將交通仿真校準表述為一個計算代價高昂的黑盒優化問題。校準質量是通過使用 Geoffrey E. Havers (GEH) 統計量比較仿真交通流量與觀測流量來評估的，這是一種廣泛使用的交通模型校準指標 [11]。令表示觀測計數，表示在仿真器實現 ω （例如給定的隨機種子）下，對應于候選參數向量 x 的仿真計數。對于每個目標，GEH 的計算公式如下：

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

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

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

即在該吸引盆中發現的最佳目標函數值，以及吸引盆規模 n k = ∣ B k ∣ ，用于統計當前有多少個已評估點屬于吸引盆 k 。

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

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

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

E. 采集策略

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

F. 實驗設計概覽

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

IV. 結果

A. 14 維校準優化

圖 2 展示了 14D 網絡優化階段的收斂情況，報告為 10 次運行中的中位數最佳觀測 GEH 及四分位距（IQR）。共享的初始化階段（評估 1-20）被排除，以突出引導優化期間的差異。GA 顯示出初始下降，在評估 40 時達到約 3.4，然后繼續緩慢改進，在評估 50-60 時達到接近 3.1-3.2 的平臺期，此后改進極小。所有 BOMs 均大幅優于 GA。標準 BO 穩步提升但仍然受限，在評估 100 時達到 1.28（自適應）和 1.37（湯普森）的中位數 GEH。

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

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

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

B. 84 維校準優化

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

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

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

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

V. 結論

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

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