The influence of noise on multi-parent crossover for an island model GA

Brahim Aboutaib, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many optimization problems tackled by evolutionary algorithms are not only computationally expensive, but also complicated with one or more sources of noise. One technique to deal with high computational overhead is parallelization. However, though the existing literature gives good insights about the expected behavior of parallelized evolutionary algorithms, we still lack an understanding of their performance in the presence of noise. This paper considers how parallelization might be leveraged together with multi-parent crossover in order to handle noisy problems. We present a rigorous running time analysis of an island model with weakly connected topology tasked with hill climbing in the presence of general additive noise. Our proofs yield insights into the relationship between the noise intensity and number of required parents. We translate this into positive and negative results for two kinds of multi-parent crossover operators. We then empirically analyze and extend this framework to investigate the trade-offs between noise impact, optimization time, and limits of computation power to deal with noise.

Original languageEnglish (US)
Title of host publicationGECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages666-674
Number of pages9
ISBN (Electronic)9781450392372
DOIs
StatePublished - Jul 8 2022
Event2022 Genetic and Evolutionary Computation Conference, GECCO 2022 - Virtual, Online, United States
Duration: Jul 9 2022Jul 13 2022

Publication series

NameGECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

Conference

Conference2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Country/TerritoryUnited States
CityVirtual, Online
Period7/9/227/13/22

Bibliographical note

Funding Information:
B. Aboutaib was supported by a IEEE CIS Graduate Student Research Grant while visiting A. M. Sutton. Some experiments were run on the CALCULCO computation facility of Univ. du Littoral Côte d’Opale.

Publisher Copyright:
© 2022 ACM.

Keywords

  • Island model
  • noisy optimization
  • runtime analysis

Fingerprint

Dive into the research topics of 'The influence of noise on multi-parent crossover for an island model GA'. Together they form a unique fingerprint.

Cite this