Abstract
Many metaheuristics such as island models and cellular evolutionary algorithms use a network of distributed populations that communicate search points along a spatial communication topology. The idea is to slow down the spread of information, reducing the risk of "premature convergence", and sacrificing exploitation for an increased exploration. We introduce the distributed black-box complexity as the minimum number of function evaluations every distributed black-box algorithm needs to optimise a given problem. It depends on the topology, the number of populations λ, and the problem size n. We give upper and lower bounds on the distributed black-box complexity for unary unbiased blackbox algorithms on a class of unimodal functions in order to study the impact of communication topologies on performance. Our results confirm that rings and torus graphs can lead to higher black-box complexities, compared to unrestricted communication. We further determine cut-off points for the number of populations λ, above which no distributed black-box algorithm can achieve linear speedups.
Original language | English |
---|---|
Title of host publication | FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII |
Publisher | Association for Computing Machinery |
Pages | 3-15 |
Number of pages | 13 |
ISBN (Electronic) | 9781450334341 |
DOIs | |
Publication status | Published - 17 Jan 2015 |
Event | 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 - Aberystwyth, United Kingdom Duration: 17 Jan 2015 → 20 Jan 2015 |
Conference
Conference | 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 |
---|---|
Country/Territory | United Kingdom |
City | Aberystwyth |
Period | 17/01/15 → 20/01/15 |
Keywords
- Black-box complexity
- Cellular evolutionary algorithms
- Island models
- Query complexity
- Runtime analysis
- Structured populations
- Theory
ASJC Scopus subject areas
- Computational Theory and Mathematics