4 Initialisation

The genetic programming algorithm requires an initial population of individuals, or syntax trees. There are many possible methods to perform tree initialisation. The ramped half-n-half method is the most commonly used. It was introduced by Koza (1992) and probabilistically selects between two recursive tree generating methods: Grow and Full. The Grow method choses a depth $d$ and randomly picks functions or terminals to build a tree, no deeper in any branch than $d$. The Full method is the same but only choses functions until $d$ is reached, creating full trees of depth $d$.

Several methods have been used to create different distributions of initial trees, where the general consensus is that a more uniform and random distribution is better for the evolutionary process. These methods have recently been described in [Luke, 2000,Luke and Panait, 2001]. While the Full and Grow methods were probably initially (and subsequently) used due to their simplicity, they offer little control over tree creation. However, while other methods do give better control, e.g. [Iba, 1996], it is not clear what methods are better for different situations and whether the complexity of these methods are justified by their performance. Thus, in the research presented in this thesis, the ramped half-n-half method will be used for initialisation.