深度强化学习结合图注意力模型求解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的方法和部分传统算法.