Simple learning algorithm for the traveling salesman problem

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPublished 1 June 1997Open access

Kan Chen

DOI10.1103/physreve.55.7809

Source URL

Citations15

View PDF

TL;DR

A learning algorithm for solving the traveling salesman problem based on a simple strategy of trial and adaptation is proposed and near-optimal tours can be obtained with the average tour lengths close to the lower bounds for the shortest tour lengths.

Abstract

We propose a learning algorithm for solving the traveling salesman problem based on a simple strategy of trial and adaptation: i) A tour is selected by choosing cities probabilistically according to the ``synaptic'' strengths between cities. ii) The ``synaptic'' strengths of the links that form the tour are then enhanced (reduced) if the tour length is shorter (longer) than the average result of the previous trials. We perform extensive simulations of the random distance traveling-salesman problem. For sufficiently slow learning rates, near optimal tours can be obtained with the average optimal tour lengths close to the lower bounds for the shortest tour lengths.

Keywords

Computer Science

ScienceOptimization by Simulated Annealing

44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more

A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.

The MIT Press eBooksAdaptation in Natural and Artificial Systems

35,568 Citations1992John H. Holland

Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.

Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem

3,797 Citations1973Simon Lin, Brian W. Kernighan

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.

ScienceComputing with Neural Circuits: A Model

2,130 Citations1986J. J. Hopfield, David W. Tank

A new conceptual framework and a minimization principle together provide an understanding of computation in model neural circuits that represent an approximation to biological neurons in which a simplified set of important computational properties is retained.

Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem

1,960 Citations1965Shen Lin

Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.

Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees

1,443 Citations1970Michael Held, Richard M. Karp

It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.

Parallel ComputingEvolution algorithms in combinatorial optimization

397 Citations1988Heinz Mühlenbein, M. Gorges-Schleuter +1 more

A new genetic algorithm which relies on intelligent evolution of individuals is presented, which is inherently parallel and shows a superlinear speedup in multiprocessor systems.

NatureOptimization strategies gleaned from biological evolution

186 Citations1985R. M. Brady

Computer algorithms are used to investigate new strategies for the 64-city travelling salesman problem, which combine conventional optimization or ‘quenching’ with biological elements, namely having a population of trial solutions, helping weaker individuals to survive, and an analogue of sexual crossing-over of genes.

NatureNew optimization methods from physics and biology

154 Citations1987David G. Bounds

Research in spin-glass physics, population genetics, and neural network dynamics has provided powerful methods for finding near-global optima of functions that have many local optima and may also give new insights into combinatorial optimization problems.

Europhysics Letters (EPL)The Cavity Method and the Travelling-Salesman Problem

92 Citations1989Werner Krauth, Marc Mézard

This work solves the zero-temperature cavity equations for the random link travelling-salesman problem and gets precise predictions for the length of the optimal tour and the probability distribution of links in this tour.