Perform crossover operation on AST in genetic programming

Question

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate.

Consider the sequences below:

0100 1000 0001 1011

0010 0110 1101 1111

A crossover without any mutation might look like this:

0100 0110 1101 1011

0010 1000 0001 1111

In that case, blocks 2 and 3 were swapped and blocks 1 and 4 remained unchanged.

I'm unsure how that would work in GP with abstract syntax trees however, because there is no guarantee that the point in the abstract tree you reference in the first parent will be compatible with the section from the second parent, for example one section might have a return type of boolean while the other has a return type of string, such as in the example below:

    p1
   /  \
  b    i
 /\   /\
b  f i  s

    p2
   /  \
  s    b
 /\   /\
i  n s  i

if you were to try to crossover branch 1 from parent 1 which has a return type of b, with branch 1 from parent 2 which has a return type of s, it would create a syntax error if it were to be ran, so how would I correctly perform a crossover on an AST, specific examples would be appreciated.

Answer 1

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:

1. select a random crossover point [P] from p1
2. swap the sub-tree [P] with a compatible one from p2

e.g.

1. random selection for p1 is [5]
2. 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:

• the previously cited "A Field Guide to Genetic Programming"
• Essential of Metaheuristics by Sean Luke