Information Technology Reference
In-Depth Information
For the purpose of GPU-FA analysis, we have carried out several experiments
with different instances of TSP extracted from TSPLib
1
[1] and DNA-FAP bench-
mark data sets, which were described by Mallen-Fullerton et. al [26]. Table 1
summarizes the information of instances (number of cities, optimal) employed
to evaluate the GPU-FA in contrast with the CPU-FA version.
Table 1.
TSP and DNA-FAP instances
TSP
Instance # of cities Optimal
kroA100
DNA-SA
Instance
# of Fragments Optimal
100
21282
x60189 4
39
11478
d657
657
48912
m154216 6
173
48052
pr1002
1002
259045
bx842596 4
442
227920
4.2 Experimentation
In order to analyse both the behaviour and performance of the algorithms, we
need to clarify some parameter definitions and mechanisms.
In both permutation problems, the distance between two fireflies is defined
by Equation 4, where
A
is the number of different edges between fireflies
i
and
j
following the order brought by the array index or likewise, the number of
consecutive differences in the array positions. For TSP, we need to evaluate one
edge more in
A
when the last index and the first one do not coincide for both
fireflies.
n
is the size of problem. Equation 4 scales
r
in the interval [0
,
10] [14].
r
ij
=
A
n
×
10
(4)
For DFA, the movement of a firefly attracted by another one depends on
A
.
In this work we have applied a 2-opt movement
k
times, where
k
is a number
generated randomly between 2 and
A
. Otherwise, random movement is generated
by applying a 2-opt operator without restrictions.
In order to make a meaningful comparison among both FA versions, we have
employed a common parametrization. Wehaveusedamaximumnumberofeval-
uations as the stop condition for both algorithms (1000000). As the population
and the new solutions may vary, it has different sizes to see if there exists dif-
ferent behaviours of the algorithms and compare that exist some advantage or
not to use different population sizes for each problem. FA works with two pop-
ulations
P
and
temp
respectively. Each one can be modified according to the
parameters
p
and
m
. Then, following the philosophy of FA, we decided to work
combining these two parameters with the follow values: 16, 32 and 48, to evaluate
the scalability of each parameter by modifying the other.
We perform 30 independent runs to test TSP and DNA-FAP instances. Ad-
ditionally we apply statistical analysis is of course very important to sustain
