Next: 4 Discussion of the Up: 5 Genetic Lineages and Previous: 2 Other Forms of   Contents

# 3 Results of Lineage Selection

Lineage selection is applied to the Ant, Parity and Regression problem domains with two experiments: a control experiment with tournament selection and an experiment which employs lineage selection. Table 5.1 describes the parameters used for the following experiments. The Binomial-3 problem is used in Chapter 6 and is described there in greater detail. The other problems and parameters are used from Chapter 4. The main difference between the parameters used here and in Chapter 4 is the use of only binary functions here. Thus, the syntax trees created in the following experiments, and for the remainder of this thesis, will be restricted to binary trees.

 The Ant Problem Min Max Mean Stdev fitness control 0.000 37.000 15.060 12.362 lineages 0.000 29.000 10.930 10.010 nodes control 43.408 116.180 79.068 14.878 lineages 41.968 88.408 62.370* 8.672 entropy control 0.292 1.169 0.709 0.170 lineages 0.542 1.509 1.127* 0.235 edit-d control 0.120 0.353 0.245 0.048 lineages 0.187 0.365 0.275* 0.036 edit-d (W) control 0.615 3.572 1.643 0.628 lineages 1.047 4.394 2.884* 0.711 The Parity Problem Min Max Mean Stdev fitness control 0.000 13.000 6.740 2.207 lineages 5.000 11.000 8.970* 1.195 nodes control 68.064 220.268 124.125 26.762 lineages 63.136 109.580 82.896* 9.443 entropy control 0.437 0.969 0.749 0.092 lineages 0.643 0.940 0.787* 0.05 edit-d control 0.102 0.409 0.221 0.066 lineages 0.259 0.471 0.363* 0.042 edit-d (W) control 0.356 3.494 1.042 0.516 lineages 2.335 5.490 4.507* 0.580 The Binomial-3 Problem Min Max Mean Stdev fitness control 0.000 5.480 0.651 0.972 lineages 0.007 6.930 1.428* 1.875 nodes control 3.000 141.308 57.351 24.950 lineages 2.992 84.372 34.401* 21.659 entropy control 0.287 2.614 1.920 0.554 lineages 0.264 2.662 1.888 0.819 edit-d control 0.200 0.533 0.361 0.060 lineages 0.227 0.711 0.403* 0.104 edit-d (W) control 0.664 2.078 1.123 0.308 lineages 0.677 5.134 2.442* 1.042

Figures 5.3 and 5.4 show the behaviour of the system for the control and lineage experiments. In Figure 5.3, the average best and average mean fitness is plotted against the generation for all experiments. In Figure 5.4, mean run values are plotted for measures of diversity and size, but final generation statistics are also reported in Table 5.2. Note that only the Ant experiments had an improvement in fitness with lineage selection, while all experiments had a significant decrease in size and increase in edit distances using lineage selection. In the control experiment, both measures of edit distance diversity decreased early in the runs and remained low. Initial increases in entropy for the control experiments were followed by either decreases or stagnation. This signifies the inability to improve either the spread of fitness values or the uniformity of the distribution. On the other hand, lineage selection had significantly higher levels of both edit distance diversity. Also, after an initial period of greater decrease of entropy, lineage selection increased entropy longer and to higher values. Figure 5.4 also shows that lineage selection produced significantly smaller individuals.

Figure 5.5 shows that under lineage selection, the distance between successive best fit individuals in the population is also higher. Note that the weighted edit distance measure is not normalised by individual size. Because lineage selection produced smaller individuals, this measure was divided by the average individual size to produce a graph similar to the non-weighted measure, but where all the lineage selection experiments remained significantly higher.

The Ant problem was the only one to benefit in terms of fitness improvement from lineage selection. While the fitness for the Parity and Binomial-3 lineage selection experiments were statistically worse, a high level of fitness was achieved in very diverse populations. This behaviour is also reflected in the phenotypic entropy. The difference in entropy values between the control and lineage selection experiments appears to be somewhat correlated to fitness improvement. Only on the Ant problem did entropy stay at the much higher levels after similar initial behaviours. On the other two problems, entropy was much lower in the initial generations (see Figure 5.4). This indicates that the ability to achieve high entropy is hindered by lineage selection in the Parity and Binomial-3 problems, resulting in worse overall fitness. However, in the Ant problem, lineage selection helps to achieve higher levels of entropy and slightly better fitness.

For the Ant experiments, Figure 5.6 shows the last generation where fitness improved versus the best fitness of the run. Under lineage selection, the Ant problem finds better fitness on average 20 generations later than the control experiment. This is a good indicator that premature convergence is being avoided. The Parity lineage selection experiments had a similar change, where the best fitness was found between 10 and 15 generations later but with a slightly worse fitness. The Binomial-3 results were not significant with respect to fitness or the last generation of improvements.

Next: 4 Discussion of the Up: 5 Genetic Lineages and Previous: 2 Other Forms of   Contents
S Gustafson 2004-05-20