Medium step sizes are harmful for the compact genetic algorithm

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2018Researchpeer-review


View graph of relations

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
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

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

ID: 151866462