Abstract
Evolutionary algorithms (GlossaryTerm
EA
s) have given rise to many parallel variants, fuelled by the rapidly increasing number of GlossaryTermCPU
cores and the ready availability of computation power through GlossaryTermGPU
s and cloud computing. A very popular approach is to parallelize evolution in island models, or coarse-grained GlossaryTermEA
s, by evolving different populations on different processors. These populations run independently most of the time, but they periodically communicate genetic information to coordinate search. Many applications have shown that island models can speed up computation significantly, and that parallel populations can further increase solution diversity.The aim of this book chapter is to give a gentle introduction into the design and analysis of parallel evolutionary algorithms, in order to understand how parallel GlossaryTerm
EA
s work, and to explain when and how speedups over sequential GlossaryTermEA
s can be obtained.Understanding how parallel GlossaryTerm
EA
s work is a challenging goal as they represent interacting stochastic processes, whose dynamics are determined by several parameters and design choices. This chapter uses a theory-guided perspective to explain how key parameters affect performance, based on recent advances on the theory of parallel GlossaryTermEA
s. The presented results give insight into the fundamental working principles of parallel GlossaryTermEA
s, assess the impact of parameters and design choices on performance, and contribute to an informed design of effective parallel GlossaryTermEA
s.Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Abbreviations
- ACO:
-
ant colony optimization
- CPU:
-
central processing unit
- DNA:
-
deoxyribonucleic acid
- EA:
-
evolutionary algorithm
- GA:
-
genetic algorithm
- GPU:
-
graphics processing unit
- GRASP:
-
greedy randomized adaptive search procedure
- LO:
-
leading one
- LZ:
-
leading zero
- PRAS:
-
polynomial-time randomized approximation scheme
- RLS:
-
randomized local search
- SSSP:
-
single-source shortest path problem
References
P.S. Oliveto, J. He, X. Yao: Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results, Int. J. Autom. Comput. 4(3), 281–293 (2007)
F. Neumann, C. Witt: Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity (Springer, Berlin, Heidelberg 2010)
J. Lässig, D. Sudholt: The benefit of migration in parallel evolutionary algorithms, Proc. Genet. Evol. Comput. Conf. (GECCO 2010) (ACM, New York 2010) pp. 1105–1112
J. Lässig, D. Sudholt: General scheme for analyzing running times of parallel evolutionary algorithms, 11th Int. Conf. Parallel Probl. Solving Nat. (PPSN 2010) (Springer, Berlin, Heidelberg 2010) pp. 234–243
J. Lässig, D. Sudholt: Adaptive population models for offspring populations and parallel evolutionary algorithms, Proc. 11th Workshop Found. Genet. Algorithms (FOGA 2011) (ACM, Berlin, Heidelberg 2011) pp. 181–192
J. Lässig, D. Sudholt: Analysis of speedups in parallel evolutionary algorithms for combinatorial optimization, 22nd Int. Symp. Algorithms Comput. (ISAAC '11) (Springer, Berlin, Heidelberg 2011) pp. 405–414
F. Neumann, P.S. Oliveto, G. Rudolph, D. Sudholt: On the effectiveness of crossover for migration in parallel evolutionary algorithms, Proc. Genet. Evol. Comput. Conf. (GECCO 2011) (ACM, New York 2011) pp. 1587–1594
M. De Felice, S. Meloni, S. Panzieri: Effect of topology on diversity of spatially-structured evolutionary algorithms, Proc. 13th Annu. Genet. Evol. Comput. Conf. (GECCO '11) (2011) pp. 1579–1586
M. Giacobini, M. Tomassini, A. Tettamanzi: Takeover time curves in random and small-world structured populations, Proc. Genet. Evol. Comput. Conf. (GECCO '05) (ACM, New York 2005) pp. 1333–1340
Z. Skolicki: An Analysis of Island Models in Evolutionary Computation, Ph.D. Thesis (George Mason University, Fairfax 2000)
E. Alba, M. Giacobini, M. Tomassini, S. Romero: Comparing Synchronous and Asynchronous Cellular Genetic Algorithms, Parallel Problem Solving from Nature VII (Springer, Berlin, Heidelberg 2002) pp. 601–610
M. Mitzenmacher, E. Upfal: Probability and Computing (Cambridge Univ. Press, Cambridge 2005)
J. Sprave: A unified model of non-panmictic population structures in evolutionary algorithms, Proc. 1999 Congr. Evol. Comput. (IEEE, Bellingham 1999) pp. 1384–1391
E. Alba: Parallel evolutionary algorithms can achieve super-linear performance, Inf. Process. Lett. 82(1), 7–13 (2002)
R.S. Barr, B.L. Hickman: Reporting computational experiments with parallel algorithms: Issues, measures, and experts' opinion, ORSA J. Comput. 5(1), 2–18 (1993)
D.E. Goldberg, K. Deb: A comparatative analysis of selection schemes used in genetic algorithms. In: Foundations of Genetic Algorithms, ed. by G.J.E. Rawlins (Morgan Kaufmann, Burlington 1991) pp. 69–93
J. Sarma, K. De Jong: An analysis of local selection algorithms in a spatially structured evolutionary algorithm, Proc. 7th Int. Conf. Genet. Algorithms (Morgan Kaufmann, Burlington 1997) pp. 181–186
E. Alba, G. Luque: Growth curves and takeover time in distributed evolutionary algorithms, Proc. Genet. Evol. Comput. Conf. (Springer, Berlin, Heidelberg 2004) pp. 864–876
G. Luque, E. Alba: Parallel Genetic Algorithms – Theory and Real World Applications, Studies in Computational Intelligence, Vol. 367 (Springer, Berlin, Heidelberg 2011)
Z. Skolicki, K.A. De Jong: The influence of migration sizes and intervals on island models, Proc. Genet. Evol. Comput. Conf. (GECCO '05) (ACM, New York 2005) pp. 1295–1302
M. Giacobini, E. Alba, M. Tomassini: Selection intensity in asynchronous cellular evolutionary algorithms, Proc. Genet. Evol. Comput. Conf. (GECCO '03) (Springer, Berlin, Heidelberg 2003) pp. 955–966
G. Rudolph: Takeover times and probabilities of non-generational selection rules, Proc. Genet. Evol. Comput. Conf. (GECCO '00) (Morgan Kaufmann, Burlington 2000) pp. 903–910
G. Rudolph: Takeover times of noisy non-generational selection rules that undo extinction, Proc. 5th Int. Conf. Artif. Neural Nets Genet. Algorithms (ICANNGA 2001) (Springer, Berlin, Heidelberg 2001) pp. 268–271
G. Rudolph: On takeover times in spatially structured populations: Array and ring, Proc. 2nd Asia-Pac. Conf. Genet. Algorithms Appl. (Global-Link Publishing, Hong Kong 2000) pp. 144–151
G. Rudolph: Takeover time in parallel populations with migration, Proc. 2nd Int. Conf. Bioinspired Optim. Methods Appl. (BIOMA 2006), ed. by B. Filipic, J. Silc (2006) pp. 63–72
M. Giacobini, M. Tomassini, A. Tettamanzi: Modelling selection intensity for linear cellular evolutionary algorithms, Proc. 6th Int. Conf. Artif. Evol., Evol. Artif. (Springer, Berlin, Heidelberg 2003) pp. 345–356
M. Giacobini, E. Alba, A. Tettamanzi, M. Tomassini: Selection intensity in cellular evolutionary algorithms for regular lattices, IEEE Trans. Evol. Comput. 9, 489–505 (2005)
C. Witt: Runtime analysis of the $(\mu+1)$EA on simple pseudo-Boolean functions, Evol. Comput. 14(1), 65–86 (2006)
D. Sudholt: The impact of parametrization in memetic evolutionary algorithms, Theor. Comput. Sci. 410(26), 2511–2528 (2009)
M. Giacobini, E. Alba, A. Tettamanzi, M. Tomassini: Modeling selection intensity for toroidal cellular evolutionary algorithms, Proc. Genet. Evol. Comput. Conf. (GECCO '04) (Springer, Berlin, Heidelberg 2004) pp. 1138–1149
J. Rowe, B. Mitavskiy, C. Cannings: Propagation time in stochastic communication networks, 2nd IEEE Int. Conf. Digit. Ecosyst. Technol. (2008) pp. 426–431
J. Scharnow, K. Tinnefeld, I. Wegener: The analysis of evolutionary algorithms on sorting and shortest paths problems, J. Math. Model, Algorithms 3(4), 349–366 (2004)
B. Doerr, E. Happ, C. Klein: Crossover can provably be useful in evolutionary computation, Theor. Comput. Sci. 425, 17–33 (2012)
B. Doerr, E. Happ, C. Klein: A tight analysis of the $(1+1)$-EA for the single source shortest path problem, Proc. IEEE Congr. Evol. Comput. (CEC '07) (IEEE, Bellingham 2007) pp. 1890–1895
C. Horoba, D. Sudholt: Ant colony optimization for stochastic shortest path problems, Proc. Genet. Evol. Comput. Conf. (GECCO 2010) (ACM, New York 2010) pp. 1465–1472
D. Sudholt, C. Thyssen: Running time analysis of ant colony optimization for shortest path problems, J. Discret. Algorithms 10, 165–180 (2012)
E. Alba, J.M. Troya: A survey of parallel distributed genetic algorithms, Complexity 4, 31–52 (1999)
E. Alba, M. Tomassini: Parallelism and evolutionary algorithms, IEEE Trans. Evol. Comput. 6, 443–462 (2002)
E. Alba, N. Nedjah, L. de Macedo Mourelle: Parallel Evolutionary Computations (Springer, Berlin, Heidelberg 2006)
E. Alba: Parallel Metaheuristics: A New Class of Algorithms (Wiley-Interscience, New York 2005)
T.G. Crainic, N. Hail: Parallel metaheuristics applications. In: Parallel Metaheuristics: A New Class of Algorithms, (Wiley-Interscience, New York 2005)
S. Droste, T. Jansen, I. Wegener: On the analysis of the $(1+1)$ evolutionary algorithm, Theor. Comput. Sci. 276, 51–81 (2002)
T. Friedrich, P.S. Oliveto, D. Sudholt, C. Witt: Analysis of diversity-preserving mechanisms for global exploration, Evol. Comput. 17(4), 455–476 (2009)
C. Witt: Worst-case and average-case approximations by simple randomized search heuristics, Proc. 22nd Symp. Theor. Asp. Comput. Sci. (STACS '05) (Springer, Berlin, Heidelberg 2005) pp. 44–56
T. Jansen, K.A. De Jong, I. Wegener: On the choice of the offspring population size in evolutionary algorithms, Evol. Comput. 13, 413–440 (2005)
C. Igel, M. Toussaint: A no-free-lunch theorem for non-uniform distributions of target functions, J. Math. Model, Algorithms 3(4), 313–322 (2004)
J. Lässig, D. Sudholt: Experimental supplements to the theoretical analysis of migration in the island model, 11th Int. Conf. Parallel Probl. Solving Nat. (PPSN 2010) (Springer, Berlin, Heidelberg 2010) pp. 224–233
F. Neumann: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem, Comput. Oper. Res. 35(9), 2750–2759 (2008)
B. Doerr, N. Hebbinghaus, F. Neumann: Speeding up evolutionary algorithms through asymmetric mutation operators, Evol. Comput. 15, 401–410 (2007)
B. Doerr, D. Johannsen: Adjacency list matchings – An ideal genotype for cycle covers, Proc. Genet. Evol. Comput. Conf. (GECCO '07) (ACM, New York 2007) pp. 1203–1210
B. Doerr, C. Klein, T. Storch: Faster evolutionary algorithms by superior graph representation, 1st IEEE Symp. Found. Comput. Intell. (FOCI '07) (2007) pp. 245–250
R.A. Watson, T. Jansen: A building-block royal road where crossover is provably essential, Proc. Genet. Evol. Comput. Conf. (GECCO '07) (ACM, New York 2007) pp. 1452–1459
T. Jansen, I. Wegener: On the analysis of evolutionary algorithms – A proof that crossover really can help, Algorithmica 34(1), 47–66 (2002)
T. Jansen, I. Wegener: Real royal road functions – Where crossover provably is essential, Discret. Appl. Math. 149, 111–125 (2005)
T. Storch, I. Wegener: Real royal road functions for constant population size, Theor. Comput. Sci. 320, 123–134 (2004)
S. Fischer, I. Wegener: The one-dimensional ising model: Mutation versus recombination, Theor. Comput. Sci. 344(2/3), 208–225 (2005)
D. Sudholt: Crossover is provably essential for the ising model on trees, Proc. Genet. Evol. Comput. Conf. (GECCO '05) (ACM, New York 2005) pp. 1161–1167
P.S. Oliveto, J. He, X. Yao: Analysis of the $(1+1)$-EA for finding approximate solutions to vertex cover problems, IEEE Trans. Evol. Comput. 13(5), 1006–1029 (2009)
T. Jansen, P.S. Oliveto, C. Zarges: On the analysis of the immune-inspired B-cell algorithm for the vertex cover problem, Proc. 10th Int. Conf. Artif. Immune Syst. (ICARIS 2011) (Springer, Berlin, Heidelberg 2011) pp. 117–131
I. Wegener: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Evolutionary Optimization, ed. by R. Sarker, X. Yao, M. Mohammadian (Kluwer, Dordrecht 2002) pp. 349–369
F. Neumann, I. Wegener: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theor. Comput. Sci. 378(1), 32–40 (2007)
D. Sudholt, C. Zarges: Analysis of an iterated local search algorithm for vertex coloring, 21st Int. Symp. Algorithms Comput. (ISAAC 2010) (Springer, Berlin, Heidelberg 2010) pp. 340–352
D. Sudholt: General lower bounds for the running time of evolutionary algorithms, 11th Int. Conf. Parallel Probl. Solving Nat. (PPSN 2010) (Springer, Berlin, Heidelberg 2010) pp. 124–133
P.K. Lehre: Fitness-levels for non-elitist populations, Proc. 13th Annu. Genet. Evol. Comput. Conf. (GECCO '11) (ACM, New York 2011) pp. 2075–2082
B. Doerr, D. Johannsen, C. Winzen: Drift analysis and linear functions revisited, IEEE Congr. Evol. Comput. (CEC '10) (2010) pp. 1967–1974
E. Cantú Paz: A survey of parallel genetic algorithms, Tech. Rep., Illinois Genetic Algorithms Laboratory (University of Illinois at Urbana Champaign, Urbana 1997)
M. Tomassini: Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Springer, Berlin, Heidelberg 2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Sudholt, D. (2015). Parallel Evolutionary Algorithms. In: Kacprzyk, J., Pedrycz, W. (eds) Springer Handbook of Computational Intelligence. Springer Handbooks. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43505-2_46
Download citation
DOI: https://doi.org/10.1007/978-3-662-43505-2_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43504-5
Online ISBN: 978-3-662-43505-2
eBook Packages: EngineeringEngineering (R0)