Parallel Genetic Algorithms for Hypercube Machines

In this paper we investigate the design of highly parallel Genetic Algorithms. The Traveling Salesman Problem is used as a case study to evaluate and compare different implementations. To fix the various parameters of Genetic Algorithms to the case study considered, the Holland sequential Genetic Algorithm, which adopts different population replacement methods and crossover operators, has been implemented and tested. Both fine-grained and coarse-grained parallel GAs which adopt the selected genetic operators have been designed and implemented on a 128-node nCUBE 2 multicomputer. The fine-grained algorithm uses an innovative mapping strategy that makes the number of solutions managed independent of the number of processing nodes used. Complete performance results showing the behaviour of Parallel Genetic Algorithms for different population sizes, number of processors used, migration strategies are reported.