選自chaitjo's blog
作者：Chaitanya K. Joshi , Rishabh Anand
機器之心編譯
機器之心編輯部
最近，針對旅行推銷員等組合優化問題開發神經網絡驅動的求解器引起了學術界的極大興趣。這篇博文介紹了一個神經組合優化步驟，将幾個最近提出的模型架構和學習範式統一到一個架構中。透過這一系列步驟，作者分析了深度學習在路由問題方面的最新進展，并提供了新的方向來啟發今後的研究，以創造實際的價值。
組合優化問題的背景
組合優化是數學和計算機科學交叉領域的一個實用領域，旨在解決 NP 難的限制優化問題。NP 難問題的挑戰性在于詳盡地尋找 NP 難問題的解超出了現代計算機的限制，是以不可能在大規模問題上最優地解決 NP 難問題。
我們為什麼要關心這個問題？因為針對流行問題的穩健可靠的近似算法具有巨大的實際應用價值，并且也是現代産業的支柱。例如，旅行推銷員問題 (TSP) 是最流行的組合優化問題 (COP)，從物流和排程到基因組學和系統生物學等多種應用中都有出現。
旅行推銷員問題是如此著名，或者說難以攻克，甚至有專門的 xkcd 漫畫！
TSP 和路由問題
TSP 也是路由問題的經典示例——路由問題是一類 COP，它需要一系列節點（例如城市）或邊（例如城市之間的道路）以特定順序周遊，同時需要滿足一組限制或優化一組變量。TSP 要求按照確定所有節點都被通路一次的順序周遊一組邊。從算法的角度來看，我們的銷售人員的最佳「旅行」路線是一系列標明的邊，這些邊滿足了哈密頓循環中的最小距離或時間，請參見圖 1 中的說明。
圖 1：TSP 提出以下問題：給定一個城市清單和每對城市之間的距離，銷售人員通路每個城市并傳回出發城市的最短路線是什麼？（來源：MathGifs）
在現實世界和實際場景中，路由問題或車輛路由問題 (VRP) 可能會涉及超出普通的 TSP 的挑戰性限制。例如，帶有時間視窗的 TSP (TSPTW) 将「時間視窗」限制添加到 TSP 圖中的節點。這意味着某些節點隻能在固定的時間間隔内通路。另一種變體是，容量車輛路線問題 (CVRP) ，旨在為通路一組客戶（即城市）的車隊（即多個銷售人員）找到最佳路線，每輛車都具有最大承載能力。
圖 2：TSP 和相關的車輛路徑問題類别。VRP 的限制的條件和 TSP 的不同，該圖呈現了相對充分研究的那些限制條件。在真實世界中可能存在具有更複雜和非标準限制的類 VRP 問題！（來源：改編自 Benslimane 和 Benadada，2014 年）
用深度學習解決路由問題
為路由問題開發可靠的算法和求解器需要大量的專家直覺和多年的反複試驗。例如，線性規劃、切割平面算法和分支定界問題中最先進的 TSP 求解器 Concorde 耗費了人們 50 多年的時間才得到；這是一段關于其曆史的鼓舞人心的視訊（https://www.youtube.com/watch?v=q8nQTNvCrjE）。Concorde 可以找到多達數萬個節點的最優解，但執行時間極長。正如讀者所想象的那樣，為複雜的 VRP 設計算法會更具挑戰性，也更耗時，尤其是在現實世界的限制條件下，例如混合容量或時間視窗問題。
于是，機器學習社群開始關注以下問題：
我們可以使用深度學習來讓解決 COP 所需的專家直覺流程自動化，甚至增強專家直覺嗎？
有關更深入的動機，請參閱 Mila 的這項精妙調查：https://arxiv.org/abs/1811.06128
神經組合優化
如果把 COP 問題比作一根釘子，那麼神經組合優化可以說是一種嘗試使用深度學習方法來解決問題的錘子。神經網絡經過訓練之後，可以直接從問題執行個體本身中學習來産生 COP 的近似解。這一系列研究始于 Google Brain 的開創性 Seq2seq 指針網絡和使用強化學習來實作神經組合優化的論文。如今，圖神經網絡通常是深度學習驅動的求解器的核心架構選擇，因為它們解決了這些問題相關的圖結構。
神經組合優化旨在通過以下方式改進傳統的 COP 求解器：
非手工的啟發式方法。神經網絡不需要應用專家手動設計啟發式和規則，而是通過模仿最佳求解器或通過強化學習來學習這些啟發式和規則（下一節中展示了一個示例）。
GPU 快速推理。對于問題規模較大的情況，傳統求解器的執行時間通常很長，例如 Concorde 用了 7.5 個月的時間解決了擁有 109,399 個節點的最大 TSP。另一方面，一旦用來近似求解 COP 的神經網絡訓練完成，那麼使用的時候就具有顯着有利的時間複雜度，并且可以通過 GPU 進行并行化。這使得它們非常适合解決實時決策問題，尤其是路由問題。
應對新穎且研究不足的 COP。神經組合優化可以顯着加快針對具有深奧限制的新問題或未研究問題的特定 COP 求解器的開發進度。此類問題經常出現在科學級的發現或計算機體系結構中，一個令人興奮的成功例子是谷歌的晶片設計系統，它将為下一代 TPU 提供動力。你沒看錯——下一個運作神經網絡的 TPU 晶片是由神經網絡設計的！
神經組合優化步驟
使用 TSP 作為典型示例，我們現在提出一個通用的神經組合優化步驟，可用于表征現代深度學習驅動的幾個路由問題的方法。
最先進的 TSP 方法将城市的原始坐标作為輸入，并利用 GNN 或 Transformer 結合經典圖搜尋算法來建設性地建構近似解。其架構可以大緻分為：（1）自回歸模型，以逐漸的方式建構解集；(2) 非自回歸模型，一次性産生所有解。可以通過監督學習或通過強化學習最小化 TSP 周遊的長度來訓練模型以模仿最佳求解器。
圖 3：神經組合優化步驟（來源：Joshi 等人，2021）。
Joshi 等人在 2021 年提出的 5 階段步驟将突出的模型架構和學習範式整合到一個統一的架構中。這個步驟将使我們能夠剖析和分析深度學習在路由問題方面的最新發展，并為激勵未來的研究提供新的方向。
第一步通過圖定義問題
圖 4：問題定義：TSP 是通過城市 / 節點的全連接配接圖定義的，此圖可以進一步稀疏化。
TSP 是通過一個全連接配接圖定義的，其中節點對應于城市，邊表示它們之間的道路。該圖可以通過啟發式算法（例如 k-nn 最近鄰算法）進行稀疏化。這使模型能夠擴充到所有節點的成對計算都難以處理的大型執行個體中 [Khalil 等人，2017 年]，或者通過減少搜尋空間來更快地學習 [Joshi 等人，2019 年]。
第二步：擷取圖節點和邊的隐空間嵌入
圖 5：圖嵌入：每個圖節點的嵌入是使用圖神經網絡編碼器獲得的，該編碼器通過遞歸聚合來自每個節點的鄰居的特征來建構局部結構特征。
GNN 或 Transformer 編碼器将 TSP 圖中的每個節點和邊，或者在兩者中選擇一個，作為輸入來計算隐空間表示或嵌入特征。在每一層當中，節點從其鄰居那裡收集特征，再通過遞歸消息傳遞來表示局部圖結構。堆疊 L 層後，網絡就能從每個節點的 L 跳鄰域中建構節點的特征。
Transformers [Deudon et al., 2018, Kool et al., 2019] 和 Gated Graph ConvNets [Joshi et al., 2019] 等各向異性和基于注意力的 GNN 已成為編碼路由問題的預設選擇。鄰域聚合期間的注意力機制至關重要，因為它允許每個節點根據其對解決手頭任務的相對重要性來權衡其鄰居節點。
重要的是，Transformer 編碼器可以看作是全連接配接圖上的注意力 GNN，即圖注意力網絡 (GAT)。請參閱此部落格文章以獲得直覺的解釋。
第三、四步：将嵌入轉換為離散解
圖 5：解碼和搜尋：為每個節點或每條邊配置設定屬于解集的機率（這裡，MLP 對每條邊進行預測以獲得邊機率的「熱力圖」），然後轉換為離散決策中經典的圖搜尋技術，例如貪心搜尋或束搜尋。
一旦圖的節點和邊被編碼為隐空間表示，我們必須将它們解碼為離散的 TSP 解決方法。具體來說，可以通過兩步過程完成：首先，将機率配置設定給每個節點或每條邊來将節點或邊添加到解集當中，無論是互相獨立地（即非自回歸解碼）或是通過圖周遊有條件地（即自回歸解碼）。接下來，通過經典的圖搜尋技術（例如由機率預測引導的貪心搜尋或束搜尋）将預測機率轉換為離散決策（稍後我們将在讨論近期趨勢和未來方向時，讨論更多關于圖搜尋的内容）。
解碼器的選擇需要在資料效率和實作效率之間權衡：自回歸解碼器 [Kool et al., 2019] 将 TSP 轉換為 Seq2Seq 模型， 或基于一組無序城市節點的有序旅遊路線的語言翻譯任務。他們通過每次選擇一個節點來明确地模拟路由問題的順序歸納偏差。另一方面，非自回歸解碼器 [Joshi et al., 2019] 将 TSP 視為生成邊緣機率熱力圖的任務。NAR 方法明顯更快，更适合實時推理，因為它是一次性而不是逐漸地生成預測。然而，NAR 方法忽略了 TSP 的順序性，與 AR 解碼相比，訓練效率可能較低 [Joshi 等人，2021]。
第五步：模型訓練
最後，整個編碼器 - 解碼器模型以端到端的方式進行訓練，就像用于計算機視覺或自然語言處理的深度學習模型一樣。在最簡單的情況下，可以通過模仿最優求解器（即通過監督學習）來訓練模型以産生接近最優的解。對于 TSP，Concrode 求解器用于為數百萬個随機執行個體生成最佳旅遊路線的有标簽訓練資料集。帶有 AR 解碼器的模型通過強制教學（teacher-forcing ）模式進行訓練，來輸出節點的最佳旅行序列 [Vinyals et al., 2015]，而帶有 NAR 解碼器的模型經過訓練後，可以從未周遊的邊集中識别出在旅行期間周遊的邊 [Joshi et al., 2019]。
然而，為監督學習建立标記資料集是一個昂貴且耗時的過程。特别是對于大規模問題執行個體，最佳求解器在準确性上的保證可能不複存在，這會導緻用于監督訓練的解決方案不精确。從實踐和理論的角度來看，這遠非是理想的方式 [Yehuda et al., 2020]。
對于未充分研究的問題來說，在缺乏标準解決方案的情況下，強化學習通常是一種優雅的替代方案。由于路由問題通常需要順序決策以最小化特定于問題的成本函數（例如 TSP 的旅行長度），它們可以優雅地投入 RL 架構中，該架構訓練智能體以最大化獎勵函數（損失函數的負值） . 帶有 AR 解碼器的模型可以通過标準政策梯度算法 [Kool et al., 2019] 或 Q 學習 [Khalil et al., 2017] 進行訓練。
各階段中的成果簡介
我們可以通過 5 階段步驟來描述 TSP 深度學習中的傑出成果。回想一下，步驟包括：（1）問題定義（2）圖嵌入（3）解碼（4）解搜尋（5）政策學習。下表從 Oriol Vinyals 及其合作者發表的指針網絡論文開始介紹，紅色突出表示該論文具有主要創新和貢獻。
未來工作的最新進展和途徑
有了統一的 5 階段步驟，我們接下來重點介紹深度學習路由問題的一些最新進展和趨勢。同時還将提供一些未來的研究方向，重點探讨如何提高對大規模和真實世界執行個體的泛化能力。
利用等方差和對稱性
作為最有影響力的早期作品之一，自回歸注意力模型 [Kool et al., 2019] 将 TSP 視為可以用 Seq2Seq 解決的語言翻譯問題，并将 TSP 旅行順序建構為城市排列。該公式的一個直接缺點是它沒有考慮路由問題的潛在對稱性。
圖 6：一般來說，TSP 有一個唯一的最優解 (L)。然而，在自回歸公式下，當解表示為節點序列時，存在多個最優排列 (R)。（來源：Kwon 等人，2020）
POMO: Policy Optimization with Multiple Optima [Kwon et al., 2020] 建議在建設性自回歸公式中利用起始城市的不變性。他們訓練了與之前相同的注意力模型，但不同之處在于他們使用了一種新的強化學習算法（上述步驟中的第 5 步），該算法利用了多個最優旅行排列。
圖 7：在旋轉、反射和轉換後，城市坐标的歐幾裡得對稱群的 TSP 解保持不變。将這些對稱性納入模型可能是解決大規模 TSP 的原則性方法。
同樣地，Ouyang 等人在 2021 年對注意力模型進行了更新，考慮了輸入城市坐标的旋轉、反射和平移（即歐幾裡得對稱群）的不變性。他們提出了一種自回歸方法，通過同時在問題定義階段（步驟 1）執行資料增強并在圖形編碼（步驟 2）期間使用相對坐标來確定不變性。他們在 TSPLib 資料集上進行的從随機執行個體到現實世界的零樣本泛化實驗顯示他們的模型具有很好的效果。
未來的工作可能會在架構設計上遵循幾何深度學習 (GDL) 藍圖。GDL 告訴我們要明确考慮資料或問題的對稱性和歸納偏差，并将其結合起來。由于路由問題需要被嵌入在歐幾裡得坐标中，以及路由是循環的，是以将這些限制直接納入模型架構或學習範式可能是一種原則性方法，可以提高對比訓練期間更大的大規模執行個體的泛化能力。
改進後的圖搜尋算法
另一個有影響力的研究方向是一次性非自回歸圖卷積網絡方法 [Joshi et al., 2019]。最近的幾篇論文提出保留相同的門控 GCN 編碼器（步驟 2），同時用更強大和靈活的圖搜尋算法替換束搜尋元件（步驟 4），例如動态規劃 [Kool et al., 2021] 或蒙特卡洛樹搜尋 (MCTS) [Fu et al., 2020]。
圖 8：門控 GCN 編碼器 [Joshi 等人，2019 年] 可用于為 TSP、CVRP 和 TSPTW 生成邊預測「熱力圖」（透明紅色）。這些可以由 DP 或 MCTS 進一步處理以輸出路由（純色）。GCN 從本質上減少了複雜搜尋算法的解搜尋空間，複雜搜尋算法在搜尋所有可能的路線時可能難以處理。（資料來源：Kool 等人，2021 年）
Fu 等人提出的 GCN + MCTS 架構有一種非常有趣的方法，該方法可以在很小的 TSP 問題上有效地訓練模型，并以零樣本的方式（類似 Joshi 等人最初探究的 GCN + 束搜尋方式）成功地将學習的政策轉移到更大的圖上。他們通過更新問題定義（步驟 1）來確定 GCN 編碼器的預測結果可以在 TSP 從小到大變化時仍然具有泛化能力：規模較大的問題執行個體被表示為許多較小的子圖，這些子圖的大小與 GCN 的訓練圖相同，然後在執行 MCTS 之前合并 GCN 的邊預測結果。
圖 9：GCN + MCTS 架構 [Fu et al., 2020] 将大型 TSP 問題表示為一組與用于訓練的 GCN 的圖大小相同的規模較小的子圖。将 GCN 預測得到的子圖的邊熱力圖合并在一起，可以獲得原圖的熱圖。這種分而治之的方法確定了 GCN 的嵌入和預測能夠很好地從較小的執行個體推廣到較大的執行個體。（來源：Fu et al., 2020）
這種分而治之的政策最初由 Nowak 等人在 2018 年提出，以確定 GNN 的嵌入和預測能夠很好地泛化從較小到較大的 TSP 執行個體（最多 10,000 個節點）。将 GNN、分而治之和搜尋政策融合在一起，來處理多達 3000 個節點的大規模 CVRP 問題同樣充滿無限可能。[Li et al., 2021]。
總體而言，這一系列的工作表明，模型的神經元和符号 / 搜尋元件的設計之間的更強耦合對于分布外泛化至關重要 [Lamb 等人，2020]。然而，同樣值得注意的是，在 GPU 上實作圖搜尋的設計高度定制化和并行化，可能對每個新問題都是一種挑戰。
學習改進次優解
最近，從 Chen 等人在 2019 的工作和 Wu 等人在 2021 年的工作開始，許多論文探索了建設性的 AR 和 NAR 解的替代方案，包括疊代改進（次優）解學習或局部搜尋學習。其他著名論文包括 Cappart et al., 2021, da Costa et al., 2020, Ma et al., 2021, Xin et al., 2021 和 Hudson et al., 2021.。
圖 10：通過在局部搜尋算法中的指導決策來學習改進次優 TSP 解的架構。(a) 原始的 Transformer 編碼器 - 解碼器架構 [Wu et al., 2021]，該方法使用正弦位置編碼來表示目前的次優旅行排列；(b) Ma et al., 2021 通過在對稱性問題上做了進一步的更新：具有可學習的位置編碼的雙端 Transformer 編碼器 - 解碼器，能夠捕捉 TSP 旅行的循環性質；(c) 正弦曲線與周期性位置編碼的可視化。
在所有這些工作中，由于深度學習用于指導經典局部搜尋算法中的決策（這些算法被設計為無論問題規模如何都能工作），是以與建設性方法相比，這種方法隐含地導緻對更大問題執行個體的更好的零樣本泛化。實際來說，這是一個非常理想的屬性，因為在非常大或真實世界的 TSP 執行個體上進行訓練可能很棘手。
值得注意的是，NeuroLKH [Xin et al., 2021] 使用通過 GNN 生成的邊機率熱力圖來改進經典的 Lin-Kernighan-Helsgaun 算法，并展示了對具有 5000 個節點的 TSP 以及跨對 TSPLib 資料集中，執行個體的強大零樣本泛化能力。
這項工成果的限制之一是需要事先手工設計的局部搜尋算法，對于新的或未充分研究的問題可能是會缺少的。另一方面，通過在解碼和搜尋過程中實施限制，建設性的方法可以說更容易适應新問題。
促進泛化的學習範式
未來的工作可以着眼于新的學習範式（步驟 5），這些範式明确關注監督和強化學習之外的泛化，例如 Hottung et al., 2020 探索了自動編碼器目标，以學習路由問題解的連續空間，而 Geisler et al., 2021 訓練神經求解器，使其對對抗性擾動具有魯棒性。
目前，大多數論文都建議在非常小的随機 TSP 上有效地訓練模型，然後以零樣本的方式将學習到的政策轉移到更大的圖和真實世界的執行個體中。合乎邏輯的下一步是在少數特定問題執行個體上微調模型。Hottung et al., 2021 在 2021 年邁出了第一步，建議通過主動搜尋為每個特定問題執行個體微調模型參數的子集。在未來的工作中，将微調作為元學習問題進行探索可能會很有趣，元學習問題的目标是訓練模型參數，用于快速适應新的資料分布和問題。
另一個有趣的可以探索的方向是通過對流行的路由問題（如 TSP 和 CVPR）進行多任務預訓練，然後針對特定問題的微調來解決具有挑戰性限制的未充分研究的路由問題。與自然語言進行中作為預訓練目标的語言模組化類似，路由預訓練的目标是學習通常來說會有用的潛在表示，這些表示可以很好地轉移到新的路由問題上。
改進後的評估協定
除了算法創新之外，社群一再呼籲推出更現實的評估協定，這可以推動現實世界路由問題的進步和工業界的落實 [Francois et al., 2019, Yehuda et al., 2020]。最近， Accorsi et al., 2021 為實驗設計和與經典運籌學 (OR) 技術的比較提供了一套權威指南。他們希望對标準化基準進行公平和嚴格的比較将成為将深度學習技術內建到工業路由求解器中的第一步。
總的來說，令人鼓舞的是，近期的論文不僅顯示了對微小的随機 TSP 執行個體的輕微性能提升，而且還采用了 TSPLib 和 CVPRLib 等真實世界的基準測試資料集。此類路由問題集合包含來自全球城市和道路網絡的圖表及其精确解決方案，并已成為 OR 社群中新求解器的标準測試平台。
同時，我們必須在其他論文都在使用的前 n 個 TSPLib 或 CVPRLib 執行個體上不「過拟合」。是以，更好的合成資料集與公平的基準測試進展密切相關，例如 Queiroga et al., 2021 (https://openreview.net/forum?id=yHiMXKN6nTl) 最近提出了一個新的合成 了 10,000 個 CVPR 測試執行個體的庫。
圖 11：關注 ML4CO 等社群競賽能有效地跟蹤研究進展。（來源：ML4CO 網站）。對新構造的現實世界資料集進行定期競賽，例如 NeurIPS 2021 的 ML4CO 競賽和 IJCAI 2021 的 AI4TSP，也是跟蹤深度學習和路由問題交叉點進展的一個有效手段。
我們強烈呼籲能夠在 YouTube 上擷取來自 ML4CO、NeurIPS 2021 的有價值的小組讨論和演講。
總結
這篇博文介紹了一系列神經組合優化步驟，這些步驟将最近關于深度學習的論文統一到一個單一的架構中。然後，通過此架構的視角，我們分析和剖析最近的研究進展，并預測未來研究的方向。
最後一點想說的是，神經組合優化的更深刻的研究動機可能并不是為了在經過充分研究的路由問題上勝過經典方法。神經網絡可以用作解決以前未遇到的 NP 難問題的通用工具，尤其是那些對于設計啟發式算法而言并非微不足道的問題。我們贊歎神經組合優化最近在設計計算機晶片、優化通信網絡和基因組重建方面的應用，并期待未來有更多有價值的應用！