Domino convergence: Why one should hill-climb on linear functions

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

51 Downloads (Pure)


In the theory community of evolutionary computation, linear pseudo-boolean functions are often regarded as easy problems since all of them can be optimized in expected time O(n log n) by simple unbiased algorithms. However, results from genetic algorithms and estimation-of-distribution algorithms indicate that these algorithms treat different linear functions differently. More precisely, an effect called "domino convergence" is described in the literature, which means that bits of large weight in the linear function are optimized earlier than bits of low weight. Hence, different linear functions may lead to rather different expected optimization times. The present paper conducts a study of domino convergence. By rigorous runtime analyses, it is shown that domino convergence is mostly a consequence of the crossover underlying genetic algorithms and EDAs. Here a performance gap of order Ω(n/log n) between different linear functions is proved. In simple mutation-only EAs the effect of domino convergence is much less pronounced, with the typical performance gap being logarithmic in the population size. The effect disappears when population size 1 is used and the algorithm is reduced to hillclimbing. Different selection mechanisms, including cut and tournament selection are investigated and their impact on domino convergence is analyzed.
Original languageEnglish
Title of host publicationProceedings of the 2018 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date2018
ISBN (Print)978-1-4503-5618-3
Publication statusPublished - 2018
Event2018 Genetic and Evolutionary Computation Conference - Kyoto Terrsa, Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018


Conference2018 Genetic and Evolutionary Computation Conference
LocationKyoto Terrsa


  • Theory
  • Genetic algorithms
  • Estimation of distribution algorithms
  • Run-time analysis

Fingerprint Dive into the research topics of 'Domino convergence: Why one should hill-climb on linear functions'. Together they form a unique fingerprint.

Cite this