Evolution strategies - a comprehensive introduction
Inhaltsverzeichnis
Referenz
Beyer, H.G., Schwefel, H.P.: Evolution strategies - a comprehensive introduction. Natural Comput. 1(1), 3–52 (2002)
DOI
http://dx.doi.org/10.1023/A%3A1015059928466
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.
Extended Abstract
Bibtex
@Article{Beyer2002,
author="Beyer, Hans-Georg and Schwefel, Hans-Paul",
title="Evolution strategies -- A comprehensive introduction",
journal="Natural Computing",
year="2002",
volume="1",
number="1",
pages="3--52",
issn="1572-9796",
doi="10.1023/A:1015059928466",
url="http://dx.doi.org/10.1023/A:1015059928466 http://de.evo-art.org/index.php?title=Evolution_strategies_-_a_comprehensive_introduction"
}
Used 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
Arnold BC, Balakrishnan N and Nagaraja HN (1992) A First Course in Order Statistics.Wiley, New York
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 RN-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
Bäck T (1996) Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, NY
Bäck T, Fogel D and Michalewicz Z (eds) (1997) Handbook of evolutionary computation. IOP Publishing and Oxford University Press, New York
Beyer H-G (1990) Simulation of steady states in dissipative systems by darwin’s paradigm of evolution. J. Non-Equilib. Thermodyn. 15: 45–58
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
Beyer H-G (1995) Toward a theory of evolution strategies: on the benefit of sex – the (μ/μ, λ)- theory. Evolutionary Computation 3(1): 81–111
Beyer H-G (1996) Toward a theory of evolution strategies: Self-adaptation. Evolutionary Computation 3(3): 311–347
Beyer H-G (1997) An alternative explanation for the manner in which genetic algorithms operate. BioSystems 41: 1–15
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
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
Beyer H-G (2001b) The Theory of Evolution Strategies. Natural Computing Series. Springer, Heidelberg
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
Born J (1978) Evolutionsstrategien zur numerischen Lösung von Adaptationsaufgaben. Dissertation A. Humboldt-Universität, Berlin
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
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
Droste S, Jansen T andWegener I (1998b) A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with Boolean inputs. Evolutionary Computation 6(2): 185–196
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
Eiben AE, Hinterding R and Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3(2): 124–141
Fisz M (1971) Wahrscheinlichkeitsrechnung und mathematische Statistik. VEB Deutscher Verlag der Wissenschaften, Berlin
Fogel D (ed) (1998) Evolutionary Computation: The Fossil Record. IEEE Press, Piscataway, NJ
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
Fogel LJ (1962) Autonomous automata. Industrial Research 4: 14–19
Fogel LJ, Owens AJ andWalsh MJ (1966) Artificial Intelligence through Simulated Evolution. Wiley, New York
Goldberg D (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, Reading, MA
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
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
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
Hansen N and A Ostermeier (2001) Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9(2): 159–195
Hartmann D (1974) Optimierung balkenartiger Zylinderschalen aus Stahlbeton mit elastischem und plastischem Werkstoffverhalten. Dr.-Ing. Dissertation, University of Dortmund, Dortmund
HerdyM(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.
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.
Holland JH (1962) Outline for a logical theory of adaptive systems. JACM 9: 297–314
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Holland JH (1995) Hidden Order: How Adaptation Builds Complexity. Addison-Wesley, Reading, MA
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
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).
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
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
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
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
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
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 DecisionMaking, pp. 187–193. National Chiao Tung University, Taipei
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.
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
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
Lin S and Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21: 498–516
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
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
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
Motwani R and Raghavan P (1995) Randomized Algorithms. Cambridge University Press, New York, NY
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
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
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
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
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
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
Rappl G (1989), On linear convergence of a class of random search algorithms. Zeitschrift f. angew. Math. Mech. (ZAMM) 69(1): 37–45
Rechenberg I (1965) Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Farnborough p. Library Translation 1122
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
Rechenberg I (1978) Evolutionsstrategien. In: Schneider B and Ranft U (eds) Simulationsmethoden in der Medizin und Biologie, pp. 83–114. Springer-Verlag, Berlin
Rechenberg I (1994) Evolutionsstrategie ’94. Frommann-Holzboog Verlag, Stuttgart
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
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
Rudolph G (1997a) Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovaˇc, Hamburg. PhD-Thesis
Rudolph G (1997b) How mutation and selection solve long-path problems in polynomial expected time. Evolutionary Computation 4(2): 195–205
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
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
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
Schwefel H-P (1981) Numerical Optimization of Computer Models. Wiley, Chichester
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
Schwefel H-P (1995) Evolution and Optimum Seeking. Wiley, New York, NY
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
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
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
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.
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
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
Links
Full Text
