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.