拉拢优化题目的背景
拉拢优化是数学和计算机科学交叉领域的一个实用领域，旨在解决 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