Information Theory, Fitness, and Sampling Semantics

One of the most significant developments in genetic programming (GP) research in the last few years has been a growing focus on the semantics of programs. Traditional GP is focused on program text and designed operators and representations around syntactic transformations. For example, a mutation operator will be designed to make a small-but-not-too-small change to the text of the program, with the hope that it would have a similar effect on program behaviour. By contrast, semantic methods are based on the idea that GP should be designed so that operators and representations work on the meaning and behaviour of the programs represented—i.e. on their input-output mappings. So, for example, a semantic mutation operator would (either by generate-and-test or by design) make a small-but-not-too-small change to that input-output behaviour. Early work on semantic methods in GP focused on the creation of semantic diversity; for example, ensuring that the IO behaviours of programs in the initial population were all different [2], or that crossover and mutation operators did not give rise to child programs that had the same behaviour as the parent programs, or which made a transformation of the behaviour of a certain distance in semantic space [1, 3, 8, 9]. The core of this process is a generate-and-test approach that generates candidate programs and rejects them if some semantic measure is exceeded. More recently, focus has shifted towards the creation of GP methods that operate on semantics by design. For example, the geometric semantic GP approach [7, 10] redesigns the operators so that, for example, a crossover operator generates a program that is “inbetween ” the behaviours of the two parent programs. This is achieved by construction, by forming a chil