基于图卷积和注意力神经网络的旅行商问题新解法  

New Solution for Traveling Salesman Problem Based on Graph Convolution and Attention Neural Network

作　　者：韦念念 韩曙光[1] WEI Niannian;HAN Shuguang(School of Science,Zhejiang Sci-Tech University,Hangzhou 310018,China)

机构地区：[1]浙江理工大学理学院,杭州310018

出　　处：《计算机科学》2024年第S01期210-217,共8页Computer Science

基　　金：国家自然科学基金(12071436)。

摘　　要：旅行商问题是一个经典的组合优化问题。为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能。对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例。发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022 s,0.0178 s,1.7643 s,2.3074 s和2.0538 s。因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中。Traveling salesman problem is a classic combinatorial optimization problem.To solve the problem quickly,a learning branch rule is designed,which is based on a deep learning model composed of graph embedding network,graph convolutional neural network,attention neural network and multi-layer perceptron,and the traditional branch and bound algorithm is modified to improve the algorithm performance.Traveling salesman problem instances of 15 cities are supervised and trained,and the traveling salesman problem instances of 10,15,20,25 and 30 cities are tested on the SCIP solver respectively.We find that the solution time of the branch and bound algorithm based on learning branch rule is-0.0022 s,0.0178 s,1.7643 s,2.3074 s,and 2.0538 s faster than that of the algorithm based on traditional branch rules,respectively.Therefore,the selection of branch variables based on graph neural networks is effective in improving traditional branch rules and can be well normalized to traveling salesman problem instances with larger training scales.

关 键 词：旅行商问题 图卷积神经网络 注意力网络 分支定界算法 监督学习 

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