Newsgroups: comp.ai.neural-nets
Path: utzoo!utgpu!jarvis.csri.toronto.edu!csri.toronto.edu!songw
From: songw@csri.toronto.edu (Wenyi Song)
Subject: Re: implementation of "traveling salesman algorithm" on CM
Message-ID: <8902070440.AA02663@russell.csri.toronto.edu>
Keywords: TSP, Hopfield's work
Organization: University of Toronto, CSRI
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU>
Date: Mon, 6 Feb 89 23:40:53 EST

In article <1233@usfvax2.EDU> pollock@usfvax2.UUCP (Wayne Pollock) writes:
>In article <1637@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi) writes:
>
>Funny you should ask; we spent an entire lecture today discussing this
>very problem in my Parallel Processing and Distributed Computing class.
>The short answer is for M cities, an M X M neural network can find very
>close to optimal solutions in a very short time.  In AT&T Bell Labs, I've
>heard that they have designed hardware, had it manufactured, and used it
>to find the solution for a large problem.  The whole time used (including
						^^^^^^^^^^^^^^^^^^^^^^^^^^
>manufaturing the chip) was less than the time it took using traditional
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>methods on a Cray-1!  (I am assuming that if the story is true, the
^^^^^^^^^^^^^^^^^^^^
>Cray-1 method found an optimal solution; even so, this is impressive!)
>Hopfield and Tank[1985] describe a case involving over 100 cities in which
							^^^^^^^^^^
>a neural network computes a solution which is only a fraction of 1% longer
>than the optimal solution, in only a few milliseconds of computation.  They
>remark that it would have taken weeks to have found an optimal solution
>even using a Cray.
>

I gather what you referred to is

J. J. Hopfield and D. W. Tank, "Neural" Computation of Decisions in
		Optimization Problems, Biological Cybernetics, 52, 141-152, 1985

If that's the case, then ...

They showed simulation results of the 10-city problem. It needs 100 neurons.
They also showed some simulation results of the 30-city problem, which requires
900 neurons. But nothing about the 100 city problem.

Not only the simulation of the 100-city problem is difficult, in terms of
computing time cost, but also the hardware implementation of their orginal
model. This is because it needs 10,000 neurons. If they are fully inter-
connected, then you have to put another (100,000,000 - 10,000) synapses into
the chip. For comparison, DRAM is probably just reaching the density of 64 Mbits
in a chip.


So how about the comparison in terms of speed? Let's look at the well known
Lin-Kernighan algorithm.

S. Lin and B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling-
		Salesman Problem, Operations Research, 21, 498-516, 1973

As reported, a typical 100-city problem requires about three minutes on their
GE635 computer to obtain the optimum with above 95% confidence. Note they
didn't use a Cray-1.

Note we should conduct a fair comparison. If one insists on using Gray to
enumerate all possible paths for the TSP problem, then ...