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)


    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
    Number of pages7
    Publication statusPublished - 2015
    EventFoundations of Genetic Algorithms (FOGA) - University of Wales Aberystwyth UK
    Duration: 17 Jan 201520 Jan 2015


    ConferenceFoundations of Genetic Algorithms (FOGA)
    CityUniversity of Wales Aberystwyth UK
    Internet address


    • Analysis Of Algorithms
    • Global optimization
    • Problem Complexity


    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