Information Technology Reference
In-Depth Information
minimum computational efforts are 1,276,000 and 384,000, respectively. For
enzyme GP, minimum computational effort has been calculated at 79,000 for the
even-three-parity problem with a population of 100. For the even-four-parity
problem with a population of 625, minimum computational effort is 2,588,750
with crossover and 1,830,000 without. This suggests that enzyme GP cannot
easily evolve even-
n
-parity circuits where
n>
3, at least for these (relatively
small) population sizes, and especially when crossover is used. This agrees with
Miller's findings, where only 15 correct even-four-parity circuits were found
in the course of 400 million evaluations. Langdon [18] suggested that parity
circuits are unsuitable benchmarks for GP. Furthermore, parity circuits involve
a high degree of structure reuse, and it seems possible that subtree crossover,
which is able to transfer substructures independently of their original context,
may be more able to develop this sort of pattern than enzyme GP.
SOLUTION SIZE EVOLUTION
Another problem with GP is bloat, the phenomenon whereby program size
increases considerably faster than program functionality. In standard GP, pro-
gram size growth is near quadratic [19], yet the exact causes of bloat are not
known. Nevertheless, a number of theories have been proposed. These include
hitchhiking [39], protection from disruptive operators [7], operator biases [1],
removal biases [38], and search space bias [21].
Enzyme GP, in contrast, does not suffer from bloat [24, 25]. This is true both
when solution length is bounded, which is the case for uniform crossover, and
when length is unbounded, in the case of TR crossover. Genome size evolution
for both operators is shown in Figure 3.12. These graphs show three different
scenarios. In the top-left graph, initial phenotype length is below the minimum
length required to solve the problem. In the bottom-left graph, the initial length
is above and near the minimum length. In the graphs on the right, initial length
is well above the minimum length.
Where the initial phenotype size is below the minimum size of an optimal
solution, there is an average increase in both genotype and phenotype size,
with phenotype size growing faster than genotype size and both leveling off
once the phenotype is large enough to solve the problem. Where phenotype
size is near and above the minimum, average phenotype size remains constant,
though genotype size still demonstrates a net growth. Where phenotype size
is well above the minimum, there is an average decrease in phenotype size,
whereas genotype size remains, on average, constant.
Interestingly, this suggests a bias in phenotype size evolution toward short,
yet viable, solution sizes. At the same time, there is no bias in genotype size
so long as it is sufficient to contain the phenotype. Enzyme GP does not pe-
nalize longer solutions during evaluation and, consequently, there must be an
