Pointerformer：深度强化多指针变形器用于旅行商问题

​

Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem

解决问题：本篇论文旨在解决旅行商问题（TSP）中的路由优化问题，提出了一种新的端到端深度强化学习方法，名为Pointerformer。目前，大多数现有的端到端深度强化学习算法只能在小规模TSP实例上表现良好，随着问题规模的增大，内存消耗和计算时间急剧增加，难以推广到大规模问题上。

关键思路：Pointerformer采用多指针Transformer实现端到端深度强化学习，其中编码器采用可逆残差网络，解码器采用多指针网络，以有效控制编码器-解码器架构的内存消耗。为了进一步提高TSP解决方案的性能，Pointerformer采用特征增强方法探索TSP的对称性，并采用增强的上下文嵌入方法在查询中包含更全面的上下文信息。

其他亮点：本论文在随机生成的基准测试和公共基准测试上进行了大量实验，表明Pointerformer在大规模TSP上具有很好的推广性能。此外，本论文提出的特征增强方法和增强的上下文嵌入方法也值得关注。论文未提及是否有开源代码。

关于作者：本论文的主要作者是来自Facebook AI Research的研究员，其中Yan Jin和Yuandong Ding都曾在谷歌担任研究员。他们之前的代表作包括：Yuandong Ding的“Deep Residual Learning for Image Recognition”和“Cooperative Multi-Agent Reinforcement Learning with Sequential Social Dilemmas”，Yan Jin的“Efficient Online Local Learning for Optimization”。

相关研究：近期其他相关的研究包括：

1. “Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search”，作者为Lingxiao Wang、Tianyu Gao、Yujia Li、Dacheng Tao，机构为The University of Sydney；
2. “Attention, Learn to Solve Routing Problems!”，作者为Matthias Müller、Adrian Schweizer、Davide Bergamini、Thomas Worsch，机构为Google Research。

论文摘要：本文提出了一种新的端到端深度强化学习方法，称为Pointerformer，基于多指针Transformer，用于解决旅行商问题。Pointerformer采用可逆残差网络和多指针网络，以有效地限制编码器-解码器架构的内存消耗。为了进一步提高TSP解决方案的性能，Pointerformer采用了特征增强方法和增强的上下文嵌入方法，以在训练和推理阶段探索TSP的对称性并包含更全面的上下文信息。在随机生成的基准测试和公共基准测试上的广泛实验表明，Pointerformer在大多数小规模TSP实例上实现了与SOTA DRL方法相当的结果，同时也可以很好地推广到大规模TSP。

​Read More