Multiplicative Drift Analysis

Abstract

In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multiplicative version of the classical drift theorem. This allows easier analyses in those settings where the optimization progress is roughly proportional to the current distance to the optimum. To display the strength of this tool, we regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. Here, we first give a relatively simple proof for the fact that any linear function is optimized in expected time $O(n\log n)$, where $n$ is the length of the bit string. Afterwards, we show that in fact any such function is optimized in expected time at most ${(1+o(1)) 1.39 \euler n\ln (n)}$, again using multiplicative drift analysis. We also prove a corresponding lower bound of $(1-o(1))en\ln (n)$ which actually holds for all functions with a unique global optimum. We further demonstrate how our drift theorem immediately gives natural proofs (with better constants) for the best known runtime bounds for the (1+1) Evolutionary Algorithm on combinatorial problems like finding minimum spanning trees, shortest paths, or Euler tours.

Contains results from our GECCO 2010 and CEC 2010 conference paper

Cited by in corpus (29)

• Better Runtime Guarantees Via Stochastic Domination
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• 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
• The $(1+(\lambda ,\lambda ))$ Genetic Algorithm for Permutations
• Precise Runtime Analysis for Plateau Functions
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• Fast Mutation in Crossover-based Algorithms
• Fixed-Target Runtime Analysis
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• First Steps Towards a Runtime Analysis of Neuroevolution
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms
• Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
• Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
• Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• Analyzing the Expected Hitting Time of Evolutionary Computation-based Neural Architecture Search Algorithms
• On Hitting Times for General Quantum Markov Processes
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA