Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Letter
  • Published:

Optimization strategies gleaned from biological evolution

Nature volume 317, pages 804–806 (1985)Cite this article

Abstract

Several problems, in particular the ‘travelling salesman’ problem1 wherein one seeks the shortest route encompassing a randomly distributed group of cities, have been optimized by repeated random alteration (mutation) of a trial solution followed by selection of the cheaper (fitter) solution. Most non-trivial problems have complicated fitness functions, and optimization tends to become stuck in local fitness maxima. A recently introduced strategy to escape (simulated annealing) involves accepting unfavourable mutations with finite probability1–3. Independently, there has been interest in genetic strategies which overcome the problem of fitness maxima in biological evolution4–6, and several authors have applied biological elements to optimization7,8. Here we use computer algorithms 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. The new strategies were faster and gave better results than simulated annealing.

This is a preview of subscription content, access via your institution

Access options

Buy this article

  • Purchase on Springer Link
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Similar content being viewed by others

References

  1. Kirkpatrick, S., Gelatt, C. D. Jr & Vecchi, M. P. Science 220, 671–680 (1983).

    Article  ADS  MathSciNet  CAS  Google Scholar 

  2. Vanderbilt, D. & Louie, S. G. J. Comput. Phys. 56, 259–271 (1984).

    Article  ADS  MathSciNet  Google Scholar 

  3. Smith, W. E., Barrett, H. H. & Paxman, R. G. Opt. Lett. 8, 199 (1983).

    Article  ADS  CAS  Google Scholar 

  4. Dobzhansky, T., Ayala, F. J., Stebbins, G. L. & Valentine, J. W. Evolution, 165–191 (Freeman, San Francisco, 1977).

    Google Scholar 

  5. Kourilsky, P. & Gachelin, G. La Recherche 155, 642–653 (1983).

    Google Scholar 

  6. Dover, G. A. BioScience 32, 526–533 (1982).

    Article  CAS  Google Scholar 

  7. De Jong, K. IEEE Trans. Syst., Man, Cybern. 10, 566–574 (1980).

    Article  Google Scholar 

  8. Holland, J. H. Adaption in Natural and Artificial Systems (University of Michigan, Ann Arbor, 1975).

    MATH  Google Scholar 

  9. Darwin, C. On the origin of Species 1st edn (facsimile Harvard University Press, 1964).

    Google Scholar 

  10. Stanley, S. M. The New Evolutionary Timetable, 72–109 (Harper and Row, London, 1981).

    Google Scholar 

  11. Perlmutter, R. M. et al. Adv. Immun. 35, 1–37 (1984).

    Article  CAS  Google Scholar 

  12. Kaartinen, M., Griffiths, G. M., Markham, A. F. & Milstein, C. Nature 304, 320–324 (1983).

    Article  ADS  CAS  Google Scholar 

  13. Dyson, F. J. Disturbing the Universe, 218–224 (Pan, London, 1981).

    Google Scholar 

  14. Feyerabend, P. Against Method (NLB, London, 1975).

    Google Scholar 

  15. Kuhn, T. S. The Structure of Scientific Revolutions 2nd edn (University of Chicago Press, 1970).

    Google Scholar 

  16. Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. Cogn. Sci. 9, 147–169 (1985).

    Article  Google Scholar 

  17. Hopfield, J. J. Proc. natn Acad. Sci. U.S.A. 79, 2554–2558 (1982).

    Article  ADS  MathSciNet  CAS  Google Scholar 

  18. Holland, J. H. Progress in Theoretical Biology Vol. 4 (eds Rosen, R. & Snell, F. M.) 263–293 (Academic, New York, 1976).

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Cavendish Laboratory, Madingley Road, Cambridge, CB3 0HE, UK

    R. M. Brady

Authors
  1. R. M. Brady
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brady, R. Optimization strategies gleaned from biological evolution. Nature 317, 804–806 (1985). https://doi.org/10.1038/317804a0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/317804a0

This article is cited by

Comments

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Search

Advanced search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing