alogos.systems.cfggpst.crossover

Crossover functions for CFG-GP-ST.

Functions

subtree_exchange(grammar, genotype1, genotype2, parameters=None)

Generate new CFG-GP-ST genotypes by exchanging suitable subtrees.

Detailed object descriptions

alogos.systems.cfggpst.crossover.subtree_exchange(grammar, genotype1, genotype2, parameters=None)[source]

Generate new CFG-GP-ST genotypes by exchanging suitable subtrees.

Randomly select nodes containing the same nonterminal in two trees and swap their subtrees. Note that CFG-GP-ST uses serialized trees. Crossover can be done directly in the serialized representation and does not require a preliminary reconstructing of trees. This inplace modification leads to a considerable speedup.

Parameters:

  • grammar (Grammar)

  • genotype1 (Genotype) – Genotype of the first parent.

  • genotype2 (Genotype) – Genotype of the second parent.

  • parameters (dict or ParameterCollection, optional) – Following keyword-value pairs are considered by this function:

    • max_nodes (int) : Represents the maximum number of nodes allowed inside newly generated trees

Returns:

  • genotype1 (Genotype) – Genotype of the first child.

  • genotype2 (Genotype) – Genotype of the second child.

Notes

The randomly selected nodes may be the root nodes of both trees, which means that the crossover will produce genotypes that are identical to the given genotypes. It would be possible to exclude the root nodes from the random node selection, but in case of recursive grammars the start symbol may appear in lower parts of the tree and then a swap between root node and lower node produces novel genotypes.

References

  • 1995, Whigham: Grammatically-based Genetic Programming

    • “All terminals have at least one nonterminal above them in the program tree (at the very least S), so without loss of generality we may constrain crossover points to be located only on nonterminals. The crossover operation maintains legal programs of the language (as defined by the grammar) by ensuring that the same non-terminals are selected at each crossover site. The parameter MAX-TREE-DEPTH is used to indicate the deepest parse tree that may exist in the population. The crossover algorithm (see figure 3) is: […]”

    • “We note that the parameter MAX-TREE-DEPTH may exclude some crossover operations from being performed. In the current system, if following crossover either new program exceeds MAX-TREE-DEPTH the entire operation is aborted, and the crossover procedure recommenced from step 1.”

  • 2003, Poli, McPhee: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

    • An example where the name “subtree-swapping” is used for the same crossover operation.