Search Contact information
University of Cambridge Home Department of Engineering
University of Cambridge > Engineering Department > Machine Intelligence Lab

Abstract for aiyer_tr55

Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR55

A SUBSPACE APPROACH TO SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS WITH HOPFIELD NETWORKS

Sreeram V. B. Aiyer and Frank Fallside

January 1991

This paper extends and generalizes the subspace analysis of the Hopfield Network presented in our earlier work [IEEE trans. NN. 6/90]. In [IEEE trans. NN. 6/90] it was shown that the ability of the Hopfield Network to confine a vector within a particular subspace was essential to the network's ability to reach valid solutions to the Travelling Salesman problem. Through the use of Kronecker (Tensor) products, this paper shows how an analogous subspace can be constructed for a much larger class of combinatorial optimization problems. By using the form of this subspace as the basis for determining the elements of the network connection matrix, convergence to a valid solution can be guaranteed. Further, the quality of the final solution is significantly improved. This is confirmed by benchmark experiments using 30 and 50 city Travelling Salesman problems as an illustrative example. These indicate that the network can reliably and efficiently achieve solutions within 2\% of the global optimum.

NB New version created 4May98 with fixes for postscript bugs in original


(ftp:) aiyer_tr55.ps.Z (http:) aiyer_tr55.ps.Z
PDF (automatically generated from original PostScript document - may be badly aliased on screen):
  (ftp:) aiyer_tr55.pdf | (http:) aiyer_tr55.pdf

If you have difficulty viewing files that end '.gz', which are gzip compressed, then you may be able to find tools to uncompress them at the gzip web site.

If you have difficulty viewing files that are in PostScript, (ending '.ps' or '.ps.gz'), then you may be able to find tools to view them at the gsview web site.

We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.

© 2005 Cambridge University Engineering Dept
Information provided by milab-maintainer