Paper Info
Title
Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization - (Extended Abstract).
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.
Year
Venue
Field
2011
ALGORITHMS AND COMPUTATION
Combinatorics,Evolutionary algorithm,Computer science,Combinatorial optimization,Sorting,Heuristics,Eulerian path,Parallel running,Maximization,Speedup
DocType
Volume
ISSN
Conference
7074
0302-9743
Citations 
PageRank 
References 
0
0.34
12
Authors
2
Name
Order
Citations
PageRank
Jörg Lässig117522.53
Dirk Sudholt2106364.62