Level-based analysis of genetic algorithms and other search processes

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

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)
301 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)707 - 719
Number of pages13
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number5
Early online date18 Sep 2017
DOIs
Publication statusPublished - Oct 2018

Keywords

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

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