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

DOI10.1007/978-3-642-25591-5_42MaRDI QIDQ3104635zbMATH OpenOpenAlexFDO

Authors Jörg Lässig, Dirk Sudholt

Publication date 16 December 2011

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

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

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)

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.

Recommendations

• Analysis of speedups in parallel evolutionary algorithms and (1 + ) 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

Cited in

(11)

• Analysis of speedups in parallel evolutionary algorithms and (1 + ) EAs for combinatorial optimization
• Island models meet rumor spreading
• 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
• Design and analysis of migration in parallel evolutionary algorithms
• 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)