Grammatical evolution for the genetic algorithm

Grammatical evolution algorithm

The grammatical evolution algorithm is inspired by the biological process used to generate a protein from genetic material as well as the larger genetic evolutionary process. The genome is made up of DNA like a chain of building blocks that are transcribed into RNA. The RNA codons are in turn translated into amino acid sequences and used in the protein. The resulting protein in its environment is the phenotype.

The phenotype is a computer program created from a genome based on binary chains. The genome is decoded into a sequence of integers which in turn are mapped to pre-defined rules that make up the program. Mapping from genotype to phenotype is a one-to-many process that uses a packaging function.

It is like the biological process seen in many bacteria, viruses and mitochondria, where the same genetic material is used in the expression of different genes. Mapping adds robustness to the process both in the ability to adopt genetic operators used during the evolutionary process on the sub-symbolic representation and the transcription of well-formed executable programs from the representation.

The goal of the grammatical evolution algorithm is to adapt an executable program to a problem-specific objective function. This is achieved through an iterative process with surrogates of evolutionary mechanisms such as descent with variation, genetic mutation and recombination, genetic transcription and gene expression. A population of programs is expanded in subsymbolic form as variable-length binary strings and mapped to symbolic and well-structured form as grammar without context for execution.

A grammar is defined in Backus Normal Form (BNF), which is a contextless grammar expressed as a series of production rules comprising terminals and non-terminals. A variable length binary string representation is used for the optimization process. Bits are read from the genome of candidate solutions in blocks of 8 called codons and decoded into an integer (between 0 and 2 ^ 8 - 1).

If the end of the binary string is reached while reading integers, the reading process loops back to the beginning of the string, creating a circular genome. Integers are mapped to expressions in the BNF until a complete syntactically correct expression is formed. This may not use an entire genome of solutions, or use the decoded genome more than once given its circular nature.

The grammatical evolution was designed to optimize the programs (such as the equations math) for specific cost functions. The classical genetic operators used by thegenetic algorithm can be used in the grammatical evolution algorithm, such as point mutations and one-point crossover. Additional genetic operators can be used with variable length representations such as codon segments, duplication (append to end), number of randomly selected codons, and deletion.

grammatical evolution algorithm