Transcript Genetic Programming with Primitive Recursion

Gene Expression Programming
with Pre-Order Traversals
Stefan Kahrs
University of Kent at Canterbury
RASC 2006
Kahrs - GEP pre-order
Overview
• intro
• gene expression programming and
grammar evolution
• breeding by crossover, meaning
• change to pre-order traversal
• a problem with that
• ... and its solution
RASC 2006
Kahrs - GEP pre-order
Genetic Programming
breed
fitness criterion
mutate
select
population of programs
RASC 2006
Kahrs - GEP pre-order
GEP and GE
• separate genotype and phenotype
• genetic information (determining an
individual) is given as the list of nodes
of the syntax tree in level-order (GEP)
or pre-order (GE)
• from this a syntax tree is recovered
• the list can have additional node
symbols that do not contribute to the
RASC 2006
- GEP pre-order
tree (allows forKahrs
mutation)
Why GEP/GE?
• separation of genotype/phenotype
allows the manipulation of program
individuals (optimisation) without
interfering with breeding
• avoids program bloat, program sizes
are bounded
RASC 2006
Kahrs - GEP pre-order
Example, level-order traversal
+
sin
*
x
2
+
x
+, sin, *, x, 2, +, x, y
RASC 2006
Kahrs - GEP pre-order
y
Example, pre-order traversal
+
sin
+
*
x
x
2
+, sin, *, x, 2, +, x, y
RASC 2006
Kahrs - GEP pre-order
y
Cross-over breeding
• take two individuals A and B
• throw a dice to determine a crossover
point k
• create a new individual whose first k
symbols are the first k symbols of A,
and its remaining ones are all but the
first k symbols of B
RASC 2006
Kahrs - GEP pre-order
In Pictures
but it does not quite work that way, in general
RASC 2006
Kahrs - GEP pre-order
Arity
• we can extend the notion of arity from
symbols to sequences of symbols
arity() = 1
arity(s·f) = arity(s)-1+arity(f), if arity(s)>0
arity(s·f) = 0, otherwise
• explanation: top-down tree traversal,
placing f in the unfinished tree closes an
open place and opens arity(f) new ones
RASC 2006
Kahrs - GEP pre-order
Example
• take our previous sequence +, sin, *, x, 2, +, x, y
• take the initial segment of the first 5 symbols,
i.e. +, sin, *, x, 2
• its arity is 1
• this means: if we draw the incomplete tree of
this segment there is 1 hole left to be filled
with a subtree
• this incomplete tree segment would be part of
the offspring if this individual fathered with
RASC 2006
crossover point 5Kahrs - GEP pre-order
Procreation with different arity
at crossover point
RASC 2006
Kahrs - GEP pre-order
Trees with arity 1 and 2 at
crossover point 5
+
+
sin
x
*
2
sin
+
x
RASC 2006
sin
*
y
x
Kahrs - GEP pre-order
2
*
y
1
Offspring, father left tree
The subtree that has been placed
in the gap is not a subtree of the
mother, though it is composed
from nodes from the mother
+
sin
*
x
2
*
x
RASC 2006
y
Kahrs - GEP pre-order
So...
• if the arities are the same at cross-over
point then subtrees of the mother are
preserved
• otherwise, mum is atomised and
reassembled
• making the fresh subtrees fairly random
• problems:
– asymmetric contribution in procreation
RASC 2006
Kahrs - GEP pre-order
– level of randomness that is hard to control
A solution
• replace level-order traversal with preorder traversal (which GE uses anyway)
• why? in pre-order traversal subtrees
occur as consecutive subsequences
• notion of arity (of sequences) is
unchanged!
RASC 2006
Kahrs - GEP pre-order
Crossover at 6, different arities
+
+
sin
x
*
2
sin
+
x
RASC 2006
sin
*
y
x
Kahrs - GEP pre-order
2
*
y
1
Crossover at 6, different arities
+
sin
*
x
2
the subtrees pasted into
the tree are either from
the mother, or the
dormant part of the
mother (here: the z)
+
*
y
RASC 2006
z
1
Kahrs - GEP pre-order
A problem
• how do we generate the initial
population?
• with level-order traversal we place
(random) non-nullary symbols at the
beginning of the sequence, nullary
symbols at the end – the result are
balanced trees
• if we do this with pre-order traversal we
RASC
2006 lop-sided trees
Kahrs - GEP
pre-order
get
(more
lists than
Alternatively
• we can meddle with the probabilities to
prevent lop-sidedness, i.e. same
probability for opening/closing a branch
• problem: this gives us microbes (very
small trees) and these buggers breed
as if the end of the world is nigh
RASC 2006
Kahrs - GEP pre-order
Solution
• level-order traversal works well at the
beginning, pre-order traversal works
well subsequently, so: why not use them
this way!
• create the initial population by reading a
sequence as a level-order traversal
• then traverse those trees pre-orderly,
and overwrite the genome
• from then on, use pre-order only
RASC 2006
Kahrs - GEP pre-order