A Heterogeneous Framework for the Global Parallelisation of Genetic Algorithms

Mohammad Hamdan

Department of Computer Science, Yarmouk University, Jordan

Abstract: There is a big need for the parallelisation of genetic algorithms.  In this paper, a heterogeneous framework for the global parallelisation of genetic algorithms is presented. The framework uses a static all-worker parallel programming paradigm based on collective communication. It follows the single program multiple data parallel programming model. It utilises the power of parallel machines by allowing multiple crossover and mutation operators being used within a single genetic algorithm.  This mixture of operators  can  be  applied  to  the  strings  of  a  population  in  parallel  without  changes  to the  canonical  sequential  genetic  algorithm. These features help the parallel genetic algorithm in exploiting the search space efficiently and thoroughly when compared to the sequential genetic algorithm. The framework is instantiated with specific parameters to solve an NP-hard problem, the asymmetric travelling salesman problem.  The results  for the  parallel  genetic  algorithm  are very  good  in  terms  of  solution  quality. Also very good speedup and scalability results were achieved on the parallel machine.

Keywords: Genetic algorithms, parallel processing, parallel genetic algorithms, crossover, mutation, TSP.

Received November 14, 2006; accepted February 28, 2007