next up previous
Next: DEPTH AND SIZE LIMITS Up: Quadratic Bloat in Genetic Previous: BINARY 6-MULTIPLEXOR

   
CONVERGENCE

We consider but reject two possible explanations for the failure of the 6-multiplexor runs to reach a quadratic exponent:

Firstly, the power law coefficients for the two problems are statistically different. I.e. the difference (1.5 v. 2.0) is unlikely to be due to random variations.

Secondly, the multiplexor programs are shorter, so the Flajolet limit does not apply. However [Flajolet and Oldyzko1982, Table II] shows, the parabolic estimate is within 10% of the actual mean for programs of more than 1000 nodes. By generation 90 on average the bulk of the populations exceed 1000. I.e. for at least 500 generations the bulk of the 6 multiplexor populations are reasonably close to the Flajolet limit.

Having rejected these our proposed explanation is, in discrete problems, crossover may cease to be disruptive when the programs become very large. (Similar inability to effect big trees is reported in [Langdon and Nordin2000, Section 2]). In fact there are whole generations when every program in the population has an identical fitness. Therefore the selection pressure driving bloat falls as the populations grow in length and we suggest this is why the quadratic limit is not reached. [Tackett1994] also points to the importance of selection pressure on bloat. Figure 9 shows the fraction of parent programs selected entirely at random rises towards 100% in all ten runs.


Figure: 9 Fraction of selection tournaments where all 7 potential parents have the same fitness. For clarity we plot the mean of ten generations at a time. Ten runs of the binary 6-multiplexor problem.


next up previous
Next: DEPTH AND SIZE LIMITS Up: Quadratic Bloat in Genetic Previous: BINARY 6-MULTIPLEXOR
Bill Langdon
2000-03-16