能用Transformer网络解决经典旅行商算法问题？NTU-Xavier Bresson教授讲解，附PPT与视频

旅行商问题(TSP)是最受欢迎和研究最多的组合问题，始于1951年的冯·诺依曼。它推动了几种优化技术的发现，如切割平面、分支定界、局部搜索、拉格朗日松弛和模拟退火。

在过去的五年里，我们看到了一些有前途的技术的出现，在这些技术中(图)神经网络能够学习新的组合算法。主要的问题是，深度学习能否从数据中学习更好的启发式，即取代人类工程的启发式?这很有吸引力，因为开发有效解决NP难题的算法可能需要多年的研究，而许多行业问题本质上是组合在一起的。

在这项工作中，我们提出将最近成功开发的用于自然语言处理的Transformer架构应用于组合TSP。训练是通过强化学习完成的，因此没有TSP训练解决方案，解码使用波束搜索。我们报告了与最近学习的启发式相比性能的改进，TSP50的最佳差距为0.004%，TSP100为0.50%。

http://www.ipam.ucla.edu/abstract/?tid=16703&pcode=DLC2021