Sub-tree Swapping Crossover and Arity Histogram Distributions

Dignum S., Poli R.

13th European Conference on Genetic Programming, İstanbul, Turkey, 7 - 09 April 2010, vol.6021, pp.38-49 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 6021
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.38-49
  • Istanbul Technical University Affiliated: No


Recent theoretical work has characterised the search bias of GP sub-tree swapping crossover in terms of program length distributions, providing an exact fixed point for trees with internal nodes of identical arity. However, only an approximate model (based on the notion of average arity) for the mixed-arity case has been proposed. This leaves a particularly important gap in our knowledge because multi-arity function sets are commonplace in GP and deep lessons could be learnt from the fixed point. In this paper, we present an accurate theoretical model of program length distributions when mixed-arity function sets are employed. The new model is based on the notion of an only histogram, a count of the number of primitives of each arity in a program. Empirical support is provided and a discussion of the model is used to place earlier findings into a more general context.