Keywords: grammatical evolution, Backus Naur form, genetic programming, Santa Fe trail.

Grammatical evolution (GE) can process rules with a tree structure using a one-dimensional chromosome genetic algorithm. The algorithm is as follows:

1. Define a syntax in Backus Naur form (BNF), which translates the genotype (chromosome) to a phenotype (function).
2. Generate randomly initial individuals to construct an initial population.
3. Translate the chromosome to a function using the BNF.
4. Estimate the fitness of the chromosome.
5. Apply selection, crossover and mutation to the population to generate a new population.
6. Terminate the process if the criterion is satisfied.
7. Go to step 3

In this study, we introduce three algorithms for improving the convergence speed of the original GE.

• Scheme 1: The rules are selected by the roulette selection, instead of the remainder in original GE.
• Scheme 2: The selection probability of the recursive rules is controlled according to the length of the generated program.
• Scheme 3: The selection probability of the nonterminal rule is calculated from numbers of nonterminal rules in all individuals.

In the numerical example, the algorithms were applied to the Santa Fe trail problem, to find the program to control artificial ants collecting foods. The comparison of the original GE and scheme 1 shows that the use of scheme 1 improves the convergence speed. However, scheme 2 and scheme 3 are less effctive than the performance of the original GE.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £78 +P&P)