Black-box Complexity of Parallel Search with Distributed Populations

Tools

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

Text
FOGA.pdf
Permissions: Administrator Access Only
Download (469kB)

Official URL: https://dl.acm.org/doi/10.1145/2725494.2725504

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):

https://doi.org/10.1145/2725494.2725504