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

2.2 STANDARD APPROACHES TO PARALLELIZING EVOLUTIONARY ALGORITHMS

In this section we present the three fundamentally different ways of parallelizing evolutionary algorithms (EA) that are the farming model, the island model, and the neighborhood model. But we have to start with the classic (serial) model of evolutionary algorithms:

The classic evolutionary algorithm (cf. [21]) for solving a problem P operates on a set of n individuals, also called population. Every individual is the “genetic representation” of a potential solution to P, the genotype or chromosome. The classic chromosome is a fixed-length string of genes. Every gene has a value from its set of alleles. If the alleles are binary values, we have the special case of genetic algorithms, as introduced and studied extensively by Holland [13] and Goldberg [11], Obviously, for some problems it may be advisable to use more complex data structures than strings (graph drawing is an example of such a problem [4]).

The quality of the individual is determined with respect to the problem's objective function. Based on their relative quality, individuals are selected as parents to produce offspring for the next generation. Therefore, the relative quality is also called fitness, because, genetically, the fitness of an individual is a measure of its reproductive strength (which can only be determined relative to a population).

The classic selection method corresponds to the use of a roulette wheel where the size of a sector depends ...