next up previous
Next: Grammatical Evolution Up: Grammatical Evolution: A Steady Previous: Grammatical Evolution: A Steady

Introduction

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.


next up previous
Next: Grammatical Evolution Up: Grammatical Evolution: A Steady Previous: Grammatical Evolution: A Steady
root
1998-10-02