基于图卷积和注意力神经网络的旅行商问题新解法
New Solution for Traveling Salesman Problem Based on Graph Convolution and Attention Neural Network
韦念念 1韩曙光1
作者信息
- 1. 浙江理工大学理学院 杭州 310018
- 折叠
摘要
旅行商问题是一个经典的组合优化问题.为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能.对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例.发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022s,0.0178s,1.7643s,2.3074s和2.053 8s.因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中.
Abstract
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 neu-ral 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 trave-ling 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.002 2s,0.017 8 s,1.764 3 s,2.307 4 s,and 2.053 8 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 prob-lem instances with larger training scales.
关键词
旅行商问题/图卷积神经网络/注意力网络/分支定界算法/监督学习Key words
Traveling salesman problem/Graph convolutional neural network/Attention neural network/Branch and bound algo-rithm/Supervised learning引用本文复制引用
出版年
2024
NETL
NSTL
万方数据