基于Transformer的旅行商问题解法

在针对旅行商问题(Travelling Salesman Problem)的近似求解算法中,传统启发式算法收敛速度较慢,准确性较低。为解决上述问题,该文提出一种基于Transformer的神经网络方法。该方法使用神经网络,可有效提高近似解的求解速度和准确性,并使用Transformer注意力机制全面提高神经网络的性能。该方法使用强化学习进行训练,使用束搜索算法进行搜索。使用该方法对随机50节点的旅行商问题进行测试,试验结果表明该种基于Transformer的旅行商问题解法,可在较低的复杂度前提下,得到近似于精确解的效果。

In approximate solutions to the traveling salesman problem(TSP),traditional heuristic algorithms are known for their slow convergence speed and low accuracy.To address these issues,this paper proposes a neural network approach based on Transformers.This method utilizes neural networks to effectively improve the speed and accuracy of approximate solutions,while leveraging the Transformer's attention mechanism to enhance the overall performance of the neural network.This method uses reinforcement learning for training and beam search algorithm for search.This method is used to test the random 50-node traveling salesman problem,and the experimental results show that the solution of the traveling salesman problem based on Transformer can get the effect which is similar to the exact solution under the premise of low complexity.