一种带泛化性能的动态混合模型求解大范围TSP问题  

A Dynamic Hybrid Model with Generalization Performance to Solve Large-Scale TSP

作　　者：柯琳 杨笑笑 陈智斌[1] KE Lin;YANG Xiaoxiao;CHEN Zhibin(Faculty of Science,Kunming University of Science and Technology,Kunming 650000)

机构地区：[1]昆明理工大学理学院,昆明650000

出　　处：《系统科学与数学》2024年第1期31-44,共14页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(11761042,12361065)资助课题.

摘　　要：旅行商问题(TSP)是组合最优化中的典型问题,求解TSP问题的现实意义重大.随着深度强化学习(DRL)在工业界的广泛应用,利用DRL模型自动设计学习算法成为近期的研究热点.为提升DRL模型在大范围TSP问题上的泛化能力,文章提出一种动态图卷积网络编码和空间注意力机制解码的混合模型求解大范围TSP问题.动态图卷积模块可以动态编码节点信息,从而有效地更新每个节点的隐藏层状态;空间注意力有利于捕捉节点之间的全局联系,进而通过加权所有局部特征计算和提取关键特征.实验结果表明文章模型将TSP50的训练策略泛化至TSP250/500/750/1000时的优化性能超越了先前DRL模型,且在TSPlib标准数据集上的测试结果也显示出模型对优化性能的提升.Traveling salesman problem(TSP)is a typical problem in combinatorial optimization,and the relevance of solving the TSP is significant.Using deep reinforcement learning(DRL)models to automatically design learning algorithms has become a recent research hotspot as DRL is widely used in industry.In order to enhance the generalization ability of the DRL model on the large-scale TSP,this paper proposes a hybrid model of dynamic graph convolutional network to encode and spatial attention mechanism to decode for tackling the large-scale TSP.Dynamic graph convolution module can dynamically encode node information so as to efficiently update the hidden layer state of each node.Spatial attention facilitates capturing the global connections between nodes,and then calculating and extracting key features by weighting all local features.Experimental results show that our model outperforms the previous DRL model for optimization when generalizing the training strategy of TSP50 to TSP250/500/750/1000,and the test results on the standard dataset of TSPlib also show the improvement of the model for optimization performance.

关 键 词：旅行商问题 深度强化学习 动态图卷积网络 空间注意力 组合最优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O224[自动化与计算机技术—控制科学与工程]