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

Volume

7

fYear

1994

fDate

27 Jun-2 Jul 1994

Firstpage

4577

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICNN.1994.375012

Filename

375012