用深度學(xué)習解決旅行推銷(xiāo)員問(wèn)題，研究者走到哪一步了？

最近，針對旅行推銷(xiāo)員等組合優(yōu)化問(wèn)題開(kāi)發(fā)神經(jīng)網(wǎng)絡(luò )驅動(dòng)的求解器引起了學(xué)術(shù)界的極大興趣。這篇博文介紹了一個(gè)神經(jīng)組合優(yōu)化步驟，將幾個(gè)最近提出的模型架構和學(xué)習范式統一到一個(gè)框架中。透過(guò)這一系列步驟，作者分析了深度學(xué)習在路由問(wèn)題方面的最新進(jìn)展，并提供了新的方向來(lái)啟發(fā)今后的研究，以創(chuàng )造實(shí)際的價(jià)值。

組合優(yōu)化問(wèn)題的背景
組合優(yōu)化是數學(xué)和計算機科學(xué)交叉領(lǐng)域的一個(gè)實(shí)用領(lǐng)域，旨在解決 NP 難的約束優(yōu)化問(wèn)題。NP 難問(wèn)題的挑戰性在于詳盡地尋找 NP 難問(wèn)題的解超出了現代計算機的限制，因此不可能在大規模問(wèn)題上最優(yōu)地解決 NP 難問(wèn)題。
我們?yōu)槭裁匆P(guān)心這個(gè)問(wèn)題？因為針對流行問(wèn)題的穩健可靠的近似算法具有巨大的實(shí)際應用價(jià)值，并且也是現代產(chǎn)業(yè)的支柱。例如，旅行推銷(xiāo)員問(wèn)題 (TSP) 是最流行的組合優(yōu)化問(wèn)題 (COP)，從物流和調度到基因組學(xué)和系統生物學(xué)等多種應用中都有出現。
旅行推銷(xiāo)員問(wèn)題是如此著(zhù)名，或者說(shuō)難以攻克，甚至有專(zhuān)門(mén)的 xkcd 漫畫(huà)！

TSP 和路由問(wèn)題
TSP 也是路由問(wèn)題的經(jīng)典示例——路由問(wèn)題是一類(lèi) COP，它需要一系列節點(diǎn)（例如城市）或邊（例如城市之間的道路）以特定順序遍歷，同時(shí)需要滿(mǎn)足一組約束或優(yōu)化一組變量。TSP 要求按照確保所有節點(diǎn)都被訪(fǎng)問(wèn)一次的順序遍歷一組邊。從算法的角度來(lái)看，我們的銷(xiāo)售人員的最佳「旅行」路線(xiàn)是一系列選定的邊，這些邊滿(mǎn)足了哈密頓循環(huán)中的最小距離或時(shí)間，請參見(jiàn)圖 1 中的說(shuō)明。

圖 1：TSP 提出以下問(wèn)題：給定一個(gè)城市列表和每對城市之間的距離，銷(xiāo)售人員訪(fǎng)問(wèn)每個(gè)城市并返回出發(fā)城市的最短路線(xiàn)是什么？（來(lái)源：MathGifs）
在現實(shí)世界和實(shí)際場(chǎng)景中，路由問(wèn)題或車(chē)輛路由問(wèn)題 (VRP) 可能會(huì )涉及超出普通的 TSP 的挑戰性約束。例如，帶有時(shí)間窗口的 TSP (TSPTW) 將「時(shí)間窗口」約束添加到 TSP 圖中的節點(diǎn)。這意味著(zhù)某些節點(diǎn)只能在固定的時(shí)間間隔內訪(fǎng)問(wèn)。另一種變體是，容量車(chē)輛路線(xiàn)問(wèn)題 (CVRP) ，旨在為訪(fǎng)問(wèn)一組客戶(hù)（即城市）的車(chē)隊（即多個(gè)銷(xiāo)售人員）找到最佳路線(xiàn)，每輛車(chē)都具有最大承載能力。
圖 2：TSP 和相關(guān)的車(chē)輛路徑問(wèn)題類(lèi)別。VRP 的約束的條件和 TSP 的不同，該圖呈現了相對充分研究的那些約束條件。在真實(shí)世界中可能存在具有更復雜和非標準約束的類(lèi) VRP 問(wèn)題?。▉?lái)源：改編自 Benslimane 和 Benadada，2014 年）
用深度學(xué)習解決路由問(wèn)題
為路由問(wèn)題開(kāi)發(fā)可靠的算法和求解器需要大量的專(zhuān)家直覺(jué)和多年的反復試驗。例如，線(xiàn)性規劃、切割平面算法和分支定界問(wèn)題中最先進(jìn)的 TSP 求解器 Concorde 耗費了人們 50 多年的時(shí)間才得到；這是一段關(guān)于其歷史的鼓舞人心的視頻（https://www.youtube.com/watch?v=q8nQTNvCrjE）。Concorde 可以找到多達數萬(wàn)個(gè)節點(diǎn)的最優(yōu)解，但執行時(shí)間極長(cháng)。正如讀者所想象的那樣，為復雜的 VRP 設計算法會(huì )更具挑戰性，也更耗時(shí)，尤其是在現實(shí)世界的限制條件下，例如混合容量或時(shí)間窗口問(wèn)題。
于是，機器學(xué)習社區開(kāi)始關(guān)注以下問(wèn)題：
我們可以使用深度學(xué)習來(lái)讓解決 COP 所需的專(zhuān)家直覺(jué)流程自動(dòng)化，甚至增強專(zhuān)家直覺(jué)嗎？
有關(guān)更深入的動(dòng)機，請參閱 Mila 的這項精妙調查：https://arxiv.org/abs/1811.06128
神經(jīng)組合優(yōu)化
如果把 COP 問(wèn)題比作一根釘子，那么神經(jīng)組合優(yōu)化可以說(shuō)是一種嘗試使用深度學(xué)習方法來(lái)解決問(wèn)題的錘子。神經(jīng)網(wǎng)絡(luò )經(jīng)過(guò)訓練之后，可以直接從問(wèn)題實(shí)例本身中學(xué)習來(lái)產(chǎn)生 COP 的近似解。這一系列研究始于 Google Brain 的開(kāi)創(chuàng )性 Seq2seq 指針網(wǎng)絡(luò )和使用強化學(xué)習來(lái)實(shí)現神經(jīng)組合優(yōu)化的論文。如今，圖神經(jīng)網(wǎng)絡(luò )通常是深度學(xué)習驅動(dòng)的求解器的核心架構選擇，因為它們解決了這些問(wèn)題相關(guān)的圖結構。
神經(jīng)組合優(yōu)化旨在通過(guò)以下方式改進(jìn)傳統的 COP 求解器：

• 非手工的啟發(fā)式方法。神經(jīng)網(wǎng)絡(luò )不需要應用專(zhuān)家手動(dòng)設計啟發(fā)式和規則，而是通過(guò)模仿最佳求解器或通過(guò)強化學(xué)習來(lái)學(xué)習這些啟發(fā)式和規則（下一節中展示了一個(gè)示例）。

• GPU 快速推理。對于問(wèn)題規模較大的情況，傳統求解器的執行時(shí)間通常很長(cháng)，例如 Concorde 用了 7.5 個(gè)月的時(shí)間解決了擁有 109,399 個(gè)節點(diǎn)的最大 TSP。另一方面，一旦用來(lái)近似求解 COP 的神經(jīng)網(wǎng)絡(luò )訓練完成，那么使用的時(shí)候就具有顯著(zhù)有利的時(shí)間復雜度，并且可以通過(guò) GPU 進(jìn)行并行化。這使得它們非常適合解決實(shí)時(shí)決策問(wèn)題，尤其是路由問(wèn)題。

• 應對新穎且研究不足的 COP。神經(jīng)組合優(yōu)化可以顯著(zhù)加快針對具有深奧約束的新問(wèn)題或未研究問(wèn)題的特定 COP 求解器的開(kāi)發(fā)進(jìn)度。此類(lèi)問(wèn)題經(jīng)常出現在科學(xué)級的發(fā)現或計算機體系結構中，一個(gè)令人興奮的成功例子是谷歌的芯片設計系統，它將為下一代 TPU 提供動(dòng)力。你沒(méi)看錯——下一個(gè)運行神經(jīng)網(wǎng)絡(luò )的 TPU 芯片是由神經(jīng)網(wǎng)絡(luò )設計的！

神經(jīng)組合優(yōu)化步驟
使用 TSP 作為典型示例，我們現在提出一個(gè)通用的神經(jīng)組合優(yōu)化步驟，可用于表征現代深度學(xué)習驅動(dòng)的幾個(gè)路由問(wèn)題的方法。
最先進(jìn)的 TSP 方法將城市的原始坐標作為輸入，并利用 GNN 或 Transformer 結合經(jīng)典圖搜索算法來(lái)建設性地構建近似解。其架構可以大致分為：（1）自回歸模型，以逐步的方式構建解集；(2) 非自回歸模型，一次性產(chǎn)生所有解?？梢酝ㄟ^(guò)監督學(xué)習或通過(guò)強化學(xué)習最小化 TSP 遍歷的長(cháng)度來(lái)訓練模型以模仿最佳求解器。
圖 3：神經(jīng)組合優(yōu)化步驟（來(lái)源：Joshi 等人，2021）。
Joshi 等人在 2021 年提出的 5 階段步驟將突出的模型架構和學(xué)習范式整合到一個(gè)統一的框架中。這個(gè)步驟將使我們能夠剖析和分析深度學(xué)習在路由問(wèn)題方面的最新發(fā)展，并為激勵未來(lái)的研究提供新的方向。
第一步通過(guò)圖定義問(wèn)題
圖 4：?jiǎn)?wèn)題定義：TSP 是通過(guò)城市 / 節點(diǎn)的全連接圖定義的，此圖可以進(jìn)一步稀疏化。
TSP 是通過(guò)一個(gè)全連接圖定義的，其中節點(diǎn)對應于城市，邊表示它們之間的道路。該圖可以通過(guò)啟發(fā)式算法（例如 k-nn 最近鄰算法）進(jìn)行稀疏化。這使模型能夠擴展到所有節點(diǎn)的成對計算都難以處理的大型實(shí)例中 [Khalil 等人，2017 年]，或者通過(guò)減少搜索空間來(lái)更快地學(xué)習 [Joshi 等人，2019 年]。
第二步：獲取圖節點(diǎn)和邊的隱空間嵌入
圖 5：圖嵌入：每個(gè)圖節點(diǎn)的嵌入是使用圖神經(jīng)網(wǎng)絡(luò )編碼器獲得的，該編碼器通過(guò)遞歸聚合來(lái)自每個(gè)節點(diǎn)的鄰居的特征來(lái)構建局部結構特征。
GNN 或 Transformer 編碼器將 TSP 圖中的每個(gè)節點(diǎn)和邊，或者在兩者中選擇一個(gè)，作為輸入來(lái)計算隱空間表示或嵌入特征。在每一層當中，節點(diǎn)從其鄰居那里收集特征，再通過(guò)遞歸消息傳遞來(lái)表示局部圖結構。堆疊 L 層后，網(wǎng)絡(luò )就能從每個(gè)節點(diǎn)的 L 跳鄰域中構建節點(diǎn)的特征。
Transformers [Deudon et al., 2018, Kool et al., 2019] 和 Gated Graph ConvNets [Joshi et al., 2019] 等各向異性和基于注意力的 GNN 已成為編碼路由問(wèn)題的默認選擇。鄰域聚合期間的注意力機制至關(guān)重要，因為它允許每個(gè)節點(diǎn)根據其對解決手頭任務(wù)的相對重要性來(lái)權衡其鄰居節點(diǎn)。
重要的是，Transformer 編碼器可以看作是全連接圖上的注意力 GNN，即圖注意力網(wǎng)絡(luò ) (GAT)。請參閱此博客文章以獲得直觀(guān)的解釋。
第三、四步：將嵌入轉換為離散解
圖 5：解碼和搜索：為每個(gè)節點(diǎn)或每條邊分配屬于解集的概率（這里，MLP 對每條邊進(jìn)行預測以獲得邊概率的「熱力圖」），然后轉換為離散決策中經(jīng)典的圖搜索技術(shù)，例如貪心搜索或束搜索。
一旦圖的節點(diǎn)和邊被編碼為隱空間表示，我們必須將它們解碼為離散的 TSP 解決方法。具體來(lái)說(shuō)，可以通過(guò)兩步過(guò)程完成：首先，將概率分配給每個(gè)節點(diǎn)或每條邊來(lái)將節點(diǎn)或邊添加到解集當中，無(wú)論是相互獨立地（即非自回歸解碼）或是通過(guò)圖遍歷有條件地（即自回歸解碼）。接下來(lái)，通過(guò)經(jīng)典的圖搜索技術(shù)（例如由概率預測引導的貪心搜索或束搜索）將預測概率轉換為離散決策（稍后我們將在討論近期趨勢和未來(lái)方向時(shí)，討論更多關(guān)于圖搜索的內容）。
****的選擇需要在數據效率和實(shí)現效率之間權衡：自回歸**** [Kool et al., 2019] 將 TSP 轉換為 Seq2Seq 模型， 或基于一組無(wú)序城市節點(diǎn)的有序旅游路線(xiàn)的語(yǔ)言翻譯任務(wù)。他們通過(guò)每次選擇一個(gè)節點(diǎn)來(lái)明確地模擬路由問(wèn)題的順序歸納偏差。另一方面，非自回歸**** [Joshi et al., 2019] 將 TSP 視為生成邊緣概率熱力圖的任務(wù)。NAR 方法明顯更快，更適合實(shí)時(shí)推理，因為它是一次性而不是逐步地生成預測。然而，NAR 方法忽略了 TSP 的順序性，與 AR 解碼相比，訓練效率可能較低 [Joshi 等人，2021]。
第五步：模型訓練
最后，整個(gè)編碼器 - ****模型以端到端的方式進(jìn)行訓練，就像用于計算機視覺(jué)或自然語(yǔ)言處理的深度學(xué)習模型一樣。在最簡(jiǎn)單的情況下，可以通過(guò)模仿最優(yōu)求解器（即通過(guò)監督學(xué)習）來(lái)訓練模型以產(chǎn)生接近最優(yōu)的解。對于 TSP，Concrode 求解器用于為數百萬(wàn)個(gè)隨機實(shí)例生成最佳旅游路線(xiàn)的有標簽訓練數據集。帶有 AR ****的模型通過(guò)強制教學(xué)（teacher-forcing ）模式進(jìn)行訓練，來(lái)輸出節點(diǎn)的最佳旅行序列 [Vinyals et al., 2015]，而帶有 NAR ****的模型經(jīng)過(guò)訓練后，可以從未遍歷的邊集中識別出在旅行期間遍歷的邊 [Joshi et al., 2019]。
然而，為監督學(xué)習創(chuàng )建標記數據集是一個(gè)昂貴且耗時(shí)的過(guò)程。特別是對于大規模問(wèn)題實(shí)例，最佳求解器在準確性上的保證可能不復存在，這會(huì )導致用于監督訓練的解決方案不精確。從實(shí)踐和理論的角度來(lái)看，這遠非是理想的方式 [Yehuda et al., 2020]。
對于未充分研究的問(wèn)題來(lái)說(shuō)，在缺乏標準解決方案的情況下，強化學(xué)習通常是一種優(yōu)雅的替代方案。由于路由問(wèn)題通常需要順序決策以最小化特定于問(wèn)題的成本函數（例如 TSP 的旅行長(cháng)度），它們可以?xún)?yōu)雅地投入 RL 框架中，該框架訓練智能體以最大化獎勵函數（損失函數的負值） . 帶有 AR ****的模型可以通過(guò)標準策略梯度算法 [Kool et al., 2019] 或 Q 學(xué)習 [Khalil et al., 2017] 進(jìn)行訓練。
各階段中的成果簡(jiǎn)介
我們可以通過(guò) 5 階段步驟來(lái)描述 TSP 深度學(xué)習中的杰出成果?；叵胍幌?，步驟包括：（1）問(wèn)題定義→（2）圖嵌入→（3）解碼→（4）解搜索→（5）策略學(xué)習。下表從 Oriol Vinyals 及其合作者發(fā)表的指針網(wǎng)絡(luò )論文開(kāi)始介紹，紅色突出表示該論文具有主要創(chuàng )新和貢獻。

未來(lái)工作的最新進(jìn)展和途徑
有了統一的 5 階段步驟，我們接下來(lái)重點(diǎn)介紹深度學(xué)習路由問(wèn)題的一些最新進(jìn)展和趨勢。同時(shí)還將提供一些未來(lái)的研究方向，重點(diǎn)探討如何提高對大規模和真實(shí)世界實(shí)例的泛化能力。
利用等方差和對稱(chēng)性
作為最有影響力的早期作品之一，自回歸注意力模型 [Kool et al., 2019] 將 TSP 視為可以用 Seq2Seq 解決的語(yǔ)言翻譯問(wèn)題，并將 TSP 旅行順序構建為城市排列。該公式的一個(gè)直接缺點(diǎn)是它沒(méi)有考慮路由問(wèn)題的潛在對稱(chēng)性。
圖 6：一般來(lái)說(shuō)，TSP 有一個(gè)唯一的最優(yōu)解 (L)。然而，在自回歸公式下，當解表示為節點(diǎn)序列時(shí)，存在多個(gè)最優(yōu)排列 (R)。（來(lái)源：Kwon 等人，2020）
POMO: Policy Optimization with Multiple Optima [Kwon et al., 2020] 建議在建設性自回歸公式中利用起始城市的不變性。他們訓練了與之前相同的注意力模型，但不同之處在于他們使用了一種新的強化學(xué)習算法（上述步驟中的第 5 步），該算法利用了多個(gè)最優(yōu)旅行排列。
圖 7：在旋轉、反射和轉換后，城市坐標的歐幾里得對稱(chēng)群的 TSP 解保持不變。將這些對稱(chēng)性納入模型可能是解決大規模 TSP 的原則性方法。

同樣地，Ouyang 等人在 2021 年對注意力模型進(jìn)行了升級，考慮了輸入城市坐標的旋轉、反射和平移（即歐幾里得對稱(chēng)群）的不變性。他們提出了一種自回歸方法，通過(guò)同時(shí)在問(wèn)題定義階段（步驟 1）執行數據增強并在圖形編碼（步驟 2）期間使用相對坐標來(lái)確保不變性。他們在 TSPLib 數據集上進(jìn)行的從隨機實(shí)例到現實(shí)世界的零樣本泛化實(shí)驗顯示他們的模型具有很好的效果。
未來(lái)的工作可能會(huì )在架構設計上遵循幾何深度學(xué)習 (GDL) 藍圖。GDL 告訴我們要明確考慮數據或問(wèn)題的對稱(chēng)性和歸納偏差，并將其結合起來(lái)。由于路由問(wèn)題需要被嵌入在歐幾里得坐標中，以及路由是循環(huán)的，因此將這些約束直接納入模型架構或學(xué)習范式可能是一種原則性方法，可以提高對比訓練期間更大的大規模實(shí)例的泛化能力。
改進(jìn)后的圖搜索算法
另一個(gè)有影響力的研究方向是一次性非自回歸圖卷積網(wǎng)絡(luò )方法 [Joshi et al., 2019]。最近的幾篇論文提出保留相同的門(mén)控 GCN 編碼器（步驟 2），同時(shí)用更強大和靈活的圖搜索算法替換束搜索組件（步驟 4），例如動(dòng)態(tài)規劃 [Kool et al., 2021] 或蒙特卡洛樹(shù)搜索 (MCTS) [Fu et al., 2020]。
圖 8：門(mén)控 GCN 編碼器 [Joshi 等人，2019 年] 可用于為 TSP、CVRP 和 TSPTW 生成邊預測「熱力圖」（透明紅色）。這些可以由 DP 或 MCTS 進(jìn)一步處理以輸出路由（純色）。GCN 從本質(zhì)上減少了復雜搜索算法的解搜索空間，復雜搜索算法在搜索所有可能的路線(xiàn)時(shí)可能難以處理。（資料來(lái)源：Kool 等人，2021 年）
Fu 等人提出的 GCN + MCTS 框架有一種非常有趣的方法，該方法可以在很小的 TSP 問(wèn)題上有效地訓練模型，并以零樣本的方式（類(lèi)似 Joshi 等人最初探究的 GCN + 束搜索方式）成功地將學(xué)習的策略轉移到更大的圖上。他們通過(guò)更新問(wèn)題定義（步驟 1）來(lái)確保 GCN 編碼器的預測結果可以在 TSP 從小到大變化時(shí)仍然具有泛化能力：規模較大的問(wèn)題實(shí)例被表示為許多較小的子圖，這些子圖的大小與 GCN 的訓練圖相同，然后在執行 MCTS 之前合并 GCN 的邊預測結果。
圖 9：GCN + MCTS 框架 [Fu et al., 2020] 將大型 TSP 問(wèn)題表示為一組與用于訓練的 GCN 的圖大小相同的規模較小的子圖。將 GCN 預測得到的子圖的邊熱力圖合并在一起，可以獲得原圖的熱圖。這種分而治之的方法確保了 GCN 的嵌入和預測能夠很好地從較小的實(shí)例推廣到較大的實(shí)例。（來(lái)源：Fu et al., 2020）
這種分而治之的策略最初由 Nowak 等人在 2018 年提出，以確保 GNN 的嵌入和預測能夠很好地泛化從較小到較大的 TSP 實(shí)例（最多 10,000 個(gè)節點(diǎn)）。將 GNN、分而治之和搜索策略融合在一起，來(lái)處理多達 3000 個(gè)節點(diǎn)的大規模 CVRP 問(wèn)題同樣充滿(mǎn)無(wú)限可能。[Li et al., 2021]。
總體而言，這一系列的工作表明，模型的神經(jīng)元和符號 / 搜索組件的設計之間的更強耦合對于分布外泛化至關(guān)重要 [Lamb 等人，2020]。然而，同樣值得注意的是，在 GPU 上實(shí)現圖搜索的設計高度定制化和并行化，可能對每個(gè)新問(wèn)題都是一種挑戰。
學(xué)習改進(jìn)次優(yōu)解
最近，從 Chen 等人在 2019 的工作和 Wu 等人在 2021 年的工作開(kāi)始，許多論文探索了建設性的 AR 和 NAR 解的替代方案，包括迭代改進(jìn)（次優(yōu)）解學(xué)習或局部搜索學(xué)習。其他著(zhù)名論文包括 Cappart et al., 2021, da Costa et al., 2020, Ma et al., 2021, Xin et al., 2021 和 Hudson et al., 2021.。
圖 10：通過(guò)在局部搜索算法中的指導決策來(lái)學(xué)習改進(jìn)次優(yōu) TSP 解的架構。(a) 原始的 Transformer 編碼器 - ****架構  [Wu et al., 2021]，該方法使用正弦位置編碼來(lái)表示當前的次優(yōu)旅行排列；(b)  Ma et al., 2021 通過(guò)在對稱(chēng)性問(wèn)題上做了進(jìn)一步的升級：具有可學(xué)習的位置編碼的雙端 Transformer 編碼器 - ****，能夠捕捉 TSP 旅行的循環(huán)性質(zhì)；(c) 正弦曲線(xiàn)與周期性位置編碼的可視化。
在所有這些工作中，由于深度學(xué)習用于指導經(jīng)典局部搜索算法中的決策（這些算法被設計為無(wú)論問(wèn)題規模如何都能工作），因此與建設性方法相比，這種方法隱含地導致對更大問(wèn)題實(shí)例的更好的零樣本泛化。實(shí)際來(lái)說(shuō)，這是一個(gè)非常理想的屬性，因為在非常大或真實(shí)世界的 TSP 實(shí)例上進(jìn)行訓練可能很棘手。
值得注意的是，NeuroLKH [Xin et al., 2021] 使用通過(guò) GNN 生成的邊概率熱力圖來(lái)改進(jìn)經(jīng)典的 Lin-Kernighan-Helsgaun 算法，并展示了對具有 5000 個(gè)節點(diǎn)的 TSP 以及跨對 TSPLib 數據集中，實(shí)例的強大零樣本泛化能力。
這項工成果的限制之一是需要事先手工設計的局部搜索算法，對于新的或未充分研究的問(wèn)題可能是會(huì )缺少的。另一方面，通過(guò)在解碼和搜索過(guò)程中實(shí)施約束，建設性的方法可以說(shuō)更容易適應新問(wèn)題。
促進(jìn)泛化的學(xué)習范式
未來(lái)的工作可以著(zhù)眼于新的學(xué)習范式（步驟 5），這些范式明確關(guān)注監督和強化學(xué)習之外的泛化，例如 Hottung et al., 2020 探索了自動(dòng)編碼器目標，以學(xué)習路由問(wèn)題解的連續空間，而 Geisler et al., 2021 訓練神經(jīng)求解器，使其對對抗性擾動(dòng)具有魯棒性。
目前，大多數論文都建議在非常小的隨機 TSP 上有效地訓練模型，然后以零樣本的方式將學(xué)習到的策略轉移到更大的圖和真實(shí)世界的實(shí)例中。合乎邏輯的下一步是在少數特定問(wèn)題實(shí)例上微調模型。Hottung et al., 2021 在 2021 年邁出了第一步，建議通過(guò)主動(dòng)搜索為每個(gè)特定問(wèn)題實(shí)例微調模型參數的子集。在未來(lái)的工作中，將微調作為元學(xué)習問(wèn)題進(jìn)行探索可能會(huì )很有趣，元學(xué)習問(wèn)題的目標是訓練模型參數，用于快速適應新的數據分布和問(wèn)題。
另一個(gè)有趣的可以探索的方向是通過(guò)對流行的路由問(wèn)題（如 TSP 和 CVPR）進(jìn)行多任務(wù)預訓練，然后針對特定問(wèn)題的微調來(lái)解決具有挑戰性約束的未充分研究的路由問(wèn)題。與自然語(yǔ)言處理中作為預訓練目標的語(yǔ)言建模類(lèi)似，路由預訓練的目標是學(xué)習通常來(lái)說(shuō)會(huì )有用的潛在表示，這些表示可以很好地轉移到新的路由問(wèn)題上。
改進(jìn)后的評估協(xié)議
除了算法創(chuàng )新之外，社區一再呼吁推出更現實(shí)的評估協(xié)議，這可以推動(dòng)現實(shí)世界路由問(wèn)題的進(jìn)步和工業(yè)界的落實(shí) [Francois et al., 2019, Yehuda et al., 2020]。最近， Accorsi et al., 2021 為實(shí)驗設計和與經(jīng)典運籌學(xué) (OR) 技術(shù)的比較提供了一套權威指南。他們希望對標準化基準進(jìn)行公平和嚴格的比較將成為將深度學(xué)習技術(shù)集成到工業(yè)路由求解器中的第一步。
總的來(lái)說(shuō)，令人鼓舞的是，近期的論文不僅顯示了對微小的隨機 TSP 實(shí)例的輕微性能提升，而且還采用了 TSPLib 和 CVPRLib 等真實(shí)世界的基準測試數據集。此類(lèi)路由問(wèn)題集合包含來(lái)自全球城市和道路網(wǎng)絡(luò )的圖表及其精確解決方案，并已成為 OR 社區中新求解器的標準測試平臺。
同時(shí)，我們必須在其他論文都在使用的前 n 個(gè) TSPLib 或 CVPRLib 實(shí)例上不「過(guò)擬合」。因此，更好的合成數據集與公平的基準測試進(jìn)展密切相關(guān)，例如 Queiroga et al., 2021 (https://openreview.net/forum?id=yHiMXKN6nTl) 最近提出了一個(gè)新的合成 了 10,000 個(gè) CVPR 測試實(shí)例的庫。
圖 11：關(guān)注 ML4CO 等社區競賽能有效地跟蹤研究進(jìn)展。（來(lái)源：ML4CO 網(wǎng)站）。對新構造的現實(shí)世界數據集進(jìn)行定期競賽，例如 NeurIPS 2021 的 ML4CO 競賽和 IJCAI 2021 的 AI4TSP，也是跟蹤深度學(xué)習和路由問(wèn)題交叉點(diǎn)進(jìn)展的一個(gè)有效手段。
我們強烈呼吁能夠在 YouTube 上獲取來(lái)自 ML4CO、NeurIPS 2021 的有價(jià)值的小組討論和演講。
總結
這篇博文介紹了一系列神經(jīng)組合優(yōu)化步驟，這些步驟將最近關(guān)于深度學(xué)習的論文統一到一個(gè)單一的框架中。然后，通過(guò)此框架的視角，我們分析和剖析最近的研究進(jìn)展，并預測未來(lái)研究的方向。
最后一點(diǎn)想說(shuō)的是，神經(jīng)組合優(yōu)化的更深刻的研究動(dòng)機可能并不是為了在經(jīng)過(guò)充分研究的路由問(wèn)題上勝過(guò)經(jīng)典方法。神經(jīng)網(wǎng)絡(luò )可以用作解決以前未遇到的 NP 難問(wèn)題的通用工具，尤其是那些對于設計啟發(fā)式算法而言并非微不足道的問(wèn)題。我們贊嘆神經(jīng)組合優(yōu)化最近在設計計算機芯片、優(yōu)化通信網(wǎng)絡(luò )和基因組重建方面的應用，并期待未來(lái)有更多有價(jià)值的應用！
原文鏈接：https://www.chaitjo.com/post/deep-learning-for-routing-problems/?continueFlag=b220d49bda26d4033730216fbc9275d5