Run-Time Analysis of Population-Based Evolutionary Algorithm in Noisy Environments

Adam Prügel-Bennett, Jonathan Rowe, Jonathan Shapiro, Jun He (Editor), Thomas Jansen (Editor), Gabriela Ochoa (Editor), Christine Zarges (Editor)

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    444 Downloads (Pure)

    Abstract

    This paper analyses a generational evolutionary algorithm using only selection and uniform crossover. With a probability arbitrarily close to one the evolutionary algorithm is shown to solve onemax in O(n log2(n)) function evaluations using a population of size c,n, log(n). We then show that this algorithm can solve onemax with noise variance n again in O(n log2(n)) function evaluations.
    Original languageEnglish
    Title of host publicationProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17 - 20, 2015
    EditorsJun He, Thomas Jansen, Gabriela Ochoa, Christine Zarges
    Place of PublicationACM Digital Library
    PublisherAssociation for Computing Machinery
    Pages69-75
    Number of pages7
    DOIs
    Publication statusPublished - 2015
    EventFoundations of Genetic Algorithms (FOGA) - University of Wales Aberystwyth UK
    Duration: 17 Jan 201520 Jan 2015
    http://doi.acm.org/10.1145/2725494.2725498

    Conference

    ConferenceFoundations of Genetic Algorithms (FOGA)
    CityUniversity of Wales Aberystwyth UK
    Period17/01/1520/01/15
    Internet address

    Keywords

    • Analysis Of Algorithms
    • Global optimization
    • Problem Complexity

    Fingerprint

    Dive into the research topics of 'Run-Time Analysis of Population-Based Evolutionary Algorithm in Noisy Environments'. Together they form a unique fingerprint.

    Cite this