Black-box Complexity of Parallel Search with Distributed Populations

Badkobeh, Golnaz; Lehre, Per Kristian and Sudholt, Dirk. 2015. 'Black-box Complexity of Parallel Search with Distributed Populations'. In: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17 - 20, 2015. Aberystwyth, United Kingdom. [Conference or Workshop Item]

No full text available
[img] Text
Permissions: Administrator Access Only

Download (469kB)

Abstract or Description

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 black- box 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.

Item Type:

Conference or Workshop Item (Talk)

Identification Number (DOI):


Black-box complexity, query complexity, structured popula-tions, island models, cellular evolutionary algorithms, run-time analysis, theory

Departments, Centres and Research Units:




Event Location:

Aberystwyth, United Kingdom

Item ID:


Date Deposited:

30 Jul 2020 14:02

Last Modified:

30 Jul 2020 14:02


View statistics for this item...

Edit Record Edit Record (login required)