Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!amdcad!sun!pitstop!sundc!seismo!uunet!merk!alliant!linus!sdo
From: sdo@linus.UUCP (Sean D. O'Neil)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Summary: Let's all use our brains
Keywords: TSP, connection machine
Message-ID: <44608@linus.UUCP>
Date: 8 Feb 89 01:52:33 GMT
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU> <6173@phoenix.Princeton.EDU> <18090@glacier.STANFORD.EDU>
Reply-To: sdo@faron.UUCP (Sean D. O'Neil)
Distribution: usa
Organization: The MITRE Corporation, Bedford MA
Lines: 47

In article <18090@glacier.STANFORD.EDU> jbn@glacier.STANFORD.EDU (John B. Nagle) writes:
>In article <1233@usfvax2.EDU> pollock@usfvax2.UUCP (Wayne Pollock) writes:
>>(Quoted without permission from my class notes (by Dr. Stark:)
>>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.
>
>...  Comparing
>the time required to find a near-optimum solution with a hardware neural
>net to that required to find an optimal solution on a Cray is misleading,
>if not fraudulent.  While finding an optimal solution is expensive,
>finding a near-optimal solution on a digital computer is quite efficient.  
>I can get solutions for a 100-node network on an IBM PC/AT (6MhZ!) in well 
>under two minutes, using the Bell Labs algorithm.  This is the right result 
>to compare with the neural net, not the brute-force optimal solution.


Bravo!  Finally someone brings some sense into this discussion.  John
is absolutely right about this.  In point of fact, there are very good
reasons NOT to use Hopfield and Tank's neural net solution to the TSP
aside from the fact that Lin and Kernighan's algorithm already gives
an adequate answer using relatively cheap computing equipment (such
as the fact that the coefficients don't stay the same for different
size problems).

The real point of Hopfield and Tank's work is that they took a 'hard'
problem and were able to get good solutions to it using the constrained
quadratic minimization performed by the Hopfield network.  This suggests
that one might be able to handle other similar 'hard' problems this way,
problems for which no good approximate algorithm like Lin and Kernighan's
exists.  The trick, of course, is finding a way to map whatever problem
you might have into a quadratic minimization suitable for a Hopfield net.
More likely than not, this is a *heuristic* mapping, so good performance
is not guaranteed.

Good work I have seen in this area includes a Hopfield net for doing 
multiple target data association for tracking, by Sengupta and Iltis 
at UCSB (see ICASSP '88 proceedings) and a neural net for 
superresolution of ultrasonic images by Jack Winters at Bell Labs 
(see ICNN '88).  An interesting fact is that the outputs of both these 
networks are interpreted as analog values.  This contrasts sharply
with the 0-1 interpretation usually forced on Hopfield nets.


Sean O'Neil