Information Technology Reference
In-Depth Information
Indeed, several evolution-inspired algorithms used the TSP as a battleground
to develop combinatorial-specific search operators (see, e.g., Ferreira 2002b
for a detailed list of the most common combinatorial-specific operators).
For the TSP with 19 cities there are 19! = 1.21645
X
10
17
combinations to
search. If we fix the starting point (and consequently the ending point, for
salespersons must return home), the number of possible combinations is
halved to 6.0823
X
10
16
. Furthermore, if we choose a configuration where all
the cities lie in a rectangle as shown in Figure 11.6, we can rigorously evalu-
ate the performance of the algorithm as we know beforehand the correct
solution; for a 19 cities tour, the minimum distance will be obviously 20.
y
16
15
14
13
12
11
10
17
18
9
19
8
x
0
1
2
3
4
5
6
7
Figure 11.6.
Configuration of 19 cities arranged in a rectangle. The arrow indicates
the starting and finishing point. Obviously, the shortest tour is to trace the rect-
angle which has a distance of 20.
Obviously, we cannot use the tour length directly as a measure of fitness of
the evolving solutions, as the shorter the tour the fitter the individual. Thus, for
each generation, the fitness
f
i
of an individual program
i
in generation
g
is
evaluated by the formula:
f
i
=
T
g
- t
i
+
1
(11.11)
where
t
i
is the length of the tour encoded in
i
, and
T
g
is the length of the
largest tour encoded in the chromosomes of the current population. This
way, the fitness of the worst individual of the population is always equal to
one. As usual, individuals are selected according to fitness by roulette-wheel
selection and in each generation the best individual is cloned unchanged into
the next generation. Both the performance and parameters used per run are
summarized in Table 11.1.
