Information Technology Reference
In-Depth Information
less efficient ones: sequence deletion/insertion and generalized permutation.
All these combinatorial-specific operators allow the introduction of genetic
variation without disrupting the balance of multigene families and, there-
fore, always produce valid structures.
Before proceeding with the description of their mechanisms, it is useful to
compare their performances (Figure 11.3). The problem chosen to make this
analysis is the traveling salesperson problem (TSP) of section 11.3.1 with 19
cities using population sizes of 100 individuals and evolutionary times of
200 generations. As Figure 11.3 clearly demonstrates, the best operator is by
far inversion, followed by gene deletion/insertion, whereas restricted per-
mutation is the less efficient of all.
100
90
80
70
60
Inversion
Gene Del/Ins
Permutation
50
40
30
20
10
0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Operator rate
Figure 11.3.
Comparison of inversion, gene deletion/insertion, and restricted
permutation on the traveling salesperson problem with 19 cities. For this analysis,
P
= 100 and
G
= 200. The success rate was evaluated over 100 identical runs.
11.2.1 Inversion
The inversion operator randomly selects the chromosome, the multigene family
to be modified, the inversion points in the MGF, and inverts the sequence
between these points. Each chromosome can only be modified once by this
operator.
