Annealing Networks and Fractal Landscapes

[Raymond Lister]

A postscript file containing the following paper has been placed in the
neuroprose archive, as lister.anneal.ps.Z ...


               Annealing  Networks  and  Fractal  Landscapes

                               Raymond Lister
                      Dept. of Electrical Engineering,
		         University of Queensland QLD 4072,
				 Australia

			   ray at s1.elec.uq.oz.au


                                  Abstract

It is well known that Hopfield and Tank networks give poor solutions to
the Traveling Salesman Problem; but we show that the popular explanation
for the poor performance is either wrong, or at best incomplete.  The
popular explanation is that the network has difficulty in balancing the
trade-off between the path length and the legality components of the
energy function.  We first describe an experiment which has an outcome
that is not accounted for by this explanation.  We then propose an
alternative: these networks would scale better if their dynamics
effectively implemented a "divide-and-conquer" strategy.  That is, if
they recursively decomposed the problem into smaller independent
sub-problems.  An annealing network can do so if the energy landscape has
a self-similar "quasi-fractal" structure.  We believe this proposition
applies to both discrete and analog networks.  We support our proposition
by describing results from our work on the Traveling Salesman Problem.
We then consider the implications for two other optimization problems:
graph bisection and coloring.  


Here is an example of how to retrieve this file:

> ftp archive.cis.ohio-state.edu        (or ftp 128.146.8.52)
Connected to archive.cis.ohio-state.edu.
220 archive.cis.ohio-state.edu FTP server ready.
Name: anonymous
331 Guest login ok, send ident as password.
Password:<type your email address here>
230 Guest login ok, access restrictions apply.
ftp> binary
200 Type set to I.
ftp> cd pub/neuroprose
250 CWD command successful.
ftp> get lister.anneal.ps.Z
200 PORT command successful.
150 Opening BINARY mode data connection for lister.anneal.ps.Z
226 Transfer complete.
ftp> quit
221 Goodbye.
> uncompress lister.anneal.ps.Z
> lpr lister.anneal.ps