Abstract for gee_tr77

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

NEURAL NETWORKS AND COMBINATORIAL OPTIMIZATION PROBLEMS --- THE KEY TO A SUCCESSFUL MAPPING

Andrew H. Gee, Sreeram V. B. Aiyer and Richard W. Prager

July 1991

For several years now there has been much research interest in the use of Hopfield networks to solve combinatorial optimization problems. Although initial results were disappointing, it has since been demonstrated how modified network dynamics and better problem mapping can greatly improve the solution quality. The aim of this paper is to build on this progress by presenting a new analytical framework in which problem mappings can be evaluated without recourse to purely experimental means. A linearized analysis of the Hopfield network's dynamics forms the main theory of the paper, followed by a series of experiments in which some problem mappings are investigated in the context of these dynamics. In all cases the experimental results are compatible with the linearized theory, and observed weaknesses in the mappings are fully explained within the framework. What emerges is a largely analytical technique for evaluating candidate problem mappings, without having to resort to the more usual trial and error.


(ftp:) gee_tr77.ps.Z (http:) gee_tr77.ps.Z
PDF (automatically generated from original PostScript document - may be badly aliased on screen):
  (ftp:) gee_tr77.pdf | (http:) gee_tr77.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.