用深度學(xué)習(xí)解決旅行推銷員問題，研究者走到哪一步了？

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

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

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

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

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

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

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

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

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

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