Analysis of speedups in parallel evolutionary algorithms for combinatorial optimization (extended abstract)

DOI10.1007/978-3-642-25591-5_42zbMATH Open1350.68248arXiv1109.1766OpenAlexW2104529187MaRDI QIDQ3104635FDOQ3104635

Authors: Jörg Lässig, Dirk Sudholt 

Publication date: 16 December 2011

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected by a graph structure as communication topology. Each island periodically communicates copies of good solutions to neighboring islands in a process called migration. We consider the speedup gained by island models in terms of the parallel running time for problems from combinatorial optimization: sorting (as maximization of sortedness), shortest paths, and Eulerian cycles. Different search operators are considered. The results show in which settings and up to what degree evolutionary algorithms can be parallelized efficiently. Along the way, we also investigate how island models deal with plateaus. In particular, we show that natural settings lead to exponential vs. logarithmic speedups, depending on the frequency of migration.

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

Recommendations

• Analysis of speedups in parallel evolutionary algorithms and \((1 + \lambda)\) EAs for combinatorial optimization
• Design and analysis of migration in parallel evolutionary algorithms
• Island models meet rumor spreading
• Parallel genetic algorithms. Theory and real world applications
• Dynamic neighborhood structures in parallel evolution strategies

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Cited In (10)

• Island models meet rumor spreading
• Analysis of speedups in parallel evolutionary algorithms and \((1 + \lambda)\) EAs for combinatorial optimization
• The cost of randomness in evolutionary algorithms: crossover can save random bits
• The use of tail inequalities on the probable computational time of randomized search heuristics
• On the impact of the migration topology on the island model
• Lower bounds from fitness levels made easy
• A runtime analysis of parallel evolutionary algorithms in dynamic optimization
• Parallel Evolutionary Algorithms Performing Pairwise Comparisons
• The speciating Island model: an alternative parallel evolutionary algorithm
• Dynamic neighborhood structures in parallel evolution strategies

This page was built for publication: Analysis of speedups in parallel evolutionary algorithms for combinatorial optimization (extended abstract)

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