Solving the traveling salesman problem using a recurrent neural network
Mikhail Sergeevich Tarkov
A.V. Rzhanov’s Institute of Semiconductor Physics SB RAS, Novosibirsk
Keywords: traveling salesman problem, recurrent neural Hopfield network, 2-opt, CUDA technology, LKH algorithm
Abstract
A new algorithm (NWTA-algorithm) for solving the traveling salesman problem (TSP) is proposed. The algorithm is based on the use of the Hopfield recurrent neural network, the WTA method (“Winner takes all”) for the cycle formation, and 2-opt optimization method. A special feature of the algorithm proposed is in the use of the method of partial (prefix) sums to accelerate the solution of the system of the Hopfield network equations. For attaining additional acceleration, the parallelization of the algorithm proposed is performed on GPU with the CUDA technology. Several examples from the TSPLIB library with the number of cities from 51 to 2,392 show that the algorithm proposed finds approximate solutions of the TSP (a relative increase in the length of the route with respect to the optimum is 0.03 ÷ 0.14). With a large number of cities (130 and more) the NWTA-algorithm running duration on the CPU is in 4 ÷ 24 times less than the duration of the heuristic LKH algorithm giving optimal solutions for all TSPLIB examples.
|
