Information Technology Reference
In-Depth Information
The GPUs represent a low cost environment for massively parallel compu-
tations with APIs and development kits for parallel applications. NVIDIA has
created a parallel computing platform and programming model called CUDA
(Compute Unified Device Architecture) [30] that allows the development of GPU
routines called kernels. Each kernel defines instructions that are executed on the
GPU device by many threads at the same time following the Simple Instruction
Multiple Data (SIMD) model. NVIDIA has advertised its potential for bringing
facilities for the programming in these devices and invested great efforts to create
a programmable and transparent GPU architecture for programmers [30].
Several studies have presented ideas on how to port existing algorithms run-
ning on CPUs to the new GPU architecture: genetic algorithms [16], cellu-
lar genetic algorithms [40], particle swarm optimization [12] and some oth-
ers [4,6,22,41]. In particular, there are contemporary contributions about GPUs
that deal with permutation combinatorial problems [23,24,27,39].
The Firefly-Inspired Algorithms (FA), which were developed by Yang [42,43],
are recent bio-inspired algorithms that have achieved outstanding results in var-
ious domains [8,11,25,45]. FAs have become an increasingly important tool of
Swarm Intelligence that has been applied in almost all areas of optimization,
as well as in engineering practice [44]. FA is a population-based Swarm Intel-
ligence approach based on the flashing patterns and behaviour of fireflies [43].
FAs have some significant advantages over other metaheuristics, such as genetic
algorithms and Particle Swarm Optimizers [9]. A couple of its distinctive advan-
tages are: the automatic subgrouping and its ability to deal with multimodal
problems [43]. Fireflies can randomly subdivide into sub-groups and each group
can potentially swarm around a local optimum. All optima (obviously including
the global optimum) can be obtained simultaneously if the number of fireflies is
much higher than the number of subgroups [42,43]. Its characteristics become
an attractive alternative to parallelize. In a few years, a lot of research around
FA has been done with excellent results [2,10] in many different fields like Power
Energy Systems [5,8], mobile networks [3] and permutations combinatorial prob-
lems [25,36,44]. However, parallel FA for general purposes and, in particular, for
permutation combinatorial problems constitutes a new developing research area
and there are relatively fewer papers published on this topic [13,32].
In this work, we present a Discrete Firefly Algorithm on GPUs (GPU-DFA)
for permutation combinatorial problems. Therefore, here we show a parallel DFA
running entirely on GPU, and demonstrate that the proposed optimization tech-
nique is quite amenable for massive parallelism to obtain larger performances
and substantial improvements in gain times. We have also studied the behaviour
of GPU-DFA over a set of combinatorial problems not only to establish the
time reductions, but also the numerical advantages of this swarm intelligence
algorithm. In particular, permutation combinatorial optimization problems are
presented in the world in many ways, appearing as an excellent way to evaluate
the performance of our GPU version with problems of interest related to cur-
rent society [18]. In our case, the following well-known problems are analysed:
Travelling Salesman Problem (TSP) and DNA Fragment Assembly Problem
