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

8.4 PARALLEL GENETIC ALGORITHMS

The genetic algorithm paradigm offers intrinsic parallelism in the search for an acceptable solution in a large-search space. To find a solution, genetic algorithms start from different points in the search space. This makes GAs very easy to parallelize, in contrast to simulated annealing, which is intrinsically sequential and thus hard to parallelize. Hard problems like the task-allocation problems need large population sizes. GAs with large populations suffer from lack of efficiency due to the high execution time. Parallel genetic algorithms (PGAs) reduce the overall execution time to reach acceptable solutions and enhance research efficiency.

Several approaches of parallelizinig a GA have been proposed in the literature. They can be classified, into three main classes: centralized, coarse-grain, and fine-grain. These are shown in Fig. 8.3.

8.4.1 The Centralized Approach

The centralized approach, also called global GAs, treats the entire population as a single breeding unit. The global GAs use a master/slave model. While most of the GA operations (selection and reproduction) are executed sequentially on the master node, the evaluations are done in parallel on the slave nodes and the results are sent to the master. Near linear speedup may be obtained using global GAs when the fitness function evluation is significantly more computationally expensive than the GA itself [8].

8.4.2 Coarse-Grain Decomposition

The coarse-grain methods can be decomposed ...