Adaptive Drift Analysis

Abstract

We show that, for any c>0, the (1+1) evolutionary algorithm using an arbitrary mutation rate p_n = c/n finds the optimum of a linear objective function over bit strings of length n in expected time Theta(n log n). Previously, this was only known for c at most 1. Since previous work also shows that universal drift functions cannot exist for c larger than a certain constant, we instead define drift functions which depend crucially on the relevant objective functions (and also on c itself). Using these carefully-constructed drift functions, we prove that the expected optimisation time is Theta(n log n). By giving an alternative proof of the multiplicative drift theorem, we also show that our optimisation-time bound holds with high probability.

version 2 - fixed typos

Cited by in corpus (16)

• Better Runtime Guarantees Via Stochastic Domination
• Does Comma Selection Help To Cope With Local Optima
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Working Principles of Binary Differential Evolution
• Multiplicative Up-Drift
• Runtime Analysis for Permutation-based Evolutionary Algorithms
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• (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
• Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
• Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA