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

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

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

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

成为VIP会员查看完整内容
25

相关内容

【普林斯顿-Mengdi Wang】强化学习统计复杂度,35页ppt
专知会员服务
20+阅读 · 2020年11月15日
【普林斯顿】持续视角下的机器学习,31页ppt及视频
专知会员服务
23+阅读 · 2020年8月19日
非凸优化与统计学,89页ppt,普林斯顿Yuxin Chen博士
专知会员服务
100+阅读 · 2020年6月28日
视频中的多目标跟踪【附PPT与视频资料】
人工智能前沿讲习班
30+阅读 · 2018年11月29日
【GAN货】用神经网络生成音乐
专知
12+阅读 · 2018年9月15日
Arxiv
19+阅读 · 2021年4月8日
Arxiv
3+阅读 · 2020年2月5日
Music Transformer
Arxiv
5+阅读 · 2018年12月12日
VIP会员
微信扫码咨询专知VIP会员