Level-based analysis of genetic algorithms and other search processes

Dogan Corus, Duc Cuong Dang, Anton V. Eremeev, Per Kristian Lehre

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
Number of pages10
ISBN (Electronic)978-3-319-10762-2
ISBN (Print)978-3-319-10761-5
Publication statusPublished - 2014
Event13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia
Duration: 13 Sept 201417 Sept 2014

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Level-based analysis of genetic algorithms and other search processes'. Together they form a unique fingerprint.

Cite this