优化为何重要？

自人类诞生之初，即数百万年前，每一项技术创新和每一项改善我们生活和我们在地球上生存和繁衍能力的发明，都是由聪明的人类的聪明才智设计的。从火到轮子，从电到量子力学，我们对世界和周围事物的复杂性的理解已经增加到我们常常难以直观掌握的程度。

如今，飞机、汽车、轮船、卫星、复杂结构等许多领域的设计者都严重依赖算法来改进它们，而算法往往以人类无法实现的微妙方式来改进。除了设计之外，优化在网络路由（互联网和移动）、物流、广告、社交网络甚至医学等日常事务中也发挥着至关重要的作用。未来，随着我们的技术不断改进和复杂化，解决大规模难题的能力可能会有更高的需求，并且需要在优化算法方面取得突破。

组合优化问题

广义上讲，组合优化问题是指从一组有限的对象中找出“最佳”对象的问题。在这种情况下，“最佳”是通过给定的评估函数来衡量的，该评估函数将对象映射到某个分数或成本，目标是找到成本最低的对象。大多数实际有趣的组合优化问题（从现在起称为 COP）也非常困难，因为即使问题规模很小，集合中的对象数量也会极快地增加，因此穷举搜索不切实际。

为了更清楚地说明问题，我们将重点关注一个特定问题，即众所周知的旅行商问题 (TSP)。在这个问题中，我们有N 个城市，我们的推销员必须访问所有城市。然而，在城市之间旅行会产生一些费用，我们必须找到一条路线，在前往所有城市并返回出发城市时，最小化总累计费用。例如，下图显示了美国所有首都城市的最佳路线：

这一问题自然会出现在许多重要的应用中，例如规划、配送服务、制造、DNA 测序等。寻找更好的路线有时会带来严重的财务影响，这促使科学界和企业投入大量精力寻找解决此类问题的更好方法。

在为具有 K 个城市的 TSP 实例构建行程时，我们在行程构建过程的每个阶段都会淘汰一个城市，直到没有剩余的城市。在第一阶段，我们有 K 个城市可供选择来开始行程，在第二阶段我们有 K-1 个选项，然后有 K-2 个选项，依此类推。我们可以构建的可能行程数是每个阶段选项数的乘积，因此该问题的复杂度类似于O(K!)。对于小数字，这似乎并不是那么糟糕。假设我们有一个 5 个城市的问题，可能的行程数为 5!=120。但对于 7 个城市，它增加到 5040，对于 10 个城市，它已经是 3628800，而对于 100 个城市，它将达到惊人的 9.332622e+157，这比宇宙中的原子数量要多许多个数量级。现实世界中出现的 TSP 实例通常涉及数千个城市，并且需要在大量文献中开发了数十年的高度复杂的搜索算法和启发式方法才能在合理的时间内（可能是几个小时）解决。不幸的是，现实世界应用中出现的许多 COP 具有独特的细微差别和限制，使我们无法仅使用最先进的求解器来解决已知问题（例如 TSP），而是需要我们开发针对该问题的特定方法和启发式方法。这个过程可能漫长而艰巨，可能需要领域专家的工作来检测特定问题的组合搜索空间中的某些结构。

由于近年来深度学习在许多领域取得了巨大成功，让机器学习如何自行解决问题的可能性听起来非常有希望。将设计算法的过程自动化以解决困难的 COP 可以节省大量金钱和时间，并且可能产生比人类设计的方法更好的解决方案（正如我们在 AlphaGo 等成就中所看到的，它击败了人类数千年的经验）。

利用图形表示进行学习

2016 年，一篇名为“学习图上的组合优化算法”的论文对这个问题进行了早期的尝试。在这篇论文中，作者训练了一种名为structure2vec的图神经网络（我在另一篇文章中讨论了图神经网络），以贪婪地构建几个困难 COP 的解决方案，并获得了非常好的近似比（生产成本与最优成本之间的比率）。

基本思想是这样的：问题的状态可以表示为一个图，神经网络在此图上构建解决方案。在解决方案构建过程的每次迭代中，我们的网络都会观察当前图，并选择一个节点添加到解决方案中，之后根据该选择更新图，并重复该过程，直到获得完整的解决方案。

作者使用DQN算法训练了他们的神经网络，并展示了学习模型能够推广到比训练时更大的问题实例的能力。他们的模型甚至可以很好地推广到 1200 个节点的实例（而在大约 100 个节点的实例上进行训练），并且可以在 12 秒内产生解决方案，有时甚至比商业求解器在 1 小时内找到的解决方案还要好。他们的方法的一个很大的缺点是他们使用了一个“辅助”函数来帮助神经网络找到更好的解决方案。这个辅助函数是人为设计的，并且针对具体问题，这是我们想要避免的。

使用基于图的状态表示非常有意义，因为许多 COP 可以非常自然地以这种方式表达，就像这个 TSP 图的例子一样：

节点代表城市，边代表城市间距离。可以构建一个非常相似的图，而无需边属性（如果我们出于某种原因不假设距离知识）。近年来，基于图的神经网络模型（无论是否假设结构知识）的普及度令人难以置信地上升，最明显的是在自然语言处理领域，Transformer风格的模型已成为许多任务的最新技术。

有许多优秀的文章详细解释了 Transformer 架构，因此我不会深入研究它，而是给出一个非常简短的概述。Transformer 架构是由 Google 研究人员在一篇名为“ Attention Is All You Need ”的著名论文中引入的，用于解决 NLP 中出现的序列问题。不同之处在于，与明确输入一系列输入向量的循环神经网络（如 LSTM）不同，Transformer 将输入作为一组对象，并且必须采取特殊方法来帮助它看到“序列”中的顺序。Transformer 使用多个层，这些层由多头自注意力子层和全连接子层组成。

与图的关系在注意层中变得明显，这实际上是输入“节点”之间的一种消息传递机制。每个节点都会观察其他节点并关注那些对它来说更“有意义”的节点。这与图注意网络中发生的过程非常相似，事实上，如果我们使用掩码来阻止节点向不相邻的节点传递消息，我们会得到一个等效的过程。

学习解决没有人类知识的问题

在他们的论文“注意！学习解决路线问题”中，作者解决了几个涉及图上路线代理的组合优化问题，包括我们现在熟悉的旅行商问题。他们将输入视为一个图，并将其提供给嵌入图节点的改进的 Transformer 架构，然后按顺序选择要添加到路线中的节点，直到构建了完整的路线。将输入视为一个图比输入一系列节点更“正确”，因为它消除了对城市在输入中的顺序的依赖，只要它们的坐标不变。这意味着无论我们如何排列城市，给定图神经网络的输出都将保持不变，这与序列方法不同。

在论文中提出的架构中，图由一个 Transformer 风格的编码器嵌入，该编码器为所有节点生成嵌入，并为整个图生成单个嵌入向量。为了生成解决方案，每次都会为单独的解码器网络提供一个特殊的上下文向量，该向量由图嵌入和最后一个和第一个城市的嵌入以及未访问城市的嵌入组成，并输出未访问城市的概率分布，该概率分布被采样以生成下一个要访问的城市。解码器按顺序生成城市，直到游览完成，然后根据游览长度给予奖励。

作者使用一种名为 REINFORCE 的强化学习算法来训练他们的模型，这是一种基于策略梯度的算法。其版本的伪代码如下：

他们使用滚动网络来确定性地评估实例的难度，并定期使用策略网络的参数更新滚动网络。使用这种方法，作者在几个问题上取得了出色的结果，超越了我在前面几节中提到的其他方法。然而，他们仍然在最多 100 个节点的小实例上训练和评估他们的方法。虽然这些结果很有希望，但与现实世界相比，这样的实例微不足道。

扩展到非常大的问题

最近，一篇名为“通过深度强化学习在大型图上学习启发式方法”的论文向解决现实世界的问题迈出了重要的一步。在这篇论文中，作者训练了一个图卷积网络来解决诸如最小顶点覆盖 (MVC) 和最大覆盖问题 (MCP) 等大型问题。他们使用一种流行的贪婪算法来训练神经网络以嵌入图并预测每个阶段要选择的下一个节点，然后使用 DQN 算法进一步训练它。

他们在包含数百万个节点的图上评估了他们的方法，并取得了比当前标准算法更好、更快的结果。虽然他们确实利用了手工设计的启发式方法来帮助训练他们的模型，但未来的研究可能会消除这一限制，并学会解决巨大的 Tabula Rasa 问题。

总体而言，我认为在具有巨大搜索空间的问题中寻找结构是强化学习的一个重要且实用的研究方向。许多 RL 的批评者声称，到目前为止，它仅用于解决游戏和简单的控制问题，而将其转移到现实世界的问题仍然非常遥远。虽然这些说法可能是正确的，但我认为我在本文中概述的方法代表了非常实际的用途，可以在不久的将来使 RL 受益，遗憾的是它们没有像视频游戏方法那样引起人们的关注。