Information Technology Reference
In-Depth Information
This analysis clearly shows the importance of the permanent introduction
of genetic variation through mutation and similar non-homogenizing opera-
tors such as RIS or IS transposition. Note that populations of 50 individuals
evolve, in this case, very inefficiently. And the often spoken fatalist remark
about the inability of GP populations to evolve beyond 50 generations can be
fully understood. As Figure 12.14 emphasizes, homogenizing systems show
no appreciable increase in success rate after 50 generations. Remember that
genetic programming uses almost exclusively a GP-specific recombination
(sub-tree crossover) as the only source of genetic variation. Here we can see
that even recombinational mechanisms more disruptive than the recombina-
tion used in genetic programming (namely, one-point and two-point recom-
bination), are inadequate to make populations evolve efficiently. This obvi-
ously accounts for some of the superiority of GEP over GP, although, of
course, the most important is the genotype/phenotype representation and all
the things this representation brings with itself. The plot for the 250-mem-
bers population indicates that only the use of huge population sizes will per-
mit an efficient evolution in those systems. Note, however, that not even for
such large population sizes was it possible to surpass the results obtained for
populations of only 50 individuals when mutation and transposition were
switched on (see Figure 12.13).
12.7 Analysis of Different Selection Schemes
It is known that the fruits of selection are better seen with time. Thus, we are
going to analyze the performance of three different selection schemes using
two different problems by evaluating the variation of success rate with evo-
lutionary time.
The selection schemes I chose to study include the already known rou-
lette-wheel selection used in all the problems of this topic, a two-players
tournament selection, and a deterministic selection scheme. For all the
schemes, even deterministic selection, the cloning of the best individual is
also done in order to allow the use of a fair amount of genetic modification
without loosing the best trait.
The tournament selection with elitism works as follows: two individuals
are randomly picked up and the best of them is chosen to reproduce once. If
they happen to have the same fitness, then one of them is randomly chosen to
reproduce. Thus, each generation, for populations of
N
individuals,
N
tour-
naments are made so that the population size is kept unchanged.
