Biomedical Engineering Reference
In-Depth Information
TABLE 17.1
Comparison of GA versus GP.
GA
GP
Representation
Fixed length
Variable length
Individual
Passive
Active
Genome
Parameters
Program/algorithm
Input
None
Input values
Fitness
One value
Many fitness cases
Typical application
Function optimization
Function approximation
10
100
10
100,000
Typical size of search space
representation, as in Eq.
(17.1)
? Does it use mul-
tiple fitness cases or is there only one fitness
measurement? The former is a GP approach, the
latter a GA approach. Naturally, a GP approach
will search a larger space of possibilities because
the combinatorics of its structures is much larger,
with typical GP search spaces 10
1,000
times larger
than typical GA search spaces.
Table 17.1
sum-
marizes the issues.
architectural designs (
structures,
for short). The
overarching principle is to subject all these kinds
of structures with variable complexity to forces
of evolution by applying mutation, crossover,
and fitness-based selection. The results must
not necessarily be programs, but they could
be descriptions for designs (e.g., structures of
bridges) or other manipulatable elements.
An ever-present difficulty with GP is that the
evolution of structures of variable complexity
(e.g., program code) often leads to individuals
with a large number of elements, often with con-
siderable redundancy. Notably it was found that
variable complexity often leads to inefficient code
that requires a lot of memory space. Several
researchers subsequently observed that the evo-
lutionary forces seem to exert a pressure toward
more complex solutions, parts of which could be
removed after evolution without doing any harm
to the behavior of the evolved solution. By draw-
ing an analogy from biological evolution of
genomes, this phenomenon was originally called
code bloat
,
intron growth
, or
growth of ineffective code
[28]
. It was found that code growth is not the only
unintended result of evolutionary processes, but
it has been the most examined emergent phenom-
enon to date
[29]
.
6
At least three different influ-
ences are at work promoting the growth of
complexity
17.4 ADVANCES AND STATE OF
THE ART
In his seminal work of 1992, Koza established
the field of GP by arguing convincingly that
manipulation of structures of symbolic expres-
sions is possible with evolutionary algorithms
and that the resulting technique would have
a wide variety of applications. In subsequent
years, the field experienced both broadening and
deepening
[24]
. Many different representations
for GP were studied, among them other generic
data structures such as sequences of instructions
or directed graphs, as well as more exotic data
structures such as memory stacks or neural net-
works. Today, different approaches are consid-
ered GP, from the evolution of expression trees
to the evolution of electronic circuits or even
during
evolution.
The
most
6
Another emergent phenomenon in GP is the emergence of repetitive code
[30]
.
