Information Technology Reference
In-Depth Information
the problems analyzed in this chapter, when restricted permutation is used in
conjunction with inversion the success rate decreases slightly.
11.2.4 Other Search Operators
In this section, we are going to analyze another set of combinatorial-specific
operators: sequence deletion/insertion and generalized permutation. These
operators are related, respectively, to gene deletion/insertion and restricted
permutation. Compared to inversion, these operators are extremely ineffi-
cient but, nevertheless, the analysis of their performance and mechanisms
can give us some clues about the fundamental attributes that a good combi-
natorial-specific operator must have.
Sequence Deletion/Insertion
We have seen that the gene deletion/insertion operator described in section
11.2.2 permits only the transposition of single genes, in other words, it al-
lows the transposition of small sequences composed of only one element. A
different operator can be easily implemented that deletes/inserts sequences
of varied length (sequence deletion/insertion operator). This might appear
more advantageous than the deletion/insertion of genes, but experience shows
the opposite (see Figure 11.4 below). In fact, this operator produces results
that are even worse than the restricted permutation operator on the traveling
salesperson problem with 19 cities (compare with Figure 11.3). Indeed, an
identical analysis done with this operator showed that sequence deletion/
insertion is incapable of solving the 19 cities TSP using population sizes of
100 individuals for 200 generations. Thus, an easier version of the TSP with
13 cities was chosen in order to allow the comparison between gene dele-
tion/insertion and sequence deletion/insertion (Figure 11.4). For this analy-
sis, a population size of 100 individuals and an evolutionary time of 200
generations were used, that is, exactly the same values of
P
and
G
used in the
much harder TSP with 19 cities.
Generalized Permutation
Generalized permutation is a variation of the restricted permutation operator
described in section 11.2.3. Recall that during restricted permutation only a
pair of genes are exchanged per chromosome, that is, the restricted permuta-
tion rate
p
rp
is evaluated by
p
rp
N
P
, where
N
C
represents the number of
C
