Application of a Modified Hopfield Network to the Traveling Salesman Problem

• Autorzy: Zbigniew Nagórny
• Języki publikacji: EN

Abstrakty

EN

This paper presents the results of the application of the modified Hopfield network to the travelling salesman problem (TSP). A cost function of the TSP consists of four components: two terms which ensure that the salesman's tour is valid, the term which forces neurons to have the output signal equal to 0 or 1, and the total length of the salesman's tour. For two 10-city benchmarks the average tour length of obtained solutions is equal to the optimal tour length. Other works did not report such results using the classical Hopfield network. For greater numbers of cities, the solution quality is significantly better in comparison with the quality of results achieved in other works. The method of auto-tuning of the constant in the fourth component of the cost function is presented. This method ensures very good quality results for randomly generated instances of the 10-city TSP. The presented network is destined for hardware implementation. (original abstract)

Słowa kluczowe

EN

Sale; Sales analysis; Optimalization; Artificial neural networks method

PL

Sprzedaż; Analiza sprzedaży; Optymalizacja; Metoda sztucznych sieci neuronowych

• Czasopismo: Economics and Organization of Enterprise
• Rocznik: 2009
• Tom: 6
• Numer: nr 4
• Strony: 58--66

Twórcy

autor

Zbigniew Nagórny

Bibliografia

• Brandt RD, Wang Y, Laub AJ, Mitra SK (1988) Alternative networks for solving the traveling salesman problem and the list-matching problem. In: Proceeding of the International Joint Conference on Neural Networks, vol. 2. pp 333-340
• Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. BioSystems 43:73-81
• Durbin R, Willshaw D (1987) An analogue approach to the travelling salesman problem using an elastic net method. Nature 326:689-691
• Freeman JA, Skapura DM (1991) Neural networks: algorithms, applications, and programming techniques. Addison-Wesley, Reading
• Hertz J, Krogh A, Palmer RG (1991) Introduction to the theory of neural computation. Addison-Wesley, Redwood City
• Hopfield JJ, Tank DW (1985) "Neural" computation of decisions in optimization problems. Biological Cybernetics 52:141-152
• Kamgar-Parsi B, Kamgar-Parsi B (1990) On problem solving with Hopfield neural networks. Biological Cybernetics 62:415-423
• Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671-680
• Li SZ (1996) Improving convergence and solution quality of Hopfield-type neural networks with augmented Lagrange multipliers. IEEE Transactions on Neural Networks 7:1507-1516
• Mańdziuk J (2000) Hopfield-type neural networks. Theory and applications. AOW EXIT, Warsaw (in Polish)
• Mańdziuk J (2000) Optimization with the Hopfield network based on correlated noises: Experimental approach. Neurocomputing 30:301-321
• Mańdziuk J (1996) Solving the travelling salesman problem with the Hopfield-type neural network. Demonstratio Mathematica 29:219-231
• Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs. Springer-Verlag, Berlin, New York
• Michalewicz Z, Fogel DB (2004) How to solve it: modern heuristics. Springer, Berlin, New York
• Nagórny Z, Kos A (2005) Optimization by using a modified Hopfield network. Electronics and Telecommunications Quarterly 51:255-275 (in Polish)
• Pham DT, Karaboga D (2000) Intelligent optimisation techniques. Springer, London, New York
• Qu H, Yi Z, Tang H (2006) Improving local minima of columnar competitive model for TSPs. IEEE Transactions on Circuits and Systems-I 53:1353-1362
• Reinelt G (1995) TSPLIB 95 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/
• Tadeusiewicz R (1993) Neural networks. AOW, Warsaw (in Polish)
• Van den Bout DE, Miller TK III (1989) Improving the performance of the Hopfield-Tank neural network through normalization and annealing. Biological Cybernetics 62:129-139
• Wilson GV, Pawley GS (1988) On the stability of the travelling salesman problem algorithm of Hopfield and Tank. Biological Cybernetics 58:63-70
• Zurada JM (1992) Introduction to artificial neural systems. West, St. Paul

Identyfikatory

DOI

10.2478/v10061-010-0028-z