深度强化学习结合图注意力模型求解TSP问题

摘要：

旅行商问题(Traveling Salesman Problem,TSP)是组合最优化问题(Combinatorial Optimization Problem,COP)中的经典问题,多年以来一直被反复研究.近年来深度强化学习(Deep Reinforcement Learning,DRL)在无人驾驶、工业自动化、游戏等领域的广泛应用,显示了强大的决策力和学习能力.结合DRL和图注意力模型,通过最小化路径长度求解TSP问题.改进REINFORCE算法,训练行为网络参数,可以有效地减小方差,防止局部最优;在编码结构中采用位置编码(Positional Encoding,PE),使多重的初始节点在嵌入的过程中满足平移不变性,可以增强模型的稳定性;进一步结合图神经网络(Graph Neural Network,GNN)和Transformer架构,首次将GNN聚合操作处理应用到Transformer的解码阶段,有效捕捉图上的拓扑结构及点与点之间的潜在关系.实验结果显示,模型在100-TSP问题上的优化效果超越了目前基于DRL的方法和部分传统算法.

关键词：深度强化学习、旅行商问题、图注意力模型、图神经网络、组合最优化

所属期刊栏目：58

分类号：O22;TP18(运筹学)

资助基金：国家自然科学基金11761042

在线出版日期：2022-09-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：420-429