最近，针对旅行推销员等组合优化问题开发神经网络驱动的求解器引起了学术界的极大兴趣。这篇博文介绍了一个神经组合优化步骤，将几个最近提出的模型架构和学习范式统一到一个框架中。透过这一系列步骤，作者分析了深度学习在路由问题方面的最新进展，并提供了新的方向来启发今后的研究，以创造实际的价值。
组合优化问题的背景
组合优化是数学和计算机科学交叉领域的一个实用领域，旨在解决 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 及其合作者发表的指针网络论文开始介绍，红色突出表示该论文具有主要创新和贡献。
