A tight lower bound on the expected runtime of standard steady state genetic algorithms

Pietro S. Oliveto, Dirk Sudholt, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Recent progress in the runtime analysis of evolutionary algorithms (EAs) has allowed the derivation of upper bounds on the expected runtime of standard steady-state GAs. These upper bounds have shown speed-ups of the GAs using crossover and mutation over the same algorithms that only use mutation operators (i.e., steady-state EAs) both for standard unimodal (i.e., OneMax) and multimodal (i.e., Jump) benchmark functions. These upper bounds suggest that populations are beneficial to the GA as well as higher mutation rates than the default 1/n rate. However, making rigorous claims was not possible because matching lower bounds were not available. Proving lower bounds on crossover-based EAs is a notoriously difficult task as it is hard to capture the progress that a diverse population can make. We use a potential function approach to prove a tight lower bound on the expected runtime of the (2 + 1) GA for OneMax for all mutation rates c/n with c < 1.422. This provides the last piece of the puzzle that completes the proof that larger population sizes improve the performance of the standard steady-state GA for OneMax for various mutation rates, and it proves that the optimal mutation rate for the (2 + 1) GA on OneMax is [EQUATION].

Original languageEnglish
Title of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date25 Jun 2020
Pages1323-1331
ISBN (Electronic)9781450371285
DOIs
Publication statusPublished - 25 Jun 2020
Event2020 Genetic and Evolutionary Computation Conference - Online Event, Cancun, Mexico
Duration: 8 Jul 202012 Jul 2020
https://gecco-2020.sigevo.org/index.html/HomePage

Conference

Conference2020 Genetic and Evolutionary Computation Conference
LocationOnline Event
CountryMexico
CityCancun
Period08/07/202012/07/2020
Internet address

Fingerprint

Dive into the research topics of 'A tight lower bound on the expected runtime of standard steady state genetic algorithms'. Together they form a unique fingerprint.

Cite this