Title :
Hopfield-style neural networks and the TSP
Author :
Wolfe, William J. ; Parry, Michael H. ; MacMillan, James M.
Author_Institution :
Campus Box 109, Colorado Univ., Denver, CO, USA
fDate :
27 Jun-2 Jul 1994
Abstract :
We describe the results of our travelling salesman problem (TSP) neural model, using a linearization of the Hopfield model and an orthogonal projection onto the feasible subspace, including the definition of a region of parameter space that ensures exclusive convergence to tours. Our TSP results are relatively good for up to 30 cities, achieving a large number of optimal tours, but scaling remains a problem. For a particular 100 city problem the results are not very good, giving tours that are 80-90% longer than the optimal tour. We compare the performance of the network to the sequential nearest city algorithm, and provide several ideas for improving the performance of the network, including a divide and conquer approach. The relationship of TSP networks to lateral inhibition networks is also described
Keywords :
Hopfield neural nets; convergence of numerical methods; operations research; optimisation; travelling salesman problems; Hopfield neural networks; convergence; divide and conquer approach; orthogonal projection; parameter space; scaling; sequential nearest city algorithm; travelling salesman problem neural model; CADCAM; Cities and towns; Computer aided manufacturing; Convergence; Hardware; Hopfield neural networks; Knowledge representation; Neural networks; Parallel algorithms; Traveling salesman problems;
Conference_Titel :
Neural Networks, 1994. IEEE World Congress on Computational Intelligence., 1994 IEEE International Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-1901-X
DOI :
10.1109/ICNN.1994.375012
