chrisk@nlm.nih.gov (Christopher Y. Kim) (04/12/91)
Hi, A couple of us medical students in medical informatics heard a lecture on neural nets where Dr. Nicholas DeCleris from Maryland mentioned something about using a neural network to solve the travelling salesman problem, done by someone at Cornell. Does anyone know about this, and what the reference (journal or book) we can find this? I would prefer an e-mail reply than a post because I may not scan here often, but either one is fine. Thanks in advance, Chris Kim <chrisk@nlm.nih.gov>
smagt@fwi.uva.nl (Patrick van der Smagt) (04/16/91)
chrisk@nlm.nih.gov (Christopher Y. Kim) writes: >A couple of us medical students in medical informatics heard a lecture >on neural nets where Dr. Nicholas DeCleris from Maryland mentioned something >about using a neural network to solve the travelling salesman problem, The first person to SOLVE tsp earns the Nobel prize for maths, I'm sure. The rumour you've caught concerns a `novel' approximation of tsp. The primary reference is the Hopfield and Tank article, %A J. J. Hopfield %A D. W. Tank %D 1985 %J Biological Cybernetics %V 52 %P 141--152 %T `Neural' computation of decisions in optimization problems And from then on articles spring up like mushrooms. Theoretically, it is very nice, but practically it doesn't come near the Lin & Kernighan (1973) algorithm. A comparison which I found I don't know where (to be fed through LaTeX): \begin{tabular}{l||r|r|c} Algorithm & \# cities & good & runtime (400 cities) \\\hline\hline L--K & 50,000 & 2\% & 20s \\\hline Hopfield & 30 & 17\% & $6\cdot60\cdot60s$ \\\hline \end{tabular} There are quite a few improvements on H&T, such as %A A. Joppe %A H. R. A. Cardon %A J. C. Bioch %T A neural network for solving the travelling salesman problem on the basis of city adjacency in the tour %D 1990 %B ICANN %C Paris but still, a long way far from L&K. Patrick van der Smagt /\/\ \ / Organisation: Faculty of Mathematics & Computer Science / \ University of Amsterdam, Kruislaan 403, _ \/\/ _ NL-1098 SJ Amsterdam, The Netherlands | | | | Phone: +31 20 525 7524 | | /\/\ | | Fax: +31 20 525 7490 | | \ / | | | | / \ | | email: smagt@fwi.uva.nl | | \/\/ | | | \______/ | \________/ /\/\ ``The opinions expressed herein are the author's only and do \ / not necessarily reflect those of the University of Amsterdam.'' / \ \/\/
chrisk@nlm.nih.gov (Christopher Y. Kim) (04/17/91)
Thank you for all the responses. Obviously, I have a lot of reading to do,
but it seems that the neural net approach is generally slower than conventional
heuristic algorithms. I will summarize what has been mailed to me so far for
the convenience of those who wanted me to forward the e-mail replies. I will
abbreviate the "Travelling Salesman Problem" as TSP below.
The "classic" papers plus a book:
(1) Lin S, Kernighan BW. An Effective Heuristic Algorithm for the TSP.
Operations Research 21:2, 498-516 (1973).
(2) Hopfield JJ, Tank, DW. "Neural" computation of decisions in optimization
problems. Biological Cybernetics 52, 141-152 (1985).
(3) Lawler EL, et al (eds.). The TSP. New York: Wiley, 1985.
(book - reportedly comprehensive)
One VERY recent article that is a good place to start:
Xu X, Tsai WT. Effective Neural Algorithms for the TSP. Neural Networks
4:2, 193-206 (1991).
Elastic net method
(1) Durbin R, Willshaw DJ. An analogue approach to the TSP using an elastic
net method. Nature 326, 689-691 (1987).
(2) Durbin R, Szeliski R, Yuille, A. An Analysis of the Elstic Net Approach
to the TSP. Neural Computation 1, 348-358 (1989).
Kohonen's Self-Organizationap
(1) Angeniol B, Vaubois G, Texier J. Self-organizing feature maps and the
TSP. Neural Networks 1, 289-293 (1988).
(2) Fort JC. Solving a Combinatorial Problem via a Self-Organizing Process:
An Application of the Kohonen Algorithm to the TSP. Biological
Cybernetics 59, 33-40 (1988).
Genetic Algorithms
(1) Grefenstette J, Gopal R, Rosmaita B, Van Gucht D. Genetic Algorithms
for TSP. Proceedings of the Int'l Conf on Genetic Alogorithms
and their Applications, 1985.
(2) Oliver IM, Smith DJ, Holand JRC. A study of permutation crossover
operators on the TSP. Proceedings of the Int'l Conf on Genetic
Algorithms and their Applicatons, 1987.
Other sources also mentioned -
(1) Kirkpatrick, Gellati, Vecchi. [title?]. Science 220, 671-680 (1983).
[Simulated annealing re: Lin & Kernighan, 1973]
(2) Yuille A. Generalized Deformable Models, Staistical Physics and Matching
Problems. Neural Computation 2, 1-24 (1990).
I apologize for any typos, especially as I have only looked up five of these
sources so far.
Thanks to luox@copper.ucs.indiana.edu, muttiah@ecn.purdue.edu, srikanth@
rex.cs.tulane.edu, kcj@goanna.cs.rmit.oz.au, siemon@anja.informatik.
uni-dortmund.de, lesher@ncifcrf.gov, and smagt@fwi.uva.nl
for their contributions to this list.
Chris Kim :-)pmm@acsu.buffalo.edu (patrick m mullhaupt) (04/17/91)
In article <1991Apr15.192648.535@fwi.uva.nl> smagt@fwi.uva.nl (Patrick van der Smagt) writes: >chrisk@nlm.nih.gov (Christopher Y. Kim) writes: > >>A couple of us medical students in medical informatics heard a lecture >>on neural nets where Dr. Nicholas DeCleris from Maryland mentioned something >>about using a neural network to solve the travelling salesman problem, > >The first person to SOLVE tsp earns the Nobel prize for maths, I'm sure. If I'm not mistaken, I believe there is no Nobel prize for Mathematics, (rumor has it that Nobel's wife ran off with a mathematician).
ian@ponder.csci.unt.edu (Ian Parberry) (04/17/91)
>>The first person to SOLVE tsp earns the Nobel prize for maths, I'm sure. > > > If I'm not mistaken, I believe there is no Nobel prize for >Mathematics, (rumor has it that Nobel's wife ran off with a >mathematician). The person who (sic) "solves" TSP (which I take as meaning the person who proves that P is not equal to NP, or otherwise), would probably be in line for the Turing award. I don't know if the Fields medal committee considers theoretical computer science as mathematics. [For those who don't keep up with either Computer Science or Mathematics, the Fields medal is to Mathematics what the Nobel prize is to Science. The Turing award is to Computer Science what the Fields medal is to Mathematics. To a first approximation.] ____ Ian Parberry ian@dept.csci.unt.edu Dept. of Computer Science, Univ. of North Texas, P.O. Box 13886, Denton, TX 76203-3886 "Bureaucracy is expanding to meet the needs of an expanding bureaucracy"
fahn@cs.columbia.edu (Paul N. Fahn) (04/17/91)
In article <1991Apr16.232447.14364@solo.csci.unt.edu> ian@ponder.csci.unt.edu (Ian Parberry) writes: > >[For those who don't keep up with either Computer Science or Mathematics, >the Fields medal is to Mathematics what the Nobel prize is to Science. >The Turing award is to Computer Science what the Fields medal is to >Mathematics. To a first approximation.] Except that the Turing award can be given to someone over 40! Paul Fahn fahn@cs.columbia.edu
smagt@fwi.uva.nl (Patrick van der Smagt) (04/17/91)
ian@ponder.csci.unt.edu (Ian Parberry) writes: >>>The first person to SOLVE tsp earns the Nobel prize for maths, I'm sure. >> >> >> If I'm not mistaken, I believe there is no Nobel prize for >>Mathematics, (rumor has it that Nobel's wife ran off with a >>mathematician). >The person who (sic) "solves" TSP (which I take as meaning the person >who proves that P is not equal to NP, or otherwise), would probably >be in line for the Turing award. I don't know if the Fields medal >committee considers theoretical computer science as mathematics. No, quite convinced. Would earn the Nobel prize for maths. Patrick