Causality of Hierarchical Variable Length Representations

In this paper the strong causality of program tree representations is considered. A quantitative, probabilistic causality measure is used in contrast to statistical fitness landscape analysis methods. Although it fails to rank different problems according to their difficulty, it is helpful to choose the right coding for a given task. The investigation utilizes a metric on the search space called tree edit distance. Different ways to define such a measure are discussed. 1. Introduction Algorithms in which problem solving is formulated as a search in the space of programs (i.e. expressions of a context free formal language) represented by trees are successfully applied to a growing field of tasks. However, there are few theoretical investigations concerning the properties of this coding, which is mainly used in genetic programming, but also within the scope of stochastic hillclimbing and simulated annealing. O'Reilly [1] proposed an analysis of the variable length representation based ..