next up previous
Next: Discussion Up: Boolean Program Spaces Previous: 6 Input Boolean

Even-6 Parity and Always-On-6 Full Trees

 

Restricting our search to just the full trees yields a similar fitness distribution for the even-6 parity problem, see Figure 13. However the distribution of fitness values is considerably wider with a range of 25--38 (twice that for the whole search space) and a standard deviation of 0.68.

Adding XOR to the function set (see Figure 15) further widens the distribution (the standard deviation becomes 1.8).

Even when including XOR, solutions are so rare that their proportion is difficult to estimate accurately. Given this the proportion of solutions in the full trees appears to be the same as in the rest of the search space (with the same program length) despite an overall spreading of the fitness distribution. (The only even-6 parity programs found by random search through full trees contained either 15 or 31 nodes). Both with XOR and without the distribution of hits on the even-6 parity problem returned by full trees shows some dependence on depth of tree but this is much less dramatic than is the case with the three input parity functions, see Figures 6 and 7. However, as with asymmetric trees, this appears to die away as the programs become bigger.

Searching just the full trees yields a similar fitness distribution for the always-on-6 problem as for the whole search space (compare Figures 8 and 12). However the peaks corresponding to functions returning true multiples of 4, 8, 16 or 32 times are now far less prominent and instead always-on-6 itself and its compliment, always-off-6, now dominate and together represent 35% of all trees, compared to 18% when consider asymmetric trees as well. Also the troughs at odd numbers of hits are also less prominent, each representing about 0.5% rather than about 0.3% of all programs.

Adding XOR to the function set (see Figure 14) has the effect of further smoothing the distribution. The peaks at either extreme are now 8% with a typical odd values near 32 being 1.4% and even being 1.8%. Both with XOR and without the distribution of the number of trues returned by full trees shows some dependence on depth of tree. However, as with even-6 parity, this appears to fade away as the programs become bigger.

 


:   Number of ones returned by 6-input full trees (note linear scale)

 


:   Even-6 parity full tree program space

 


:   Number of ones returned by 6-input full trees, XOR included (note linear scale)

 


:   Even-6 parity full tree program space, including XOR in function set



next up previous
Next: Discussion Up: Boolean Program Spaces Previous: 6 Input Boolean



William B Langdon
Tue Jun 16 15:05:48 BST 1998