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.
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
Boseniuk T, Ebeling W, Engel A (1987) Boltzmann and Darwin strategies in complex optimization. Phys Lett 125A:307–310
Brady RM (1985) Optimization strategies gleaned from natural evolution. Nature 317:804–806
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
Fogel DB (1989) An evolutionary approach to the traveling salesman problem. Biol Cybern 60:139–144
Fontana W, Schuster P (1987) A computer model of evolutionary optimization. Biophys Chem 26:123–147
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
Holland JH (1975) Adaption in natural and artificial systems. University of Michigan Press, Ann Arbor
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Lawler E (1976) Combinatorial optimization, networks and matroids. Holt, Rinehart and Winston, New York
Lawler E, Lenstra A, Rinnooy Kan G (1985) The traveling salesman problem. Wiley, New York
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
Mühlenbein H, Gorges-Schleuter M, Krämer O (1988) Evolution algorithms in combinatorial optimazation. Par Comp 7:65–85
Rechenberg I (1973) Evolutionsstrategien. Frommann-Holzboog, Stuttgart
Schwefel HP (1981) Numerical optimization of computer models. Wiley, Chichester
Wang Q (1987) Optimization by simulating molecular evolution. Biol Cybern 57:95–101
Author information
Authors and Affiliations
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
About this article
Cite this article
Banzhaf, W. The “molecular” traveling salesman. Biol. Cybern. 64, 7–14 (1990). https://doi.org/10.1007/BF00203625
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00203625