Accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem

• Autorzy: Nagórny Z.
• Języki publikacji: EN

Abstrakty

EN

The objective of this work was to study the accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem. In this work the 8-bit accuracy influence of the hardware implementation of weights, activation functions, and external input signals on the quality of achieved solutions for 100 randomly generated instances of the 10-city TSP was studied and comparable results in comparison with the simulation in which the network was simulated using double precision floating point numbers were obtained. The results show that the hardware implementation of the Hopfield network with the 8-bit accuracy allows to obtain satisfactory solutions for the TSP. It should be also noted that the network described in this work utilizes the novel method of auto-tuning of Hopfield network parameters and thanks to this method, in contrast to other works, none of the network parameters is tuned for a given solved TSP on the basis of preliminary simulations. The Hopfield network presented in this work is destined for the hardware implementation. The application of the hardware implementation of the network could significantly decrease the time required to obtain the combinatorial problem solution in comparison with methods using von Neumann architecture computers.

Słowa kluczowe

EN

combinatorial optimization; hardware implementation of neural networks; Hopfield network; parameter auto-tuning; travelling salesman problem

PL

optymalizacja kombinatoryczna; implementacja sprzętowa sieci neuronowej; sieć Hopfielda; samodostrajanie parametru; problem komiwojażera

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2012
• Tom: Vol. 20, nr 1
• Strony: 51--67
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Nagórny Z.

• The John Paul II Catholic University of Lublin Off-Campus Faculty of Law and Economic Sciences in Stalowa Wola ul. Ofiar Katynia 6a, 37-450 Stalowa Wola, Poland,

Bibliografia

• [1] Tadeusiewicz, R., Using Neural Models for Evaluation of Biological Activity of Selected Chemical Compounds, In: Applications of Computational Intelligence in Biology, Current Trends and Open Problems, Studies in Computational Intelligence, edited by T. G. Smolinski, M. G. Milanova, and A.-E. Hassanien, Springer-Verlag, Berlin, Heidelberg, New York, 2008, pp. 135- 159.
• [2] Szaleniec, M., Tadeusiewicz, R., and Witko, M., How to select an optimal neural model of chemical reactivity? Neurocomputing, Vol. 72, 2008, pp. 241-256.
• [3] Tadeusiewicz, R., Neural network as a tool for medical signals filtering, diagnosis aid, therapy assistance and forecasting improving, In: IFMBE Proceedings, Vol. IV: Image processing, biosignals processing, modelling and simulation, biomechanics, edited by O. Dössel andW. C. Schlegel, Springer- Verlag, Berlin, Heidelberg, New York, 2009, pp. 1532-1534.
• [4] Tadeusiewicz, R., Using Neural Networks for Simplified Discovery of Some Psychological Phenomena, In: Artificial Intelligence and Soft Computing, Springer-Verlag, Berlin, Heidelberg, New York, 2010, pp. 104-123.
• [5] Durbin, R. and Willshaw, D., An analogue approach to the travelling salesman problem using an elastic net method, Nature, Vol. 326, 1987, pp. 689- 691.
• [6] Hopfield, J. J. and Tank, D. W., "Neural" computation of decisions in optimization problems, Biological Cybernetics, Vol. 52, 1985, pp. 141-152.
• [7] Michalewicz, Z. and Fogel, D. B., How to solve it: modern heuristics, Springer, 2004.
• [8] Tadeusiewicz, R., New Trends in Neurocybernetics, Computer Methods in Materials Science, Vol. 10, No. 1, 2010, pp. 1-7.
• [9] Kirkpatrick, S., Gelatt, C. D. J., and Vecchi, M. P., Optimization by simulated annealing, Science, Vol. 220, 1983, pp. 671-680.
• [10] Michalewicz, Z., Genetic algorithms + data structures = evolution programs, Springer-Verlag, 1996.
• [11] Dorigo, M. and Gambardella, L. M., Ant colonies for the travelling salesman problem, BioSystems, Vol. 43, 1997, pp. 73-81.
• [12] Kos, A. and Nagórny, Z., Modified Hopfield Neural Network for Travelling Salesman Problem, In: Proceedings of the 2nd Conference Tools of Information Technology, Rzeszów, Poland, 2007, pp. 17-22.
• [13] Nagórny, Z., Application of a Modified Hopfield Network to the Traveling Salesman Problem, Economics and Organization of Enterprise, Vol. 6, 2009, pp. 58-66.
• [14] Wilson, G. V. and Pawley, G. S., On the stability of the travelling salesman problem algorithm of Hopfield and Tank, Biological Cybernetics, Vol. 58, 1988, pp. 63-70.
• [15] Brandt, R. D., Wang, Y., Laub, A. J., and Mitra, S. K., 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, 1988, pp. 333-340.
• [16] Kamgar-Parsi, B. and Kamgar-Parsi, B., On problem solving with Hopfield neural networks, Biological Cybernetics, Vol. 62, 1990, pp. 415-423.
• [17] Glesner, M. and Pöchmüller, W., Neurocomputers. An overview of neural networks in VLSI, Chapman & Hall, 1994.
• [18] Lansner, J. A. and Lehmann, T., An Analog CMOS Chip Set for Neural Networks with Arbitrary Topologies, IEEE Transactions on Neural Networks, Vol. 4, 1993, pp. 441-444.