Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem

Abstract

The implementation of parallel genetic algorithms on a graphic processor GPU to solve the Travelling Salesman Problem instances is presented. Two versions of parallel genetic algorithms are implemented, a Parallel Genetic Algorithm with Islands Model and a Parallel Genetic Algorithm with Elite Island; the two versions were executed on a GPU. In both cases, each individual is represented by a thread, and each island is represented by a block of threads. The main feature of the Parallel Genetic Algorithm with Elite Island in this work is that there is not migration between islands, instead, an Elite Island is created with the best individuals from each of the islands to share the best individuals. The individual with minimal fitness function is the sought solution. The results show that the Elite Island model is better than the island model with migration of individuals.