Structuring chromosomes for context-free grammar evolution

This paper investigates the use of genetic algorithms for inferring small regular and context-free grammars. Applied simply, a genetic algorithm is not very effective at this. To overcome this problem we investigate two methods of structuring the chromosomes. The first is to bias the distribution of `1´s in the population of chromosomes according to an algebraic expansion technique previously developed by the author. This `design´ of the chromosome distribution, shows no bias to any particular type of language (i.e. full generality is retained) yet improves convergence. The second method involves performing the evolution (i.e. making the mutations) in a different space, where the grammars are represented in `embedded normal form´. The latter approach structures the chromosome to represent context-free rather than regular grammars, for example. It is shown that biasing the chromosome in this fashion produces extremely fast convergence, and 3-symbol palindromes grammars are learned in typically less than 10 generations