Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
Hsien‐Kuei Hwang, Carsten Witt · 2019
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