next up previous
Next: Grammatical Evolution Up: Grammatical Evolution : Evolving Previous: Backus Naur Form

Genetic Algorithm for Developing Software

Genetic Algorithm for Developing Software (GADS) as described by [Paterson 97] uses fixed length chromosomes which encode which production rules are to be applied. If, when interpreting a gene, it doesn't make syntactic sense, e.g. trying to apply rule 2.A as the first production, or when no operator is available, it is ignored.

If, at the end of the chromosome, there are gaps in the expression, i.e. non-terminals which did not have any terminal chosen for them, a default value is inserted. The default value must be tailored for each production rule. In [Paterson 97] it was suggested that an empty production is the suitable approach, however, this is not always possible. Consider the BNF above, rules 2 and 3 must produce an operator of some description, otherwise the entire expression would be compromised. Thus, an arbitrary decision must be taken about which rule should be used as the default. If, for example, an individual was generated that had the non terminal <op> in it, with all of the genes exhausted, one must decide which of the rules 2A..2D should be used as a default rule. Clearly, an unfortunate or misguided choice could harm the evolution of a population.


next up previous
Next: Grammatical Evolution Up: Grammatical Evolution : Evolving Previous: Backus Naur Form
Red Hat Linux User
1998-10-02