Black-box complexity of parallel search with distributed populations

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


Colleges, School and Institutes


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 languageEnglish
Title of host publicationFOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII
Publication statusPublished - 17 Jan 2015
Event13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 - Aberystwyth, United Kingdom
Duration: 17 Jan 201520 Jan 2015


Conference13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015
CountryUnited Kingdom


  • Black-box complexity, Cellular evolutionary algorithms, Island models, Query complexity, Runtime analysis, Structured populations, Theory

ASJC Scopus subject areas