.png){kind=icon}
.png){kind=icon}
Return
Parallel Black-Box Complexity With Tail Bounds
.png){kind=icon}
OA
AI
DOI：10.1109/TEVC.2019.2954234.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose a new black-box complexity model for search algorithms evaluating lambda search points in parallel. The parallel unary unbiased black-box complexity gives lower bounds on the number of function evaluations every parallel unary unbiased black-box algorithm needs to optimize a given problem. It captures the inertia caused by offspring populations in evolutionary algorithms and the total computational effort in parallel metaheuristics.(1) We present complexity results for LeadingOnes and OneMax. Our main result is a general performance limit: we prove that on every function every lambda-parallel unary unbiased algorithm needs at least a certain number of evaluations (a function of problem size and lambda) to find any desired target set of up to exponential size, with an overwhelming probability. This yields lower bounds for the typical optimization time on unimodal and multimodal problems, for the time to find any local optimum, and for the time to even get close to any optimum. The power and versatility of this approach is shown for a wide range of illustrative problems from combinatorial optimization. Our performance limits can guide parameter choice and algorithm design; we demonstrate the latter by presenting an optimal lambda-parallel algorithm for OneMax that uses parallelism most effectively.
Keywords:
Complexity theory
Optimization
Sociology
Statistics
Search problems
Evolutionary computation
Parallel processing
Black-box complexity
parallelization
parameter control
runtime analysis
theory
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W