Skip to main content
Log in

The “molecular” traveling salesman

  • Published:
Biological Cybernetics Aims and scope Submit manuscript

Abstract

We consider a method for optimization of NP-problems motivated by natural evolution. The basic entity is a population of individuals searching in state space defined by the problem. A message exchange mechanism between individuals enables the system to proceed fast and to avoid local optima. We introduce the concept of isolated evolution to maintain a certain degree of variance in the population. The global optimum can be approached to an arbitrary degree. The method is applied to the TSP and its behavior is shown in a couple of simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bonomi E, Lutton J-L (1984) The N-city traveling salesman problem: Statistical mechanics and the metropolis algorithm. SIAM Rev 26:551–568

    Article  Google Scholar 

  • Boseniuk T, Ebeling W, Engel A (1987) Boltzmann and Darwin strategies in complex optimization. Phys Lett 125A:307–310

    Google Scholar 

  • Brady RM (1985) Optimization strategies gleaned from natural evolution. Nature 317:804–806

    Google Scholar 

  • Bremermann HJ, Rogson M, Salaff S (1965) Search by evolution. In: Maxfield M, Callahan A, Fogel LJ (eds) Biophysics and cybernetic systems. Spartan Books, Washington, pp 157–167

    Google Scholar 

  • Fogel DB (1989) An evolutionary approach to the traveling salesman problem. Biol Cybern 60:139–144

    Article  Google Scholar 

  • Fontana W, Schuster P (1987) A computer model of evolutionary optimization. Biophys Chem 26:123–147

    Article  PubMed  Google Scholar 

  • Grefenstette JJ, Gopal R, Rosmaita B, Van Gucht D (1985) Genetic algorithms for the traveling salesman problem. In: Grefenstette JJ (ed) Proceedings of the International Conference on Genetic Algorithms and their Applications. Carnegie Mellon University, Pittsburgh, pp 160–168

    Google Scholar 

  • Holland JH (1975) Adaption in natural and artificial systems. University of Michigan Press, Ann Arbor

    Google Scholar 

  • Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680

    Google Scholar 

  • Lawler E (1976) Combinatorial optimization, networks and matroids. Holt, Rinehart and Winston, New York

    Google Scholar 

  • Lawler E, Lenstra A, Rinnooy Kan G (1985) The traveling salesman problem. Wiley, New York

    Google Scholar 

  • Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller EJ (1953) Equations of state calculations by fast computing machines. J Chem Phys 21:1087–1091

    Article  Google Scholar 

  • Mühlenbein H, Gorges-Schleuter M, Krämer O (1988) Evolution algorithms in combinatorial optimazation. Par Comp 7:65–85

    Article  Google Scholar 

  • Rechenberg I (1973) Evolutionsstrategien. Frommann-Holzboog, Stuttgart

    Google Scholar 

  • Schwefel HP (1981) Numerical optimization of computer models. Wiley, Chichester

    Google Scholar 

  • Wang Q (1987) Optimization by simulating molecular evolution. Biol Cybern 57:95–101

    Article  PubMed  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

On leave from: Institut für Theoretische Physik und Synergetik, Universität Stuttgart, Pfaffenwaldring 57/IV, D-7000 Stuttgart 80, Federal Republic of Germany

Rights and permissions

Reprints and permissions

About this article

Cite this article

Banzhaf, W. The “molecular” traveling salesman. Biol. Cybern. 64, 7–14 (1990). https://doi.org/10.1007/BF00203625

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00203625

Keywords

Navigation