Canonical representation in genetic programming
Andy J. Keane · ePrints Soton (University of Southampton) · 2008
This paper explores the effect of different forms of representation and different forms of genetic operations on the performance of a Genetic Programming (GP) system. The GP system is based on a Genetic Algorithm (GA) that evolves software agents, represented by tree structures, which are then applied to some problems in robotics. In their evolved form, the trees are not well-formed, and many of them include a considerable amount of intronic material that plays no part in the performance of the underlying agent. We introduce an alternative way of representing the agent, which eliminates the intronic material and reflects more clearly the decisions that the agent needs to make in different situations as it attempts to solve problems in spatial awareness. We use the term canonical to refer to this alternative tree structure. We then extend the standard GP crossover operator to perform canonical crossover, in which the parents exchange canonical sub-trees. This paper shows that using canonical evolution alongside conventional evolution can result in substantial improvements in the performance of the GP system and thus the resulting agents, the level of improvement being dependent on the mix of canonical and non-canonical members of the population, and on the rates and types of crossover.