Does comma selection help to cope with local optima?

DOI10.1007/S00453-021-00896-7MaRDI QIDQ2144274zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• On non-elitist evolutionary algorithms optimizing fitness functions with a plateau
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Runtime analysis of non-elitist populations: from classical optimisation to partial information

Cites work

• scientific article; zbMATH DE number 1617341 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• Adaptive drift analysis
• An exponential lower bound for the runtime of the compact genetic algorithm on jump functions
• Analyzing evolutionary algorithms. The computer science perspective.
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Automata, Languages and Programming
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Concentration of first hitting times under additive drift
• Drift analysis and average time complexity of evolutionary algorithms
• Drift analysis and evolutionary algorithms revisited
• Foundations of Genetic Algorithms
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Improved time complexity analysis of the simple genetic algorithm
• Level-based analysis of the univariate marginal distribution algorithm
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• Multiplicative up-drift
• On the analysis of the \((1+1)\) evolutionary algorithm
• Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances
• Probability Inequalities for Sums of Bounded Random Variables
• Runtime analysis for self-adaptive mutation rates
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Simplified drift analysis for proving lower bounds in evolutionary computation
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• The impact of parametrization in memetic evolutionary algorithms
• The interplay of population size and mutation probability in the (1+ ) EA on OneMax
• Theory of evolutionary computation. Recent developments in discrete optimization
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Towards a runtime comparison of natural and artificial evolution
• Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax

Cited in

(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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144274)