Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem
Instituto Politecnico Nacional, CITEDI, Ave. del Parque 1310, Mesa de Otay, Tijuana, B.C., 22510, Mexico
DIFU100 ci@, Vol. 8, No. 2, 2014
@article{sanchez2015parallel,
title={Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem},
author={S{‘a}nchez, Leopoldo Noel Gaxiola},
journal={Revista en Ingenier{‘i}a y Tecnolog{‘i}a, UAZ},
volume={8},
number={2},
year={2015}
}
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.
April 27, 2015 by hgpu
