Does comma selection help to cope with local optima?

DOI10.1007/s00453-021-00896-7OpenAlexW3101412094MaRDI QIDQ2144274

Benjamin Doerr

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.01274

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Related Items (4)

Choosing the right algorithm with hints from complexity theory ⋮ Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Stagnation detection meets fast mutation

Cites Work

• Unnamed Item
• Unnamed Item
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Concentration of first hitting times under additive drift
• Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Improved time complexity analysis of the simple genetic algorithm
• The impact of parametrization in memetic evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax
• Level-based analysis of the univariate marginal distribution algorithm
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• Adaptive drift analysis
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• Multiplicative up-drift
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• The interplay of population size and mutation probability in the \((1+\lambda )\) EA on OneMax
• Towards a runtime comparison of natural and artificial evolution
• Analyzing randomized search heuristics via stochastic domination
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• Runtime analysis for self-adaptive mutation rates
• Drift Analysis and Evolutionary Algorithms Revisited
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• 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
• Probability Inequalities for Sums of Bounded Random Variables
• Foundations of Genetic Algorithms
• Automata, Languages and Programming
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Does comma selection help to cope with local optima?