A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost

Abstract

We prove that the compact genetic algorithm (cGA) with hypothetical population size $\mu =\Omega (\sqrt{n}\log n)\cap \text{poly}(n)$ with high probability finds the optimum of any $n$-dimensional jump function with jump size $k<\frac{1}{20}\ln n$ in $O(\mu \sqrt{n})$ iterations. Since it is known that the cGA with high probability needs at least $\Omega (\mu \sqrt{n}+n\log n)$ iterations to optimize the unimodal OneMax 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. Our runtime guarantee improves over the recent upper bound $O(\mu n^{1.5}\log n)$ valid for $\mu =\Omega (n^{3.5+\epsilon })$ of Hasenöhrl and Sutton (GECCO 2018). For the best choice of the hypothetical population size, this result gives a runtime guarantee of $O(n^{5+\epsilon })$, whereas ours gives $O(n\log n)$. We also provide a simple general method based on parallel runs that, under mild conditions, (i)~overcomes the need to specify a suitable population size, but gives a performance close to the one stemming from the best-possible population size, and (ii)~transforms EDAs with high-probability performance guarantees into EDAs with similar bounds on the expected runtime.

25 pages, full version of a paper to appear at GECCO 2019

References in corpus (1)

• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost

Cited by in corpus (12)

• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• Does Comma Selection Help To Cope With Local Optima
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Fast Mutation in Crossover-based Algorithms
• Fixed-Target Runtime Analysis
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value
• An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics