Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-14T13:24:56.452Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometric Convergence of Genetic Algorithms Under Tempered Random Restart

Part of: Probabilistic methods, simulation and stochastic differential equations Markov processes

Published online by Cambridge University Press:  14 July 2016

F. Mendivil ,
R. Shonkwiler  and
M. C. Spruill
F. Mendivil*
Affiliation:
Acadia University
R. Shonkwiler*
Affiliation:
Georgia Institute of Technology
M. C. Spruill*
Affiliation:
Georgia Institute of Technology
*
∗Postal address: Mathematics Department, Acadia University, Wolfville, Nova Scotia, Canada. Email address: [email protected]
∗∗Postal address: School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA.
∗∗Postal address: School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Geometric convergence to 0 of the probability that the goal has not been encountered by the nth generation is established for a class of genetic algorithms. These algorithms employ a quickly decreasing mutation rate and a crossover which restarts the algorithm in a controlled way depending on the current population and restricts execution of this crossover to occasions when progress of the algorithm is too slow. It is shown that without the crossover studied here, which amounts to a tempered restart of the algorithm, the asserted geometric convergence need not hold.

Keywords

Nonstationary Markov chainhitting timePerron–Frobeniusdecreasing mutation rate

MSC classification

Secondary: 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) 65C05: Monte Carlo methods
Type
Research Article
Information
Journal of Applied Probability , Volume 46 , Issue 4 , December 2009 , pp. 960 - 974
Copyright
Copyright © Applied Probability Trust 2009 

References

[1] Cerf, R. (1996). A new genetic algorithm. Ann. Appl. Prob. 6, 778–817.Google Scholar
[2] Cerf, R. (1996). The dynamics of mutation-selection algorithms with large population sizes. Ann. Inst. H. Poincaré Prob. Statist. 32, 455–508.Google Scholar
[3] Davis, E. T. and Principe, J. C. (1993). A Markov framework for the simple genetic algorithm. Evolut. Comput. 1, 269–288.Google Scholar
[4] Hu, A., Shonkwiler, R. and Spruill, M. C. (2002). Estimating the convergence rate of a restarted search process. Internat. J. Comput. Numer. Anal. Appl. 1, 353–367.Google Scholar
[5] Löwe, M. (1996). On the convergence of genetic algorithms. Exposition. Math. 14, 289–312.Google Scholar
[6] Mendivil, F., Shonkwiler, R. and Spruill, M. C. (2001). Restarting search algorithms with applications to simulated annealing. Adv. Appl. Prob. 33, 242–259.Google Scholar
[7] Shonkwiler, R. and Van Vleck, E. (1994). Parallel speed-up of Monte Carlo methods for global optimization. J. Complexity 10, 64–95.Google Scholar