PaperlayerView exact revision on arXiv

Source-linked AI summary

The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate

Benjamin Doerr, Christian Gießen, Carsten Witt, Jing Yang

arXiv:1704.02191v3cs.NE

TL;DR

Evolutionary algorithms depend on effective parameter settings, motivating simpler self-adjusting approaches that adapt rates from recent performance. This paper analyzes a self-adjusting (1+λ) EA on OneMax and proves an expected runtime of O(nλ/log λ + n log n) fitness evaluations, matching an asymptotically optimal bound.

  • Problem

    Evolutionary algorithms often depend crucially on selecting suitable parameter settings, motivating designer-friendly self-adjusting rules that adapt parameters from recent performance.

    Source: §1 · pp. 1–2

  • Method

    The (1+λ) EA creates offspring with larger and smaller mutation rates, then adjusts the rate according to which subpopulation produces the best offspring.

    Source: §10 · p. 35

  • Results

    O(nλ/log λ + n log n) fitness evaluations are sufficient to optimize OneMax, matching a runtime previously shown asymptotically optimal among λ-parallel black-box algorithms [2].

    Source: §10 · p. 37

  • Takeaways & Limitations

    The self-adjusting mechanism finds very good mutation rates on the fly and speeds up the mutation-based algorithm on OneMax by more than a constant factor.

    Source: §10 · p. 37

    The generalization of larger beneficial mutation rates and the mechanism's improvements to other algorithms and problems remain open questions.

    Source: §10 · p. 37

Abstract

from arXiv · show

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+\lambda)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+\lambda)$ EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(n\lambda/\log\lambda+n\log n)$. This time is asymptotically smaller than the optimization time of the classic $(1+\lambda)$ EA. Previous work shows that this performance is best-possible among all $\lambda$-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.

1 Introduction

The paper introduces a simple self-adjusting mutation-rate mechanism for population-based EAs and analyzes it on OneMax. It shows that the mechanism can attain the asymptotically optimal runtime associated with carefully chosen dynamic mutation rates.

1 Introduction

  • Dynamic parameter control can outperform fixed settings, but fitness-dependent rules shift the design burden toward finding a suitable functional relation between state and parameter.The paper motivates simpler self-adjusting rules because mutation-rate success is non-monotonic: low success can reflect either too-small or too-large mutation rates.Source: §1 · p. 2

1.1 A New Self-Adjusting Mechanism for Population-Based EAs

  • The mechanism creates offspring using mutation rates twice and half the current rate, then adjusts the current rate based on the better-performing subpopulation.The rate is bounded so that the subpopulation rates remain within [1/n, 1/2].Source: §1.1 · pp. 2–3
  • Random rate modifications allow the algorithm to escape locally attractive rates and reach other discrete mutation rates with inverse-polynomial probability.The analysis exploits these random modifications to show that sufficiently good mutation rates are selected on the fly.Source: §1.1 · p. 3

1.2 Runtime Analysis for the Self-Adjusting (1+λ) EA on OneMax

  • The self-adjusting (1+λ) EA optimizes OneMax in O(nλ/log λ + n log n) expected fitness evaluations, matching the asymptotically optimal runtime for λ-parallel unbiased black-box algorithms.The result is also described as the first super-constant speed-up achieved by a simple mutation-based EA through self-adjusting mutation rates.Source: §1.2 · p. 4
  • A fixed mutation rate r = ln(λ)/2 also achieves Θ(n/log λ) generations when λ is not too small, whereas constant rates are not asymptotically optimal in that regime.This provides a side result showing that mutation rates substantially larger than the usual constant choice can be useful on OneMax.Source: §1.2 · pp. 3–4
  • The runtime analysis partitions OneMax optimization into fitness-distance regimes because proving sufficient progress requires precise comparisons between the two offspring subpopulations.The proof overview identifies the far, middle, and near regions as requiring different arguments.Source: §1.2 · p. 5

2 Related Work

Related work establishes that dynamic and self-adjusting parameter choices can outperform static settings, while motivating a simpler mutation-rate mechanism for population-based EAs.

2.1 The (1+λ) EA

  • The (1+λ) EA has well-understood OneMax runtimes, including population-size-dependent speed-ups and several explicit bounds on other test functions.These analyses largely concern fixed parameters or specific dynamic choices.Source: §2.1 · p. 5

2.2.1 Deterministic Parameter Control

  • Dynamic parameter control can outperform static settings, but deterministic schedules may also be slower by Θ(log n) on classic problems.The cited cyclic scheme can significantly outperform every static rate on an example function while losing on many standard problems.Source: §2.2 · p. 5, §2.2.1 · p. 6

2.2.2 Adaptive Parameter Control

  • Adaptive and fitness-dependent parameter choices improve runtimes on several benchmarks, but discovering the right dependence on fitness may be difficult for algorithm users.Examples include improvements on LeadingOnes and OneMax through mutation rates or offspring population sizes tied to fitness distance.Source: §2.2.2 · pp. 6–7, §2.2.3 · p. 7

2.2.3 Self-adjusting and Self-adaptive Parameter Control

  • Self-adjusting mechanisms replace manually discovered functional dependencies with simple feedback rules, and prior analyses show improvements for population size, island number, and mutation strength.The cited literature includes success-based updates and self-adaptive mutation rates with promising theoretical speed-ups.Source: §2.2.3 · pp. 7–8
  • The proposed mechanism addresses bookkeeping and discounting difficulties in the learning mechanism of by using larger populations to learn from the current iteration.It also deliberately tests parameter values slightly away from the current optimum.Source: §2.2.3 · p. 8

2.2.4 Selection Hyper-Heuristics

  • Selection hyper-heuristics dynamically choose among low-level operators, but runtime comparisons remain incomplete and operator choice can depend critically on phase-length adaptation.For LeadingOnes, several heuristics have tight but overlapping bounds; later work obtains an asymptotically optimal runtime with multiplicative phase-length adjustment.Source: §2.2.4 · pp. 8–10
  • A reported mixed 1-bit/2-bit-flip runtime bound appears incorrect at p = 0, where only 2-bit flips cannot reach the optimum from odd Hamming distance.The expected optimization time is therefore infinite in that case, as noted in the text.Source: §2.2.4 · p. 9

3 Preliminaries

The preliminaries define the self-adjusting (1+λ) EA and collect drift, concentration, occupation-probability, and inequality tools used in its runtime analysis.

3.1 Algorithm

  • The algorithm creates half its offspring with mutation rate r/2 and half with rate 2r, then updates r using either the winning rate or a random neighboring rate.The update is success-based with probability 1/2 and random with probability 1/2, including iterations where the parent survives.Source: §3.1 · pp. 10–11
  • Mutation rates are clipped to [2, n/4], and the initial rate only needs to satisfy rinit ≥ 2.The bounds keep the subpopulation rates within useful mutation-strength ranges.Source: §3.1 · pp. 10–11
  • Random rate adjustments allow the algorithm to cross valleys of unfavorable mutation-rate values when offspring quality is not unimodal in the rate.The text contrasts this with larger, more irregular random deviations from the current rate.Source: §3.1 · p. 11
  • Runtime is measured in generations, whereas function evaluations are λ times larger because each generation evaluates λ offspring.Generation count is especially relevant when offspring evaluations are massively parallel.Source: §3.1 · pp. 11–12

3.2 Drift Theorems

  • Variable and multiplicative drift theorems convert expected progress toward an absorbing optimum into upper bounds on hitting time.The preliminaries also state additive drift as a special case of variable drift.Source: §3.2 · p. 12

3.3 Chernoff Bounds

  • Chernoff and Bernstein inequalities provide concentration bounds for independent variables, including bounded variables and upper-tail deviations.These estimates support the later control of offspring quality and mutation-rate fluctuations.Source: §3.3 · p. 13

3.4 Occupation Probabilities

  • Occupation-probability analysis bounds how far a mutation rate can move when its logarithm has bounded steps and drift toward a target.Lemma 7 gives an exponentially decreasing upper bound on large rate excursions under a downward-drift condition.Source: §3.4 · p. 13

3.5 Useful Inequalities

  • The section also records elementary logarithmic and exponential inequalities used repeatedly in the runtime proofs.These include ln x ≤ x/e and related bounds for exponential expressions.Source: §3.5 · p. 14

4 Proof Overview

The proof partitions OneMax by fitness distance and combines region-specific mutation-rate control with variable drift to bound the total runtime.

4 Proof Overview

  • Variable drift converts region-specific expected fitness progress into an expected number of generations until the optimum.The parent distance k is the objective value and Hamming distance to the all-zero optimum under minimization.Source: §4 · p. 14
  • The main technical challenge is proving that self-adjustment selects sufficiently good mutation rates often enough to guarantee progress.Different fitness-distance regimes require different analyses of the two offspring subpopulations.Source: §4 · p. 14
  • In the far region, rates roughly proportional to ln λ / ln(en/k) are needed, while concentration controls deviations as the target range changes with k.The analysis seeks sufficiently high rates to obtain average progress of order ln λ per iteration where required.Source: §4 · pp. 14–15
  • The middle region needs only constant-probability rates below roughly 1/2 ln λ, yielding progress at least min{1, λk/32n} and traversal time O(n/log λ).Occupation probabilities and concentration make excessively large rates unlikely, while random fluctuations can reduce the rate into the useful range.Source: §4 · p. 15
  • In the near region, the optimal rate is r = 2, but both subpopulations often produce parent copies, so the smaller rate wins through having more best offspring.This establishes downward drift toward 2 and requires additional control of rare rates above ln λ.Source: §4 · pp. 15–16
  • A potential function combined with occupation probabilities shows that the difficult interval above the near-region threshold is left toward lower rates with probability Ω(1).Rates above ln λ typically make all offspring worse than the parent, but the proof must handle a small interval lacking direct rate drift.Source: §4 · p. 16

5 Far Region

In the far region, the self-adjusting EA drives its mutation rate toward a logarithmic fitness-dependent interval and reaches distance k ≤ n/ln λ in O(n/log λ) expected iterations.

5 Far Region

  • The analysis covers the regime k ≥ n/ln λ, where progress is easier but the optimal mutation rate changes most sharply.Source: §5 · p. 16
  • The analysis first establishes constant-probability selection of the 2r or r/2 subpopulation under corresponding rate regimes, supporting directional rate adjustment.Source: §5 · pp. 16–18
  • When the rate is too large, the best offspring is unlikely to be at least as good as its parent, pushing rate selection downward.Source: §5 · p. 19
  • The mutation rate has constant drift toward [c1(k) ln n, c2(k) ln n], while random rate movements permit entry into a narrower range with useful fitness drift.Source: §5 · pp. 19, 24
  • Within the useful range, the expected fitness drift is at least 10^-3 ln λ for k near n/2 and remains logarithmic in λ across the far region.Source: §5 · pp. 19, 21, 22
  • O(n/log λ) expected iterations suffice to reach fitness distance k ≤ n/ln λ, regardless of the initial mutation rate.Source: §5 · pp. 22, 24

6 Middle Region

In the middle region, rates up to logarithmic size provide sufficient drift, and the self-adjusting EA reaches distance k ≤ n/λ in O(n/log λ) expected generations.

6 Middle Region

  • The relevant mutation-rate region is 1 ≤ r ≤ ln(λ)/2, so performance in this part of the search is relatively insensitive to the exact rate.Source: §6 · pp. 24–25
  • For n/λ ≤ k ≤ n/ln λ and 2 ≤ r ≤ ln λ, the analysis derives a positive fitness drift from offspring that avoid flipping zero-bits.Source: §6 · p. 25
  • O(n/log λ) expected generations suffice to reduce the OneMax distance from k ≤ n/ln λ to k ≤ n/λ.Source: §6 · p. 26
  • Rate adjustment reaches the upper useful range in O(log n) generations, after which random rate changes enter rates at most ln(λ) with constant probability.Source: §6 · p. 26

7 Near Region

In the near region, the algorithm repeatedly brings the mutation rate down to constant values, enabling a multiplicative fitness drift and an O(n log(n)/λ + log n) expected time to reach the optimum.

7 Near Region

  • For 4 ≤ r_t ≤ ln(λ)/4, the next mutation rate equals r_t/2 with probability at least 0.5099, driving the rate toward constant values.Source: §7 · pp. 26, 29
  • The selection bias toward the half-rate subpopulation follows from its larger supply of offspring that avoid zero-bit flips when the current distance is at most n/λ.Source: §7 · pp. 26–27
  • The near-region analysis restricts one lemma to r_t ≥ 4, although the authors state this restriction is not strictly necessary.Source: §7 · p. 28
  • O(n log(n)/λ + log n) expected generations suffice to reach the optimum from distance k ≤ n/λ.Source: §7 · pp. 29–30
  • Once the rate is O(1), the OneMax distance has improvement probability Θ(λ/n), yielding O(n log(n)/λ) generations by multiplicative drift.Source: §7 · pp. 29–30

8 Putting Everything Together

Combining the far, middle, and near analyses yields the overall generation bound, while a fixed rate r = ln(λ)/2 achieves the same asymptotic improvement in the relevant regime.

8 Putting Everything Together

  • O(n/log λ + n log(n)/λ) expected generations follow by adding the bounds for the three fitness-distance regions.Source: §8 · p. 30
  • The far-region contribution is O(n/log λ), including the time needed to adjust the mutation rate toward useful ranges.Source: §8 · p. 30
  • The middle-region analysis contributes O(n/log λ) generations to reduce the distance to at most n/λ.Source: §8 · p. 30
  • The near-region contribution is O(n log(n)/λ) generations, based on the drift established for low mutation rates.Source: §8 · p. 30

9 Experiments

Experiments on OneMax with n = 5000 compare the self-adjusting algorithm against static-rate and structural variants across offspring population sizes and update factors. The self-adjusting method gains an advantage at larger λ, while smaller update factors and two subpopulations generally perform better in the tested settings.

Static versus self-adjusting rates

  • For λ > 400, the self-adjusting (1+λ) EA outperforms both static mutation-rate settings, whereas static settings win for λ ≤ 400.Both algorithms improve as λ increases; the experiment used 10000 runs with λ from 100 to 1000.Source: §9 · p. 31
  • The fitness-dependent mutation-rate scheme outperforms all other considered variants in the experiments.Source: §9 · p. 31

Subpopulation variants

  • Three subpopulations slightly outperform two for small population sizes, but two subpopulations are better for very high population sizes.The comparison included versions with and without random rate-adjustment steps.Source: §9 · p. 31, Figure 2 · p. 33

Mutation-rate update factors

  • Lower update factors F yield better performance in the tested range, while experiments with F > 2 perform worse than F = 2.0.The tested factors were F = 2.0, 1.5, and 1.01; larger factors cause more abrupt rate changes, whereas smaller factors adjust more slowly.Source: Figure 3 · p. 34, §9 · p. 35
  • The mutation rate is more unsteady for higher F and more stable for smaller updates, although the specific runtimes in an illustrative run do not follow a monotonic ordering.For F = 1.01, 1.05, and 1.1, the reported runtimes were 19766, 19085, and 19857, respectively.Source: §9 · p. 35
  • Because F has only a modest runtime influence, the authors suggest treating the algorithm as effectively parameter-less rather than optimizing F.Source: §9 · p. 35

10 Conclusions

The paper introduces a simple self-adjusting mutation scheme for the (1+λ) EA and shows that it reaches an asymptotically optimal OneMax runtime. The analysis also identifies broader scope boundaries and open questions for the mechanism.

Contribution

  • The scheme creates offspring with larger and smaller mutation rates, then adjusts the rate according to the successful subpopulation.This avoids the careful exploration-exploitation and forgetting-rate choices required by the earlier learning scheme.Source: §10 · pp. 35, 37

Main result

  • O(nλ/log λ + n log n) expected fitness evaluations match the runtime of a carefully fitness-dependent mutation rate and are asymptotically optimal among λ-parallel black-box algorithms.The result indicates that the self-adjusting mechanism can find sufficiently good mutation rates on the fly.Source: §10 · pp. 35, 37

Analysis

  • The quality of the best offspring is less concentrated than average offspring quality, making precise analysis of the winning subpopulation the main technical challenge.The proof must determine which subpopulation contains the best offspring and how ties are distributed.Source: §10 · p. 37

Additional result

  • A fixed mutation rate r = ln(λ)/2 also achieves O(n/log λ + n log(n)/λ^1/2), asymptotically optimal unless λ is small.This rate is substantially larger than the usual constant mutation-rate choice.Source: §10 · p. 37

Open questions

  • The study leaves open whether the mechanism works without random rate adjustments and how its benefits generalize beyond the (1+λ) EA and OneMax.The conclusion also suggests testing other adjustment factors and three-subpopulation variants in applications.Source: §10 · pp. 35, 37
Loading 1704.02191v3…