It has been known for some time that programs within GP populations tend to rapidly increase in size as the population evolves [Koza1992,Altenberg1994,Tackett1994,Blickle and Thiele1994,Nordin and Banzhaf1995,Nordin1997,McPhee and Miller1995,,Soule et al.1996,Langdon et al.1999]. If unchecked this consumes excessive machine resources and so is usually addressed either by enforcing a size or depth limit on the programs or by an explicit size component in the GP fitness [Koza1992,Iba et al.1994,Zhang and Mühlenbein1995,Rosca1997,Rosca and Ballard1996] although other techniques have been proposed [Ryan1994,Blickle1996,Nordin et al.1996,Soule and Foster1997,Soule1998,Hooper et al.1997,Angeline1998,Langdon2000]. However there is still interest in exploring why such bloat happens, its speed and the limits (if any) on bloat.
We extend [Langdon et al.1999,Langdon2000] to consider unbounded artificial evolution for hundreds of generations. Naturally bloat in such circumstances is extremely resource intensive and so we have been restricted to considering simple benchmark problems, one discrete and one continuous. A binary tree version of the Boolean 6 multiplexor problem [Koza1992] and a symbolic regression of a fourth order polynomial. At up to a million elements, these may be amongst the largest programs deliberately evolved so far.
In Section 2 we briefly restate our argument that bloat occurs on average at a sub-quadratic rate. Section 3 describes two experiments which look for the proposed quadratic limit, their results are given in Section 4. While Section 5 shows measurements of GP specific convergence, which explains why, in one case, the quadratic limit is not reached. Section 6 gives results on the potentially beneficial impact of commonly used depth and size limits. Section 7 discusses our theory and results in comparison with other theories of bloat. General conclusions for GP are drawn in Section 8.