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)

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.

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
PublisherSpringer
Pages912-921
Number of pages10
ISBN (Electronic)978-3-319-10762-2
ISBN (Print)978-3-319-10761-5
DOIs
Publication statusPublished - 2014
Event13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia
Duration: 13 Sep 201417 Sep 2014

Publication series

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

Conference

Conference13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
Country/TerritorySlovenia
Period13/09/1417/09/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this