Biomedical Engineering Reference
In-Depth Information
important influence has to do with the protection
effect of redundant code if subjected to the action
of crossover or mutation. Redundant code is
more resistant to crossover and mutation and
allows its carrier solution to survive better, com-
pared to other individuals that do not possess this
redundancy
[31]
. Removal bias in crossover oper-
ations
[32]
that describes the fact that code can
grow to infinity from any size but only be reduced
to zero from a particular size is another explana-
tion. Finally, a genetic drift toward larger solu-
tions
[33]
has been named as an important
influence.
Over the last decade, the relation between
robustness of organisms and their evolvability
has been under intense study in biology (see, for
example, Ref.
34
). A seeming paradox between
these two features frequently found in Nature
has been resolved. It was found that neutral evo-
lution is a key aspect of robustness.
Neutral evo-
lution
refers to the capability of evolution to
change genotypes without changes to pheno-
types of individuals.
7
This capability has been
known for decades, and had previously been
discovered to be an important process in evolu-
tion
[35]
. The understanding of neutrality led to
new mathematical models like the idea of neu-
tral networks
[36]
. These ideas are beginning to
exert influence in the EC community
[37]
, and it
turns out that, also in GP, solutions that are more
robust are preferred through the evolutionary
process, another emergent phenomenon
[38, 39]
.
Although the GA theory has been well estab-
lished, theoretical progress in GP has been more
difficult to achieve since GP works with variable
complexity and multiple fitness cases for fitness
scoring. Many researchers are working to pro-
duce results for GP by gleaning from GA
research. The schema theory of GA
[40, 41]
has
been a primary target of knowledge transfer.
8
In
the meantime, several different schema theo-
rems have been formulated for GP, and theory
has progressed substantially
[42]
.
As researchers analyzed search spaces of
programs, it was realized that their size is many
orders of magnitude larger than search spaces
of combinatorial optimization problems. A typ-
ical size for a program search space might be
10
100
,
000
, as opposed to a typical search space for
a combinatorial optimization problem being of
the order of 10
100
. Although this finding might
be interpreted as discouraging for search mech-
anisms, it was also realized that the solution
density in program spaces is, above a certain
threshold of complexity, constant with chang-
ing complexity
[43]
. In other words, there are
proportionally many more valid solutions in
program spaces than in the spaces of combina-
torial optimization problems.
GP has made great strides over the last two
decades, but many issues are still open and
require continued investigation. The theory of
GP
[42]:
• hassucceededinindingappropriate
schema theorems that allow to understand
how the search space and the population
representation interact,
• hasstartedtoanalyzeMarkovchainmodels
of the search process dynamics, and
• hasfoundwaystocharacterizesearch
spaces (difficulty, complexity) and relate
them to the performance of GP systems.
In coming years, GP theory is expected to
make progress on the treatment of dynamical
7
The genotype of an individual is its genetic make-up, potentially subjected to mutation and crossover, whereas
the phenotype of an individual is the resulting program (behavior).
8
A
schema
in a GA is a subpattern of the genotype that takes the form of a template and can be used to identify
several genotypes. For instance, in a binary string genotype with 4 bits: 1 * 0 *, all genotypes with a 1 in posi-
tion 1 and a 0 in position 3 belong to this schema.
