Meta-Genetic Programming: Co-evolving the Operators of Variation - Bruce Edmonds

2. The Basic Technique

Instead of being hard-coded, the operators are represented as tree structures. For simplicity this is an untyped tree structure in the manner of Koza [8]. Two randomly chosen trees along with randomly chosen nodes from those trees are passed to be operated on by the operator tree. The terminals refer to one or other of these trees at the respective node. The structure of the operator tree represents transformations of this (tree, node) pair until the root node produces the resulting gene for the next operator.

Thus there could be the following terminals:

rand1 - return the first, randomly chosen gene plus random node;
rand2 - return the second, randomly chosen gene plus random node;
bott1 - return the first, randomly chosen gene plus the root node;
bott2 - return the second, randomly chosen gene plus the root node.

and the following branching nodes:

top - cut the passed tree at the passed node and return it with the root node;
up1 - pass the tree as it is but choose the node immediately up the first branch;
up2 - pass the tree as it is but choose the node immediately up the second branch;
down - pass the tree as it is but choose the node immediately down;
down1 - identical to down (so that the operators will not have an inherent bias up or down);
subs - pass down a new tree which is made by substituting the subtree at the node of first argument with for the subtree in the second at the second's indicated node.

For example if the operator, [up2 [top [rand1]]] were passed the following input pair of (tree, node) pairs to act upon, ([B [A [A [B [2]] [1]] [3]]], [1 1]), ([A [1] [2]], [2]) it would return the pair ([A [B [2]], [2])*1 - this process is illustrated below in figure 1.

Figure 1: An example action of an operator on a pair of trees with selected nodes

A second example is if the operator, [subs [bott2] [rand2]] were passed the same inputs it would return ([A [1] [A [1] [2]]], [2]) - as illustrated in figure 2.

Figure 2: A second example of an operator acting on a pair of trees with selected nodes

Thus a cut&graft operator (one half of a traditional GP crossover) could be represented like this (figure 3).

Figure 3: A cut and graft operator encoded as a tree

This takes the first random gene, cuts off the top at the randomly chosen position and then substitutes this for the subtree at the randomly chosen position of the second chosen gene. The single leaf rand1 would represent propagation.

The population of operators is treated just like any other genetic population, being itself operated on by another population of operators. This sequence must eventually stop with a fixed non-evolving population of operators or a population that acts upon itself.

The base population and operator population(s) will have different fitness functions - the basic one determined by the problem at hand and the operator's function by some measure of success in increasing the fitness of the population they operate on.

Meta-Genetic Programming: Co-evolving the Operators of Variation - Bruce Edmonds - 28 JAN 98

[Next] [Previous] [Top] [Contents]

Generated with CERN WebMaker