Application of a Modified Hopfield Network to the Traveling Salesman Problem

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.