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|
|Number of pages||14|
|State||Published - 2022|
|Event||17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - Dortmund, Germany|
Duration: Sep 10 2022 → Sep 14 2022
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||17th International Conference on Parallel Problem Solving from Nature, PPSN 2022|
|Period||9/10/22 → 9/14/22|
Bibliographical notePublisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
- Parallel evolutionary algorithms
- Runtime analysis