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

8.6 DISCUSSION

Three instances of PGA-based techniques for solving the task-mapping problem were described. All of them use the decomposition approach to exploit parallelism by dividing the population of chromosomes. Two versions of the decomposition approach were presented: the coarse-grained version and the fine-grained version.

The fine-grained PGA suits massively parallel architectures that include numerous processors. The population is mapped into the network, one individual per processor. All of the GA steps—evaluation, selection, reproduction, and replacement—are done in parallel. The selection is done locally in the neighborhood of each individual. The restriction of neighborhood to only directly connected individuals is to avoid overhead and complexity of routing algorithms. As expected, it was observed that solution quality improves with an increase in the population size. For a population that is too small, a premature convergence can occur, and the optimal solution would never be reached. To avoid the loss of diversity in the population, an adaptive mutation rate can be used.

Two instances of coarse-grained PGAs were presented. One is implemented as cooperating sequential GAs, and the other uses a master–slave model. Both of them use a migration strategy to exchange chromosomes between the various subpopulations. For the former, at set intervals, a small number of fitter chromosomes in one population replace the least fit in another population. For the latter, the master ...