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

    Abstract

    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
    PublisherACM
    Publication date2011
    Pages2083-2090
    ISBN (Print)978-1-4503-0557-0
    DOIs
    Publication statusPublished - 2011
    Event2011 Genetic and Evolutionary Computation Conference - Dublin, Ireland
    Duration: 12 Jul 201116 Jul 2011
    http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2011.html

    Conference

    Conference2011 Genetic and Evolutionary Computation Conference
    CountryIreland
    CityDublin
    Period12/07/201116/07/2011
    Internet address

    Keywords

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

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

    Cite this