Search Space Extension and PGAs: A Comparative Study of Parallelization Schemes to Genetic Algorithms using the TSP

K. Davoian (Germany)


Parallel genetic algorithms, traveling salesman problem, genetic algorithms


Parallel genetic algorithms (PGAs) have been developed to reduce the execution time of serial genetic algorithms (SGA) and to solve larger problems. They typically find better solutions, as they are likely to be more resistant to premature convergence to local minima compared to serial genetic algorithms. This paper presents a comparative study of four different PGAs using the traveling salesman problem (TSP) as the case application in order to quantify their performance on the basis of small initial populations. Besides the well-known parallelization approaches, a new parallelization scheme is considered which combines iterative data exchanges and new solutions generation, thus extending a search space during the evolution. To make the comparison fair, all PGAs are using the same baseline serial genetic algorithm, started from the same set of initial populations and tested on the same known instances from the TSPLIB-archive.

Important Links:

Go Back