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

DOI10.1145/3299904.3340304zbMATH Open1433.68643arXiv1904.08415OpenAlexW3101428723MaRDI QIDQ5215477FDOQ5215477

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)

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.

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)

Cited In (3)

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

Recommendations

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

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)