Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

2.1 INTRODUCTION

In this chapter we will have a closer look at the role of parallelism in genetic (or, more general, evolutionary) algorithms (short GA or EA, respectively), an aspect that can significantly influence their time performance and the quality of solutions found.

Evolutionary algorithms are inherently parallel. This is a straightforward observation based on the fact that most genetic operators work independently on different individuals of a population. In particular, evaluation and mutation can be performed concurrently on all individuals. This is also true for the crossover operation that acts on just two individuals. On the other hand, selection is more difficult to parallelize, since in standard evolutionary algorithms parents are selected with respect to their performance relative to all other individuals in the population, i.e., global information is required. This may cause a large overhead of communication and thus severely limit the obtainable speedup.

Therefore, there have been several approaches to modify the structure of evolutionary algorithms in order to allow for better parallelization. In particular, in the island (or deme) model (cf. [27, 29]), the population is split into several subpopulations (islands) such that the selection is local to these islands combined with periodic migration between islands, and in the neighborhood (or diffusion) model, the individuals are laid out spatially and selection of partners for reproduction is restricted to local ...