Sharp Bounds by Probability-Generating Functions and Variable Drift

Benjamin Doerr, Mahmoud Fouz, Carsten Witt

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    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.
    Original languageEnglish
    Title of host publicationGenetic and Evolutionary Computation Conference, GECCO'11
    Publication date2011
    ISBN (Print)978-1-4503-0557-0
    Publication statusPublished - 2011
    Event2011 Genetic and Evolutionary Computation Conference - Dublin, Ireland
    Duration: 12 Jul 201116 Jul 2011


    Conference2011 Genetic and Evolutionary Computation Conference
    Internet address


    • Variable Drift
    • Probability-Generating Functions
    • Evolutionary Algorithms
    • Quasirandomness


    Dive into the research topics of 'Sharp Bounds by Probability-Generating Functions and Variable Drift'. Together they form a unique fingerprint.

    Cite this