Source-linked AI summary
Multiplicative Drift Analysis
Benjamin Doerr, Daniel Johannsen, Carola Winzen
TL;DR
The paper addresses runtime analysis for randomized search heuristics, focusing on the (1+1) EA on linear functions. It introduces multiplicative drift analysis and obtains upper and lower runtime bounds, extending the lower bound to functions with a unique global optimum.
Problem
The runtime of the (1+1) EA on arbitrary linear functions is a central problem in evolutionary-algorithm theory, with a known O(n ln n) bound requiring a simplified proof.
Method
The paper introduces a multiplicative drift theorem and applies weighted Hamming distance to the optimum as a potential for linear functions.
Results
All linear functions are optimized in expected time at most (1 + o(1))1.39en ln(n), while functions with a unique global optimum require at least (1 − o(1))en ln(n).
Takeaways & Limitations
The bounds imply that all linear functions have roughly the same optimization time, within a 39% range, and the theorem also applies to minimum spanning trees, shortest paths, and Euler tours.
Takeaways & Limitations
Finding a potential function that yields point-wise drift for every search point and objective function may be difficult.
Abstract
from arXiv · showhide
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))e n\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.
1 Introduction
The paper introduces multiplicative drift analysis to simplify runtime analyses when progress scales with the current potential, and applies it to the (1+1) EA and combinatorial optimization problems.
- 1 Introduction: The (1+1) EA runtime for arbitrary linear functions was an influential problem, but its general proof was highly technical.Earlier analyses of particular functions were easier, while drift analysis enabled a significantly simpler proof.
- 1 Introduction: Multiplicative drift analysis requires progress that depends multiplicatively on the current potential value.It separates structural optimization analysis from calculating expected runtime bounds and can produce sharper bounds.
- 1 Introduction: A simple potential-function argument gives an expected optimization time of O(n log n) for the (1+1) EA on every linear function.The potential reaching zero implies that the desired optimum has been found.
- 1 Introduction: (1 + o(1))1.39en ln(n) is the improved upper bound for the expected optimization time on arbitrary linear functions.The improvement uses parts of Jägerskupper’s distribution-based drift analysis.
- 1 Introduction: (1 −o(1))en ln(n) is a lower bound applying to all functions with a unique global optimum, including linear functions with non-zero coefficients.The result follows by showing that OneMax has the smallest expected optimization time in that class.
- 1 Introduction: The method also gives straightforward analyses for minimum spanning trees, single-source shortest paths, and Euler tours, improving leading asymptotic constants.These analyses reproduce previously obtained runtime results for the three combinatorial problems.
2 Multiplicative Drift Analysis
Multiplicative drift analysis extends classical drift analysis by measuring progress relative to the current potential, making natural distance-based potentials useful for randomized search heuristics. The theorem supports runtime analyses for linear functions and several combinatorial optimization problems.
- Potential functions: A potential function maps search points to non-negative values, with zero indicating an optimum; tracking it converts optimization time into the hitting time of zero.The potential may be defined over search points or populations, and the associated random variable is its value during each iteration.
- Ideal potential functions: The ideal additive-drift potential is E[T | x(0) = x], but using it requires already knowing the exact expected optimization time from every starting point.This makes the ideal potential unsuitable as a direct runtime-analysis tool despite satisfying the additive drift condition exactly.
- Multiplicative drift theorem: Multiplicative drift requires expected decrease proportional to the current positive potential and yields a logarithmic dependence on the initial-to-minimum potential ratio.The theorem is presented as a multiplicative counterpart of the classical additive drift result and is derived from it.
- Natural potentials: The multiplicative approach permits natural potentials such as objective-value distance to the optimum, which directly bounds runtimes for minimum spanning trees, shortest paths, and Euler tours.For linear functions, the weighted Hamming distance can yield tighter bounds independent of the range of potential fitness values, although it is more difficult to analyze.
- Applications: The theorem applies where expected weight decrease was previously used and improves the leading constant in the main runtime bound for linear functions.The paper also applies the tool to four problems: linear pseudo-Boolean optimization, minimum spanning trees, single-source shortest paths, and Euler tours.
3 The Runtime of the (1+1) Evolutionary Algorithm on Pseudo-Boolean Functions
The section introduces the (1+1) EA and analyzes its runtime on pseudo-Boolean functions, focusing on linear functions and multiplicative drift. It gives simpler and sharper bounds, including an almost tight upper bound and a matching lower-bound scale.
- Linear functions: Θ(n log n) is the expected runtime of the (1+1) EA on all linear functions with non-zero weights.This general result includes elementary cases such as OneMax and BinVal, despite their different acceptance behavior.
- Multiplicative drift: O(n log n) follows from a simple multiplicative-drift proof for optimizing any linear function.The proof uses a potential whose drift is at least linear in its current value, satisfying the multiplicative drift condition.
- Potential-function caveat: Using OneMax as a potential can yield only 1/n^2 point-wise drift for BinVal at a suitable search point.This illustrates why constructing a potential satisfying a strong point-wise drift condition for every function and search point can be difficult.
- Sharper bounds: (1 + o(1))1.39e n ln(n) is the upper bound obtained for minimizing any linear function on n bits.Applying multiplicative drift analysis improves the earlier constant 2.02e by replacing a halving argument.
- Lower bounds: (1 − o(1))e n ln(n) is a lower bound for the expected runtime on every function with a unique global optimum.The result follows by comparing such functions with OneMax and applies in particular to linear functions with non-zero coefficients.
4 Multiplicative Drift on Combinatorial Problems
The section applies multiplicative drift analysis to combinatorial optimization processes. It derives runtime bounds for minimum spanning trees, single-source shortest paths, and Euler tours.
- Overview: Multiplicative drift occurs naturally in combinatorial optimization, allowing runtime analyses to use potentials measuring distance from an optimum.The examples cover minimum spanning trees and single-source shortest paths, with an additional Euler-tour analysis.
- Minimum spanning trees: 2em^2(1 + ln m + ln wmax) bounds the MST optimization time from an arbitrary spanning tree.The analysis uses the weight gap w(x) − wopt and accepted 2-bit flips whose average decrease is proportional to the current gap.
- Single-source shortest paths: 6n^3(1 + 2 ln n + ln wmax) bounds the SSSP optimization time from an arbitrary shortest-path tree candidate.The gap between the current and optimal tree is used as the potential, with maximal gap n^2wmax.
- Euler tours: em ln m bounds the Euler-tour optimization time for the edge-based distribution, starting from an arbitrary cycle cover.The potential is the number of cycles minus one, and the probability of decreasing fitness by one is at least f(x)/em.
5 Discussion and Outlook
The paper applies multiplicative drift analysis to linear functions and several combinatorial optimization problems, obtaining simplified runtime analyses and improved constants. Its bounds for arbitrary linear functions are close, while the exact common runtime remains open.
- Applications: Multiplicative drift occurs naturally in runtime analyses of linear functions, minimum spanning trees, shortest paths, and Euler tours.The resulting drift theorem yields good runtime bounds for these problems.
- Linear functions: (1−o(1))en ln(n) is proved as a lower bound that extends from OneMax to all functions with a unique global optimum.The extension follows from showing that OneMax is the function easiest optimized by the (1+1) EA.
- Open question: The close upper and lower bounds leave open whether all linear functions have expected optimization time (1 + o(1))en ln(n).
- Applications: For minimum spanning trees, shortest path trees, and Euler tours, the paper identifies multiplicative drift and determines leading constants in expected optimization-time bounds.
Note Added in Proof
A subsequent result shows that the stopping-time bounds can also hold with high probability under an initial-potential condition, at the cost of a slightly larger leading constant.
- With high probability, the stopping time T is at most of the same order as its expectation bound when X(0) is at least Ω(n).The corresponding bounds in Theorem 9, Theorem 15, and Theorem 17 also hold with high probability using a slightly larger leading constant.