Abstract
Since the state transitions of an evolutionary algorithm (EA) are of stochastic nature, the deterministic concept of the “convergence to the optimum” is not appropriate. In order to clarify the exact semantic of a phrase like “the EA converges to the global optimum” one has to, at first, establish the connection between EAs and stochastic processes before distinguishing between the various modes of stochastic convergence of stochastic processes. Subsequently, this powerful framework is applied to derive convergence results for EAs.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aarts EHL, Korst J (1989) Simulated annealing and Boltzman machines: a stochastic approach to combinatorial optimization and neural computing. Wiley, Chichester
Adler D (1993) Genetic algorithms and simulated annealing: A marriage proposal. In: IEEE international conference on neural networks, San Francisco, CA, March–April 1993. IEEE Press, Piscataway, NJ, pp 1104–1109
Agapie A (1998a) Genetic algorithms: minimal conditions for convergence. In: Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) AE'97: Artificial evolution: Third European conference; selected papers, Nimes, France, October 1997. Springer, Berlin, pp 183–193
Agapie A (1998b) Modelling genetic algorithms: from Markov chains to dependance with complete connections. In: Bäck T, Eiben AE, Schoenauer M, Schwefel HP (eds) Parallel problem solving from nature – PPSN V. Springer, Berlin, pp 3–12
Agapie A (2007) Evolutionary algorithms: modeling and convergence. Editura Academiei Române, Bucarest, Romania
Agapie A, Agapie M (2007) Transition functions for evolutionary algorithms on continuous state-space. J Math Model Algorithms 6(2):297–315
Auger A (2004) Convergence results for the (1,λ)-ES using the theory of φ-irreducible Markov chains. Theor Comput Sci 334(1–3):181–231
Bélisle CJP (1992) Convergence theorems for a class of simulated annealing algorithms on \({\mathbb R}^{d}\). J Appl Probability 29:885–895
Beume N, Naujoks B, Preuss M, Rudolph G, Wagner T (2009) Effects of 1-greedy S-metric-selection on innumerably large pareto fronts. In: Ehrgott M et al. (eds) Proceedings of 5th international conference on evolutionary multi-criterion optimization (EMO 2009), Nantes, France, April 2009. Springer, Berlin, pp 21–35
Bienvenüe A, Francois O (2003) Global convergence for evolution strategies in spherical problems: some simple proofs and difficulties. Theor Comput Sci 306(1–3):269–289
Born J (1978) Evolutionsstrategien zur numerischen Lösung von Adaptationsaufgaben. Dissertation A, Humboldt-Universität, Berlin
Bucy R (1965) Stability and positive supermartingales. J Differ Equations 1(2):151–155
Bucy R, Joseph P (1968) Filtering for stochastic processes with applications to guidance. Interscience Publishers, New York
Davis T (1991) Toward an extrapolation of the simulated annealing convergence theory onto the simple genetic algorithm. PhD thesis, University of Florida, Gainesville
Davis T, Principe J (1993) A Markov chain framework for the simple genetic algorithm. Evol Comput 1(3):269–288
Devroye LP (1976) On the convergence of statistical search. IEEE Trans Syst Man Cybern 6(1):46–56
Doob J (1967) Stochastic processes, 7th edn. Wiley, New York
Dueck G, Scheuer T (1990) Threshold accepting: a general purpose optimization algorithm superior to simulated annealing. J Comput Phys 90(1):161–175
Eiben AE, Aarts EHL, van Hee KM (1991) Global convergence of genetic algorithms: a Markov chain analysis. In: Schwefel HP, Männer R (eds) Parallel problem solving from nature. Springer, Berlin, pp 4–12
Fogel D (1994) Asymptotic convergence properties of genetic algorithms and evolutionary programming: analysis and experiments. Cybern Syst 25(3): 389–407
Greenwood G, Zhu Q (2001) Convergence in evolutionary programs with self-adaptation. Evol Comput 9(2):147–157
Haario H, Saksman E (1991) Simulated annealing process in general state space. Adv Appl Probability 23:866–893
Hajek B (1988) Cooling schedules for optimal annealing. Math Oper Res 13(2):311–329
Hanne T (1999) On the convergence of multiobjective evolutionary algorithms. Eur J Oper Res 117(3): 553–564
He J, Kang K (1999) On the convergence rates of genetic algorithms. Theor Comput Sci 229(1–2):23–39
He J, Yu X (2001) Conditions for the convergence of evolutionary algorithms. J Syst Archit 47(7): 601–612
Iosifescu M (1980) Finite Markov processes and their applications. Wiley, Chichester
Iosifescu M, Grigorescu S (1990) Dependence with complete connections and its applications. Cambridge University Press, Cambridge
Jägersküpper J (2006) How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms. Theor Comput Sci 361(1):38–56
Jägersküpper J (2007) Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theor Comput Sci 379(3):329–347
Lukacs E (1975) Stochastic convergence, 2nd edn. Academic, New York
Mahfoud SW, Goldberg DE (1992) A genetic algorithm for parallel simulated annealing. In: Männer R, Manderick B (eds) Parallel problem solving from nature, vol 2. North Holland, Amsterdam, pp 301–310
Mahfoud SW, Goldberg DE (1995) Parallel recombinative simulated annealing: a genetic algorithm. Parallel Comput 21:1–28
Meyn S, Tweedie R (1993) Markov chains and stochastic stability. Springer, London
Muhammad A, Bargiela A, King G (1999) Fine-grained parallel genetic algorithm: a global convergence criterion. Int J Comput Math 73(2):139–155
Neveu J (1975) Discrete-parameter martingales. North Holland, Amsterdam
Nix A, Vose M (1992) Modeling genetic algorithms with Markov chains. Ann Math Artif Intell 5:79–88
Nummelin E (1984) General irreducible Markov chains and non-negative operators. Cambridge University Press, Cambridge
Oppel U, Hohenbichler M (1978) Auf der Zufallssuche basierende Evolutionsprozesse. In: Schneider B, Ranft U (eds) Simulationsmethoden in der Medizin und Biologie. Springer, Berlin, pp 130–155
Pintér J (1984) Convergence properties of stochastic optimization procedures. Math Oper Stat Ser Optimization 15:405–427
Rudolph G (1994a) Convergence of non-elitist strategies. In: Proceedings of the first IEEE conference on evolutionary computation, vol 1. Orlando, FL, June 1994. IEEE Press, Piscataway, NJ, pp 63–66
Rudolph G (1994b) Convergence properties of canonical genetic algorithms. IEEE Trans Neural Netw 5(1):96–101
Rudolph G (1994c) An evolutionary algorithm for integer programming. In: Davidor Y, Schwefel HP, Männer R (eds) Parallel problem solving from nature, vol 3. Springer, Berlin, pp 139–148
Rudolph G (1996) Convergence of evolutionary algorithms in general search spaces. In: Proceedings of the third IEEE conference on evolutionary computation, Nagoya, Japan, May 1996. IEEE Press, Piscataway, NJ, pp 50–54
Rudolph G (1997a) Convergence properties of evolutionary algorithms. Kovač, Hamburg
Rudolph G (1997b) Convergence rates of evolutionary algorithms for a class of convex objective functions. Control Cybern 26(3):375–390
Rudolph G (1998a) Evolutionary search for minimal elements in partially ordered finite sets. In: Porto VW, Saravanan N, Waagen D, Eiben AE (eds) Evolutionary programming VII, Proceedings of the 7th annual conference on evolutionary programming, San Diego, CA, March 1998. Springer, Berlin, pp 345–353
Rudolph G (1998b) Finite Markov chain results in evolutionary computation: a tour d’horizon. Fund Inform 35(1–4):67–89
Rudolph G (1998c) On a multi-objective evolutionary algorithm and its convergence to the Pareto set. In: Proceedings of the 1998 IEEE international conference on evolutionary computation, Anchorage, AK, May 1998. IEEE Press, Piscataway, NJ, pp 511–516
Rudolph G (1999) Global convergence and self-adaptation: A counter-example. In: CEC'99: Proceedings of the 1999 congress of evolutionary computation, vol 1. Washington, DC, July 1999. IEEE Press, Piscataway, NJ, pp 646–651
Rudolph G (2001a) Evolutionary search under partially ordered fitness sets. In: Sebaaly MF (ed) ISI 2001: Proceedings of the international NAISO congress on information science innovations, Dubai, UAE, March 2001. ICSC Academic Press, Millet and Sliedrecht, pp 818–822
Rudolph G (2001b) Self-adaptive mutations may lead to premature convergence. IEEE Trans Evol Comput 5(4):410–414
Rudolph G (2005) Analysis of a non-generational mutationless evolutionary algorithm for separable fitness functions. Int J Comput Intell Res 1(1):77–84
Rudolph G, Agapie A (2000) Convergence properties of some multi-objective evolutionary algorithms. In: Zalzala A, Fonseca C, Kim JH, Smith A, Yao X (eds) CEC 2000: Proceedings of the 2000 congress on evolutionary computation, vol 2. La Jolla, CA, July 2000. IEEE Press, Piscataway, NJ, pp 1010–1016
Schmitt L (2001) Theory of genetic algorithms. Theor Comput Sci 259(1–2):1–61
Schmitt L (2004) Theory of genetic algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness functions under scaling. Theor Comput Sci 310(1–3):181–231
Schmitt LM, Nehaniv CL, Fujii RH (1998) Linear analysis of genetic algorithms. Theor Comput Sci 200(1–2):101–134
Schütze O, Laumanns M, Tantar E, Coello Coello C, Talbi EG (2007) Convergence of stochastic search algorithms to gap-free Pareto front approximations. In: GECCO 2007: Proceedings of the 9th annual conference on genetic and evolutionary computation, London, July 2007. ACM, New York, pp 892–901
Semenov M, Terkel D (2003) Analysis of convergence of an evolutionary algorithm with self-adaptation using a stochastic Lyapunov function. Evol Comput 11(4):363–379
Seneta E (1981) Non-negative matrices and Markov chains, 2nd edn. Springer, New York
Solis FJ, Wets RJB (1981) Minimization by random search techniques. Math Oper Res 6(1):19–30
Suzuki J (1993) A Markov chain analysis on a genetic algorithm. In: Forrest S (ed) Proceedings of the fifth international conference on genetic algorithms, Urbana-Champaign, IL, June 1993. Morgan Kaufmann, San Mateo, CA, pp 146–153
Suzuki J (1995) A Markov chain analysis on simple genetic algorithms. IEEE Trans Syst Man Cybern 25(4):655–659
Suzuki J (1998) A further result on the Markov chain model of genetic algorithm and its application to a simulated annealing-like strategy. IEEE Trans Syst Man Cybern B 28(1):95–102
Williams D (1991) Probability with martingales. Cambridge University Press, Cambridge
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms: comparative case study. In: Eiben A et al. (eds) Parallel problem solving from nature (PPSN V). Springer, Berlin, pp 292–301
Zitzler E, Thiele L, Bader J (2008) On set-based multiobjective optimization. Technical Report 300, Computer Engineering and Networks Laboratory, ETH Zurich
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this entry
Cite this entry
Rudolph, G. (2012). Stochastic Convergence. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds) Handbook of Natural Computing. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92910-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-92910-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92909-3
Online ISBN: 978-3-540-92910-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering