An exponential lower bound for the runtime of the compact genetic algorithm on jump functions

DOI10.1145/3299904.3340304MaRDI QIDQ5215477zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr

Publication date 11 February 2020

Published in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

evolutionary algorithmsruntime analysis

Mathematics Subject Classification ID

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

Abstract: In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multi-modal jump function class, Hasen"ohrl and Sutton (GECCO 2018) proved that the runtime of the compact genetic algorithm with suitable parameter choice on jump functions with high probability is at most polynomial (in the dimension) if the jump size is at most logarithmic (in the dimension), and is at most exponential in the jump size if the jump size is super-logarithmic. The exponential runtime guarantee was achieved with a hypothetical population size that is also exponential in the jump size. Consequently, this setting cannot lead to a better runtime. In this work, we show that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings.

Recommendations

• The runtime of the compact genetic algorithm on jump functions
• Tight bounds on the expected runtime of a standard steady state genetic algorithm
• A rigorous analysis of the compact genetic algorithm for linear functions
• An upper bound on the convergence rates of canonical genetic algorithms
• Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs
• On the runtime analysis of the simple genetic algorithm
• The complex parameter landscape of the compact genetic algorithm
• Techniques for bounding the convergence rate of genetic algorithms

Cited in

(5)

• The complex parameter landscape of the compact genetic algorithm
• Does comma selection help to cope with local optima?
• The runtime of the compact genetic algorithm on jump functions
• A rigorous analysis of the compact genetic algorithm for linear functions
• How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys

This page was built for publication: An exponential lower bound for the runtime of the compact genetic algorithm on jump functions

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