×

zbMATH — the first resource for mathematics

How to analyse evolutionary algorithms. (English) Zbl 1061.90119
Summary: Many variants of evolutionary algorithms have been designed and applied. The experimental knowledge is immense. The rigorous analysis of evolutionary algorithms is difficult, but such a theory can help to understand, design, and teach evolutionary algorithms. In this survey, first the history of attempts to analyse evolutionary algorithms is described and then new methods for continuous as well as discrete search spaces are presented and discussed.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
68W20 Randomized algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alander, J.T., Bibliography of genetic algorithms, (), 1-22
[2] D.V. Arnold, Local performance of evolution strategies in the presence of noise, Ph.D. Thesis, University of Dortmund, Dortmund, 2001. · Zbl 1140.90300
[3] D.V. Arnold, H.-G. Beyer, On the use of evolution strategies for noisy optimization, J. Comput. Optim. Appl., to appear.
[4] D.V. Arnold, H.-G. Beyer, Local performance of the (μ/μI, λ)-ES in a noisy environment, Proc. Foundations of Genetic Algorithms, Vol. 6, Morgan Kaufmann, San Francisco, CA, 2001, pp. 127-141. · Zbl 1001.68199
[5] D.V. Arnold, H.-G. Beyer, Performance analysis of evolution strategies with multi-recombination in high-dimensional \(R\^{}\{N\}\)-search spaces disturbed by noise, Theoret. Comput. Sci., to appear. · Zbl 1060.90083
[6] T. Bäck, Optimal mutation rates in genetic search, Proc. 5th Internat. Conf. on Genetic Algorithms, 1993, pp. 2-8.
[7] T. Bäck, D.B. Fogel, Z. Michalewicz (Eds.), Handbook of Evolutionary Computation, Oxford University Press, New York, and Institute of Physics Publishing, Bristol, 1997. · Zbl 0883.68001
[8] R.K. Belew, L.B. Booker (Eds.), Proc. 4th Internat. Conf. on Genetic Algorithms (ICGA’91), Morgan Kaufmann, San Mateo, CA, 1991.
[9] H.-G. Beyer, Towards a theory of ‘evolution strategies’: progress rates and quality gain for \((1,\^{}\{+\}λ)\)-strategies on (nearly) arbitrary fitness functions, Proc. PPSN III (Parallel Problem Solving from Nature), Springer, Heidelberg, 1994, pp. 58-67.
[10] Beyer, H.-G., Toward a theory of evolution strategies: the (μ , λ)-theory, Evolutionary comput., 2, 4, 381-407, (1995)
[11] Beyer, H.-G., Toward a theory of evolution strategiesself-adaptation, Evolutionary comput., 3, 3, 311-347, (1996)
[12] Beyer, H.-G., An alternative explanation for the manner in which genetic algorithms operate, Biosystems, 41, 1-15, (1997)
[13] Beyer, H.-G., On the performance of (1,λ)-evolution strategies for the ridge function class, IEEE trans. evolutionary comput., 5, 3, 218-235, (2001)
[14] Beyer, H.-G., The theory of evolution strategies, natural computing series, (2001), Springer Heidelberg
[15] H.-G. Beyer, D.V. Arnold, Fitness noise and localization errors of the optimum in general quadratic fitness models, Proc. Genetic and Evolutionary Computation Conference (GECCO), Morgan Kaufmann, San Francisco, CA, 1999, pp. 817-824.
[16] Beyer, H.-G.; Deb, K., On self-adaptive features in real-parameter evolutionary algorithms, IEEE trans. evolutionary comput., 5, 3, 250-270, (2001)
[17] H.-G. Beyer, H.-P. Schwefel, Evolution strategies: a comprehensive introduction, Natural Comput. 1, in press. · Zbl 1014.68134
[18] H.G. Beyer, E. Brucherseifer, W. Jakob, H. Pohlheim, B. Sendhoff, T.B. To, Evolutionäre Algorithmen—Begriffe und Definitionen, Technical Report of the Collaborative Research Center 531, Computational Intelligence, CI-115/01 University of Dortmund, 2001.
[19] J. Born, Evolutionsstrategien zur numerischen Lösung von Adaptationsaufgaben, Ph.D. Thesis, Humboldt-Universität, Berlin, 1978.
[20] Davis, T.E.; Principe, J.C., A Markov chain framework for the simple genetic algorithm, Evolutionary comput., 1, 3, 269-288, (1993)
[21] K. De Jong, Are genetic algorithms function optimizers?, Proc. PPSN II (Parallel Problem Solving from Nature), North-Holland, Amsterdam, 1992, pp. 3-13.
[22] K. De Jong, Genetic algorithms are NOT function optimizers, Foundations of Genetic Algorithms, Vol. 2, Morgan Kaufmann, San Mateo, CA, 1993, pp. 5-17.
[23] S. Droste, T. Jansen, K. Tinnefeld, I. Wegener, A new framework for the valuation of algorithms for black-box optimization, 2001, preprint.
[24] Droste, S.; Jansen, T.; Wegener, I., On the analysis of the (1+1) evolutionary algorithm, Theoret. comput. sci., 276, 51-81, (2002) · Zbl 1002.68037
[25] S. Droste, T. Jansen, I. Wegener, On the optimization of unimodal functions with the (1+1) evolutionary algorithm, Proc. PPSN V (Parallel Problem Solving from Nature), Lecture Notes in Computer Science, Vol. 1498, Springer, Berlin, 1998, pp. 13-22.
[26] S. Droste, T. Jansen, I. Wegener, A natural and simple function which is hard for all evolutionary algorithms, Proc. IECON’2000 (IEEE International Conference on Industrial Electronics, Control and Instrumentation), 2000, pp. 2704-2709.
[27] S. Droste, T. Jansen, I. Wegener, Dynamic parameter control in simple evolutionary algorithms, Proc. Foundations of Genetic Algorithms, Vol. 6, 2001, pp. 275-294. · Zbl 0987.68098
[28] Eiben, A.; Aarts, E.; van Hee, K., Global convergence of genetic algorithmsa Markov chain analysis, (), 4-12
[29] L.J. Eshelman, J.D. Schaffer, Real-coded genetic algorithms and interval schemata, in: L.D. Whitley (Ed.), Proc. Foundations of Genetic Algorithms, Vol. 2, 1991, pp. 187-202.
[30] E. Fiesler, R. Beale (Eds.), Handbook of Neural Computation, Oxford University Press, New York, and Institute of Physics Publishing, Bristol, 1997.
[31] Fogel, D.B., On the philosophical differences between evolutionary algorithms and genetic algorithms, (), 23-29
[32] Fogel, D.B., Evolutionary computationtoward a new philosophy of machine intelligence, (1995), IEEE Press New York
[33] D.B. Fogel (Ed.), Evolutionary Computation—The Fossil Record, IEEE Press, Piscataway, NJ, 1998. · Zbl 0908.68210
[34] D.B. Fogel, W. Atmar (Eds.), Proc. 1st Annu. Conf. on Evolutionary Programming (EP’92), Evolutionary Programming Society, San Diego, CA, 1992.
[35] Fogel, L.J.; Owens, A.J.; Walsh, M.J., Artificial intelligence through simulated evolution, (1966), Wiley New York · Zbl 0148.40701
[36] D.B. Fogel, H.-P. Schwefel, T. Bäck, X. Yao (Eds.), Proc. 5th IEEE Conf. on Evolutionary Computation, 2nd IEEE World Congr. on Computational Intelligence, IEEE Press, Piscataway, NJ, 1998.
[37] Garnier, J.; Kallel, L.; Schoenauer, M., Rigorous hitting times for binary mutations, Evolutionary comput., 7, 173-203, (1999)
[38] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[39] Goldberg, D.E.; Deb, K.; Clark, J.H., Genetic algorithms, noise, and the sizing of populations, Complex systems, 6, 4, 333-362, (1992) · Zbl 0800.68600
[40] Grefenstette, J.J., Deception considered harmful, (), 75-91
[41] N. Hansen, A. Ostermeier, Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation, Proc. IEEE Internat. Conf. on Evolutionary Computation (ICEC’96), IEEE Press, New York, 1996, pp. 312-317.
[42] Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evolutionary comput., 9, 2, 159-195, (2001)
[43] G.R. Harik, E. Cantú-Paz, B.L. Miller, D.E. Goldberg, The gambler’s ruin problem, genetic algorithms, and the sizing of populations, Proc. 1997 IEEE Internat. Conf. on Evolutionary Computation (ICEC ’97), IEEE Press, Piscataway, NJ, Indianapolis, IN, 1997, pp. 7-12.
[44] M. Herdy, Reproductive isolation as strategy parameter in hierarchically organized evolution strategies, Proc. PPSN II (Parallel Problem Solving from Nature), Elsevier, Amsterdam, 1992, pp. 207-217.
[45] C. Höhn, C. Reeves, Are long path problems hard for genetic algorithms?, Proc. PPSN IV (Parallel Problem Solving from Nature), Lecture Notes in Computer Science, Vol. 1141, Springer, Berlin, 1996, pp. 134-143.
[46] Holland, J.H., Adaptation in natural and artificial systems, (1975), The University of Michigan Press Ann Arbor, MI
[47] J. Horn, D.E. Goldberg, K. Deb, Long path problems, Proc. PPSN III (Parallel Problem Solving from Nature), Lecture Notes in Computer Science, Vol. 866, Springer, Berlin, 1994, pp. 149-158.
[48] T. Jansen, I. Wegener, On the analysis of evolutionary algorithms—a proof that crossover really can help, Proc. 7th European Symp. on Algorithms (ESA’99), Lecture Notes in Computer Science, Vol. 1643, Springer, Berlin, 1999, pp. 184-193. · Zbl 0943.68139
[49] T. Jansen, I. Wegener, On the choice of the mutation probability for the (1+1)EA., Proc. PPSN VI (Parallel Problem Solving from Nature), Lecture Notes in Computer Science, Vol. 1917, Springer, Berlin, 2000, pp. 89-98.
[50] T. Jansen, I. Wegener, On the utility of populations in evolutionary algorithms, Proc. GECCO’2001 (Genetic and Evolutionary Computation Conference), 2001, pp. 1034-1041.
[51] T. Jansen, I. Wegener, Real royal road functions—where crossover provably is essential, Proc. GECCO’2001 (Genetic and Evolutionary Computation Conference), 2001, pp. 375-382. · Zbl 1101.68079
[52] T. Jansen, I. Wegener, On the analysis of a dynamic evolutionary algorithm, J. Discrete Algorithms, submitted for publication. · Zbl 1128.68118
[53] Jaynes, E.T., Where do we stand on maximum entropy?, (), 15-118
[54] Maynard Smith, J., Models of evolution, Proc. roy. soc. London B, 219, 315-325, (1983) · Zbl 0531.92015
[55] Z. Michalewicz, J.D. Schaffer, H.-P. Schwefel, D.B. Fogel, H. Kitano (Eds.), Proc. First IEEE Conf. on Evolutionary Computation, 1st IEEE World Congress on Computational Intelligence, IEEE Press, Piscataway, NJ, 1994.
[56] M. Mitchell, S. Forrest, J.H. Holland, The royal road function for genetic algorithms: fitness landscapes and GA performance, Proc. 1st European Conf. Artificial Life, MIT Press, Cambridge, MA, 1994, pp. 245-254.
[57] M. Mitchell, J.H. Holland, S. Forrest, When will a genetic algorithm outperform hill climbing? Advances in Neural Information Processing Systems.
[58] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge · Zbl 0849.68039
[59] H. Mühlenbein, How genetic algorithms really work. I. Mutation and hillclimbing, Proc. PPSN II (Parallel Problem Solving from Nature), 1992, pp. 15-25.
[60] Mühlenbein, H.; Schlierkamp-Voosen, D., The science of breeding and its application to the breeder genetic algorithm icontinuous parameter optimization, Evolutionary comput., 1, 1, 25-49, (1993)
[61] A.I. Oyman, Convergence behavior of evolution strategies on ridge functions, Ph.D. Thesis, University of Dortmund, Dortmund, 1999.
[62] Oyman, A.I.; Beyer, H.-G., Analysis of the (μ/μ, λ)-ES on the parabolic ridge, Evolutionary comput., 8, 3, 267-289, (2000)
[63] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[64] A. Prügel-Bennett, A. Rogers, Modelling genetic algorithm dynamics, Proc. 2nd EvoNet Summer School on Theoretical Aspects of Evolutionary Computing, Springer, Heidelberg, 2001, pp. 59-85. · Zbl 1001.68184
[65] Prügel-Bennett, A.; Shapiro, J.L., An analysis of genetic algorithms using statistical mechanics, Phys. rev. lett., 72, 9, 1305, (1994)
[66] X. Qi, F. Palmieri, Adaptive mutation in the genetic algorithms, Proc. 2nd Annu. Conf. on Evolutionary Programming, Evolutionary Programming Society, La Jolla, CA, 1993, pp. 192-196.
[67] Rabani, Y.; Rabinovich, Y.; Sinclair, A., A computational view of population genetics, Random structures and algorithms, 12, 314-334, (1998) · Zbl 0955.92023
[68] G. Rappl, Konvergenzraten von Random Search verfahren zur globalen Optimierung, Ph.D. Thesis, HSBw München, Germany, 1984.
[69] Rappl, G., On linear convergence of a class of random search algorithms, Zeitschrift angew. math. mech. (ZAMM), 69, 1, 37-45, (1989) · Zbl 0671.90067
[70] Rechenberg, I., Evolutionsstrategieoptimierung technischer systeme nach prinzipien der biologischen evolution, (1973), Frommann-Holzboog Stuttgart
[71] Rechenberg, I., Evolutionsstrategie’94, (1994), Frommann-Holzboog Verlag Stuttgart
[72] Rudolph, G., On correlated mutations in evolution strategies, (), 105-114
[73] Rudolph, G., Convergence properties of canonical genetic algorithms, IEEE trans. neural networks, 5, 1, 96-101, (1994)
[74] Rudolph, G., Convergence properties of evolutionary algorithms, (1997), Verlag Dr. Kovač Hamburg
[75] Rudolph, G., How mutation and selection solve long-path problems in polynomial expected time, Evolutionary comput., 4, 64-78, (1997)
[76] E.H. Ruspini, P.P. Bonissone, W. Pedrycz (Eds.), Handbook of Fuzzy Computation, Institute of Physics Publishing, Bristol, 1998. · Zbl 0902.68068
[77] H.-P. Schwefel, Kybernetische Evolution als Strategie der experimentellen Forschung in der Strömungstechnik, Dipl.-Ing. Thesis, Technical University of Berlin, Hermann Föttinger-Institute for Hydrodynamics, March 1965.
[78] Schwefel, H.-P., Numerische optimierung von computer-modellen mittels der evolutionsstrategie, Interdisciplinary systems research, Vol. 26, (1977), Birkhäuser Basle, Switzerland · Zbl 0347.65035
[79] Schwefel, H.-P., Direct search for optimal parameters within simulation models, (), 91-102
[80] Schwefel, H.-P., Numerical optimization of computer models, (1981), Wiley Chichester
[81] H.-P. Schwefel, Collective phenomena in evolutionary systems, in: P. Checkland, I. Kiss (Eds.), Problems of Constancy and Change—The Complementarity of Systems Approaches to Complexity, Papers presented at the 31st Ann. Meeting of International Society for General System Research, Vol. 2, International Society for General System Research, Budapest, 1987, pp. 1025-1033.
[82] H.-P. Schwefel, R. Männer (Eds.), Parallel Problem Solving from Nature—Proc. 1st Workshop PPSN, Lecture Notes in Computer Science, Vol. 496, Springer, Berlin, 1991.
[83] J.L. Shapiro, Statistical mechanics theory of genetic algorithms, Proc. 2nd EvoNet Summer School on Theoretical Aspects of Evolutionary Computing, Springer, Heidelberg, 2001, pp. 87-108. · Zbl 1001.68185
[84] J.L. Shapiro, A. Prügel-Bennett, L.M. Rattray, A statistical mechanical formulation of the dynamics of genetic algorithms, Lecture Notes in Computer Science, Vol. 865, Springer, Heidelberg, 1994, pp. 17-27.
[85] Spears, W.M., Evolutionary algorithmsthe role of mutation and recombination, (2000), Springer Heidelberg · Zbl 0952.68151
[86] Vose, M.D., The simple genetic algorithmfoundations and theory, (1999), MIT Press Cambridge, MA
[87] I. Wegener, Theoretical aspects of evolutionary algorithms, Proc. ICALP’2001, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 64-78. · Zbl 0986.68137
[88] I. Wegener, C. Witt, On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions, J. Discrete Algorithms, accepted for publication. · Zbl 1066.90143
[89] A.C. Yao, Probabilistics computations: towards a unified measure of complexity, Proc. 17th IEEE Symp. on Foundations of Computer Science (FOCS), 1977, pp. 222-227.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.