Black-box complexity of parallel search with distributed populations

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

Standard

Black-box complexity of parallel search with distributed populations. / Badkobeh, Golnaz; Lehre, Per Kristian; Sudholt, Dirk.

FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery , 2015. p. 3-15.

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

Harvard

Badkobeh, G, Lehre, PK & Sudholt, D 2015, Black-box complexity of parallel search with distributed populations. in FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery , pp. 3-15, 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015, Aberystwyth, United Kingdom, 17/01/15. https://doi.org/10.1145/2725494.2725504

APA

Badkobeh, G., Lehre, P. K., & Sudholt, D. (2015). Black-box complexity of parallel search with distributed populations. In FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (pp. 3-15). Association for Computing Machinery . https://doi.org/10.1145/2725494.2725504

Vancouver

Badkobeh G, Lehre PK, Sudholt D. Black-box complexity of parallel search with distributed populations. In FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery . 2015. p. 3-15 https://doi.org/10.1145/2725494.2725504

Author

Badkobeh, Golnaz ; Lehre, Per Kristian ; Sudholt, Dirk. / Black-box complexity of parallel search with distributed populations. FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery , 2015. pp. 3-15

Bibtex

@inproceedings{ffff514045cc4c49ab7c1a5a623ef08e,
title = "Black-box complexity of parallel search with distributed populations",
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.",
keywords = "Black-box complexity, Cellular evolutionary algorithms, Island models, Query complexity, Runtime analysis, Structured populations, Theory",
author = "Golnaz Badkobeh and Lehre, {Per Kristian} and Dirk Sudholt",
year = "2015",
month = jan,
day = "17",
doi = "10.1145/2725494.2725504",
language = "English",
pages = "3--15",
booktitle = "FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII",
publisher = "Association for Computing Machinery ",
note = "13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 ; Conference date: 17-01-2015 Through 20-01-2015",

}

RIS

TY - GEN

T1 - Black-box complexity of parallel search with distributed populations

AU - Badkobeh, Golnaz

AU - Lehre, Per Kristian

AU - Sudholt, Dirk

PY - 2015/1/17

Y1 - 2015/1/17

N2 - 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.

AB - 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.

KW - Black-box complexity

KW - Cellular evolutionary algorithms

KW - Island models

KW - Query complexity

KW - Runtime analysis

KW - Structured populations

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=84950259716&partnerID=8YFLogxK

U2 - 10.1145/2725494.2725504

DO - 10.1145/2725494.2725504

M3 - Conference contribution

AN - SCOPUS:84950259716

SP - 3

EP - 15

BT - FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

PB - Association for Computing Machinery

T2 - 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015

Y2 - 17 January 2015 through 20 January 2015

ER -