旅行商问题(TSP)的Transformer解法

利用 Transformer 解决 TSP 的原创方法         

旅行商问题 (TSP, Travelling Salesman Problem) 是组合优化的经典挑战之一。虽然已经研究了很长时间，但目前还没有确切的方法来保证最优解。随着人工智能领域的进步，应对 TSP 的新方案应运而生。在本文中，我们利用 transformer 神经网络找出解决此问题的好方法。相应代码可在此存储库(https://github.com/dcaffo98/transpormer)中获得。

背景——TSP

给定一个城市列表和每对城市之间的距离，访问每个城市恰好一次并返回起始城市的最短路径是什么？（来源：维基百科）

上面的问题定义了旅行商问题 (TSP)，这是NP-hard 难题之一，这意味着目前没有已知的方法可以在多项式时间内得出最优解。更正式一点，给定一个图G ( V , E )，其中V是节点集（城市），E是连接V中任何一对节点的边集，我们被要求找到在G中游历的最短哈密顿量（即“仅访问每个城市一次并返回起始城市的路线”）。

在这个项目中，我们将节点视为一对简单的特征，即二维向量空间中的 x 和 y 位置。因此，任何一对节点(u, v)之间都存在一条边，其权重由u和v之间的欧几里德距离给出。

背景——TSP 的Transformer

我们从 Bresson 等人的工作中汲取灵感。[1]，他们利用Transformer神经网络来解决 TSP，获得了非常有希望的结果。简而言之，他们的模型分为两个部分。首先，transformer encoder将一组标记作为输入，即表示输入图G中节点的向量，并借助自注意力层将它们转换为新的潜变量空间。我们将encoder的输出称为图嵌入。随后，transformer decoder被输入一个虚构的标记z，它向模型发出开始构建游历的信号，加上来自encoder的图嵌入，并生成概率分布，对图中每个节点被选为游历中的下一个候选节点的可能性进行建模。我们从该分布中绘制对应于所选节点的索引t 。然后，我们将z与第 t 个图嵌入连接起来，我们再次将结果序列提供给decoder，该序列表征部分游历。这个过程一直持续到所有可用的节点都被选中为止。完成后，我们从获得的序列中删除z并将第一个选定的节点附加到它，从而结束游历。这样的decoder称为自回归，因为在每个选择步骤中，它都会处理上一步的输出。该模型使用 REINFORCE [2] 算法进行训练，以最小化从每个具有 50 个节点的随机图生成的旅行的平均长度。

建议的方法

Bresson 等人提出的架构概述。（右）和我们（左）。请注意，我们的网络没有自回归组件，即输出和输入之间没有反向链接。

在这个项目中，我们也采用了Transformer架构，因为我们的目标是利用注意力来学习图中节点之间有价值的全局依赖关系。同时，我们想设计一个模型，避免任何自回归组件，即直接输出可行的 TSP 解决方案的神经网络，而不需要对每个节点进行一次前向传递。

我们首先考虑可以将 TSP 构造为一个按顺序排列的问题。我们有一堆未定义顺序的节点，我们想弄清楚如何对它们进行排序，以便生成的旅行尽可能短。在神经网络中表示顺序的概念通常是通过某种位置编码[3] 来完成的。也就是说，我们将输入集中的每个标记与特定向量相加，其分量对于特定位置是唯一的。因此，如果我们改变标记的顺序，位置向量就会不同，从而导致标记也不同。自然地，位置编码有很多可能的实现，但为了简单起见，我们坚持最初的提议。

我们方法的核心是注意力运算符，特别是交叉注意力，所以这里我们简要回顾一下。

注意力的3步解释。

关键的一步是第二步。A是一个[n,n]矩阵，其(i,j)项是与第 i 个标记与第 j个标记的余弦相似度成正比的实数。要理解原因，请回忆一下步骤 2 中的(i,j)是查询i和键j之间点积的结果，两者都是形状为(d_k)的两个向量。但是，除了由相同向量的范数的乘积表示的比例因子之外，点积只不过是两个向量之间夹角的余弦值。

两个向量之间的余弦公式。

在将 softmax（第 3 步）应用到A之后（实际上，应用到A的缩放版本，但这不是重要的东西），我们得到一个矩阵，其第 i行是概率分布，对查询i的可能性建模类似于键j =1,…, n。最后，A对V应用线性变换，通过查询和键之间的相似性对其d=1,…k特征进行加权。例如，假设x_0、x_1和x_2是分别代表纽约（NY）、华盛顿特区（WDC）和洛杉矶（LA）城市的标记。它们的特点与3个大都市的地理位置有关。我们从中提取Q、K和V的 3个矩阵，并计算注意力矩阵A。由于 NY-WDC 的距离比 NY-LA 短得多，因此A的第一行在其第一列中将具有非常高的值（因为 NY-NY 的距离自然是最短的），在第二列中具有中高值列，第三个值较低。NY 也由矩阵V中的第一行表示，即v_0。那么，AV矩阵乘法之后，v_0的特征主要由 A 的第一行 (NY) 加权，第二行 (WDC) 合理加权，第三行 (LA) 加权较差。同样的过程也适用于其他两个城市。我们的原始标记集已转换为一组新的向量，其中它们的特征由（在本例中为空间）相似性加权。

这种类型的注意力被称为自注意力，因为Q、K和V都来自相同的输入。另一方面，在 transformer decoder中，还有第二种注意力，交叉注意力。这次，查询Q来自decoder本身。例如，在 Bresson等人的模型中。，Q代表部分游历。K和V是encoder输出的相反线性投影。

那么，在这项工作中，我们建议以不同的方式利用交叉注意力。事实上，我们使用位置编码作为查询，而键和值是从先前的自注意力层中提取的，它可以自由地对G的所有节点进行操作。这样，当我们计算注意力矩阵时，我们最终得到一个矩阵，其中每一行都是给定位置与给定节点相似的可能性的概率分布。下图可能有助于理解这一说法。

可视化我们模型中的交叉注意力。

根据上面的注意力矩阵，节点#1 可能是提议的游历中的第一个。#46 可能是第二个。节点#39 和#36 将分别放置在第三和第四位置。节点 #23 是第五和第六位置的良好候选者，依此类推……实际上，这样一个矩阵的元素(i,j)表示节点j被插入位置i的可能性。我们的模型本质上是一堆块，每个块都包含一个自注意力层、呈现的交叉注意力，最后是一个前馈网络，就像在任何transformer中一样。最后一个交叉注意层的注意矩阵将用于生成游历。我们的模型产生的完整注意力矩阵是这样的：

未经训练的注意矩阵，权重随机初始化。

这显然很混乱。在使用 REINFORCE 算法优化网络以最小化平均游历长度后，我们最终得到如下矩阵。

训练后的注意力矩阵。

从上面的矩阵开始，我们可以为每一行绘制一个节点，得到的序列将是我们的旅程（在追加第一个节点后将其关闭）。为了简单起见，在所有的实验中，我们都使用贪心解码来选择节点，即我们总是选择当前行具有最高值的节点。我们将探索其他策略（例如集束搜索算法）留给未来的开发。

可行方案

您可能已经发现了我们方法的主要问题。要构建一个可行的旅行，我们只需要选择每个节点一次。相反，如果你仔细观察上一张图，你会发现有一些重复。即，节点#47 和节点#32 一样是最有可能获得两个连续位置的节点。事实上，我们的网络无法提供可行的 TSP 解决方案。我们想从模型中得到的是一个置换矩阵。即每行和每列的单个条目值为 1 的矩阵。问题是神经网络不擅长预测这种稀疏对象。

为了克服这个障碍，我们可以将 TSP 表述为线性求和分配(LSA) 问题，其（逆）成本矩阵是由我们的Transformer计算的注意力矩阵。在这项工作中，我们利用SciPy的实现来找到节点集（典型 LSA 公式中的worker）和游历中的位置集（jobs）之间的最小成本匹配。

Sinkhorn 算子

当然，成本由置换矩阵给出的 LSA 的求解很简单：您只需为矩阵的每一行选择1 。因此，我们训练的目标是使最终的注意力矩阵尽可能接近排列矩阵，这样 LSA 就会很容易，并且会导向代表总长度较短的旅行的匹配。

在我们的项目中，我们利用 Sinkhorn 算子 [4] 将我们模型的密集注意力矩阵转变为软排列矩阵：它们并不真正代表排列，但它们非常接近它。在下文中，我展示了典型培训设置的过程。我们的模型提出的解决方案的平均游历长度预计会在训练时减少。如果我们在解决 LSA 问题之前停止应用 Sinkhorn，则不会发生这种情况。

Sinkhorn 算子对我们方法的影响。

结果和比较

我们将我们的建议与 Christofides [5] 的算法（一种流行的 TSP 启发式算法）以及 Bresson 等人的自回归变换器进行比较，我们将其作为训练设置的参考。评估是在 10000 个图上进行的，每个图有 50 个节点，其坐标是随机生成的。

在这里，我们提供了一个箱形图，描述了三个竞争者提出的解决方案的长度。毫无疑问，我们的Transformer是上下文中最糟糕的。在不利用自回归的情况下利用神经网络生成良好的 TSP 解决方案是一项艰巨的任务。

来自三种比较方法的 TSP 解决方案的长度。

然而，解决优化问题不仅仅与性能有关。计算时间也起着重要作用。这是我们提议的主要特征：由于我们的Transformer需要单个前向传递来提供解决方案，因此我们比 Bresson等人的方法更快。因为它们必须循环的次数与图中的节点数一样多才能获得完整的游历。下图显示了使用 Python分析器测量的计算时间。对于 Christofides，我们使用NetworkX的实现。请注意，为了公平比较，这两个神经网络在 CPU 上运行，因为 Christofides 不被认为是在 GPU 上运行。

解决 TSP 实例的 CPU 计算时间。

最后，我们展示了我们网络产生的最佳旅游的一些定性结果。在这些情况下，我们的模型能够改进 Christofides 生成的解决方案。

定性结果：来自 Christofides 的NetworkX实施（左）和我们的Transformer（右）的 TSP 解决方案。

结论和未来的工作

在这项工作中，我们提出了一个原创的神经网络来解决 TSP。虽然我们设法设计了一个合适的架构来避免自动回归，但所提议的游历的质量值得怀疑。这种方法的主要缺点是它不是端到端的神经方法，因为我们需要解决一个 LSA 实例以确保可行的解决方案。我们试图通过在损失函数中添加一些惩罚项来强制模型避免节点重复，但我们没有得到任何好的结果。从集合中学习排列本身就是一项艰巨的任务。

也许，仅仅从单纯的贪心解码切换到集束搜索策略就足以略微改善结果。此外，还有更高级的强化学习算法有待探索，例如PPO。我们希望其他人可能会受到这个项目的启发，并将继续探索这条道路。

参考

[1] Bresson, Xavier, and Thomas Laurent. “The transformer network for the traveling salesman problem.” arXiv preprint arXiv:2103.03012 (2021)

[2] Williams, Ronald J. “Simple statistical gradient-following algorithms for connectionist reinforcement learning.” Reinforcement learning (1992): 5–32

[3] Vaswani, Ashish, et al. “Attention is all you need.” Advances in neural information processing systems 30 (2017)

[4] Adams, Ryan Prescott, and Richard S. Zemel. “Ranking via sinkhorn propagation.” arXiv preprint arXiv:1106.1925 (2011)

[5] Christofides, Nicos. Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976