Black-box Complexity of Parallel Search with Distributed Populations

DOI10.1145/2725494.2725504MaRDI QIDQ2981878zbMATH OpenOpenAlexFDO

Authors Golnaz Badkobeh, Per Kristian Lehre, Dirk Sudholt

Publication date 10 May 2017

Published in Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2725494.2725504

zbMATH Keywords

black-box complexitycellular evolutionary algorithmsisland modelsquery complexityruntime analysisstructured populations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Distributed algorithms (68W15)

Recommendations

• The complexity of parallel search
• Black-box complexity for bounding the performance of randomized search heuristics
• The deterministic complexity of parallel multisearch
• The complexity of parallel multisearch on coarse-grained machines
• The Sample Complexity of Search Over Multiple Populations
• Efficiency of randomized parallel backtrack search
• The Computational Complexity of the Parallel Knock-Out Problem
• The computational complexity of the parallel knock-out problem
• Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms

Cites work

• Absorption time of the Moran process
• Approximating fixation probabilities in the generalized Moran process
• scientific article; zbMATH DE number 3148873 (Why is no real title available?)
• On the fixation probability of superstars

Cited in

(16)

• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Island models meet rumor spreading
• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Optimal mutation rates for the (1+) EA on OneMax through asymptotically tight drift analysis
• Static and self-adjusting mutation strengths for multi-valued decision variables
• The interplay of population size and mutation probability in the (1+ ) EA on OneMax
• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
• Runtime analysis for self-adaptive mutation rates
• On the impact of the performance metric on efficient algorithm configuration
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)
• Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation
• Many-objective problems where crossover is provably essential
• Achieving tight \(O(4^k)\) runtime bounds on \(\textsc{Jump}_k\) by proving that genetic algorithms evolve near-maximal population diversity

This page was built for publication: Black-box Complexity of Parallel Search with Distributed Populations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2981878)