组合优化问题的背景组合优化是数学和计算机科学交叉领域的一个实用领域，旨在解决NP-hard约束优化问题。NP-hard问题的挑战在于，穷举寻找NP-hard问题的解超出了现代计算机的极限，因此不可能在大规模问题上最优地解决NP-hard问题。我们为什么要关心这个？因为针对流行问题的鲁棒可靠的近似算法具有巨大的实用价值，是现代工业的支柱。例如，旅行商问题(TSP)是最流行的组合优化问题(COP)，出现在从物流和调度到基因组学和系统生物学的各种应用中。旅行商问题非常有名，或者说非常棘手，甚至还有专门的xkcd漫画！TSP和路由问题TSP也是路由问题的一个经典例子——路由问题是一类COP，需要按特定顺序遍历一系列节点（如城市）或边（如城市之间的道路），同时满足一组约束或优化一组变量。TSP需要以确保所有节点都被访问一次的顺序遍历一组边。从算法的角度来看，我们的销售人员的最佳“旅行”路线是一系列选定的边缘，这些边缘满足哈密顿循环中的最小距离或时间，请参见图1中的插图。图1：TSP提出以下问题：给定一个列表城市的数量以及每对城市之间的距离，销售人员访问每个城市并返回原籍城市的最短路线是什么？（来源：MathGifs）在现实世界和实际场景中，路径问题或车辆路径问题(VRP)可能涉及超出普通TSP的具有挑战性的约束。例如，TSPwithTimeWindow(TSPTW)将“时间窗口”约束添加到TSP图中的节点。这意味着某些节点只能在固定的时间间隔内访问。另一个变体，容量车辆路由问题(CVRP)，旨在为访问一组客户（即城市）的车队（即多个销售人员）找到最佳路线，每个客户具有最大承载能力。图2：TSP和相关的车辆路径问题类。VRP的约束不同于TSP的约束，图中显示了那些研究得相对充分的约束。现实世界中可能存在更复杂和非标准约束的类似VRP的问题！（来源：改编自Benslimane和Benadada，2014年）用深度学习解决路由问题为路由问题开发可靠的算法和求解器需要大量的专家直觉和多年的反复试验。例如，Concorde，用于线性规划、切割平面算法和分支定界问题的最先进的TSP求解器用了50多年才问世；这是一个关于其历史的鼓舞人心的视频(https://www.youtube.com/watch?v=q8nQTNvCrjE)。Concorde可以找到上万个节点的最优解，但是执行时间非常长。正如读者可以想象的那样，为复杂的VRP设计算法可能更具挑战性和耗时，尤其是在现实世界的限制下，例如混合容量或时间窗口问题。因此，机器学习社区开始关注以下问题：我们能否使用深度学习来自动化甚至增强解决COP所需的专家直觉过程？有关更深入的动机，请参阅Mila的这项漂亮调查：https://arxiv.org/abs/1811.06128神经组合优化学习用锤子解决问题的方法。神经网络经过训练后，可以直接从问题实例本身学习，产生COP的近似解。这一系列研究始于GoogleBrain开创性的Seq2seq指针网络和使用强化学习进行神经组合优化的论文。如今，图神经网络通常是深度学习驱动求解器的核心架构选择，因为它们解决了与这些问题相关的图结构。神经组合优化旨在通过以下方式改进传统的COP求解器：非手工启发式。神经网络不需要应用专家手动设计启发式和规则，而是通过模仿最好的求解器或通过强化学习来学习这些启发式和规则（下一节将展示一个例子）。GPU快速推理。对于较大的问题，传统求解器的执行时间通常很长，例如协和飞机用了7.5个月解决了最大的TSP，有109,399个节点。另一方面，一旦用于近似COP的神经网络经过训练，它在使用时具有非常有利的时间复杂度，并且可以由GPU并行化。这使它们非常适合解决实时决策问题，尤其是路由问题。解决新颖和未被充分研究的COP。神经组合优化可以显着加快特定COP求解器的开发，以解决具有深奥约束的新问题或未研究的问题。此类问题经常出现在科学层面的发现或计算机架构中，一个令人兴奋的成功例子是谷歌的芯片设计系统，它将为下一代TPU提供动力。你没看错——下一个运行神经网络的TPU芯片就是由神经网络设计的！神经组合优化步骤使用TSP作为典型示例，我们现在提出了一个通用的神经组合优化步骤，可用于表征现代深度学习驱动的方法来解决几个路由问题。最先进的TSP方法以城市的原始坐标作为输入，并利用GNN或Transformers结合经典图搜索算法来建设性地构造近似解。其架构大致可分为：（1）自回归模型，逐步构建解集；(2)非自回归模型，一次性生成所有解。可以通过监督学习或通过强化学习最小化TSP遍历的长度来训练模型以模拟最佳求解器。图3：神经组合优化步骤（来源：Joshi等人，2021年）。Joshi等人在2021年提出的5阶段步骤将突出的模型架构和学习范式集成到一个统一的框架中。这一步将使我们能够剖析和分析路由问题深度学习的最新发展，并提供新的方向来激发未来的研究。第一步是通过图定义问题图4：问题定义：TSP是通过城市/节点的全连接图定义的，可以进一步稀疏。TSP由一个全连接图定义，其中节点对应城市，边代表它们之间的道路。该图可以通过启发式算法（例如k-nn最近邻算法）进行稀疏化。这使模型能够扩展到所有节点的成对计算难以处理的大型实例[Khaliletal.,2017]，或者通过减少搜索空间来更快地学习[Joshietal.,2019]。Step2:Obtainlatentspaceembeddingsofgraphnodesandedges图5：图嵌入：每个图节点的嵌入是使用构建局部结构特征的图神经网络编码器获得的。GNN或Transformer编码器采用TSP图中的每个节点和边缘，或选择两者之一作为输入来计算潜在空间表示或嵌入特征。在每一层中，节点从其邻居收集特征以通过递归消息传递来表示局部图结构。堆叠L层后，网络能够从每个节点的L-hop邻域构建节点特征。Transformers[Deudonetal.,2018,Kooletal.,2019]和GatedGraphConvNets[Joshietal.,2019]等各向异性和基于注意力的GNN已成为编码路由问题的默认选择。邻域聚合期间的注意力机制至关重要，因为它允许每个节点根据其邻居对解决手头任务的相对重要性来权衡其邻居。重要的是，Transformer编码器可以看作是全连接图上的注意力GNN，即图注意力网络(GAT)。请参阅此博客文章以获得直观的解释。Steps3and4:Convertembeddingstodiscretesolutions图5：解码和搜索：给每个节点或每条边分配属于解集的概率（这里，MLP预测每条边，得到边概率图的“热功率”）)，然后将其转换为离散决策中的经典图搜索技术，例如贪婪搜索或波束搜索。一旦图的节点和边被编码为潜在空间表示，我们必须将它们解码为离散的TSP解决方案。具体来说，这可以通过两步过程完成：首先，通过为每个节点或边缘分配概率，将节点或边缘添加到解决方案集中，或者彼此独立（即非自回归解码）或通过图遍历有条件地（即自回归解码）。接下来，预测概率通过经典的图搜索技术转化为离散决策，例如由概率预测或波束搜索引导的贪婪搜索（我们将在稍后讨论近期趋势和未来方向内容时讨论更多关于图搜索的内容）。解码器的选择需要在数据效率和实现效率之间进行权衡：自回归解码器[Kooletal.,2019]将TSP转换为Seq2Seq模型，或基于一组无序的城市节点任务的有序旅游路线的语言翻译任务。他们通过一次选择一个节点来明确地模拟路由问题的顺序归纳偏差。另一方面，非自回归解码器[Joshietal.,2019]将TSP视为生成边际概率热图的任务。NAR方法明显更快并且更适合实时推理，因为它一次性生成预测，而不是增量生成。然而，NAR方法忽略了TSP的顺序性质，并且与AR解码相比训练效率可能较低[Joshi等人，2021年]。第5步：模型训练最后，整个编码器-解码器模型以端到端的方式进行训练，就像用于计算机视觉或自然语言处理的深度学习模型一样。在最简单的情况下，可以通过模仿最优求解器（即通过监督学习）来训练模型以产生接近最优的解决方案。对于TSP，Concrode求解器用于为数百万个随机实例生成最佳旅游路线的标记训练数据集。具有AR解码器的模型以教师强制模式进行训练，以输出节点的最佳巡回序列[Vinyals等人，2015]，而具有NAR解码器的模型被训练为从巡回期间遍历的边中学习在未遍历的边集中识别[乔希等人，2019]。然而，为监督学习创建标记数据集是一个昂贵且耗时的过程。特别是对于大规模问题实例，可能不存在最佳求解器准确性的保证，这导致监督训练的解决方案不精确。从实践和理论的角度来看，这远非理想[Yehudaetal.,2020]。在没有标准解决方案的情况下，强化学习通常是未被充分研究的问题的优雅替代方案。由于路由问题通常需要顺序决策以最小化特定于问题的成本函数（例如TSP的行程长度），因此可以将它们优雅地转换为RL框架，该框架训练代理以最大化奖励函数（损失函数的负值）。带有AR解码器的模型可以通过标准策略梯度算法[Kooletal.,2019]或Q-learning[Khaliletal.,2017]进行训练。各阶段成果简介我们可以通过5个阶段的步骤来描述TSP深度学习的突出成果。回想一下，这些步骤包括：(1)问题定义→(2)图嵌入→(3)解码→(4)解决方案搜索→(5)策略学习。下表从OriolVinyals和他的合作者发表的指针网络论文开始，用红色突出显示，表示该论文有重大创新和贡献。最近的进展和未来工作的途径通过统一的5阶段步骤，我们接下来重点介绍深度学习路由问题的一些最新进展和趋势。同时，将提供一些未来的研究方向，重点是如何提高对大规模和真实世界示例的泛化能力。利用等方差和对称性作为最有影响力的早期工作之一，自回归注意力模型[Kooletal.,2019]将TSP视为可以使用Seq2Seq解决的语言翻译问题，并将TSP旅行序列构建为城市排队.该公式的直接缺点是它没有考虑路由问题的潜在对称性。图6：通常，TSP具有唯一的最优解(L)。然而，在自回归公式下，当解表示为节点序列时，存在多个最优排列(R)。（来源：Kwon等人，2020年）POMO：多重最优策略优化[Kwon等人，2020年]提出在建设性自回归公式中利用起始城市的不变性。他们训练了与之前相同的注意力模型，但不同之处在于他们使用了一种新的强化学习算法（上述步骤中的第5步），该算法利用了多个最优游览排列。图7：城市坐标的欧氏对称群经过旋转、反射、变换后的TSP解不变。将这些对称性纳入模型可能是解决大规模TSP的原则性方法。同样，欧阳等人。2021升级了注意力模型以考虑输入城市坐标的旋转、反射和平移（即欧几里德对称群）的不变性。他们提出了一种自回归方法，通过在问题定义阶段（步骤1）同时执行数据扩充和在图编码（步骤2）期间使用相对坐标来确保不变性。他们在TSPLib数据集上进行的从随机实例到现实世界的零样本泛化实验表明，他们的模型表现良好。未来的工作可能会遵循建筑设计中的几何深度学习(GDL)蓝图。GDL告诉我们明确说明数据或问题中的对称性和归纳偏差，并将它们结合起来。由于路由问题需要嵌入到欧几里德坐标中，并且由于路由是循环的，因此将这些约束直接合并到模型架构或学习范例中可能是一种原则性方法，可以在训练期间提高与更大的大规模实例的对比度。泛化能力。改进图搜索算法的另一个有影响力的研究方向是单次非自回归图卷积网络方法[Joshietal.,2019]。最近的几篇论文建议保持相同的门控GCN编码器（第2步），同时用更强大和更灵活的图搜索算法替换波束搜索组件（第4步），例如动态规划[Kooletal.,2021]或MonteCarloTreeSearch(MCTS)[Fuetal.,2020]。图8：门控GCN编码器[Joshietal.,2019]可用于为TSP、CVRP和TSPTW生成边缘预测“热图”（透明红色）。这些可以由DP或MCTS进一步处理以输出路线（纯色）。GCN本质上减少了复杂搜索算法的解决方案搜索空间，这在搜索所有可能的路线时可能很棘手。（来源：Kooletal.,2021）Fu等人提出的GCN+MCTS框架。有一种非常有趣的方法可以以零样本的方式在非常小的TSP问题上有效地训练模型（类似于Joshi等人最初探索的GCN+beamsearch方法）成功地将学习到的策略转移到更大的图。他们通过更新问题定义（步骤1）确保GCN编码器的预测仍然可以随着TSP从小到大的变化而泛化：大规模问题实例表示为许多较小的子图，这些子图与GCN的大小相同训练图，然后在执行MCTS之前合并GCN的边缘预测结果。图9：GCN+MCTS框架[Fuetal.,2020]将大型TSP问题表示为一组与用于训练的GCN大小相同的较小子图。通过合并GCN预测的子图的边热图，可以得到原始图的热图。这种分而治之的方法确保GCN嵌入和预测能够很好地从较小的实例推广到较大的实例。（来源：Fuetal.,2020）这种分而治之的策略最初是由Nowak等人提出的。2018年，以确保GNN的嵌入和预测能够很好地从小型到大型TSP实例（最多10,000个节点）进行泛化。结合GNNs、分治法和搜索策略来处理高达3000个节点的大规模CVRP问题也充满了无限可能。[李等人，2021]。总体而言，这一工作表明，模型神经元的设计与符号/搜索组件之间更强的耦合对于分布外泛化至关重要[Lamb等人，2020年]。然而，同样值得注意的是，在GPU上实现图形搜索的设计是高度定制化和并行化的，这对每个新问题来说都是一个挑战。学习改进次优解决方案最近，从Chen等人的工作开始。在2019年和Wu等人。2021年，许多论文探索了AR和NAR解决方案的建设性替代方案，包括迭代改进（次优）解决方案学习或局部搜索学习。其他著名论文包括Cappart等人，2021年；daCosta等人，2020年；Ma等人，2021年；Xin等人，2021年；Hudson等人，2021年。图10：学习改进次优算法的架构通过在本地搜索算法中指导决策来解决TSP。(a)原始的Transformer编码器-解码器架构[Wuetal.,2021]，它使用正弦位置编码来表示当前的次优行程排列；(b)Maetal.,2021throughthesymmetryproblem进一步升级:adual-endingTransformerencoder-decoderwithlearnablepositionalencoding,capableofcapturingthecyclicnatureofTSPtravel;(c)正弦和周期性位置编码的可视化。在所有这些工作中，由于深度学习用于指导经典局部搜索算法（设计为无论问题大小如何都能工作）中的决策，因此这种方法隐含地导致了对更大问题实例的更好的零样本泛化。在实践中，这是一个非常理想的属性，因为在非常大的或真实世界的TSP实例上进行训练可能很棘手。值得注意的是，NeuroLKH[Xinetal.,2021]使用GNN生成的边缘概率热图改进了经典的Lin-Kernighan-Helsgaun算法，并展示了实例强大的零样本泛化能力。这项工作的局限性之一是需要事先手工设计的局部搜索算法，这对于新的或未充分研究的问题可能是缺乏的。另一方面，通过在解码和搜索过程中强制执行约束，构造方法可以说更容易适应新问题。促进泛化的学习范式未来的工作可以着眼于新的学习范式（第5步），这些范式明确关注监督学习和强化学习之外的泛化，例如Hottung等人，2020探索了自动编码器的目标，以学习路由问题解决方案的连续空间，Geisler等人，2021训练神经求解器对对抗性扰动具有鲁棒性。目前，大多数论文建议在非常小的随机TSP上有效地训练模型，然后以零样本的方式将学习到的策略转移到更大的图和真实世界的实例。合乎逻辑的下一步是在少量特定于问题的实例上微调模型。Hottung等人于2021年迈出了第一步，即2021年，提议通过主动搜索为每个特定问题实例微调模型参数的子集。在未来的工作中，将微调作为元学习问题进行探索可能会很有趣，其目标是训练模型参数以快速适应新的数据分布和问题。另一个有趣的探索方向是通过对TSP和CVPR等流行路由问题进行多任务预训练，然后针对特定问题进行微调，来解决具有挑战性约束的未充分研究的路由问题。与自然语言处理中作为预训练目标的语言建模类似，路由预训练的目标是学习通常有用的潜在表示，这些表示可以很好地迁移到新的路由问题。改进的评估协议除了算法创新，社区一再呼吁更现实的评估协议，这可以推动现实世界的路由问题和行业实施的进展[Francoisetal.,2019,Yehudaetal.,2020]。最近，Accorsi等人在2021年为实验设计和与经典运筹学(OR)技术的比较提供了一套权威指南。他们希望与标准化基准进行公平和严格的比较将成为将深度学习技术集成到工业路由求解器中的第一步。总的来说，令人鼓舞的是，最近的论文不仅在微小的随机TSP实例上显示出轻微的性能提升，而且还使用了真实世界的基准数据集，如TSPLib和CVPRLib。这个路线问题集合包含来自世界各地的城市和道路网络图及其精确解决方案，并已成为OR社区中新求解器的标准测试平台。同时，我们不能在其他论文使用的TSPLib或CVPRLib的前n个实例上“过度拟合”。因此，更好的合成数据集与公平的基准测试进展密切相关，例如Queiroga等人，2021(https://openreview.net/forum?id=yHiMXKN6nTl)最近提出了一个新的合成10,000CVPR测试实例的库。图11：关注ML4CO等社区竞赛是跟踪研究进展的有效方式。（来源：ML4CO网站）。定期对新构建的真实世界数据集进行竞赛，例如NeurIPS2021的ML4CO竞赛和IJCAI2021的AI4TSP竞赛，也是跟踪深度学习和路由问题交叉点进展的有效手段。我们强烈建议您在YouTube上观看ML4CO、NeurIPS2021的宝贵小组讨论和演示。总结这篇博文介绍了一系列神经组合优化步骤，这些步骤将最近关于深度学习的论文统一到一个框架中。然后，通过这个框架的镜头，我们分析和剖析近期的研究进展并预测未来的研究方向。最后一点要指出的是，神经组合优化的更深层次研究动机可能不是在经过充分研究的路由问题上胜过经典方法。神经网络可以用作解决以前从未遇到过的NP-hard问题的通用工具，尤其是那些对于设计启发式算法而言并非微不足道的问题。我们惊叹于最近神经组合优化在设计计算机芯片、优化通信网络和基因组重建方面的应用，并期待未来更多更有价值的应用！
