Grammars

Defining grammars

The tutorial contains an example of how to create a grammar.

The examples folder in the repo also contain several examples of grammars, including examples for classification and regressions, program synthesis and string matching.

Using builtin grammar definitions

The geneticengine.grammars module contains various ready implementations of grammars popular in Genetic Programming:

Standard Genetic Programming
Literals
Regex
Basic Math
Coding
Letters

Probabilistic Grammars and Evolving Grammars

Genetic Engine supports Probabilistic grammars by assigning weights to classes. Weights can be added by extending classes directly with the simple @weight decorator, as is done in the pcfg_example.

class Root(ABC):
    pass

@weight(0.1)
class OptionA(R):
    " This option will be selected with 10% of probability "
    pass


@weight(0.9)
class OptionB(R):
    " This option will be selected with 90% of probability "
    pass

Alternatively, the user can also programmatically define the weigth of a given production, using prod.__dict__["__gengy__"]["weight"] (as is done in the classification_probabilisticGE).

Controlling the Depth of Individuals

For backwards compatibility with PonyGE2, another Grammar-Guided Genetic Programming Framework, GeneticEngine supports two modes of defining the depth of individuals.

Depth of the tree

grammar = extract_grammar([A, B], Root, expansion_depthing=False)

Using this method, the maximum depth of an individual is the depth of its tree representation.

Depth of the grammatical expansion

grammar = extract_grammar([A, B], Root, expansion_depthing=True)

We also support grammar-expansion depthing, as done in PonyGE2. In grammar-expansion depthing, the depth is increased each time a grammar production rule is expanded. For example, suppose you have the following grammar:

A       :== 0 | B
B       :== 1 | 2

A tree with a single node of value 0 will have a depth of 2, as the expansion is A -> 0, where node A has depth 1, and node 0 will have a depth of 2. A tree with a single node of value 1 (or 2) derives from the expansion A -> B -> 1 (or 2), and will thus have a depth of 3, even though it consists of only a single node.

On the difference of both approaches

In Genetic Engine we don’t keep track of the depth of nodes, but only of the distance to (the deepest) terminal and number of nodes (consultable by applying the gengy_distance_to_term and gengy_nodes methods to any tree node). When using grammar-expansion depthing, you can only read the distance to terminal and number of nodes of actual objects. Therefore, reading the distance to terminal of a tree with the single node 0 as introduced above, will not give you the distance to the terminal of the whole tree (which would be 2), but that of the node 0, which is 1. The algorithm works correctly, but keep this in mind at consultation.