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

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

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

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

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

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

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

未來(lái)工作的最新進(jìn)展和途徑
有了統(tǒng)一的 5 階段步驟，我們接下來(lái)重點(diǎn)介紹深度學(xué)習(xí)路由問(wèn)題的一些最新進(jìn)展和趨勢(shì)。同時(shí)還將提供一些未來(lái)的研究方向，重點(diǎn)探討如何提高對(duì)大規(guī)模和真實(shí)世界實(shí)例的泛化能力。
利用等方差和對(duì)稱(chēng)性
作為最有影響力的早期作品之一，自回歸注意力模型 [Kool et al., 2019] 將 TSP 視為可以用 Seq2Seq 解決的語(yǔ)言翻譯問(wèn)題，并將 TSP 旅行順序構(gòu)建為城市排列。該公式的一個(gè)直接缺點(diǎn)是它沒(méi)有考慮路由問(wèn)題的潛在對(duì)稱(chēng)性。
圖 6：一般來(lái)說(shuō)，TSP 有一個(gè)唯一的最優(yōu)解 (L)。然而，在自回歸公式下，當(dāng)解表示為節(jié)點(diǎn)序列時(shí)，存在多個(gè)最優(yōu)排列 (R)。（來(lái)源：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)的歐幾里得對(duì)稱(chēng)群的 TSP 解保持不變。將這些對(duì)稱(chēng)性納入模型可能是解決大規(guī)模 TSP 的原則性方法。

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