Medium step sizes are harmful for the compact genetic algorithm

Johannes Lengler, Dirk Sudholt, Carsten Witt

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

55 Downloads (Pure)


We study the intricate dynamics of the Compact Genetic Algorithm (cGA) on OneMax, and how its performance depends on the step size 1/K, that determines how quickly decisions about promising bit values are fixed in the probabilistic model. It is known that cGA and UMDA, a related algorithm, run in expected time O(n log n) when the step size is just small enough (K = Θ(n log n)) to avoid wrong decisions being fixed. UMDA also shows the same performance in a very different regime (equivalent to K = Θ(log n) in the cGA) with much larger steps sizes, but for very different reasons: many wrong decisions are fixed initially, but then reverted efficiently. We show that step sizes in between these two optimal regimes are harmful as they yield larger runtimes: we prove a lower bound of Ω(K1/3n+n log n) for the cGA on OneMax for K = O(n/log2 n). For K = Ω(log3 n) the runtime increases with growing K before dropping again to O(Kn + n log n) for K = Ω(n log n). This suggests that the expected runtime for cGA is a bimodal function in K with two very different optimal regions and worse performance in between.
Original languageEnglish
Title of host publication2018 Proceedings of the Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date2018
ISBN (Print)978-1-4503-5618-3
Publication statusPublished - 2018


  • Estimation-of-distribution algorithms
  • Evolutionary algorithms
  • Running time analysis
  • Theory
  • Compact genetic algorithm (cga)

Fingerprint Dive into the research topics of 'Medium step sizes are harmful for the compact genetic algorithm'. Together they form a unique fingerprint.

Cite this