Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Evolution strategies – A comprehensive introduction

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

This article gives a comprehensive introduction into one of the main branches of evolutionary computation – the evolution strategies (ES) the history of which dates back to the 1960s in Germany. Starting from a survey of history the philosophical background is explained in order to make understandable why ES are realized in the way they are. Basic ES algorithms and design principles for variation and selection operators as well as theoretical issues are presented, and future branches of ES research are discussed.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Altenberg L (1994) The evolution of evolvability in genetic programming. In: Kinnear K (ed) Advances in Genetic Programming, pp. 47-74. MIT Press, Cambridge, MA

    Google Scholar 

  • Arnold BC, Balakrishnan N and Nagaraja HN (1992) A First Course in Order Statistics.Wiley, New York

    Google Scholar 

  • Arnold DV and Beyer H-G (2000a) Local performance of the (1 + 1)-ES in a noisy environment. IEEE Transactions on Evolutionary Computation. accepted for publication

  • Arnold DV and Beyer H-G (2000b) Performance analysis of evolution strategies with multirecombination in high-dimensional ℝN-search spaces disturbed by noise. Theoretical Computer Science. In print

  • Arnold DV and Beyer H-G (2001) Local performance of the (µ/µ I , ?)-ES in a noisy environment. In: Martin W and Spears W (eds) Foundations of Genetic Algorithms, 6, pp. 127-141. Morgan Kaufmann, San Francisco, CA

    Google Scholar 

  • Bäck T (1996) Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, NY

    Google Scholar 

  • Bäck T, Fogel D and Michalewicz Z (eds) (1997) Handbook of evolutionary computation. IOP Publishing and Oxford University Press, New York

    Google Scholar 

  • Beyer H-G (1990) Simulation of steady states in dissipative systems by darwin's paradigm of evolution. J. Non-Equilib. Thermodyn. 15: 45-58

    Google Scholar 

  • Beyer H-G (1992) Some aspects of the 'evolution strategy' for solving tsp-like optimization problems. In: Männer R and Manderick B (eds) Parallel Problem Solving from Nature, 2, pp. 361-370. Elsevier, Amsterdam

    Google Scholar 

  • Beyer H-G (1995) Toward a theory of evolution strategies: on the benefit of sex-the (µ/µ, ?)-theory. Evolutionary Computation 3(1): 81-111

    Google Scholar 

  • Beyer H-G (1996) Toward a theory of evolution strategies: Self-adaptation. Evolutionary Computation 3(3): 311-347

    Google Scholar 

  • Beyer H-G (1997) An alternative explanation for the manner in which genetic algorithms operate. BioSystems 41: 1-15

    Google Scholar 

  • Beyer H-G (2000) Evolutionary algorithms in noisy environments: Theoretical issues and guidelines for practice. Computer Methods in Applied Mechanics and Engineering 186(2-4): 239-267

    Google Scholar 

  • Beyer H-G (2001a) On the performance of (1, ?)-evolution strategies for the ridge function class. IEEE Transactions on Evolutionary Computation 5(3): 218-235

    Google Scholar 

  • Beyer H-G (2001b) The Theory of Evolution Strategies. Natural Computing Series. Springer, Heidelberg

    Google Scholar 

  • Beyer H-G and Deb K (2001) On self-adaptive features in real-parameter evolutionary algorithms. IEEE Transactions on Evolutionary Computation 5(3): 250-270

    Google Scholar 

  • Born J (1978) Evolutionsstrategien zur numerischen Lösung von Adaptationsaufgaben. Dissertation A. Humboldt-Universität, Berlin

    Google Scholar 

  • De Jong K, David D, Fogel B and Schwefel H-P (1997) A history of evolutionary computation. In: Bäck T, Fogel DB and Michalewicz Z (eds) Handbook of Evolutionary Computation, pp. A2.3:1-12. Oxford University Press, New York, and Institute of Physics Publishing, Bristol

    Google Scholar 

  • Droste S, Jansen T and Wegener I (1998a) On the optimization of unimodal functions with the (1 + 1) evolutionary algorithm. In: Eiben A, Bäck T, Schoenauer M and Schwefel H-P (eds) Parallel Problem Solving from Nature, 5, pp. 13-22. Springer-Verlag, Heidelberg

    Google Scholar 

  • Droste S, Jansen T and Wegener I (1998b) A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with Boolean inputs. Evolutionary Computation 6(2): 185-196

    Google Scholar 

  • Droste S and Wiesmann D (2000) Metric based evolutionary algorithms. In: Poli R, Banzhaf W, Langdon W, Miller J, Nordin P and Fogarty T (eds) Proc. of the Third European Conference on Genetic Programming, EuroGP 2000, pp. 29-43. Springer, Berlin

    Google Scholar 

  • Eiben AE, Hinterding R and Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3(2): 124-141

    Google Scholar 

  • Fisz M (1971) Wahrscheinlichkeitsrechnung und mathematische Statistik. VEB Deutscher Verlag der Wissenschaften, Berlin

    Google Scholar 

  • Fogel D (ed) (1998) Evolutionary Computation: The Fossil Record. IEEE Press, Piscataway, NJ

    Google Scholar 

  • Fogel DB, Schwefel H-P, Bäck T and Yao X (eds) (1998) Proc. Second IEEE World Congress on Computational Intelligence (WCCI'98) with Fifth IEEE Conf. Evolutionary Computation (IEEE/ICEC'98) Anchorage AK, May 4-9, 1998 IEEE Press, Piscataway, NJ

    Google Scholar 

  • Fogel LJ (1962) Autonomous automata. Industrial Research 4: 14-19

    Google Scholar 

  • Fogel LJ, Owens AJ and Walsh MJ (1966) Artificial Intelligence through Simulated Evolution. Wiley, New York

    Google Scholar 

  • Goldberg D (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, Reading, MA

    Google Scholar 

  • Grünz L and Beyer H-G (1999) Some observations on the interaction of recombination and self-adaptation in evolution strategies. In: Angeline P (ed) Proceedings of the CEC'99 Conference, pp. 639-645. IEEE, Piscataway, NJ

    Google Scholar 

  • Hansen N and Ostermeier A (1996) Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Proceedings of 1996 IEEE Int'l Conf. on Evolutionary Computation (ICEC '96), pp. 312-317. NY, IEEE Press

    Google Scholar 

  • Hansen N and Ostermeier A (1997) Convergence properties of evolution strategies with the derandomized covariance matrix adaptation: The (µ/µ I , ?)-CMA-ES. In: Zimmermann HJ (ed) 5th European Congress on Intelligent Techniques and Soft Computing (EUFIT'97), pp. 650-654. Aachen, Germany, Verlag Mainz

    Google Scholar 

  • Hansen N and A Ostermeier (2001) Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9(2): 159-195

    Google Scholar 

  • Hartmann D (1974) Optimierung balkenartiger Zylinderschalen aus Stahlbeton mit elastischem und plastischem Werkstoffverhalten. Dr.-Ing. Dissertation, University of Dortmund, Dortmund

    Google Scholar 

  • Herdy M (1990) Application of the 'evolutionsstrategie' to discrete optimization problems. In: Schwefel H-P and Männer R (eds) Parallel Problem Solving from Nature, 1, pp. 188-192. Springer-Verlag, Berlin.

    Google Scholar 

  • Herdy M (1992) Reproductive isolation as strategy parameter in hierarchically organized evolution strategies. In: Männer R and Manderick B (eds) Parallel Problem Solving from Nature, 2, pp. 207-217. Elsevier, Amsterdam.

    Google Scholar 

  • Holland JH (1962) Outline for a logical theory of adaptive systems. JACM 9: 297-314

    Google Scholar 

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

    Google Scholar 

  • Holland JH (1995) Hidden Order: How Adaptation Builds Complexity. Addison-Wesley, Reading, MA

    Google Scholar 

  • Horn J, Goldberg D and Deb K (1994) Long path problems. In: Davidor Y, Männer R and Schwefel H-P (eds) Parallel Problem Solving from Nature, 3, pp. 149-158. Springer-Verlag, Heidelberg

    Google Scholar 

  • Jansen T (2000) Theoretische analyse evolutionärer Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen. Phd thesis, Univ. of Dortmund, Dortmund, Germany (in German).

    Google Scholar 

  • Jansen T and Wegener I (1999) On the analysis of evolutionary algorithms-a proof that crossover really can help. In: Nesetril J (ed) Proceedings of the 7th Annual European Symposium on Algorithms (ESA '99), pp. 184-193. Berlin, Germany, LNCS 1643, Springer

    Google Scholar 

  • Jansen T and Wegener I (2000) On the choice of the mutation probability for the (1 + 1) EA. In: M Schoenauer (ed) Parallel Problem Solving from Nature, 6, pp. 89-98. Springer, Heidelberg

    Google Scholar 

  • Jansen T and Wegener I (2001) Real royal road functions-where crossover provably is essential. In: Spector L (ed) GECCO'01: Proceedings of the Genetic and Evolutionary Computation Conference. Morgan Kaufmann, San Francisco, CA

    Google Scholar 

  • Jaynes ET (1979) Where do we stand on maximum entropy? In: Levine R and Tribus M (eds) The Maximum Entropy Formalism, pp. 15-118

  • Kappler C, Bäck T, Heistermann J, Van de Velde A and Zamparelli M (1996) Refueling of a nuclear power plant: comparison of a naive and a specialized mutation operator. In: Voigt H-M, Ebeling W, Rechenberg I and Schwefel H-P (eds) Parallel Problem Solving from Nature-PPSN IV, Int'l Conf. Evolutionary Computation, pp. 829-838. Springer, Berlin

    Google Scholar 

  • Klockgether J and Schwefel H-P (1970) Two-phase nozzle and hollow core jet experiments. In: Elliott DG (ed) Proc. 11th Symp. Engineering Aspects of Magnetohydrodynamics, pp. 141-148. California Institute of Technology, Pasadena CA

    Google Scholar 

  • Kursawe F (1992) Evolution strategies for vector optimization. In: Tzeng G-H and Yu P-L (eds) Preliminary Proc. Tenth Int'l Conf.Multiple Criteria Decision Making, pp. 187-193. National Chiao Tung University, Taipei

    Google Scholar 

  • Kursawe F (1999) Grundlegende empirische Untersuchungen der Parameter von Evolutionsstrategien-Metastrategien. Dr. rer. nat.-Dissertation, University of Dortmund, Department of Computer Science, Chair of Systems Analysis. Schwefel.

    Google Scholar 

  • Laumanns M, Rudolph G and Schwefel H-P (1998) A spatial predator-prey approach to multi-objective optimization. In: Eiben AE, Bäck T, Schoenauer M and Schwefel H-P (eds) Parallel Problem Solving from Nature-PPSN V, Fifth Int'l Conf., Amsterdam, The Netherlands, September 27-30, 1998, Proc., pp. 241-249. Springer, Berlin

    Google Scholar 

  • Laumanns M, Rudolph G and Schwefel H-P (2001) Mutation control and convergence in evolutionary multi-objective optimization. In: Matousek R and Osmera P (eds) Proc. Seventh Int'l Conf. Soft Computing (MENDEL'01), pp. 24-29. Brno University of Technology, Brno, Czech Republic

    Google Scholar 

  • Lin S and Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21: 498-516

    Google Scholar 

  • Lohmann R (1992) Structure evolution and incomplete induction. In: Männer R and Manderick B (eds) Parallel Problem Solving from Nature, 2, pp. 175-185. Elsevier, Amsterdam

    Google Scholar 

  • Michalewicz Z, Schaffer JD, Schwefel H-P, Fogel DB and Kitano H (eds) (1994) Proc. First IEEE Conf. Evolutionary Computation, Vol. I (oral presentations) and II (posters) of IEEE World Congress on Computational Intelligence. Orlando FL. The Institute of Electrical and Electronics Engineers, IEEE-Press, Piscataway NJ

    Google Scholar 

  • Mitchell M, Holland J and Forrest S (1994) When will a genetic algorithm outperform hill climbing. In: Cowan J, Tesauro G and Alspector J (eds) Advances in Neural Information Processing Systems, pp. 51-58. Morgan Kaufmann, San Mateo, CA

    Google Scholar 

  • Motwani R and Raghavan P (1995) Randomized Algorithms. Cambridge University Press, New York, NY

    Google Scholar 

  • Mühlenbein H and Mahnig T (1999) FDA a scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation 7(4): 353-376

    Google Scholar 

  • Nürnberg H-T and Beyer H-G (1997) The dynamics of evolution strategies in the optimization of traveling salesman problems. In: Angeline P, Reynolds R, McDonnell J and Eberhart R (eds) Evolutionary Programming VI: Proceedings of the Sixth Annual Conference on Evolutionary Programming, pp. 349-359. Springer-Verlag, Heidelberg

    Google Scholar 

  • Ostermeier A, Gawelczyk A and Hansen N (1994) Step-size adaptation based on non-local use of selection information. In: Davidor Y, Männer R and Schwefel H-P (eds) Parallel Problem Solving from Nature, 3, pp. 189-198. Springer-Verlag, Heidelberg

    Google Scholar 

  • Oyman AI (1999) Convergence behavior of evolution strategies on ridge functions. Ph.D. Thesis, University of Dortmund, Department of Computer Science

  • Oyman AI and Beyer H-G (2000) Analysis of the (µ/µ, ?)-ES on the parabolic ridge. Evolutionary Computation 8(3): 267-289

    Google Scholar 

  • Oyman AI, Beyer H-G and Schwefel H-P (2000) Analysis of a simple ES on the “parabolic ridge”. Evolutionary Computation 8(3): 249-265

    Google Scholar 

  • Pelikan M, Goldberg D and Cantu-Paz E (1999) BOA: the bayesian optimization algorithm. In: Banzhaf W, Daida J, Eiben A, Garzon M, Honavar V, Jakiela M and Smith R (eds) GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 525-532. Morgan Kaufmann, San Francisco, CA

    Google Scholar 

  • Rappl G (1989), On linear convergence of a class of random search algorithms. Zeitschrift f. angew. Math. Mech. (ZAMM) 69(1): 37-45

    Google Scholar 

  • Rechenberg I (1965) Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Farnborough p. Library Translation 1122

    Google Scholar 

  • Rechenberg I (1971) Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Dr.-Ing. Thesis, Technical University of Berlin, Department of Process Engineering

  • Rechenberg I (1973) Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart

    Google Scholar 

  • Rechenberg I (1978) Evolutionsstrategien. In: Schneider B and Ranft U (eds) Simulationsmethoden in der Medizin und Biologie, pp. 83-114. Springer-Verlag, Berlin

    Google Scholar 

  • Rechenberg I (1994) Evolutionsstrategie '94. Frommann-Holzboog Verlag, Stuttgart

    Google Scholar 

  • Rudolph G (1992) On correlated mutations in evolution strategies. In: Männer R and Manderick B (eds) Parallel Problem Solving from Nature-Proc. Second Conf. PPSN, pp. 105-114. Free University of Brussels, Elsevier, Amsterdam

    Google Scholar 

  • Rudolph G (1994) An evolutionary algorithm for integer programming. In: Davidor Y, Männer R and Schwefel H-P (eds) Parallel Problem Solving from Nature, 3, pp. 139-148. Springer-Verlag, Heidelberg

    Google Scholar 

  • Rudolph G (1997a) Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kova?, Hamburg. PhD-Thesis

    Google Scholar 

  • Rudolph G (1997b) How mutation and selection solve long-path problems in polynomial expected time. Evolutionary Computation 4(2): 195-205

    Google Scholar 

  • Rudolph G and Agapie A (2000) Convergence properties of some multi-objective evolutionary algorithms. In: Zalzala A and Eberhart R (eds) Proc. 2000 Congress on Evolutionary Computation (CEC'00), Vol. 2. La Jolla CA, pp. 1010-1016. IEEE Press, Piscataway NJ

    Google Scholar 

  • Schwefel H-P (1965) Kybernetische Evolution als Strategie der exprimentellen Forschung in der Strömungstechnik. Master's thesis, Technical University of Berlin

  • Schwefel H-P (1968) Experimentelle Optimierung einer Zweiphasendüse Teil I. Technical Report No. 35 of the Project MHD-Staustrahlrohr 11.034/68, AEG Research Institute, Berlin

    Google Scholar 

  • Schwefel H-P (1975) Evolutionsstrategie und numerische Optimierung. Dissertation, TU Berlin, Germany

  • Schwefel H-P (1977) Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, Interdisciplinary systems research; 26. Birkhäuser, Basel

    Google Scholar 

  • Schwefel H-P (1981) Numerical Optimization of Computer Models. Wiley, Chichester

    Google Scholar 

  • Schwefel H-P (1987) Collective phenomena in evolutionary systems. In: Checkland P and Kiss I (eds) Problems of Constancy and Change-the Complementarity of Systems Approaches to Complexity, Papers presented at the 31st Annual Meeting of the Int'l Soc. for General System Research, Vol. 2. Budapest, pp. 1025-1033. Int'l Soc. for General System Research

    Google Scholar 

  • Schwefel H-P (1995) Evolution and Optimum Seeking. Wiley, New York, NY

    Google Scholar 

  • Schwefel H-P and Kursawe F (1998) On natural life's tricks to survive and evolve. In: Fogel DB, Schwefel H-P, Bäck T and Yao X (eds) Proc. Second IEEE World Congress on Computational Intelligence (WCCI'98) with Fifth IEEE Conf. Evolutionary Computation (IEEE/ICEC'98), pp. 1-8. Anchorage AK, IEEE Press, Piscataway NJ

    Google Scholar 

  • Schwefel H-P and Rudolph G (1995) Contemporary evolution strategies. In: Morana F, Moreno A, Merelo JJ and Chacon P (eds) Advances in Artificial Life. Third ECAL Proceedings, pp. 893-907. Springer-Verlag, Berlin

    Google Scholar 

  • Sendhoff B, Kreuz M and von Seelen W (1997) A condition for the genotype-phenotype mapping: Causality. In: Bäck T (ed) Proc. 7th Int'l Conf. on Genetic Algorithms, pp. 73-80. Morgan Kaufmann Publishers, Inc., Francisco, CA

    Google Scholar 

  • Syswerda G (1989) Uniform crossover in genetic algorithms. In: Schaffer JD (ed) Proc. 3rd Int'l Conf. on Genetic Algorithms, pp. 2-9. Morgan Kaufmann, San Mateo, CA.

    Google Scholar 

  • Wegener I (2000) On the design and analysis of evolutionary algorithms. In: Workshop on Algorithm Engineering as a New Paradigm. Kyoto, pp. 36-47. Research Institute for Mathematical Science, Kyoto Univ.

  • Wegener I (2001) Theoretical aspects of evolutionary algorithms. In: Spirakis P (ed), Proc. 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag, Berlin

    Google Scholar 

  • Wegener I and Witt C (2001) On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions. Submitted to Journal of Discrete Algorithms

  • Yao X (1999) Evolving artificial neural networks. Proceedings of the IEEE 87(9): 1423-1447

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science XI, University of Dortmund, Joseph-von-Fraunhoferstrasse 20, D-44221, Dortmund, Germany

    Hans-Georg Beyer & Hans-Paul Schwefel

Authors
  1. Hans-Georg Beyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans-Paul Schwefel
    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

Beyer, HG., Schwefel, HP. Evolution strategies – A comprehensive introduction. Natural Computing 1, 3–52 (2002). https://doi.org/10.1023/A:1015059928466

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1015059928466

Search

Navigation