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

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

DOI

View graph of relations

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
Pages1539-1546
ISBN (Print)978-1-4503-5618-3
DOIs
Publication statusPublished - 2018
Event2018 Genetic and Evolutionary Computation Conference - Kyoto Terrsa, Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018

Conference

Conference2018 Genetic and Evolutionary Computation Conference
LocationKyoto Terrsa
CountryJapan
CityKyoto
Period15/07/201819/07/2018
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

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

ID: 151866288