What is Size Fair Crossover?

Size fair crossover [GENP 2000] was introduced as an effective measure against the unconstrained growth of program size which is accompanied by no increase in program performance. It acts by ensuring the inserted subtree is of a similar size to the subtree it replaces. (See Figure 1).

Figure 2 shows it has been highly effective in controlling bloat (size increase) in a range of classifier combination examples.

Figure 1 An example of size fair crossover. The shaded subtree (size 4) is chosen in the first parent (top left) to be removed. A crossover fragment size 3 is chosen. There are two possible subtrees (shaded) in the second parent (middle). In size fair crossover, one is chosen at random, yielding a child of about the same size. The child produced is shown at the bottom.

In homologous crossover the left hand shaded fragment would be chosen as it it syntactically closer to the fragment it will replace.

Figure 2 Evolution of average composite classifier size with genetic programming.

The examples come from

back

W.B.Langdon@cs.ucl.ac.uk 30 August 2001 (last update 4 Oct 2012).