Information Technology Reference
In-Depth Information
A Parallel Discrete Firefly Algorithm
on GPU for Permutation Combinatorial
Optimization Problems
Pablo Vidal
and Ana Carolina Olivera
Universidad Nacional de la Patagonia Austral
Ruta N
ⓦ
3 Acceso Norte, Caleta Olivia (9011), Santa Cruz, Argentina
{pjvidal,aolivera}@uaco.unpa.edu.ar
Abstract.
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 combi-
natorial 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
ecacy and performance with respect to a CPU-DFA version. Results
demonstrate that our algorithm is a fast robust procedure for the treat-
ment of heterogeneous permutation combinatorial problems.
Keywords:
Graphic Processing Units, Optimization, Permutations, DNA
Fragment Assembly, Travelling Salesman Problem.
1 Introduction
In the last decades, metaheuristics have proved to be useful to solve combina-
torial optimization problems [20,21,29,38]. In particular, nature-inspired algo-
rithms have become very popular to solve this kind of problems [17,42]. These
techniques usually need a high amount of computational resources and time in
contrast with the need for answers in a “reasonable time” [39]. In this way,
parallelization emerges as an attractive alternative in order to decrease the ex-
ecution time and, in some cases it improves the accurate results of sequential
algorithms. In this sense, interest has been growing in the development of parallel
evolutionary algorithms by using Graphics Processing Units (GPUs) [39].
