Abstract
An important step in gaining a better understanding of the stochastic dynamics of evolving populations, is the development of appropriate analytical tools. We present a new drift theorem for populations that allows properties of their long-term behaviour, e.g. the runtime of evolutionary algorithms, to be derived from simple conditions on the one-step behaviour of their variation operators and selection mechanisms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cantú-Paz, E.: A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systems Repartis 10(2), 141–171 (1998)
Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)
Haccou, P., Jagers, P., Vatutin, V.: Branching Processes: Variation, Growth, and Extinction of Populations. Cambridge University Press, Cambridge (2005)
Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability 14(3), 502–525 (1982)
He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3(1), 21–35 (2004)
Kolotilina, L.Y.: Bounds and inequalities for the Perron root of a nonnegative matrix. Journal of Mathematical Sciences 121(4), 2481–2507 (2004)
Lehre, P.K., Yao, X.: On the impact of the mutation-selection balance on the runtime of evolutionary algorithms. In: Proc. of FOGA 2009, pp. 47–58. ACM, New York (2009)
Minc, H.: On the maximal eigenvector of a positive matrix. SIAM Journal on Numerical Analysis 7(3), 424–427 (1970)
Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proc. of GECCO 2009, pp. 835–842. ACM, New York (2009)
Sasaki, G.H., Hajek, B.: The time complexity of maximum matching by simulated annealing. Journal of the ACM 35(2), 387–403 (1988)
Seneta, E.: Non-Negative Matrices. George Allen & Unwin Ltd., London (1973)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lehre, P.K. (2010). Negative Drift in Populations. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds) Parallel Problem Solving from Nature, PPSN XI. PPSN 2010. Lecture Notes in Computer Science, vol 6238. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15844-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-15844-5_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15843-8
Online ISBN: 978-3-642-15844-5
eBook Packages: Computer ScienceComputer Science (R0)