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.

Figure 6.2: Each problem instance's final population performance values have been discretised and placed into 60 (Binomial-3) or 21 (polynomials) bins to show their distribution. Bins to the left in each instance represent better fitness.

Figure 6.3: Results of the Binomial-3 experiments. The average size of the population containing the best-of-run individual is plotted against best-of-run fitness (left column), the generation in which the best-of-run individual occurred (middle column) and the average depth of the population (right column). Each circle corresponds to one run.

Figure 6.4: Results of the random polynomial experiments. The average size of the population containing the best-of-run individual is plotted against the best-of-run fitness (left column), the generation in which the best-of-run individual occurred (middle column) and the average depth of the population (right column). Each circle corresponds to one run.

Figure 6.5: The Binomial-3 problem adjusted fitness, depth, nodes, edit distance and entropy versus generation for the control, unity, ten, and hundred experiments. Points represent the average over 100 runs.

Figure 6.6: The random polynomial experiments adjusted fitness, depth, nodes, edit distance and entropy versus generation for degree 3, 7 and 11 polynomials. Points represent the average over 100 runs.

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.