Application of a Modified Hopfield Network to the Travelling Salesman Problem
Zbigniew Nagórny
The John Paul II Catholic University of Lublin , PolandAbstract
The travelling salesman problem (TSP) is a classical example of a combinatorial optimization problem. The aim of this work is to find Hopfield network modifications, which could be efficiency used for solving the TSP. A novel method of auto-tuning of the network parameters is presented. This method ensures near optimal results for randomly generated instances of the 10-city TSP. The presented network is destined for hardware implementation, which could significantly decrease computation time in comparison with programs executed on sequential computers.
Keywords:
Automatic selection of parameters, combinatorial optimization, traveling salesman problem, Hopfield networkReferences
Brandt R.D., Wang Y., Laub A.J., Mitra S.K., Alternative networks for solving the traveling salesman problem and the list-matching problem, [w:] Proceeding of the International Joint Conference on Neural Networks 1988, vol. 2.
Dorigo M., Gambardella L.M., Ant colonies for the travelling salesman problem, “BioSystems” 1997, vol. 43.
Durbin R., Willshaw D., An analogue approach to the travelling salesman problem using an elastic net method, “Nature” 1987, vol. 326.
Hopfield J.J., Tank D.W., “Neural” computation of decisions in optimization problems, “Biological Cy- bernetics” 1985, vol. 52.
Kirkpatrick S., Gelatt C.D., Jr., Vecchi M.P., Optimization by simulated annealing, “Science” 1983, vol. 220.
Kos A., Nagórny Z., Modified Hopfield Neural Network for Travelling Salesman Problem, [w:] Pro- ceedings of the 2nd Conference Tools of Information Technology, Rzeszów 2007, http://www.te- leinformatyka.net.pl/nti/papers/Kos_Nagorny_NTI_2007.pdf (28.10.2010).
Mańdziuk J., Sieci neuronowe typu Hopfielda. Teoria i przykłady zastosowań, AOW EXIT, Warszawa 2000.
Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 1996.
Michalewicz Z., Fogel D.B., How to solve it: modern heuristics, Springer, Berlin–New York 2004.
Tadeusiewicz R., Sieci neuronowe, AOW, Warszawa 1993.
Wilson G.V., Pawley G.S., On the stability of the travelling salesman problem algorithm of Hopfield and Tank, “Biological Cybernetics” 1988, vol. 58.
The John Paul II Catholic University of Lublin
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License.
