Black-box complexity of parallel search with distributed populations

Golnaz Badkobeh, Per Kristian Lehre, Dirk Sudholt

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

13 Citations (Scopus)


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
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781450334341
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
Country/TerritoryUnited Kingdom


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

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'Black-box complexity of parallel search with distributed populations'. Together they form a unique fingerprint.

Cite this