Limitations of neural networks for solving traveling salesman problems

摘要

Feedback neural networks enjoy considerable popularity as a means of approximately solving combinatorial optimization problems. It is now well established how to map problems onto networks so that invalid solutions are never found. It is not as clear how the networks' solutions compare in terms of quality with those obtained using other optimization techniques; such issues are addressed in this paper. A linearized analysis of annealed network dynamics allows a prototypical network solution to be identified in a pertinent eigenvector basis. It is possible to predict the likely quality of this solution by examining optimal solutions in the same basis. Applying this methodology to traveling salesman problems, it appears that neural networks are well suited to the solution of Euclidean but not random problems; this is confirmed by extensive experiments. The failure of a network to adequately solve even 10-city problems is highly significant.