Adaptive population models for offspring populations and parallel evolutionary algorithms

DOI10.1145/1967654.1967671MaRDI QIDQ5276098zbMATH OpenOpenAlexFDO

Authors Jörg Lässig, Dirk Sudholt

Publication date 14 July 2017

Published in Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.0588

zbMATH Keywords

dynamic population sizeisland modeloffspring populationsparallel evolutionary algorithmsruntime analysisspatial structures

Mathematics Subject Classification ID

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

Abstract: We present two adaptive schemes for dynamically choosing the number of parallel instances in parallel evolutionary algorithms. This includes the choice of the offspring population size in a (1+$lambda$) EA as a special case. Our schemes are parameterless and they work in a black-box setting where no knowledge on the problem is available. Both schemes double the number of instances in case a generation ends without finding an improvement. In a successful generation, the first scheme resets the system to one instance, while the second scheme halves the number of instances. Both schemes provide near-optimal speed-ups in terms of the parallel time. We give upper bounds for the asymptotic sequential time (i.e., the total number of function evaluations) that are not larger than upper bounds for a corresponding non-parallel algorithm derived by the fitness-level method.

Recommendations

• Analysis of speedups in parallel evolutionary algorithms and (1 + ) EAs for combinatorial optimization
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Parallel Evolutionary Algorithms Performing Pairwise Comparisons
• Dynamic neighborhood structures in parallel evolution strategies
• Runtime analysis for self-adaptive mutation rates

Cited in

(19)

• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Static and self-adjusting mutation strengths for multi-valued decision variables
• Self-adjusting evolutionary algorithms for multimodal optimization
• Self-adjusting mutation rates with provably optimal success rules
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Runtime analysis for self-adaptive mutation rates
• Analysis of speedups in parallel evolutionary algorithms and (1 + ) EAs for combinatorial optimization
• Population Formulation of Adaptative Meso-evolution: Theory and Numerics
• From black-box complexity to designing new genetic algorithms
• Parallel metaheuristics: recent advances and new trends
• Self-adjusting offspring population sizes outperform fixed parameters on the cliff function
• Self-adjusting population sizes for the (1, )-EA on monotone functions
• 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
• Hardest monotone functions for evolutionary algorithms
• Comma selection outperforms plus selection on OneMax with randomly planted optima
• Selection hyper-heuristics can automatically adjust the learning period to optimally solve pseudo-Boolean problems
• Design and analysis of migration in parallel evolutionary algorithms

This page was built for publication: Adaptive population models for offspring populations and parallel evolutionary algorithms

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