用深度学习解决旅行推销员问题，研究者走到哪一步了？

2022 年 4 月 6 日 机器之心

选自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 难问题的通用工具，尤其是那些对于设计启发式算法而言并非微不足道的问题。我们赞叹神经组合优化最近在设计计算机芯片、优化通信网络和基因组重建方面的应用，并期待未来有更多有价值的应用！

原文链接：https://www.chaitjo.com/post/deep-learning-for-routing-problems/?continueFlag=b220d49bda26d4033730216fbc9275d5