title: General upper bounds on the runtime of parallel evolutionary algorithms.
abstract: We present a general method for analyzing the runtime of parallel evolutionary algorithms with spatially structured populations. Based on the fitness-level method, it yields upper bounds on the expected parallel runtime. This allows for a rigorous estimate of the speedup gained by parallelization. Tailored results are given for common migration topologies: ring graphs, torus graphs, hypercubes, and the complete graph. Example applications for pseudo-Boolean optimization show that our method is easy to apply and that it gives powerful results. In our examples the performance guarantees improve with the density of the topology. Surprisingly, even sparse topologies such as ring graphs lead to a significant speedup for many functions while not increasing the total number of function evaluations by more than a constant factor. We also identify which number of processors lead to the best guaranteed speedups, thus giving hints on how to parameterize parallel evolutionary algorithms.
authors.affiliation: Department of Computer Science, University of Applied Sciences Zittau/Görlitz, Germany jlaessig@hszg.de.
authors.forename: Jörg
authors.initials: J
authors.lastname: Lässig
authors.forename: Dirk
authors.initials: D
authors.lastname: Sudholt
mesh_terms: D000465:Algorithms; D003205:Computing Methodologies; D008962:Models, Theoretical; D013997:Time Factors
keywords: Parallel evolutionary algorithms; island model; runtime analysis; spatial structures