Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation

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

    138 Downloads (Pure)

    Abstract

    The analysis of randomized search heuristics on classes of functions is fundamental for the understanding of the underlying stochastic process and the development of suitable proof techniques. Recently, remarkable progress has been made in bounding the expected optimization time of the simple (1+1) EA on the class of linear functions. We improve the best known bound in this setting from (1.39+o(1))(en ln n) to (en ln n)+O(n) in expectation and with high probability, which is tight up to lower-order terms. Moreover, upper and lower bounds for arbitrary mutations probabilities p are derived, which imply expected polynomial optimization time as long as p=O((ln n)/n) and which are tight if p=c/n for a constant c. As a consequence, the standard mutation probability p=1/n is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm. Furthermore, the algorithm turns out to be surprisingly robust since large neighborhood explored by the mutation operator does not disrupt the search.
    Original languageEnglish
    Title of host publication29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
    EditorsChristoph Dürr, Thomas Wilke
    Number of pages12
    PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
    Publication date2012
    Pages420-431
    ISBN (Print)978-3-939897-35-4
    DOIs
    Publication statusPublished - 2012
    Event29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) - Paris, France
    Duration: 29 Feb 20123 Mar 2012
    http://stacs2012.lip6.fr/

    Conference

    Conference29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
    CountryFrance
    CityParis
    Period29/02/201203/03/2012
    Internet address
    SeriesLeibniz International Proceedings in Informatics
    Volume14
    ISSN1868-8969

    Bibliographical note

    Licensed under Creative Commons License NC-ND.

    Keywords

    • Randomized Search Heuristics
    • Evolutionary Algorithms
    • Linear Functions
    • Running Time Analysis

    Fingerprint

    Dive into the research topics of 'Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation'. Together they form a unique fingerprint.

    Cite this