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

Contenido principal del artículo

Leopoldo Noel Gaxiola Sánchez
Juan José Tapia Armenta
Víctor Hugo Díaz Ramírez

Resumen

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.

Detalles del artículo

Cómo citar
Gaxiola Sánchez, L. N., Tapia Armenta, J. J., & Díaz Ramírez, V. H. (2014). Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem. Difu100ci@, Revista De difusión científica, ingeniería Y tecnologías, 8(2), 84-90. Recuperado a partir de http://difu100cia.uaz.edu.mx/index.php/difuciencia/article/view/145
Sección
Artículos