Accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem
Zbigniew Nagórny
The John Paul II Catholic University of Lublin , PolandAbstract
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 (TSP) because the advantages of using the Hopfield network in this problem are mainly possible in case of the hardware implementation of the network. 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 presented in this work 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.
Keywords:
automatic selection of parameters, combinatorial optimization, vehicle routing, equipment realization of neural networks, Hopfield networkReferences
M. Glesner, W. Pöchmüller, Neurocomputers. An overview of neural networks in VLSI, London 1994, Chapman & Hall.
J. J. Hopfield, D. W. Tank, “Neural” computation of decisions in optimization problems, “Biological Cybernetics” 1985, vol. 52, ss. 141-152.
A. Kos, Z. Nagórny, Modified Hopfield Neural Network for Travelling Salesman Problem, [w:] Proceedings of the 2nd Conference Tools of Information Technology, Rzeszów 2007, ss. 17-22.
Z. Nagórny, Zastosowanie zmodyfikowanej sieci Hopfielda w problemie komiwojażera, „Przegląd Prawno-Ekonomiczny” 2010, nr 13 (4/2010), ss. 73-80.
J. A. Lansner, T. Lehmann, An Analog CMOS Chip Set for Neural Networks with Arbitrary Topologies, “IEEE Transactions on Neural Networks” 1993, vol. 4, ss. 441-444.
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.
