Sub-tree Swapping Crossover and Arity Histogram Distributions


Dignum S., Poli R.

13th European Conference on Genetic Programming, İstanbul, Türkiye, 7 - 09 Nisan 2010, cilt.6021, ss.38-49 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 6021
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.38-49

Özet

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.