Information Technology Reference
In-Depth Information
Table 11.1
Parameters for the traveling salesperson problem with 19 cities.
Number of runs
100
Number of generations
200
Population size
100
Number of multigene families
1
Number of genes per multigene family
19
Chromosome length
19
Inversion rate
0.25
Success rate
96%
The results obtained by gene expression programming are astounding if
we compare them with the performance the GA achieved on the 19-city TSP.
For instance, Haupt and Haupt (1998) could not find the shortest route using
population sizes of 800 for 200 generations. As shown in Figure 11.3 and
Table 11.1, the algorithm described here not only is capable of finding the
shortest route using populations of only 100 individuals and for the same
200 generations, but also is capable of finding the shortest route in practi-
cally all runs (in 96% of the runs, in fact). It is worth pointing out that, in this
experiment, inversion is the only source of genetic variation. Indeed, the
presence of other genetic operators, namely, gene deletion/insertion and re-
stricted permutation, decreases slightly the success rate and, therefore, these
operators were not used. Apparently, they are unnecessary for finer adjust-
ments whenever inversion is doing the search.
As stated earlier in this chapter, the chromosomal architecture used to
solve combinatorial problems corresponds exactly to the canonical genetic
algorithm. So, why the stunning difference in performance between these
two algorithms? Obviously, the answer lies in the set of genetic operators
used by GEP and by the GA. As shown in Figures 11.3, 11.4, and 11.5 above,
inversion performs significantly better than permutation (both restricted and
generalized implementations). And different kinds of permutation and ex-
tremely complicated forms of crossover are exactly the kind of search opera-
tors favored by GA researchers to solve combinatorial problems (see
Larrañaga 1998 for a review). Unfortunately, inversion was abandoned ear-
lier in the history of genetic algorithms and maybe because of this it is sel-
dom used today even in combinatorial optimization.
