Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms

Brahim Aboutaib; Andrew M. Sutton

doi:10.1007/978-3-031-14721-0_39

Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms

Brahim Aboutaib
, Andrew M. Sutton

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

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 language	English (US)
Title of host publication	Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings
Editors	Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	555-568
Number of pages	14
ISBN (Print)	9783031147203
DOIs	https://doi.org/10.1007/978-3-031-14721-0_39
State	Published - 2022
Event	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - Dortmund, Germany Duration: Sep 10 2022 → Sep 14 2022

Publication series

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

Conference

Conference	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Country/Territory	Germany
City	Dortmund
Period	9/10/22 → 9/14/22

Bibliographical note

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

Keywords

Parallel evolutionary algorithms
Runtime analysis

Publisher link

10.1007/978-3-031-14721-0_39

Find It

Find It at U of M Libraries

Cite this

Aboutaib, B., & Sutton, A. M. (2022). Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, & T. Tušar (Eds.), Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings (pp. 555-568). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-14721-0_39

Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms. / Aboutaib, Brahim; Sutton, Andrew M.
Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. ed. / Günter Rudolph; Anna V. Kononova; Hernán Aguirre; Pascal Kerschke; Gabriela Ochoa; Tea Tušar. Springer Science and Business Media Deutschland GmbH, 2022. p. 555-568 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aboutaib, B & Sutton, AM 2022, Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms. in G Rudolph, AV Kononova, H Aguirre, P Kerschke, G Ochoa & T Tušar (eds), Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13399 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 555-568, 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022, Dortmund, Germany, 9/10/22. https://doi.org/10.1007/978-3-031-14721-0_39

Aboutaib B, Sutton AM. Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms. In Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G, Tušar T, editors, Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 555-568. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-14721-0_39

Aboutaib, Brahim ; Sutton, Andrew M. / Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms. Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. editor / Günter Rudolph ; Anna V. Kononova ; Hernán Aguirre ; Pascal Kerschke ; Gabriela Ochoa ; Tea Tušar. Springer Science and Business Media Deutschland GmbH, 2022. pp. 555-568 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{85c7e39b61764bb39e727935f4676cba,

title = "Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms",

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.",

keywords = "Parallel evolutionary algorithms, Runtime analysis",

author = "Brahim Aboutaib and Sutton, \{Andrew M.\}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 ; Conference date: 10-09-2022 Through 14-09-2022",

year = "2022",

doi = "10.1007/978-3-031-14721-0\_39",

language = "English (US)",

isbn = "9783031147203",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "555--568",

editor = "G{\"u}nter Rudolph and Kononova, \{Anna V.\} and Hern{\'a}n Aguirre and Pascal Kerschke and Gabriela Ochoa and Tea Tu{\v s}ar",

booktitle = "Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms

AU - Aboutaib, Brahim

AU - Sutton, Andrew M.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Parallel evolutionary algorithms

KW - Runtime analysis

UR - https://www.scopus.com/pages/publications/85137260200

UR - https://www.scopus.com/pages/publications/85137260200#tab=citedBy

U2 - 10.1007/978-3-031-14721-0_39

DO - 10.1007/978-3-031-14721-0_39

M3 - Conference contribution

AN - SCOPUS:85137260200

SN - 9783031147203

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 555

EP - 568

BT - Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings

A2 - Rudolph, Günter

A2 - Kononova, Anna V.

A2 - Aguirre, Hernán

A2 - Kerschke, Pascal

A2 - Ochoa, Gabriela

A2 - Tušar, Tea

PB - Springer Science and Business Media Deutschland GmbH

T2 - 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022

Y2 - 10 September 2022 through 14 September 2022

ER -