能用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

内容预览：

• TSP历史

• 传统解释器

• 神经网络解释器

• 提到架构

• 解码技巧

• 数值方法

• 讨论

• 结论
  

专知便捷查看

便捷下载，请关注专知公众号（点击上方蓝色专知关注）

• 后台回复“T2SP” 可以获取《能用Transformer网络解决经典旅行商算法问题？NTU-Xavier Bresson教授讲解，附PPT与视频》专知下载链接索引

专知，专业可信的人工智能知识分发，让认知协作更快更好！欢迎注册登录专知www.zhuanzhi.ai，获取5000+AI主题干货知识资料！

欢迎微信扫一扫加入专知人工智能知识星球群，获取最新AI专业干货知识教程资料和与专家交流咨询！

点击“ 阅读原文 ”，了解使用 专知 ，查看获取5000+AI主题知识资源