# GRAPE: Grammatical Algorithms in Python for Evolution
## 2 Grammatical Evolution  
GE is a grammar-based method, which fits in the family of EAs and is used to build programs [1, 2, 3]. The genotype of a GE individual is represented by a variable-length sequence of codons, each being equivalent to an integer number, originally defined by eight bits. This genotype is mapped into a phenotype, a more understandable representation, which can be a mathematical expression or even an entire program in practically any language.  
The evolutionary process occurs at the genotypic level, which ensures that the respective phenotypes will always be syntactically correct [6]. However, the evaluation of the individuals happens at the phenotypic level, since a phenotype is a structure, which can directly be evaluated using a fitness function.  
In the evolutionary process, operators such as crossover and mutation are applied to the selected parents, in order to produce new offspring for the next generation. Crossover occurs between two parents, generally generating two offspring. The most common version is one-point crossover, which consists of randomly choosing point in each parent to split them. The resulting tails are then exchanged by the parents producing the offspring. Figure 1 shows an example of this procedure. It is worth noticing that this process can change the size of the genomes. Mutation is an operator that occurs using one parent to generate one offspring and changes the value of a codon at random. In its most common version, every codon is operated on with a predefined probability, usually a small value, which avoids changing an individual too much. This operator does not change the size of a genome, but can change the size of its respective phenotype.  
A grammar is a set of rules that define a language. In GE, grammars are usually represented in Backus-Naur Form (BNF), a notation represented by the tuple N, T, P, S, where \(N\) is the set of _non-terminals_, transitional structures used by the mapping process, \(T\) is the set of _terminals_, items that can occur in the final program, \(P\) is a set of production rules, and \(S\) is a start symbol. We can see an example of \(P\) in the Listing 1. This example represents a simple grammar with only two production rules, being the first one associated with three possible choices and the second one with five.  
```
<a>::=and(<a>,<a>) |or(<a>,<a>) |<x> <x>::=x[0]|x[1]|x[2]|x[3]|x[4]
```  
Listing 1: Example of production rules.  
Figure 1: Example of two individuals being operated by one-point crossover.  
Figure 2 shows an example of the genotype-phenotype mapping process being executed using the grammar presented in Listing 1. This genotype has eight codons, and the mapping procedure starts from the leftmost one, using the modulo operator with the value of the codon and the number of possible choices in the production rule, which is being currently mapped. The choice is made according to the remainder of the division, and the process follows from left to right, always replacing the leftmost non-terminal standing in the intermediate string. Once a fully mapped phenotype, i.e., no more non-terminals, has been produced, the mapping process stops consuming codons, ignoring any remaining ones. Apart from the _effective codons_ used in the mapping process, the unconsumed codons are named as the _tail_ of the individual. However, if all codons were used and there are still non-terminals remaining in the phenotype, that individual is considered invalid, and usually receives the worst value possible to its fitness score. An alternative approach to reduce the possibility of an individual being considered invalid is using _wrapping_, which consists of reusing the codons from the beginning [6]. Nonetheless, sometimes the mapping process cannot finish even considering many wrappings.