Multiplicative Up-Drift
Authors:
- Benjamin DoerrBDBenjamin Doerr
- Timo KötzingTKTimo Kötzing
Preprint
Abstract
Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a multiplicative growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a simple and insightful proof of the level-based theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the best-possible linear dependence on the growth parameter $\delta$ (the previous-best was quadratic). This gives immediately stronger run time guarantees for a number of applications.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Probabilistic Tools for the Analysis of Randomized Optimization Heuristics2019
- An elementary analysis of the probability that a binomial random variable exceeds its expectationStatistics & Probability Letters, 2018
- Level-Based Analysis of Genetic Algorithms and Other Search ProcessesIEEE Transactions on Evolutionary Computation, 2017
- Exponential inequalities for martingales with applicationsElectronic Journal of Probability, 2015
- The choice of the offspring population size in the () evolutionary algorithmTheoretical Computer Science, 2014
- Tight lower bound on the probability of a binomial exceeding its expectationStatistics & Probability Letters, 2014
- Multiplicative Drift AnalysisAlgorithmica, 2012
- A study of drift analysis for estimating computation time of evolutionary algorithmsNatural Computing, 2004
- Drift analysis and average time complexity of evolutionary algorithmsArtificial Intelligence, 2001
- On Tail Probabilities for MartingalesThe Annals of Probability, 1975