Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms

Brahim Aboutaib, Andrew M. Sutton

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

Abstract

We revisit the analysis of the (1 + λ ) EA in a parallel setting when the offspring population size is significantly larger than the number of processors available. If the workload is not balanced across the processors, existing runtime results do not transfer directly. We therefore consider two new scenarios that produce unbalanced processors: (1) when the computation time of the fitness function is variable and depends on the structure of the individual, and (2) when processing is interrupted as soon as a viable offspring is found on one of the machines. We derive parallel execution times for both these models as a function of both the population size and the number of parallel machines. We discuss the potential trade-off between communication overhead and execution time, and we conduct some experiments.

Original languageEnglish (US)
Title of host publicationParallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings
EditorsGünter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
PublisherSpringer Science and Business Media Deutschland GmbH
Pages555-568
Number of pages14
ISBN (Print)9783031147203
DOIs
StatePublished - 2022
Externally publishedYes
Event17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - Dortmund, Germany
Duration: Sep 10 2022Sep 14 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13399 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Country/TerritoryGermany
CityDortmund
Period9/10/229/14/22

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

  • Parallel evolutionary algorithms
  • Runtime analysis

Fingerprint

Dive into the research topics of 'Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this