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

3. Short-term Operator Success and Population Variation

Initial trials of the technique failed. It was discovered that this was due to the fact that the variation in the base population was too quickly destroyed. To show this an experiment was run where a population of 200 randomly generated operators of depth 5 in the language described above, acted on a population of 10,000 base genes of depth 7 using nodes AND, OR and NOT and terminals input-1,..., input-3. The operators were applied to 50 pairs of input genes each, which were chosen with a probability proportional to their initial fitness (as in standard GP). The fitness of the base population was evaluated on the even parity 3 problem before and after the application of the operators. The effect of the operators was evaluated by the average change in fitness of the operand genes before and after, where binary operators were evaluated by comparing the average of the input genes compared to the result.

Not surprisingly, there was only a slight improvement in the population fitness (and marginally worse than what would have been achieved by fitness proportionate selection alone), but the variation of fitnesses and the average maximum depth of base genes significantly diminished, indicating a destruction of the variation in the base population. The overall statistics are shown in table 1, below.

Table 1: Overall Statistics of Experiment

Firstly, the operators which were effectively binary increased the fitness of the population by significantly less than those that were only unary. It was not that the unary operators were particularly good at increasing fitness, just that, on average, the binary operators were worse than average - this is illustrated in figure 4 (operators that were strictly equivalent to straight propagation are excluded to aid the scaling - there were 59 of these, all unary of course).

Figure 4: Comparison of Distributions of Fitness Change Caused by Operators

I analysed the operators into those with and without certain nodes and terminals, the results are shown in table 2, in terms of standard deviations of fitness changes from the mean fitness change.

Table 2: Table of comparative effect in terms of average fitness change by operator type

The presence (or absence) of substitution, random node choice (as opposed to starting at the root) and the lack of movement up or down, were most significant in affecting fitness change. This, however may be problem specific. What is not apparent from the above is that operators which corresponded in effect to a standard half of a crossover operator, did less well than the average in improving the fitness of the base population (on average they decreased the fitnesses by a factor of 0.98), but were good at preserving variety. This indicates that short-term average increase in fitness may be less important than the occasional discovery of sharply better solutions while preserving variety.

What is more important is the effect on the population variation. This is guessed at via the variation in fitnesses of used and resulting genes from the ground population. This is shown in table 3.

Table 3: Effect on variation of fitness of types of operators

Here we can see the significant effect of the presence or otherwise of top, rand and bott type nodes in an operator. It would seem that omitting either top or rand1 & rand2 will have the effect of preserving the variation in the population. I chose to omit both top and rand1 & rand2 as the above table suggest that the effect of this might be to maximise the increase in fitness as but without the overall bias of the operator language being towards destruction of variety (as it indeed turned out). As we shall see this did have the effect of preserving the base population's variety while allowing the operator population to evolve.

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

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

Generated with CERN WebMaker