Paper Info
Title
Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools.
Abstract
The expected running time of the classical (1+1) EA on the ONEMAX benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of O((log n)/n). The same approach proposed there also leads to a full asymptotic expansion with errors of the form O(n-K log n) for any K > 0. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on ONE MAX and obtains that the expected running time E (T), starting from [n/2] one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely [EQUATION] where Δ(k) is the drift (expected increase of the number of one-bits from the state of n - k ones) and c1, c2 > 0 are explicitly computed constants. This improves the previous asymptotic error known for the sum of inverse drifts from Õ(n2/3) to a logarithmic error and gives for the first time a non-asymptotic error bound. Using standard asymptotic techniques, the difference between E (T) and the sum of inverse drifts is found to be (e/2) log n + O(1).
Year
DOI
Venue
2019
10.1145/3299904.3340302
FOGA
Keywords
DocType
Volume
randomized search heuristics,(1+1) EA,drift analysis,asymptotic methods
Conference
abs/1906.09047
ISBN
Citations 
PageRank 
978-1-4503-6254-2
1
0.35
References 
Authors
0
2
Name
Order
Citations
PageRank
Hsien-Kuei Hwang110.35
Carsten Witt298759.83