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