Refined upper bounds on the expected runtime of non-elitist populations from fitness-levels

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

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham

Abstract

Recently, an easy-to-use fitness-level technique was introduced to prove upper bounds on the expected runtime of randomised search heuristics with non-elitist populations and unary variation operators. Following this work, we present a new and much more detailed analysis of the population dynamics, leading to a significantly improved fitness-level technique. In addition to improving the technique, the proof has been simplified. From the new fitness-level technique, the upper bound on the runtime in terms of generations can be improved from linear to logarithmic in the population size. Increasing the population size therefore has a smaller impact on the runtime than previously thought. To illustrate this improvement, we show that the current bounds on the runtime of EAs with non-elitist populations on many example functions can be significantly reduced. Furthermore, the new fitness-level technique makes the relationship between the selective pressure and the runtime of the algorithm explicit. Surprisingly, a very weak selective pressure is sufficient to optimise many functions in expected polynomial time. This observation has important consequences of which some are explored in a companion paper.

Details

Original languageEnglish
Title of host publicationGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Publication statusPublished - 2014
Event16th Genetic and Evolutionary Computation Conference, GECCO 2014 - Vancouver, BC, Canada
Duration: 12 Jul 201416 Jul 2014

Conference

Conference16th Genetic and Evolutionary Computation Conference, GECCO 2014
CountryCanada
CityVancouver, BC
Period12/07/1416/07/14

Keywords

  • Drift analysis, Fitness-levels, Non-elitism, Runtime