Information Technology Reference
In-Depth Information
(DNA-FAP) are employed to test the GPU-DFA. For TSP and DNA-FAP, in-
stances of different sizes are used in order to test the behaviour and scalability of
GPU-DFA in contrast with the CPU version. To the best of our knowledge, this is
the first time that a GPU Firefly Algorithm is designed and developed especially
for permutation combinatorial problems entirely over a GPU platform [13,32].
The remainder of this paper is organized as follows. Section 2 introduces the
canonical DFA proposed by Yang [42]. Section 3 presents the general formulation
of the GPU-Discrete Firefly Algorithm. In Section 4 we describe the experimen-
tal settings, including a brief explanation about TSP and DNA-FAP instances.
The main details of the analysis and the results of the computational study
are discussed in Section 5. Finally, Section 6 provides the conclusions and also
highlights future research directions.
2 The Firefly Algorithm and Related Works
The Firefly Algorithm (FA) is a bio-inspired metaheuristic developed by Yang [42].
It was inspired by mimicking the flashing and attraction behaviour of fireflies. In
the scheme of Yang [42,43,44] the fireflies have the following characteristics [9]:
1. All fireflies are unisex, so that one firefly is attracted to other fireflies re-
gardless of their sex.
2. Attractiveness is proportional to their brightness. Hence, for any two flashing
fireflies, the less bright one will move towards the brighter one (see Fig. 1(a)).
The attractiveness is proportional to the brightness and they both decrease
as their distance increases. If no one is brighter than a particular firefly, it
moves randomly as shown in Fig. 1(b).
3. The brightness or light intensity of a firefly is affected or determined by the
landscape of the objective function to be optimized.
(a)
(b)
Fig. 1.
Firefly movement considering their attractiveness: (a)
j
moves to
i
,themost
bright firefly close to it; (b)
j
has more brightness that the most attractive firefly
i
,so
j
moves randomly
A canonical FA works with two basic concepts: the variation of light inten-
sity
I
, and the firefly attractiveness
ʲ
between two fireflies
i
and
j
[42]. This
attractiveness varies according to a distance
r
under a fixed light of absorption
coecient
ʳ
, that can be defined as follows:
