On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms

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


The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known Jump benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on Jump than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension n. In this paper, we investigate variants of the Jump function where the gap is shifted and appears in the middle of the typical search trajectory. Such gaps can still be overcome efficiently in time O (n log n) by majority-vote crossover and an estimation-of-distribution algorithm, even for gap sizes almost [EQUATION]. However, if the global optimum is located in the gap instead of the usual all-ones string, majority-vote crossover would nevertheless approach the all-ones string and be highly inefficient. In sharp contrast, an EDA can still find such a shifted optimum efficiently. Thanks to a general property called fair sampling, the EDA will with high probability sample from almost every fitness level of the function, including levels in the gap, and sample the global optimum even though the overall search trajectory points towards the all-ones string. Finally, we derive limits on the gap size allowing efficient runtimes for the EDA.
Original languageEnglish
Title of host publicationProceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Number of pages15
PublisherAssociation for Computing Machinery
Publication date2021
ISBN (Print)978-1-4503-8352-3
Publication statusPublished - 2021
Event16th ACM/SIGEVO Conference on Foundations of Genetic - Virtual Event
Duration: 6 Sep 20218 Sep 2021


Conference16th ACM/SIGEVO Conference on Foundations of Genetic
LocationVirtual Event


  • Crossover
  • Estimation-of-distribution algorithms
  • Jump function
  • Multimodal functions
  • Randomized search heuristics
  • Runtime analysis


Dive into the research topics of 'On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms'. Together they form a unique fingerprint.

Cite this