Hardest monotone functions for evolutionary algorithms

DOI10.1007/978-3-031-57712-3_10MaRDI QIDQ6635984zbMATH OpenFDO

Authors Marc Kaufmann, Maxime Larcher, Johannes Lengler, Oliver Sieberling

Publication date 12 November 2024

Full work available at URL https://doi.org/10.1007/978-3-031-57712-3_10

zbMATH Keywords

\((1 + 1)\)-EAdrift minimizationdynamic environmentsevolutionary algorithmfitness landscapehardest functionsprecise runtime analysisswitching dynamic binary value

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• Adaptive population models for offspring populations and parallel evolutionary algorithms
• Drift analysis and evolutionary algorithms revisited
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Multiplicative drift analysis
• On easiest functions for mutation operators in bio-inspired optimisation
• On the Brittleness of Evolutionary Algorithms
• OneMax is not the easiest function for fitness improvements
• Optimal parameter choices via precise black-box analysis
• Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances
• Runtime analysis of the ( + 1)-EA on the dynamic BinVal function
• Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter
• Self-adjusting population sizes for the (1, )-EA on monotone functions
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Two-dimensional drift analysis: optimizing two functions simultaneously can be hard
• When does hillclimbing fail on monotone functions: an entropy compression argument

Cited in

(1)

• Plus strategies are exponentially slower for planted optima of random height

This page was built for publication: Hardest monotone functions for evolutionary algorithms

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