Next: 2 Binomial-3 Results Up: 4 Binomial-3 and Random Previous: 4 Binomial-3 and Random   Contents

## 1 Establishing Difficulty

Daida et al. (2001) established the tunable nature of the Binomial-3 problem by demonstrating increased difficulty through the reduced frequency which good solutions are found, the longer it took for good solutions to be found and the increased size of good solutions. In Figure 6.2, the best fitness of 100 runs for each experiment are placed into bins and plotted in a histogram. The left-most bins in each experiment - corresponding to the number of best solutions found - are expectedly larger for easier instances. The Binomial-3 results show a clear trend of less good solutions with increasing ERC ranges. In the case of the polynomial results, this trend is clear for degree 3 and degree 11. Note the large number of poor fit runs for the degree 11 polynomial (the right-most bins). These `failed' runs tend to be present in regression problems where the lack of initial fitness improvements causes the run to become stuck in poor local optima. The nature of the degree 11 polynomial amplifies this effect, as we would expect. As shown later, the degree 7 polynomial produces a mixture of results but generally shows the expected behaviour.

In Figure 6.3 the results from Daida et al. (2001) are reproduced based on the experiments carried out here. Figure 6.4 shows the similar results for the generated polynomials. The same trends apply for both the Binomial-3 instances and the random polynomials. Increasing the ERC range worsens the best fitness found and increases the size and depth of the solutions when best fitness is found. When the difficulty is increased, the best-of-run solutions are found in later generations. Note that while the fitness function remains the same in the Binomial-3 problems, the polynomial fitness function does change. For the polynomial experiments, the distinguishing feature of run performance is the amount of improvement that genetic programming can find. The difference in this behaviour can be seen in Figure 6.6.

The higher degree polynomials contain smaller variations and the fitness functions across the instances are not the same. As the higher degree polynomials start with lower initial fitness, the improvement rate from initial generations to later ones is observed as a sign of performance. The higher the degree, the less improvement is made during the evolutionary process, the bigger and deeper solutions are and the later they are found. A more in-depth analysis of the behaviour of runs with respect to size, entropy and edit distance follows.

Next: 2 Binomial-3 Results Up: 4 Binomial-3 and Random Previous: 4 Binomial-3 and Random   Contents
S Gustafson 2004-05-20