PaperlayerView exact revision on arXiv

Source-linked AI summary

A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms

Dirk Sudholt

arXiv:1109.1504v2cs.NE

TL;DR

The paper addresses the difficulty of proving precise, broadly applicable lower bounds for evolutionary-algorithm running times. It introduces a fitness-level method for mutation-based EAs and obtains tight results across several problems, enabling identification of optimal algorithms and mutation rates for LO and OneMax.

  • Problem

    Precise lower bounds are difficult to prove, while existing analyses often support limited algorithmic comparisons and parameter conclusions.

  • Method

    The paper adapts fitness-level partitions with an additional transition-probability condition to prove lower bounds for mutation-based evolutionary algorithms.

  • Results

    The bounds are tight up to smaller-order terms for LO, OneMax, and long k-paths, and identify p ≈1.59/n for LO and p = 1/n for OneMax as optimal fixed mutation rates.

  • Takeaways & Limitations

    The method identifies optimal mutation-based EAs for LO and OneMax, both variants of the (1+1) EA initialized with more than one uniformly random search point.

  • Takeaways & Limitations

    The reported LO and OneMax lower-bound results do not apply to all search heuristics, and the discussed theorems concern fixed mutation rates.

Abstract

from arXiv · show

We present a new method for proving lower bounds on the expected running time of evolutionary algorithms. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general: they hold for all evolutionary algorithms that only use bit-flip mutation as variation operator---i.e. for all selection operators and population models. The lower bounds are stated with their dependence on the mutation rate. These results have very strong implications. They allow to determine the optimal mutation-based algorithm for LO and OneMax, i.e., which algorithm minimizes the expected number of fitness evaluations. This includes the choice of the optimal mutation rate.

1 Introduction

Running-time analysis helps compare evolutionary algorithms, tune their design, and understand scalability, but existing lower bounds are difficult and often narrow. This paper introduces a mutation-based fitness-level method that yields precise, broadly applicable lower bounds and identifies optimal algorithms and mutation rates for several benchmark problems.

  • Running-time analysis can assess scalability, compare algorithms, guide parameter choices, and illuminate evolutionary algorithms’ working principles.
  • Existing analyses are often challenging, restricted to specific algorithmic settings, and based on contrived functions.
  • Upper bounds alone cannot rigorously establish that one algorithm is more efficient than another; a lower bound exceeding its competitor’s upper bound is required.
  • The paper introduces mutation-based EAs as algorithms using only common bit-flip mutation after uniformly random initialization, regardless of selection operators or population models.
  • The new fitness-level lower bounds apply broadly, remain tight up to lower-order terms, and expose how expected running time depends on mutation rate.
  • For LO, OneMax, and long k-paths, the results identify optimal mutation-based algorithms or rates, including p ≈1.59/n for LO and p = 1/n for OneMax.
  • The method yields precise lower bounds without drift analysis and supports exact LO formulas, general unique-optimum results, and matching long k-path bounds.

2 Preliminaries

The paper defines mutation-based evolutionary algorithms and their optimization-time framework, then reviews mutation-rate constraints and the classical fitness-level method for upper bounds. The setup accommodates broad population and selection mechanisms while motivating lower-bound analysis.

  • Mutation-based evolutionary algorithms: Mutation-based EAs initialize individuals uniformly and subsequently use only standard bit-flip mutation, covering arbitrary selection operators and population models.The class includes (μ+λ) and (μ,λ) algorithms, island models, and other algorithms without crossover.
  • Optimization time: Optimization time is the first time index at which a global optimum is found, counted by function evaluations.The framework can also measure the hitting time of a desirable set of search points.
  • Mutation-rate constraints: For mutation probability p ≤ 1/2, unique-optimum problems impose lower bounds of (1 − μ · 2^-n) · 1/(pn) and (1 − μ · 2^-n) · e^pn on expected optimization time.These bounds imply superpolynomial or exponential running times for sufficiently small or large mutation rates.
  • Fitness-level upper bounds: The classical fitness-level method partitions the search space into strictly ordered sets and bounds the time for elitist algorithms to move between levels.For a level Ai, si lower-bounds the probability of creating an offspring in any higher level.
  • Examples: For the (1+1) EA with p = 1/n, fitness-level arguments give an OneMax upper bound of en ln n + O(n), while the LeadingOnes construction uses first-bit improvements.The canonical partition groups points by fitness.

3 Lower Bounds with Fitness Levels

The paper extends fitness-level reasoning to lower bounds by limiting transition probabilities between levels. A viscosity parameter captures how strongly improvements must progress through successive levels, yielding bounds that can approach classical upper bounds.

  • Baseline limitation: The basic lower bound can be weak because it considers only the time to leave the initial level and pessimistically assumes immediate discovery of the optimum.For LeadingOnes, this crude bound contrasts with the actual Θ(n^2) expected running time.
  • Lower-bound principle: The new lower-bound method adds transition-probability information to fitness-level arguments, making the resulting bounds proportional to fitness-level upper bounds.The key intuition is that algorithms usually skipping few levels must traverse many levels.
  • Theorem 3: Theorem 3 bounds transitions from level i to level j by ui · γi,j, with the γ-values summing to 1 and satisfying a viscosity condition governed by χ.The expected hitting time of the final level is then bounded from below.
  • Tightness: When si = ui, the lower bound matches the upper bound up to a factor of χ; under stronger conditions, the bounds are asymptotically equal or equal up to lower-order terms.These cases include constant positive viscosity and χ = 1 − o(1).
  • Applying the method: The theorem requires only upper bounds on transition probabilities, allowing flexible choices of ui, γi,j, and χ when exact probabilities are unavailable.Larger ui or smaller χ makes the conditions easier to satisfy but weakens the resulting lower bound.

4 Refined Upper Bounds with Fitness Levels

The paper also refines fitness-level upper bounds using transition probabilities and viscosity. The refinement generalizes the classical method and can reduce bounds when improvements typically skip levels in a controlled way.

  • Conditions: The additional condition (1 − χ)sj ≤ sj+1 prevents success probabilities from becoming too imbalanced across consecutive levels.This condition supports the recurrence used to derive the refined upper bound.
  • Refined upper-bound theorem: The refined upper-bound theorem assumes lower transition-probability bounds si · γi,j and a viscosity condition on γi,j, together with balanced success probabilities.The theorem bounds the expected hitting time of the final fitness level for elitist mutation-based EAs.
  • Relation to the classical method: At maximum viscosity χ = 1, the refined method reduces to the classical fitness-level method, while lower viscosities can improve the upper bound by a constant factor.Unlike the lower-bound setting, χ = 0 is not possible for this upper-bound refinement.
  • Interpretation: In the refined upper-bound interpretation, χ bounds the expected number of fitness levels gained during an improvement from level i.Thus viscosity controls how much progress a successful transition may make across the partition.

5 An Exact Formula for LeadingOnes

The fitness-level lower-bound method yields exact or matching bounds for LeadingOnes, establishing the optimal mutation-based algorithm and mutation rate. For all mutation-based EAs, the (1+1) EA_μ is optimal with a fixed rate p ≈ 1.59/n and suitable population size.

  • Lower-bound derivation: The method bounds transition probabilities on LeadingOnes by p(1 − p)^i times the probability of completing the remaining leading bits.The argument uses uniformly random bits beyond the current LeadingOnes level and assumes p ≤ 1/2.
  • Exactness and optimality: The lower bound equals the refined upper bound for the (1+1) EA_μ, giving its exact expected optimization time on LeadingOnes.The equality follows because the algorithm’s transition probabilities satisfy the theorem’s conditions with equality.
  • Exactness and optimality: Among mutation-based EAs, the (1+1) EA_μ minimizes expected function evaluations on LeadingOnes for an appropriate μ.This optimality follows from matching an all-algorithm lower bound with the algorithm-specific upper bound.
  • Optimal parameter choice: p = 1.59/n is the optimal fixed mutation rate, with 1 < μ = O(n log n) for the optimal (1+1) EA_μ.The result concerns fixed mutation rates; adaptive mutation-rate schemes can reduce expected optimization time further.

6 A Lower Bound for OneMax

For OneMax, the fitness-level method provides lower bounds for all mutation-based EAs that nearly match the (1+1) EA’s upper bound for mutation rates up to polylog(n)/n. The analysis identifies p = 1/n as the optimal mutation rate for the (1+1) EA, while its scope excludes several nonstandard search heuristics.

  • Lower bound: Theorem 9 gives a lower bound on OneMax optimization time for every mutation-based EA using mutation probability p.The result is stated for n ≥ 2 bits and is derived from upper bounds on mutation transition probabilities.
  • Lower bound: For mutation rates up to polylog(n)/n, the lower bound matches the simple (1+1) EA upper bound up to lower-order terms.For p = α/n with polylogarithmic α, the logarithmic factor becomes ln n − o(ln n).
  • Optimal mutation rate: The (1+1) EA’s expected running time is dominated by ln n for the mutation probabilities covered by the lower-bound analysis.This conclusion follows from the matching lower and upper bounds in the relevant mutation-rate range.
  • Optimal mutation rate: p = 1/n minimizes the expected running time of the (1+1) EA on OneMax.The factor p(1 − p)^(n−1) is maximized at p = 1/n, yielding the minimum under the analyzed expression.
  • Scope: The lower bound applies broadly to bit-flip mutation EAs but not to local, biased, quasirandom, or fitness-invariant-shuffling heuristics.Those search heuristics can perform better because they fall outside the mutation-based class considered.

7 A Lower Bound for all Functions with Unique Optimum

The paper transfers precise lower bounds from OneMax to every function with a unique global optimum, using the fact that finding a single target is never easier than optimizing OneMax. These results also identify optimal population size and mutation-rate choices for OneMax.

  • Motivation: OneMax is treated as the easiest function with a unique optimum because it provides the best possible hints toward the target.A lower bound for finding its target therefore extends to a broader class of functions.
  • Scope: The transfer applies to functions with a unique global optimum, including linear, monotone, unimodal, multimodal, needle, and trap functions.The class is substantially broader than standard unimodal benchmark functions.
  • Lower bound: For mutation probability 1/n, every mutation-based EA on every n-bit function with a unique optimum requires at least en ln n−en ln ln n−3en expected evaluations.The bound is more precise than the earlier asymptotic Ω(n log n) result.
  • General comparison: For arbitrary p ≤1/2, the optimization time is stochastically at least that of the (1+1) EAµ on OneMax.This stronger comparison implies the corresponding lower bound for every function with a unique global optimum.
  • Optimal algorithm: Among mutation-based EAs, the (1+1) EAµ minimizes OneMax evaluations for p = 1/n and 1 < µ = O(√n).For every fixed population size, it is never worse than another algorithm initialized with µ uniform random individuals; optimizing µ matters only through small additive terms in practice.

8 An Exponential Lower Bound for Long k-Paths

The extended lower-bound method handles long k-paths by controlling transitions to only the next d fitness levels. For the (1+1) EA, it yields exponential lower bounds that match upper bounds up to lower-order terms and identify p = 1/n as optimal in the analyzed setting.

  • Method: The extended method considers only the next d fitness levels and introduces α to lower-bound the probability that transitions remain within those levels.When d is much smaller than the number of levels, only a small fraction of transition probabilities must be analyzed.
  • Long k-paths: Long k-paths require at least k simultaneous bit flips for shortcuts beyond the first k successors, creating potentially exponentially many fitness values.Their path length is k · 2^(n/k) − k.
  • Lower bound: Theorem 15 lower-bounds the expected optimization time of the (1+1) EA starting at the first path point for mutation probability p.The bound accounts for making the required one-bit advances and for successful mutations that flip more than one bit.
  • Tightness: For k = √n and 0 < p ≤1/3, the resulting upper and lower bounds are tight up to lower-order terms.The derivation uses the extended transition-probability theorem.
  • Mutation rate: For sufficiently large n, p = 1/n minimizes the (1+1) EA’s expected number of function evaluations on these long k-paths.The comparison assumes initialization at the first point of the path.

9 Conclusions

The paper introduces a flexible fitness-level lower-bound method with transition-probability conditions and applies it broadly to mutation-based evolutionary algorithms. It obtains precise bounds for several benchmark classes and uses them to identify optimal algorithms and mutation rates.

  • Method: The method adapts fitness-level analysis with additional transition-probability conditions and permits freely chosen parameters χ, u_i, and γ_i,j subject to those conditions.The same development also refines the corresponding fitness-level method for upper bounds.
  • Scope: Mutation-based EAs include algorithms using only bit-flip mutation, regardless of parent selection or population model.The resulting bounds cover a broad class of evolutionary algorithms rather than one specific algorithm.
  • Results: The lower bounds for LO, OneMax, and long k-paths are tight against (1+1) EA upper bounds up to smaller-order terms for reasonable mutation probabilities.They are simultaneously general across mutation-based EAs and precise in their asymptotic behavior.
  • Implications: The optimal mutation-based algorithms for LO and OneMax are variants of the (1+1) EA that initialize more than one uniformly random search point.The optimal fixed rates are approximately 1.59/n for LO and 1/n for OneMax; p = 1/n is also optimal for the (1+1) EA on long k-paths.
  • Outlook: The method is not restricted to mutation-based EAs or binary search spaces and is intended for other stochastic search algorithms and representations.It can be used directly or as part of a broader analysis.
Loading 1109.1504v2…