 |
    |
Softening the Structural Difficulty in Genetic Programming with TAG-Based Representation and Insertion/Deletion Operators
Nguyen Xuan Hoai and R.I. McKay
School of IT & EE, Australian Defence Force academy, University of New South Wales, ACT 2600, Australia.x.nguyen@adfa.edu.au
rim@cs.adfa.edu.au
Abstract. In a series of papers [3-8], Daida et. al. highlighted the difficulties posed to Genetic Programming (GP) by the complexity of the structural search space, and attributed the problem to the expression tree representation in GP. In this paper, we show how to transform a fixed-arity expression tree in GP to a non fixed-arity tree (Catalan tree) using representation based on Tree Adjoining Grammars (TAGs). This non fixed-arity property, which is called feasibility, allows us to design many types of genetic operators (as in [16]). In particular, insertion/deletion operators arising naturally from the representation play a role as structural mutation operators. By using these dual operators on TAG-based representation, we demonstrate how these operators can help to soften the structural search difficulties in GP.
LNCS 3103, p. 605 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004