Exploitable parallelism in genetic algorithms
Vahl Scott Gordon · 1994
Genetic are becoming increasingly popular for function optimization, and attempts to use them for solving progressively harder problems are fostering an interest in parallel implementations. To date, research in parallel genetic has been done in a machine-dependent, ad hoc manner using explicit parallelism. Typically, a researcher has access to particular parallel hardware and adapts a genetic algorithm to the machine. This approach is necessarily machine dependent, and while it sometimes improves performance, the results are not always useful to researchers who do not have access to similar hardware. The lack of portability also makes it difficult to compare independently-generated empirical results. This dissertation presents an alternative way of studying parallel genetic using a machine-independent dataflow model of computation in conjunction with the implicit parallel programming language Sisal. Sisal makes it possible to create a variety of parallel genetic and compare their performance on a uniform platform, a simulator of the Manchester Dataflow Machine. The parallelism profiles produced by the simulator are used to identify parallelism inherent in the genetic algorithms, determine sensitivities of parallelism in the genetic operators to changes in parameter settings, and locate and measure bottlenecks. Locality issues, important in any parallel computing application, are also addressed. To examine problem-solving power, several parallel genetic are compared across a wide range of optimization functions to determine whether changes made to increase parallelism have any affect on problem-solving power. While it is infeasible to test every possible combination of models, problems, and parameters, this research looks for trends. The findings are encouraging for parallel genetic algorithm research because they indicate that performance benefits due to parallelism are not offset by declines in problem-solving capabilities. In fact, the parallel structures perform as well as or better than standard versions, even without taking parallel hardware into account. New ways of parallelizing various genetic are introduced, and, in one case, an analytical method for determining ahead of time how much parallelism can be exploited is described. Hopefully, studying genetic from this machine-independent algorithms perspective will lead researchers to find even better ways of improving performance.