Solving the traveling salesman problem using a recurrent neural network

被引：4

作者：

Tarkov M.S. ^{[1
]}

机构：

[1] Rzhanov Institute of Semiconductor Physics, Siberian Branch, Russian Academy of Sciences, pr. Akad. Lavrent’eva 13, Novosibirsk

来源：

Numerical Analysis and Applications | 2015年 / 8卷 / 03期

关键词：

2-opt; CUDA technology; LKH algorithm; recurrent neural Hopfield network; traveling salesman problem;

D O I：

10.1134/S1995423915030088

中图分类号：

学科分类号：

摘要：

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 “Winner takes all” (WTA) method for the cycle formation, and the 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 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 4 ÷ 24 times shorter than the duration of the heuristic LKH algorithm giving optimal solutions for all TSPLIB examples. © 2015, Pleiades Publishing, Ltd.

引用

页码：275 / 283

页数：8

共 15 条

[1]

Lin S., Kernighan B.W., An Effective Heuristic Algorithm for the Traveling Salesman Problem, Oper. Res., 21, 2, pp. 498-516, (1973)

[2]

Helsgaun K., An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, Eur. J. Oper. Res., 126, pp. 106-130, (2000)

[3]

Helsgaun K., General k-opt Submoves for the Lin-Kernighan TSP Heuristic, Math. Prog. Comp., 1, pp. 119-163, (2009)

[4]

Efimov V.V., Kozyrev G.I., Et al., Nejrokomp’yutery v kosmicheskoj tekhnike, (2004)

[5]

Hopfield J.J., Tank D.W., Neural” Computation of Decisions in Optimization Problems, Biol. Cyber., 52, 3, pp. 141-152, (1985)

[6]

Smith K.A., Neural Networks for Combinatorial Optimization: A Review of More than a Decade of Research, INFORMS J. Comp., 11, 1, pp. 15-34, (1999)

[7]

Feng G., Douligeris C., Using Hopfield Networks to Solve Traveling Salesman Problems Based on Stable State Analysis Technique, Proc. Int. Joint Conf. Neural Networks, 6, pp. 521-526, (2000)

[8]

Ageev A.D., Balukhto A.N., Bychkov A.V., Et al., Nejromatematika, (2002)

[9]

Wang J., Analysis and Design of a Recurrent Neural Network for Linear Programming, IEEE Trans. Circuits Systems-I: Fund. Th. Appl., 40, 9, pp. 613-618, (1993)

[10]

Hung D.L., Wang J., Digital Hardware Realization of a Recurrent Neural Network for Solving the Assignment Problem, Neurocomp., 51, pp. 447-461, (2003)

← 1 2 →