A Modified Genetic Algorithm for the Traveling Salesman Problem and Its Parallelization

K. Davoian and S. Gorlatch (Germany)


Genetic algorithms, traveling salesman problem, parallel genetic algorithms, optimization


This paper presents a new modification of the Genetic Algorithm (GA) for solving the classical Traveling Salesman Problem (TSP), with the objective of achieving its efficient implementation on multiprocessor machines. We describe the new features of our GA as compared to existing algorithms, and develop a new parallelization scheme, applicable to arbitrary GAs. In addition to parallel processes and iterative data exchanges between the involved populations, our parallel implementation also contains a generation of new possible solutions (strangers), which eliminates typical drawbacks of GA and extends the search area. The proposed algorithm allows to accelerate the solution process and generates solutions of better quality as compared with previously developed GA versions.

Important Links:

Go Back