PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Drift Analysis

Benjamin Doerr, Leslie Ann Goldberg

arXiv:1108.0295v2cs.DS

TL;DR

The paper addresses whether the (1+1) EA optimises linear functions quickly for mutation rates p_n = c/n beyond the previously understood range. It constructs objective-dependent drift functions and proves an O(n log n) expected-time bound, tight up to a constant factor, with a high-probability guarantee as well.

  • Problem

    For mutation rates p_n = c/n beyond the previously understood range, it was open whether the (1+1) EA optimises linear objectives in O(n log n) time; universal feasible drift functions do not suffice for larger c.

    Source: §1 · p. 2, §2.3 · p. 7

  • Method

    The proof constructs feasible, piece-wise polynomial drift functions that depend on the objective function.

    Source: §1 · p. 2, §6 · p. 25

  • Results

    For every constant c, the (1+1) EA has expected optimisation time O(n(f) log n(f)) on linear objectives, with a matching lower bound up to a constant factor and a high-probability bound.

    Source: §1 · p. 2, §2.4 · p. 7

  • Takeaways & Limitations

    Linear functions are optimised in O(n(f) log n(f)) time regardless of the constant in the mutation rate p_n = c/n.

    Source: §2.4 · p. 8

    The drift-function construction is stated for n sufficiently large relative to the constants c, ε, K, and γ.

    Source: §3.4 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The paper extends drift analysis of the (1+1) EA to linear objectives with mutation rate p_n = c/n for any constant c, using objective-dependent drift functions. It also derives high-probability optimisation-time bounds from a reproved multiplicative drift theorem.

1 Introduction

  • Drift analysis is a central evolutionary-algorithm technique, made explicit after earlier implicit analysis of the (1+1) EA on linear functions.The classical analysis considered mutation rate 1/n.Source: §1 · p. 1
  • Earlier drift analyses had limited mutation-rate ranges: one applied only below 1/n, while later universal drift functions stopped working at rates of at least 4/n.Prior work also left open whether the O(n log n) bound held for c ≥ 7.Source: §1 · p. 2
  • For every constant c, objective-dependent feasible drift functions yield an expected O(n log n) optimisation time for linear objectives, matching the standard lower bound up to a constant factor.The paper also proves this bound holds with high probability.Source: §1 · p. 2
  • A reproved multiplicative drift theorem gives high-probability optimisation-time bounds and can extend other known runtime bounds to high probability.The paper notes applications to prior analyses of minimum spanning trees, shortest paths, and Eulerian cycles.Source: §1 · p. 2

2 Drift Analysis

The section develops drift-based analysis for the (1+1) EA and applies it to linear objectives with mutation rate p_n = c/n. Its objective-dependent, piece-wise polynomial drift functions yield O(n(f) log n(f)) expected optimisation time and a high-probability bound.

2.1 The (1+1) evolutionary algorithm

  • The (1+1) EA starts from a uniformly random bit string, flips each bit independently, and accepts offspring with fitness no worse than the current solution.The paper studies linear objectives, which are weighted sums of bits with positive, nondecreasing coefficients.Source: §2.1 · p. 3

2.2 A simple drift theorem with tail bounds

  • A feasible drift function bounds expected optimisation time, while the drift theorem also supplies a probability-tail bound.Its analysis improves on the expected-runtime transformation used in methods of expected weight decrease, which yields a bound weaker by a constant factor.Source: §2.2 · pp. 5–6

2.3 Drift analysis for linear objective functions over bit strings

  • Earlier universal feasible drift functions gave the optimal O(n(f) log n(f)) bound at c = 1, but such families exist only for small c.For larger c, drift functions must depend on the objective function; whether the bound extends beyond c = 1 was previously open.Source: §2.3 · p. 7

2.4 Our result

  • For every positive constant c, the (1+1) EA optimises linear objectives with mutation rate p_n = c/n in expected time O(n(f) log n(f)), with a corresponding high-probability bound.Theorem 7 bounds the probability of exceeding the expected-time bound by kν(n)λ additional steps by k exp(−λ).Source: §2.4 · p. 7
  • The proof constructs objective-dependent drift functions and extends the drift theorem to piece-wise polynomial feasible families.The theorem’s method may inform drift-function design for problems whose known bounds include a log(fmax) factor from using Φf = f.Source: §2.4 · pp. 7–8

2.5 Piece-wise polynomial drift

  • Piece-wise polynomial feasible drift functions let the analysis bound optimisation time by O(n(f) log n(f)) across a fixed number of fitness-based regions.Within each region, the logarithmic range of drift values is O(log n(f)); the proof bounds transitions between adjacent regions.Source: §2.5 · p. 9

3 Construction of the Drift Function

The construction makes the drift function depend on the linear objective’s coefficient pattern, splitting bit positions into blocks so different mutation-acceptance behaviors can be handled. It then assigns weights and establishes properties needed for the resulting family to be feasible and piece-wise polynomial.

3.1 Notation and parameters

  • The parameters are chosen in sequence: ε is arbitrarily small, K is sufficiently large depending on c and ε, and γ sufficiently small depending on c, ε, and K.The analysis assumes n is sufficiently large relative to these constants.Source: §3.1 · p. 10, §3.4 · p. 13

3.2 Splitting into blocks

  • Coefficient behavior motivates blocks: steeply increasing coefficients make the leftmost flipped bit decisive, while comparable coefficients make the balance of good and bad flips decisive.The definitions of steeply increasing and comparable depend on c, and an objective may mix both patterns.Source: §3.2 · p. 10

3.3 Definition of Φf

  • The weights define Φf(x) = Σ_i w_i x_i; copy-regime weights track objective coefficients, while damped-regime weights limit their growth.The construction starts with w1 = 1 and uses the block’s rightmost weight as its reference.Source: §3.3 · p. 11
  • Jumps partition bit strings into fitness-ordered classes, and the constructed drift family is piece-wise polynomial for mutation rate c/n.The partition condition follows from weight ratios exceeding n^2 at jumps.Source: §3.3 · pp. 11–12

3.4 Auxiliary results concerning the weights wi

  • For a non-leftmost block in the damped regime, w_ℓB = K^(tc/n)w_rB when its endpoints differ by t positions.This relation is one of the auxiliary weight bounds used in the construction.Source: §3.4 · p. 13

4 Feasible Drift

This section establishes that the constructed drift functions are ν-feasible for the (1+1) EA with mutation rate c/n, where ν(n)=O(n), proving the drift condition across five cases based on bit position and neighboring blocks. This feasibility, together with the family’s piece-wise polynomial property, yields Theorem 7.

4 Feasible Drift

  • For mutation rate c/n, the constructed drift functions are ν-feasible for the EA, with ν(n)=O(n); Lemma 18 establishes the required third feasibility condition.Because the drift functions are also piece-wise polynomial, the paper applies Lemma 18 to bound expected optimisation time.Source: §4 · pp. 14, 16

4.1 Case 1

  • When B and its adjacent blocks are not long, conditioning on a bit’s flip and the left-block constraint establishes the drift bound.The argument also covers the leftmost-block case by treating a single bit as L.Source: §4.1 · p. 17

4.2 Case 2

  • When L is long and i lies in B’s rightmost miniblock, the Case 1 argument applies with the leftmost bit of B as the constraint.The mutation is conditioned on Ii[t+1]; accepted moves imply the corresponding event at ℓB.Source: §4.2 · p. 18

4.3 Case 3

  • When B lies immediately left of a long block R, the proof uses that B is in the copy regime while its short left neighbor L is damped.For accepted mutations, the proof applies the left-block constraint and compares drift weights across the two regimes.Source: §4.3 · p. 19

4.4 Case 4

  • When L is long and i lies in B’s leftmost miniblock, the proof bounds contributions from L, B, and earlier positions to establish the drift condition.It treats accepted and rejected mutations separately and concludes that Equation (3) holds.Source: §4.4 · pp. 20, 22, 23

4.5 Case 5

  • When B is long, the proof allows short neighboring blocks or artificial single-bit boundary blocks and establishes Equation (3).The conclusion gives conditional expected drift at least Pwi(1−ε) for n≥n0.Source: §4.5 · pp. 23–24
  • The constructed drift-function family is ν-feasible for the EA with ν(n) = O(n) and piece-wise polynomial with respect to the EA, yielding Theorem 7 via Lemma 9 and Definition 10.Source: §4.5 · p. 24

5 A Simple Lower Bound

This section gives a lower bound showing that the expected-runtime upper bound cannot improve by more than a constant factor. Its proof uses the difficulty of touching all initially set bits within a short run.

5 A Simple Lower Bound

  • This lower-bound argument extends Lemma 10 in using the same proof idea.Source: §5 · p. 25
  • The probability that optimization finishes within n(f) ln(n(f))/(2(ĉ + 1)) is at most exp(−n(f)Ω(1)).Here ĉ = max{1, c}, for any positive constant c and linear objective family.Source: §5 · p. 25
  • A uniform random initial string has at least n/3 one-bits with probability at least 1 − exp(−n/36), and touching all those bits within T steps is unlikely.The probability that all these bits are touched is at most exp(−(1/3)n^1/2).Source: §5 · p. 25

6 Conclusion

For any positive constant c, the paper’s constructed drift functions yield an O(n(f) log n(f)) expected optimization-time bound for linear objectives. The conclusion also reports a high-probability version and notes that the drift theorem can extend other expected-time bounds.

6 Conclusion

  • For mutation rate c/n, the (1+1) EA has expected optimization time O(n(f) log n(f)) on linear objective families over bit strings.Source: §6 · p. 25
  • The drift functions depend on the relevant objective functions, and reproving a classical drift theorem gives a high-probability version of the runtime bound.Source: §6 · p. 25
  • The revised drift theorem can extend other expected-time bounds to high probability; examples include minimum spanning trees, shortest paths, and Eulerian cycles in.Source: §6 · p. 25
Loading 1108.0295v2…