Ramped half-n-half initialisation bias in GP

Citation

Burke E, Gustafson S & Kendall G (2003) Ramped half-n-half initialisation bias in GP. In: Cantu-Paz E, Foster J, Deb K K, Davis L, Roy R, O'Reilly U, Beyer H, Standish R, Kendall G, Wilson S, Harman M, Wegener J, Dasgupta D, Potter M, Schultz A, Dowsland K, Jonoska N & Miller J (eds.) Genetic and Evolutionary Computation — GECCO 2003: Genetic and Evolutionary Computation Conference Chicago, IL, USA, July 12–16, 2003 Proceedings, Part II. Lecture Notes in Computer Science, 2724. Genetic and Evolutionary Computation Conference — GECCO 2003, Chicago, IL, USA, 12.07.2003-16.07.2003. Berlin Heidelberg: Springer, pp. 1800-1801. http://link.springer.com/chapter/10.1007/3-540-45110-2_71; https://doi.org/10.1007/3-540-45110-2_71

Abstract
Tree initialisation techniques for genetic programming (GP) are examined in [4],[3], highlighting a bias in the standard implementation of the initialisation method Ramped Half-n-Half (RHH) [1]. GP trees typically evolve to random shapes, even when populations were initially full or minimal trees [2]. In canonical GP, unbalanced and sparse trees increase the probability that bigger subtrees are selected for recombination, ensuring code growth occurs faster and that subtree crossover will have more difficultly in producing trees within specified depth limits. The ability to evolve tree shapes which allow more legal crossover operations, by providing more possible crossover points (by being bushier), and control code growth is critical. The GP community often uses RHH [4]. The standard implementation of the RHH method selects either the grow or full method with 0.5 probability to produce a tree. If the tree is already in the initial population it is discarded and another is created by grow or full. As duplicates are typically not allowed, this standard implementation of RHH favours full over grow and possibly biases the evolutionary process.