Performance Evaluation of Parallel Genetic Algorithm Using Single Program Multiple Data Technique

In this paper, we mainly investigate performance of genetic algorithms for the travelling salesman problem based on Grefenstette coding, and modified single program, multiple data (SPMD) parallel computing. In addition, solutions for potential problems encountered in the process of applying MATLAB for parallel computing are also suggested. In addition to common genetic algorithms, the proposed parallel genetic algorithm divides the initial chromosome population and evolutionary generations for parallel computing in multiple working regions of a multi-core CPU. In this way, the computation speed of codes is greatly enhanced, premature convergence into local optima is significantly alleviated, and the chromosomes can be repetitively amended by optimal paths of each parallel computing. The experimental results show that with the same population size and iterations, the proposed parallel genetic algorithm offers faster and more optimal solutions than traditional genetic algorithms.