“旅行商问题”太棘手？用图神经网络寻找最优解

全文共3438字，预计学习时长7分钟或更长

为什么优化如此重要？

从几百万年前人类生命起源开始，为了提升生活质量，提高在地球上的生存技能，人类利用睿智的脑袋进行了一次次的科技创新和发明。从火（药）到车轮，从电力到量子力学，我们对于世界及周遭事物复杂性的理解水平已经到了难以仅凭直觉去判断的程度。

如今，飞机、汽车、轮船、卫星以及用于其他目的复合结构的设计师们，极大地依赖于运用算法来提升其能力，而这种提升方式往往微妙到人们自身永远无法实现。

除了设计，优化在日常生活中也扮演着至关重要的角色，比如网络路由（互联网和移动终端）、物流、广告投放、社交网络甚至是医药信息。未来，随着科技水平的不断改进与复杂化，解决大规模难题的能力将会迎来更高需求，同时，我们也需要在算法优化上有所突破。

组合优化的问题

广义上来说，组合优化问题即是解决从有限对象集合中寻找“最佳”对象的问题。这个语境中的“最佳”是由给定的评价函数来衡量的，该函数将对象映射到某个分数或成本，其目标是找到成本最低的对象。大多数在实际中看起来有意思的组合优化问题(后文都简略为COPs)很棘手，因为即使问题的规模大小只增加一点点，集合中的对象数量也会以极快的速度增加，这使穷举搜索显得不切实际。

为了让问题更加直观明了，我们把关注点放在一个特定的问题上，即著名的旅行商问题(TSP)。在这个问题中，假设有N座城市，销售人员必须访问所有的城市。无论如何，在城际间旅行会产生一定的成本，而我们必须找到一条路线，使整个出行成本降到最低。例如，下图显示了行遍美国各州首府的最佳路线图：

这个旅行商问题广泛存在于许多重要领域的应用，例如规划、交付服务、制造业、DNA测序以及其他许多方面。寻找更好的路径与解决财务等问题息息相关，这也促使科学界和企业投入大量物力财力来寻找更好的方法。

以K个城市为TSP例子构建一个旅游路线，在路径构建过程的每个阶段会删除一个城市，直到没有剩余的城市为止。在第一个阶段，有K个城市可供选择，在第二个阶段，有K-1个选项，接着是K-2个选项，以此类推。我们能够构建的潜在路径总数量是每个阶段所拥有选项数量的乘积，这个问题的复杂性为O(K!)。

然而，这种方法比较适用于数量较小的计算。比方说，假设有5个城市，则潜在旅游路线的总数量为5!=120。但是对于有7个城市的情况来说，这个计算结果会立增到5040，10个城市已经达到则是3628800，100的结果更是惊人地高达9.332622e+157，而这数量远远超过了宇宙中原子的数量。

在现实生活中TSP的运用实例涉及到的是成千上万的城市数量运算，为了能在合理的时间(可能是几个小时)内解决问题，通常需要运用那些高度复杂的搜索算法和启发式算法，而这些算法是通过几十年下来的大量文献所开发形成的。

不幸的是，在实际应用中出现的许多COPs具有独特的细微差别和条件约束，它们阻止我们用最先进的解决方案来解决诸如TSP之类的已知问题，并且要求我们开发针对该问题的方法和启发式。这个过程可谓长路漫漫障碍重重，可能需要相关领域专家来检测特定问题组合，搜索空间中的某些结构。

这些年来，由于深度学习在许多领域都取得了巨大的成功，让机器自主学习如何解决问题似乎有望在未来实现。将算法的设计过程自动化，使其能够自发解决难以应对的COPs——这样不仅能节约大量财力和时间，也许还能生成比人工设计更加可行的解决方案（就像我们目前在AlphaGo等成果中所能看到的一样，它已经打败了人类过去通过数千年所取得的经验成就）。

运用图例学习

早在2016年，一篇名为《基于图表学习组合优化算法》的论文就对这个问题进行了早期尝试。在这篇文章中，作者训练了一种叫structure2vec的图神经网络，针对几个有难度的COPs制定贪婪的构造解决方案，并获得了非常好的近似比值(生成成本与最优成本之比)。

它的基本思路是这样子的：用图谱来表示待解决的问题，然后让图神经网络依据图谱建立解决方案。在解决方案构建过程的每次迭代中，神经网络会观察当前的图表，并选择一个节点添加到解决方案中，然后根据该选择更新图表，接着重复这个过程，直到得到一个完整的解决方案。

论文作者们使用DQN算法来训练神经网络，并证明了习得模型在运用到比所受训练更复杂的问题实例时的泛化能力。这种模型甚至可以很好地泛化到1200个节点的实例中（同时在大约100节点的实例进行训练），同时还能在12秒内生成比商业求解程序用时一小时所求得的更佳解决方案。

但是这个方法有一个很大的缺陷，就是他们会使用一个“辅助”方程来帮助图神经网络寻找更好解法。这个辅助方程是人为设计用于解决特定问题的，而这恰恰是我们想要避免的。

这种基于图例的展现方式非常容易理解，因为许多组合优化问题可以自然而然地以这种方式呈现出来，就如下面这个TSP图例所展示的一样：

图中的每个节点代表每个城市，节点边缘包含了城际间的距离，如果不考虑边缘属性，类似的图形也能够构建起来（如果我们出于某种原因不考虑距离因素在内的话）。近年来，基于图形的神经网络模型（无关乎是否具备架构知识）以令人难以置信的速度流行开来。尤其令人瞩目的是自然语言处理领域，它所使用的Transformer架构模型已经成为业内众多任务处理的最先进技术。

有许多优秀的文章详细地解释了Transformer 架构，所以本文不再深入剖析，而是做一个简述。Transformer架构是由谷歌研究人员在一篇题为“Attention Is All You Need”的论文中所介绍的。在这篇著名的论文中，Transformer架构被用于处理NLP中所面对的序列难题。不同之处在于，我们可以向递归神经网络，如长短记忆网络（LSTM），直观输入一系列的输入向量，而Transformer架构中只能以一系列对象的形式输入，且必须采用特殊的方式来让它看见“序列”的排列顺序。这个Transformer是由一个多头自注意力子层和一个完全连接的子层所组成的。

它与图谱的关系在注意力层变得明显起来，而这个注意力层实际上是输入“节点”间的一种信息传递机制。每一个节点都会观察其他节点，同时定向那些对于它们自己看起来更“有意义”的节点。这与在图谱注意力机制（Graph Attention Network）中运行的过程非常相似。实际上，如果使用一个掩码来阻止单个节点向不相邻的节点传递信息，我们将会得到一个等价的过程。

学习如何在没有人类知识的情况下解决问题

在论文《注意！学习解决路由问题》中，作者们尝试解决了几个涉及图解路由代理的组合优化难题，包括我们现在熟悉的旅行商问题。将输入数据视为一个图，并将其投入一个经过调整的Transformer构架并在构架中嵌入了图的节点，然后依次选择添加到路由的节点直到完成构建一个完整的路由为止。

将输入数据视为图形是一个比向其提供节点序列更为“正确”的方法，因为只要它们的坐标不变，就能够消除对所输入城市顺序的依赖性。这意味着，不同于上述的节点序列法，无论我们如何改变输入城市的排列，给定图神经网络的输出值都将保持不变。

在论文所提及的构架中，图谱是由Transformer 编码器嵌入的，它在为所有的节点生成嵌入层的同时也为全图生成单个嵌入向量。为了生成解决方案，每次给予一个特殊的上下文向量时都会给出一个单独的解码器网络，这个网络由图嵌入、最后一个和第一个城市以及未访问城市的嵌入组成，并会输出一个未访问城市的概率分布，然后采样生成下一个将要访问的城市。这个解码器会按顺序生成要访问的城市直到整个行程结束，然后根据旅程的长度给予反馈。

文中使用了一种名为REINFORCE的强化学习算法来训练模型，这是一种基于策略梯度的算法。其版本所使用的伪代码如下图所示：

文中使用一个滚轮网络来确切评估实例的难度，并定期使用策略网络的参数来更新这个滚轮网络。这种方法在解决几个难题上取得了不错的成效，性能上超越了前文所提到的其他方法。尽管如此，作者们仍在拥有至多100个节点的小型例子上训练和评估模型。虽然这些结果很有希望，但这些例子与现实生活中其他情况相比，犹如小巫见大巫。

扩展到大型问题

最近，一篇题为《通过深度强化学习在大型图上学习启发式算法》的论文中向解决现实世界那般规模大小的问题迈出了重要一步。在文中，作者训练了一个图卷积网络来解决诸如最小顶点覆盖(MVC)和最大覆盖问题(MCP)这样的大型实例问题。

针对这些问题，他们采用一种流行的贪心算法来训练神经网络进行嵌入图并预测每一阶段需要选择的下一个节点，在此之后使用DQN算法对其进行进一步的训练。

他们在含有数百万个节点的图上测评了其方法，并取得了比当前标准算法更优异快速的结果。虽然他们确实通过使用动手搭建的启发式来帮助训练模型，但在未来，这种方式可能会消除这种约束，并从白板状态学会解决巨大难题。

总之，在无边的搜索领域中，寻找架构是强化学习的一个重要且实用的研究方向。许多批评强化学习的人声称，到目前为止，这项技术仅被用于解决游戏和简单的操作问题，想要将其应用到解决现实问题中还很有很长的路要走。

留言 点赞 关注

我们一起分享AI学习与发展的干货

欢迎关注全平台AI垂类自媒体 “读芯术”