Sharp Bounds by Probability-Generating Functions and Variable Drift

We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al. (GECCO 2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the OneMax function is improved from 1.28nln n to 0.982nlnn, which breaks the barrier of nln n posed by coupon-collector processes. Compared to the classical (1+1) EA, whose runtime will for the first time be analyzed with respect to terms of lower order, this represents a speedup by more than a factor of e = 2.71.