A first observation is that canonical GA is based on a fixed length representation (a fixed number of genes in specific loci on the chromosome).
So crossovers GA operators are similar to biological sexual reproduction: the genetic material from both mother and father is combined in such a way that genes in the child are in (approximately) the same position as they were in its parents.
It's quite different from traditional tree-based GP crossover, which can move a sub-tree to a totally different position in the tree structure.
This form of crossover can happen since standard GP assumes a "limitation" known as closure:
all the variables, constants, arguments for functions and values returned from functions must be of the same data type.
An AST-based representation is a form of (Strongly) Typed Genetic Programming and introduces some constraints on the feasible crossover points.
Every node of the AST is associated with a type and, before performing crossover, you have to create a list of compatible crossover points:
p1[1] p2[1]
/ \ / \
[2]b i[5] [2]s b[5]
/ \ / \ / \ / \
[3]b [4]f [6]i [7]s [3]i [4]n [6]s [7]i
b(p1): [2, 3] b(p2): [5]
f(p1): [4] f(p2): []
i(p1): [5, 6] i(p2): [3, 7]
s(p1): [7] s(p2): [2, 6]
n(p1): [] n(p2): [4]
Now:
- select a random crossover point
[P]
from p1
- swap the sub-tree
[P]
with a compatible one from p2
e.g.
- random selection for
p1
is [5]
- compatible sub-trees from
p2
have root in [3]
and [7]
. Random selection is [7]
.
The result of the crossover is:
p1 p2
/ \ / \
b i s b
/\ / \ / \
b f b fs i
/ \
i s
Children haven't the same shape but it's quite standard in GP.
This is a very basic approach. With time you have to consider various other aspects:
often crossover points aren't selected with uniform probability:
typical GP primitive sets lead to trees with an average branching factor
(the num-ber of children of each node) of at least two, so the majority of the nodes will be leaves. Consequently the uniform selection of crossover points lead to crossover operations frequently exchanging only very small amounts of genetic material (i.e. small subtrees); many crossovers may in fact reduce to simply swapping two leaves.
To counter this, Koza (1992) suggested the widely used approach of choosing functions 90% of the time and leaves 10% of the time.
(from A Field Guide to Genetic Programming by Riccardo Poli, William Langdon, Nicholas McPhee, John Koza)
So simple lists of compatible crossover points couldn't be enough.
you may have to use special operators to reduce the tree size (e.g. Hoist Mutation, Shrink mutation)
in some contexts you may want a crossover operator that tend to preserve the position of genetic material (homologous).
E.g. with one point homologous crossover you have to analyze the two parent trees from the root nodes and select the crossover point only from the parts of the two trees in the common region.
The common region is related to homology, in the sense that the
common region represents the result of a matching process between parent
trees. Within the common region between two parent trees, the transfer of
homologous primitives can happen like it does in a linear bit string genetic
algorithm
("A Field Guide to Genetic Programming")
Homologous crossover presents interesting implementation details (it should be coordinated with the list of type-compatible crossover points).
AST-based representation can introduce various form of "structural bias" that crossover / mutation operators must acknowledge.
Last but not least there are other representations well suited to implement Typed Genetic Programming (even not tree-based). Linear representations may be the best choice for certain programming languages (it's fairly straightforward to realise homologous crossover when using linear representations and homologous operators are widely used in linear GP).
Two wonderful free resources for further details are: