Level-based analysis of genetic algorithms and other search processes

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

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham
  • Omsk Branch of Sobolev Institute of Mathematics

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.

Details

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
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) -
CountrySlovenia
Period13/09/1417/09/14