Evolutionary Algorithms have been used with much success for the automatic generation of programs. In particular, Koza's [Koza 92] Genetic Programming has enjoyed considerable popularity and widespread use. While Koza originally employed Lisp as his target language many experimenters generate a home grown language peculiar to their particular problem. Grammatical Evolution (GE) can be used to generate programs in any language, using a genetic algorithm to control what production rules are used in a Backus Naur Form (BNF) grammar definition.
Whigham has used grammars with respect to Genetic Programming [Whigham 95] to define the structure of the individuals in the initial population and to direct operators such as crossover to ensure syntactically correct programs are created. Whigham also used the grammar as a method of biasing the initial population towards the target solution [Whigham 96].
Whereas Whigham used a grammar to define the initial population and lets Genetic Programming operate on the resulting parse trees, GE simply encodes a binary string which the Genetic Algorithm operates on. The grammar is then used to map the individual bit strings onto a program when evaluating fitness.
GE has proved successful when applied to a symbolic regression problem [Ryan 98a], and finding trigonometric identities [Ryan 98b], here we apply GE to a symbolic integration problem taken from the literature [Koza 92]. This involves finding a function which is an integral of Cos(X)+2X+1.
In each of these cases we take a subset of C as our target language which is described in Backus Naur Form definition. A Steady State selection mechanism [Syswerda 89] has been employed and was found to reduce the number of generations required to achieve a correct solution. Using this selection mechanism we reapplied our system to the two problems previously tackled and again found an improvement in performance for both of these problems.