  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.
