1 Code Growth and Problem Difficulty

Two challenging problems in genetic programming are the application of genetic programming on increasingly difficult problem instances and the increase of solution size which is not correlated with improvement. Daida et al. (2001) recently demonstrated that when genetic programming has difficulty solving harder problem instances, solutions are generally larger in size, take longer to find, and are less numerous in the population. Of these traits, the increase in size without corresponding fitness improvement is the most worrying to genetic programming practitioners. The continued growth of solutions for difficult problems will become a limiting factor of the applicability of the algorithm; computational resources will be exhausted and the algorithm will halt before reaching a good solution. The existing theories of code growth [Langdon and Poli, 2002,Luke, 2003,Soule and Heckendorn, 2002] provide the mechanical basis for understanding why programs in a variable-length representation tend to grow in size, but do not predict the rate of growth or explain why optimal solutions can vary in size by a large degree. Additionally, the many methods used to limit code growth, or to remove non-functional code from solutions, may often lead to worse performance [Ekárt, 2000,Luke and Panait, 2002a,Soule and Foster, 1998,Zhang and Mühlenbein, 1995].

Two symbolic regression problems are used that are differently scaled in difficulty to observe the behaviour of fitness, code growth and diversity. If growth is related to instance difficulty, it will be likely that the dynamics of the population, viewed with measures of diversity, will aid in understanding the phenomenon. Symbolic regression problems are used for two main reasons. Firstly, there is a large body of existing theoretical studies using regression problems to understand genetic programming. Secondly, it is easier to reason about increasing the difficulty of fitting mathematical functions than it might be for increasing the difficulty of other types of problems.