A Parallel Discrete Firefly Algorithm on GPU for Permutation Combinatorial Optimization Problems

PABLO JAVIER VIDAL; ANA CAROLINA OLIVERA

Communications in Computer and Information Science

Springer

Año: 2014 vol. 485 p. 191 - 205

1865-0929

The parallelism provided by low cost environments as multi- core and GPU processors has encouraged the design of algorithms that can utilize it. In the last time, the GPU approach constitutes an envi- ronment of proven successful progress in the implementation of different bio-inspired algorithms without major additional costs of performance. Among these techniques, the Firefly Algorithm (FA) is a recent method based on the flashing light of fireflies. As a population-based algorithm with operations without a high level of divergence, it is well suited as a highly parallelizable model on GPU. In this work we describe the design of a Discrete Firefly Algorithm (GPU-DFA) to solve permutation combinatorial problems. Two well-known permutation optimization problems (Travelling Salesman Problem and DNA Fragment Assembling Problem) were employed in order to test GPU-DFA. We have evaluated numerical efficacy and performance with respect to a CPU-DFA version. Results demonstrate that our algorithm is a fast robust procedure for the treatment of heterogeneous permutation combinatorial problems.