Expression Mutator

Expressions are a useful genome representaton for genetic algorithms because they can be used to generate many interesting objects, such as images, sound, parametric surfaces, and implicit objects.

With this in mind, a general mutator and crossbreeder for expressions was written. It takes as input a list of allowable variables and function names, making it adaptable for many purposes.

The expression is represented internally as a tree, with functions as non-leaf nodes and numbers, variables, or vectors stored at leaves. A mutation is done by recursively walking down the tree and deciding at each node whether to mutate it. If the node is a non-leaf, then there are four possibilities for what can happen when the node is mutated (based on weighted probability). See Figure 2 for a pictorial view of the possible mutations.

1. Push the current node down the tree one level, adding a new node to replace the current one
2. Move a node from one level down up to replace the current node
3. Change the function (also changing children as appropriate for the new function)
4. Replace the node with a leaf node

  
Figure 2: Various types of mutatations performed on trees

For leaf nodes, the possible mutations are to push the node down the tree (method one from the above list) or to randomly change the value of the leaf.

Two expressions are crossbred by descending the two expression trees simultaneously. At each step, there is a probability that the node of the host expression will be replaced by the corresponding doner expression node.