How to apply Grammatical Evolution string to a solution

Question

I am learning Grammatical Evolution, but one thing that I can't seem to grasp is how to use the strings that are evolved from grammar into solving an actual problem. Is it converted into a neural network or converted into an equation, or something else? How does it receive inputs and print out outputs?

Answer 1

I've implemented grammatical evolution (GE) and a few other grammar-guided genetic programming algorithms in the package alogos. The docs contain examples of how these methods can be used to solve optimization problems from various domains.

The package allows to define search spaces with a context-free grammar in BNF or EBNF. A search goal can be defined with an objective function, which gets a candidate string of the grammar's language as input, and needs to return a numerical value as output that reflects its fitness.

Answer 2

Grammatical Evolution (GE) makes distinction between genotype and phenotype (genotype–phenotype distinction), which means an evolved genotype is not a solution by itself, but it maps to a solution.

Mutations and crossover are performed over genotypes, but to evaluate the fitness a genotype should be first transformed into a phenotype. In Grammatical Evolution this means generation of a string conforming to the chosen grammar. This solution string then should be executed, and the result of the execution evaluated to estimate the fitness of the solution.

How to actually execute the generated solution?

It highly depends on the implementation of a GE system.

If it generates solutions in some real programming language, they should be compiled and/or executed with the corresponding toolchain, ran with some test input, and the output evaluated to estimate the fitness.

If a GE system is able to execute a solution internally, no external toolchain is involved. It might be convenient to generate a syntax tree-like structure according to the grammar (instead of unstructured text), because it's quite easy to execute such a structure.

How to execute a syntax tree?

There exist an entire class of so called tree walk interpreters — not super performant, but reasonably simple in implementation. Usually such an interpreter first parses a source text and builds a syntax tree, then executes it; but in a GE system it is possible to directly generate a syntax tree, so no parsing is involved.

I can suggest "A tree-walk interpreter" chapter of a freely available book "Crafting interpreters" as a good example of constructing such an interpreter.