Level-based analysis of genetic algorithms and other search processes

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Sheffield University
  • Omsk Branch of Sobolev Institute of Mathematics, Russia
  • University of Nottingham

Abstract

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any nonelitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

Details

Original languageEnglish
Pages (from-to)707 - 719
Number of pages13
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number5
Early online date18 Sep 2017
Publication statusPublished - Oct 2018

Keywords

  • runtime analysis , genetic algorithm , estimation of distribution algorithm , approximation