How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys

DOI10.1016/j.tcs.2022.08.014OpenAlexW4293388201MaRDI QIDQ2699946

Carsten Witt

Publication date: 20 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.08.014

zbMATH Keywords

crossoverruntime analysisrandomized search heuristicsmultimodal functionsjump functionsestimation-of-distribution algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Hoeffding's inequality for supermartingales
• A rigorous analysis of the compact genetic algorithm for linear functions
• Improved time complexity analysis of the simple genetic algorithm
• On the distribution of the number of successes in independent trials
• On the analysis of the \((1+1)\) evolutionary algorithm
• Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax
• On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• Stagnation detection with randomized local search
• The runtime of the compact genetic algorithm on jump functions
• Upper and lower bounds for randomized search heuristics in black-box optimization
• The complex parameter landscape of the compact genetic algorithm
• On the Black-Box Complexity of Example Functions
• On the Distribution of the Number of Successes in Independent Trials
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms
• Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
• An exponential lower bound for the runtime of the compact genetic algorithm on jump functions
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• Theory of Evolutionary Computation
• A Sharp Uniform Bound for the Distribution of Sums of Bernoulli Trials
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Inequalities: theory of majorization and its applications

This page was built for publication: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys