Better Runtime Guarantees Via Stochastic Domination

Abstract

Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and the probability-theoretical part of deriving the desired probabilistic guarantees from this statement, and it helps finding simpler and more natural proofs. As particular results, we prove a fitness level theorem which shows that the runtime is dominated by a sum of independent geometric random variables, we prove the first tail bounds for several classic runtime problems, and we give a short and natural proof for Witt's result that the runtime of any $(\mu ,p)$ mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the \oea on the \onemax function. As side-products, we determine the fastest unbiased (1+1) algorithm for the \leadingones benchmark problem, both in the general case and when restricted to static mutation operators, and we prove a Chernoff-type tail bound for sums of independent coupon collector distributions.

Significantly extended version of a paper that appeared in the proceedings of EvoCOP 2018

References in corpus (3)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Evolutionary Algorithms and Dynamic Programming
• Fast Genetic Algorithms

Cited by in corpus (29)

• Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• Benchmarking Discrete Optimization Heuristics with IOHprofiler
• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• Does Comma Selection Help To Cope With Local Optima
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Working Principles of Binary Differential Evolution
• Multiplicative Up-Drift
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Lower Bounds from Fitness Levels Made Easy
• Benchmarking a $(\mu +\lambda )$ Genetic Algorithm with Configurable Crossover Probability
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions
• Choosing the Right Algorithm With Hints From Complexity Theory
• Fast Mutation in Crossover-based Algorithms
• Fixed-Target Runtime Analysis
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• The $(1+(\lambda ,\lambda ))$ Global SEMO Algorithm
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
• Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
• Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis
• Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value
• Enhancing Parameter Control Policies with State Information
• Runtime Analysis for Self-adaptive Mutation Rates
• An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA
• When Non-Elitism Meets Time-Linkage Problems