Does Comma Selection Help To Cope With Local Optima

Abstract

One hope when using non-elitism in evolutionary computation is that the ability to abandon the current-best solution aids leaving local optima. To improve our understanding of this mechanism, we perform a rigorous runtime analysis of a basic non-elitist evolutionary algorithm (EA), the $(\mu ,\lambda )$ EA, on the most basic benchmark function with a local optimum, the jump function. We prove that for all reasonable values of the parameters and the problem, the expected runtime of the $(\mu ,\lambda )$~EA is, apart from lower order terms, at least as large as the expected runtime of its elitist counterpart, the $(\mu +\lambda )$~EA (for which we conduct the first runtime analysis on jump functions to allow this comparison). Consequently, the ability of the $(\mu ,\lambda )$~EA to leave local optima to inferior solutions does not lead to a runtime advantage. We complement this lower bound with an upper bound that, for broad ranges of the parameters, is identical to our lower bound apart from lower order terms. This is the first runtime result for a non-elitist algorithm on a multi-modal problem that is tight apart from lower order terms.

36 pages. Full version of a paper that appeared at GECCO 2020

References in corpus (4)

• Does Comma Selection Help To Cope With Local Optima
• Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions

Cited by in corpus (17)

• A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• Does Comma Selection Help To Cope With Local Optima
• Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Lower Bounds from Fitness Levels Made Easy
• 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
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms
• Plus Strategies are Exponentially Slower for Planted Optima of Random Height
• An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics
• When Non-Elitism Meets Time-Linkage Problems