The Runtime of the Compact Genetic Algorithm on Jump Functions

Abstract

In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, Hasenöhrl and Sutton (GECCO 2018) showed for any $k=o(n)$ that the compact genetic algorithm (cGA) with any hypothetical population size $\mu =\Omega (n{e}^{4k}+n^{3.5+\epsilon })$ with high probability finds the optimum of the $n$-dimensional jump function with jump size $k$ in time $O(\mu n^{1.5}\log n)$. We significantly improve this result for small jump sizes $k\le \frac{1}{20}\ln n-1$. In this case, already for $\mu =\Omega (\sqrt{n}\log n)\cap \text{poly}(n)$ the runtime of the cGA with high probability is only $O(\mu \sqrt{n})$. For the smallest admissible values of $\mu$, our result gives a runtime of $O(n\log n)$, whereas the previous one only shows $O(n^{5+\epsilon })$. Since it is known that the cGA with high probability needs at least $\Omega (\mu \sqrt{n})$ iterations to optimize the unimodal OneMx function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. For large $k$, we show that the exponential (in $k$) runtime guarantee of Hasenöhrl and Sutton is tight and cannot be improved, also not by using a smaller hypothetical population size. We prove that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size $k$. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings.

Revised version of the journal version of my GECCO 2019 (arXiv:1903.10983) and FOGA 2019 (arXiv:1904.08415) papers

References in corpus (4)

• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions

Cited by in corpus (12)

• A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• Runtime Analysis for Permutation-based Evolutionary Algorithms
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• Choosing the Right Algorithm With Hints From Complexity Theory
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• A Fresh Look at Lamarckian Evolution and the Baldwin Effect