Level-Based Analysis of Genetic Algorithms and Other Search Processes

Dogan Corus¹, Duc-Cuong Dang¹, Anton V. Eremeev², and Per Kristian Lehre¹

¹University of Nottingham, United Kingdom

²Omsk Branch of Sobolev Institute of Mathematics, Russia

Abstract. The fitness-level technique is a simple and old way to derive upper bounds for the expected runtime of simple elitist evolutionary algorithms (EAs). Recently, the technique has been adapted to deduce the runtime of algorithms with non-elitist populations and unary variation operators [2,8]. In this paper, we show that the restriction to unary variation operators can be removed. This gives rise to a much more general analytical tool which is applicable to a wide range of search processes. As introductory examples, we provide simple runtime analyses of many variants of the Genetic Algorithm on well-known benchmark functions, such as OneMax, LeadingOnes, and the sorting problem.

LNCS 8672, p. 912 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014