next up previous contents
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.

Table 5.2: The Ant, Parity and Binomial-3 statistics for the lineage selection and control experiments. Significant difference is denoted with a `*' next to the mean values for lineage selection. Significance testing was done using the Student's T-test at the 95% confidence level.
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.3: Average mean and average best fitness vs. generation are shown for each problem and experiment type (control and lineage).
Figure 5.4: Average measures vs. generation are shown for each problem and experiment type (control and lineage).

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.

Figure 5.5: Edit distance between successive best-fit individuals for the control and lineage selection experiments.

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 up previous contents
Next: 4 Discussion of the Up: 5 Genetic Lineages and Previous: 2 Other Forms of   Contents
S Gustafson 2004-05-20