Technical Report Available

[THEPCAP%SELDC52.BITNET@VMA.CC.CMU.EDU]

                                                                     LU TP 89-1



  A NEW METHOD FOR MAPPING OPTIMIZATION PROBLEMS ONTO NEURAL NETWORKS

              Carsten Peterson and Bo Soderberg

     Department of Theoretical Physics, University of Lund
             Solvegatan 14A, S-22362 Lund, Sweden


       Submitted to International Journal of Neural Systems



ABSTRACT:

A novel modified method for obtaining approximate solutions to difficult
optimization problems within the neural network paradigm is presented. We
consider the graph partition and the travelling salesman problems. The key
new ingredient is a reduction of solution space by one dimension by using
graded neurons, thereby avoiding the destructive redundancy that has plagued
these problems when using straightforward neural network techniques. This
approach maps the problems onto Potts glass rather than spin glass theories.

A systematic prescription is given for estimating the phase transition
temperatures in advance, which facilitates the choice of optimal parameters.
This analysis, which is performed for both serial and synchronous updating of
the mean field theory equations, makes it possible to consistently avoid
chaotic bahaviour.

When exploring this new technique numerically we find the results very
encouraging; the quality of the solutions are in parity with those obtained
by using optimally tuned simulated annealing heuristics. Our numerical study,
which extends to 200-city problems, exhibits an impressive level of parameter
insensitivity.


----------
For copies of this report send a request to THEPCAP at SELDC52 [don't forget
to give your mailing address].