Geodesic
Solving the traveling salesman problem using a~recurrent neural network
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 18 (2015) no. 3, pp. 337-347.

Voir la notice de l'article provenant de la source Math-Net.Ru

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\div0.14$). With a large number of cities (130 and more) the NWTA-algorithm running duration on the CPU is in $4\div24$ times less than the duration of the heuristic LKH algorithm giving optimal solutions for all TSPLIB examples. 
@article{SJVM_2015_18_3_a7,
     author = {M. S. Tarkov},
     title = {Solving the traveling salesman problem using a~recurrent neural network},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {337--347},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2015_18_3_a7/}
}
TY  - JOUR
AU  - M. S. Tarkov
TI  - Solving the traveling salesman problem using a~recurrent neural network
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2015
SP  - 337
EP  - 347
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2015_18_3_a7/
LA  - ru
ID  - SJVM_2015_18_3_a7
ER  - 
%0 Journal Article
%A M. S. Tarkov
%T Solving the traveling salesman problem using a~recurrent neural network
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2015
%P 337-347
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2015_18_3_a7/
%G ru
%F SJVM_2015_18_3_a7
M. S. Tarkov. Solving the traveling salesman problem using a~recurrent neural network. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 18 (2015) no. 3, pp. 337-347. http://geodesic.mathdoc.fr/item/SJVM_2015_18_3_a7/

[1] Lin S., Kernigan B. W., “An effective heuristic algorithm for the travelling salesman problem”, Oper. Res., 21:2 (1973), 498–516 | DOI | MR | Zbl

[2] Helsgaun K., “An effective implementation of the Lin–Kernighan traveling salesman heuristic”, European J. of Oper. Res., 126 (2000), 106–130 | DOI | MR | Zbl

[3] Helsgaun K., “General $k$-opt submoves for the Lin–Kernighan TSP heuristic”, Math. Prog. Comp., 1 (2009), 119–163 | DOI | MR | Zbl

[4] LKH Version 2.0.7, , November, 2012 http://www.akira.ruc.dk/~keld/research/LKH/lkh.exe

[5] TSPLIB, http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html

[6] Efimov V. V., Kozyrev G. I. i dr., Nejrokomp'yutery v kosmicheskoj tekhnike, Kn. 17, ed. V. V. Efimov, Radiotekhnika, M., 2004

[7] Hopfield J. J., Tank D. W., “ ‘Neural’ computation of decisions in optimization problems”, Biological Cybernetics, 52:3 (1985), 141–152 | MR | Zbl

[8] Smith K. A., “Neural networks for combinatorial optimization: a review of more than a decade of research”, INFORMS J. on Computing, 11:1 (1999), 15–34 | DOI | MR | Zbl

[9] 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 (2000), 521–526

[10] Ageev A. D., Balukhto A. N., Bychkov A. V. i dr., Nejromatematika, Kn. 6, ed. A. I. Galushkin, IPRZhR, M., 2002

[11] Wang J., “Analysis and design of a recurrent neural network for linear programming”, IEEE Trans. On Circuits and Systems-I: Fundamental Theory and Applications, 40:9 (1993), 613–618 | DOI | Zbl

[12] Hung D. L., Wang J., “Digital hardware realization of a recurrent neural network for solving the assignment problem”, Neurocomputing, 51 (2003), 447–461 | DOI

[13] Siqueira P. H., Steiner M. T. A., Scheer S., “A new approach to solve the travelling salesman problem”, Neurocomputing, 70 (2007), 1013–1021 | DOI

[14] Tarkov M. S., Dugarov G. A., “Parallel'nyj algoritm resheniya zadachi kommivoyazhera s ispol'zovaniem rekurrentnoj nejronnoj seti”, Problemy informatiki, 2010, no. 2, 4–9

[15] Tarkov M. S., “Postroenie gamil'tonovykh tsiklov v grafakh raspredelennykh vychislitel'nykh sistem rekurrentnymi nejronnymi setyami”, Sib. zhurn. vychisl. matematiki (Novosibirsk), 13:4 (2010), 467–475 | Zbl

[16] Tarkov M. S., “Ob effektivnosti postroeniya gamil'tonovykh tsiklov v grafakh raspredelennykh vychislitel'nykh sistem rekurrentnymi nejronnymi setyami”, Upravlenie bol'shimi sistemami, 43, IPU RAN, M., 2013, 157–171

[17] Boreskov A. V., Kharlamov A. A., Osnovy raboty s tekhnologiej CUDA, DMK Press, M., 2011