Multiplicative Up-Drift
Benjamin Doerr, Timo Kötzing
Abstract
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 $$(1+\delta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>δ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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 near-linear dependence on $$1/\delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>δ</mml:mi> </mml:mrow> </mml:math> (the previous results had an at least near-quadratic dependence), and it only requires a population size near-linear in $$\delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> (this was super-quadratic in previous results). These improvements immediately lead to stronger run time guarantees for a number of applications. We also discuss the case of large $$\delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> and show stronger results for this setting.