Grammar

A grammar is a set of rules that describe the syntax of sentences and expressions in a language. While grammars were originally invented for studying natural languages, they are extensively used in computer science for describing programming languages.

<sentence> ::= <subject> <verb> <object>. | <subject> <verb>.           (1.a), (1.b)
<subject>  ::= I | You | They                                           (2.a), (2.b), (2.c)
<verb>     ::= read | write | check                                     (3.a), (3.b), (3.c)
<object>   ::= books | stories | academic papers                        (4.a), (4.b), (4.c)

Evolutionary optimisation

Evolutionary optimisation algorithms are a class of optimisation techniques inspired by natural evolution. They are used in cases where:

• The solution to the problem can be represented by a certain structure. For example, the solution is an array of binary variables, or integer numbers.
  • Typically the array size is fixed and each unique value arrangement is considered a candidate solution.
  • Using biological terminology, this structure is referred to as the chromosome or genotype.
• There exist a cost function which can quickly return the cost or fitness of any candidate solution.
• Solving the problem using gradient descent techniques is hard or impossible, because the cost function is non-smooth, or has multiple local optimas, or is simply discrete, such as the travelling salesman problem (or in hindsight, a program generated by grammars).

It most be noted that the stochastic nature of evolutionary algorithms does not guarantee the optimal solution, since most practical problems involve very large search spaces, and it is often not computationally feasible to search the whole space.

The oldest and simplest of these algorithms is the genetic algorithm (GA), which optimises a vector of binary variables. In this vignette, when referring to GA, we refer to an extended GA which handles integers numbers.

For an in depth introduction, readers are referred to Wikipedia

Applications of grammatical evolution

Any application which needs a program definable by grammar, is creatable in GE. Using a grammar allows integration of domain knowledge and a custom program syntax, which adds flexibility and precision to GE compared to other techniques such as GP.

Applications of GE include computational finance, music, and robotic control, among others. See http://www.grammatical-evolution.org/pubs.html for a collection of publications in this area.

Rediscovery of Kepler’s law by symbolic regression

Symbolic regression is the process of discovering a function, in symbolic form, which fits a given set of data. Evolutionary algorithms such as GP and GE are commonly used to solve Symbolic Regression problems. For more information, visit http://www.symbolicregression.com/.

Rediscovery of Kepler’s law has been used as a benchmark for symbolic regression (Koza 1992; Ferreira 2006; Langley, Simon, and Bradshaw 1987). Here, the goal is to find a relationship between orbital periods and distances of solar system planets from the sun. The distance and period data, normalised to Earth, are as follows:

Kepler’s third law states: \(period^2 = constant \times distance^3\)

<expr>     ::= <expr><op><expr> | <sub-expr>                         (1.a), (1.b)
<sub-expr> ::= <func>(<var>) | <var> | <var>^<n>                     (2.a), (2.b), (2.c)
<func>     ::= log | sqrt | sin | cos                                (3.a), (3.b), (3.c), (3.d)
<op>       ::= + | - | x                                             (4.a), (4.b), (4.c)
<var>      ::= distance | distance^<n> | <n>                         (5.a), (5.b), (5.c)
<n>        ::= 1 | 2 | 3 | 4                                         (6.a), (6.b), (6.c), (6.d)

library("gramEvol")

ruleDef <- list(expr  = grule(op(expr, expr), func(expr), var),
                func  = grule(sin, cos, log, sqrt),
                op    = grule(`+`, `-`, `*`),
                var   = grule(distance, distance^n, n),
                n     = grule(1, 2, 3, 4))

grammarDef <- CreateGrammar(ruleDef)

print(grammarDef)

## <expr> ::= <op>(<expr>, <expr>) | <func>(<expr>) | <var>
## <func> ::= `sin` | `cos` | `log` | `sqrt`
## <op>   ::= `+` | `-` | `*`
## <var>  ::= distance | distance^<n> | <n>
## <n>    ::= 1 | 2 | 3 | 4

ruleDef <- list(expr  = gsrule("<expr><op><expr>", "<func>(<expr>)", "<var>"),
                func  = gsrule("sin", "cos", "log", "sqrt"),
                op    = gsrule("+", "-", "*"),
                var   = grule(distance, distance^n, n),
                n     = grule(1, 2, 3, 4))

CreateGrammar(ruleDef)

## <expr> ::= <expr><op><expr> | <func>(<expr>) | <var>
## <func> ::= sin | cos | log | sqrt
## <op>   ::= + | - | *
## <var>  ::= distance | distance^<n> | <n>
## <n>    ::= 1 | 2 | 3 | 4

planets <- c("Venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus")
distance <- c(0.72, 1.00, 1.52, 5.20, 9.53, 19.10)
period <- c(0.61, 1.00, 1.84, 11.90, 29.40, 83.50)

SymRegFitFunc <- function(expr) {
  result <- eval(expr)

  if (any(is.nan(result)))
    return(Inf)

  return (mean(log(1 + abs(period - result))))
}

Evolving the grammar

GrammaticalEvolution can now be run. All of the parameters are determined automatically. To avoid wasting time, and as the best possible outcome and its error are known (because we know the answer), a terminationCost is computed and set to terminate GE when the Kepler’s equation is found.

ge <- GrammaticalEvolution(grammarDef, SymRegFitFunc,
                           terminationCost = 0.021)
ge

## Grammatical Evolution Search Results:
##   No. Generations:  11 
##   Best Expression:  sqrt(distance^3) 
##   Best Cost:        0.0201895728693592

Now that the result is found, it can be used in production. Here we only use it in a simple comparison:

best.expression <- ge$best$expression

data.frame(distance, period, Kepler = sqrt(distance^3),
           GE = eval(best.expression))

##   distance period     Kepler         GE
## 1     0.72   0.61  0.6109403  0.6109403
## 2     1.00   1.00  1.0000000  1.0000000
## 3     1.52   1.84  1.8739819  1.8739819
## 4     5.20  11.90 11.8578244 11.8578244
## 5     9.53  29.40 29.4197753 29.4197753
## 6    19.10  83.50 83.4737743 83.4737743

customMonitorFunc <- function(results){
  cat("-------------------\n")
  print(results)
}

ge <- GrammaticalEvolution(grammarDef, SymRegFitFunc,
                           terminationCost = 0.021,
                           monitorFunc = customMonitorFunc)

ge <- GrammaticalEvolution(grammarDef, SymRegFitFunc,
                           terminationCost = 0.021,
                           monitorFunc = print)

## Grammatical Evolution Search Results:
## No. Generations:  1
## Best Expression:  distance
## Best Cost:        1.60700784338907
## Grammatical Evolution Search Results:
## No. Generations:  2
## Best Expression:  distance
## Best Cost:        1.60700784338907

## Grammatical Evolution Search Results:
## No. Generations:  9
## Best Expression:  distance + distance
## Best Cost:        1.54428158317392
## Grammatical Evolution Search Results:
## No. Generations:  10
## Best Expression:  1 - distance + (cos(distance) - 1) * sin(distance^2) + distance + (log(distance) + distance + (cos(distance) - 1) * sin(distance^2) + distance)
## Best Cost:        1.4186428597461
## Grammatical Evolution Search Results:
## No. Generations:  11
## Best Expression:  sqrt(distance^3)
## Best Cost:        0.0201895728693592

Discovering Regular Expressions

A regular expressions (RE) is a string that determines a character pattern. REs are more expressive and precise in determining sub-string matches compared to wildcards, and are widely used in many string pattern matching tasks, such as searching through log files or parsing a program’s output.

Creating a regular expressions requires careful assembly of symbols and operators to match the desired pattern. While this is usually performed by an expert programmer, it is possible to use evolutionary optimisation techniques to infer a RE from examples (Bartoli et al. 2012).

In this example, we demonstrate how gramEvol can be used to learn REs.

re <- "^(\\+|-)?[[:digit:]]+(\\.[[:digit:]]+)?$"

grepl(re, "+1.1")

## [1] TRUE

grepl(re, "1+1")

## [1] FALSE

matching <- c("1", "11.1", "1.11", "+11", "-11", "-11.1")
non.matching <- c("a", "1.", "1..1", "-.1", "-", "1-", "1.-1",
                  ".-1", "1.-", "1.1.1", "", ".", "1.1-", "11-11")

re.score <- function(re) {
  score <- sum(sapply(matching, function(x) grepl(re, x))) +
           sum(sapply(non.matching, function(x)  !grepl(re, x)))
  return (length(matching) + length(non.matching) - score)
}

fitfunc <- function(expr) re.score(eval(expr))

library("rex")
library("gramEvol")
grammarDef <- CreateGrammar(list(
  re    = grule(rex(start, rules, end)),
  rules = grule(rule, .(rule, rules)),
  rule  = grule(numbers, ".", or("+", "-"), maybe(rules))))
grammarDef

## <re>    ::= rex(start, <rules>, end)
## <rules> ::= <rule> | <rule>, <rules>
## <rule>  ::= numbers | "." | or("+", "-") | maybe(<rules>)

GrammaticalExhaustiveSearch(grammarDef, fitfunc, max.depth = 7, terminationCost = 0)

## GE Search Results:
## Expressions Tested: 6577
## Best Chromosome:    0 1 3 0 2 1 3 1 0 0 1 1 0 0 3 0 0
## Best Expression:    rex(start, maybe(or("+", "-")), maybe(numbers, "."), numbers, maybe(numbers), end)
## Best Cost:          0

system.time(GrammaticalExhaustiveSearch(grammarDef, fitfunc,
                                        max.depth = 7, terminationCost = 0))

##    user  system elapsed
## 380.469  17.022 392.637

Manual mapping

To map a numeric sequence to an expression manually, use GrammarMap:

GrammarMap(c(0, 1, 0, 0, 1, 1, 0, 0), grammarDef)

## (c1 * v1) - (c1 * v1)

The sequence is zero-indexed (the first rule is zero). To see the step by step mapping, use the verbose parameter option:

GrammarMap(c(0, 1, 0, 0, 1, 1, 0, 0), grammarDef, verbose = TRUE)

##  Step Codon Symbol Rule                 Result                    
##  0                 starting:            <expr>                    
##  1    0     <expr> (<expr>)<op>(<expr>) (<expr>)<op>(<expr>)      
##  2    1     <expr> <coef>*<var>         (<coef>*<var>)<op>(<expr>)
##  3    0     <coef> c1                   (c1*<var>)<op>(<expr>)    
##  4    0     <var>  v1                   (c1*v1)<op>(<expr>)       
##  5    1     <op>   -                    (c1*v1)-(<expr>)          
##  6    1     <expr> <coef>*<var>         (c1*v1)-(<coef>*<var>)    
##  7    0     <coef> c1                   (c1*v1)-(c1*<var>)        
##  8    0     <var>  v1                   (c1*v1)-(c1*v1)           
## Valid Expression Found

## (c1 * v1) - (c1 * v1)

If the length of a sequence is insufficient for the mapping process, such that a few non-terminal elements still remain in the resulting expression, a wrapping of up to wrappings is performed. For example:

GrammarMap(c(0, 1, 0, 0, 1, 1), grammarDef, verbose = TRUE)

##  Step Codon Symbol Rule                 Result                    
##  0                 starting:            <expr>                    
##  1    0     <expr> (<expr>)<op>(<expr>) (<expr>)<op>(<expr>)      
##  2    1     <expr> <coef>*<var>         (<coef>*<var>)<op>(<expr>)
##  3    0     <coef> c1                   (c1*<var>)<op>(<expr>)    
##  4    0     <var>  v1                   (c1*v1)<op>(<expr>)       
##  5    1     <op>   -                    (c1*v1)-(<expr>)          
##  6    1     <expr> <coef>*<var>         (c1*v1)-(<coef>*<var>)    
## Non-terminal expression
## Wrapping string to position 0
##  Step Codon Symbol Rule Result            
##  7    0     <coef> c1   (c1*v1)-(c1*<var>)
##  8    1     <var>  v2   (c1*v1)-(c1*v2)   
##  9    0     <var>  v2   (c1*v1)-(c1*v2)   
## Valid Expression Found

## (c1 * v1) - (c1 * v2)

Examining a grammar

gramEvol offers several functions to examine grammar definitions.

summary reports a summary of what grammar presents:

summary(grammarDef)

## Start Symbol:                <expr> 
## Is Recursive:                TRUE 
## Tree Depth:                  Limited to 4 
## Maximum Rule Choices:        4 
## Maximum Sequence Length:     18 
## Maximum Sequence Variation:  2 2 2 2 4 4 2 2 2 4 2 2 2 2 4 2 2 2 
## No. of Unique Expressions:   18500

Many of these properties are available through individual functions:

GetGrammarDepth computes the depth of grammar tree. The parameter max.depth is used to limit recursion in cyclic grammars. For example, this grammar is cyclic because of rule <expr> ::= <expr><op><expr>, i.e., replacing a <expr> with other <expr>s. By default GetGrammarDepth limits recursion to the number of symbols defined in the grammar:

GetGrammarDepth(grammarDef)

## [1] 4

GetGrammarDepth(grammarDef, max.depth = 10)

## [1] 10

For grammars without recursion, the value returned by GetGrammarDepth is the actual depth of the tree:

grammarDef2 <- CreateGrammar(list(
  expr    = gsrule("(<subexpr>)<op>(<subexpr>)"),
  subexpr = gsrule("<coef>*<var>"),
  op      = gsrule("+", "-", "*", "/"),
  coef    = gsrule("c1", "c2"),
  var     = gsrule("v1", "v2")))

GetGrammarDepth(grammarDef2)

## [1] 3

GetGrammarDepth also supports computing the depth from any symbol:

GetGrammarDepth(grammarDef2, startSymb = "<subexpr>")

## [1] 2

GetGrammarDepth(grammarDef2, startSymb = "<coef>")

## [1] 1

GetGrammarMaxRuleSize returns the maximum number of production rules per symbol. Here, <op> has the highest number of production rules:

GetGrammarMaxRuleSize(grammarDef)

## [1] 4

GetGrammarNumOfExpressions returns the number of possible expressions existing in the grammar space. This function also uses the optional argument max.depth to limit the number of recursions and startSymb to set the starting symbol:

GetGrammarNumOfExpressions(grammarDef)

## [1] 18500

GetGrammarNumOfExpressions(grammarDef, max.depth = 2)

## [1] 4

GetGrammarNumOfExpressions(grammarDef, startSymb = "<coef>")

## [1] 2

Here, the only expressions with depth of 2 or less are constructed if rule (\(\times\)) is applied first, creating 4 expressions (i.e., \(c_1 \times v_1\), \(c_1 \times v_2\), \(c_2 \times v_1\) and \(c_2 \times v_2\)). Also if is chosen as the starting symbol, the expressions are limited to \(c_1\) and \(c_2\).

GetGrammarMaxSequenceLen computes the length of integer sequence required for iterating through the grammar space without wrapping. As with the previous functions, max.depth is set to the number of symbols defined in the grammar.

GetGrammarMaxSequenceLen(grammarDef)

## [1] 18

GetGrammarMaxSequenceLen(grammarDef, max.depth = 3)

## [1] 8

GetGrammarMaxSequenceLen(grammarDef2, startSymb = "<subexpr>")

## [1] 3

Grammatical evolution options

GrammaticalEvolution is defined as follows:

GrammaticalEvolution(grammarDef, evalFunc,
                     numExpr = 1,
                     max.depth = GrammarGetDepth(grammarDef),
                     startSymb = GrammarStartSymbol(grammarDef),
                     seqLen = GrammarMaxSequenceLen(grammarDef, max.depth, startSymb),
                     wrappings = 3,
                     suggestions = NULL,
                     optimizer = c("auto", "es", "ga"),
                     popSize = 8, newPerGen = "auto", elitism = 2,
                     mutationChance = NA,
                     iterations = 1000, terminationCost = NA,
                     monitorFunc = NULL,
                     plapply = lapply, ...)

max.depth and startSymb determine recursive grammar limitations, similar to what was explained in the previous section.

The rest of the parameters are the evolutionary optimisation options:

• GrammaticalEvolution evolves a population of popSize chromosomes for a number of iterations.
• if optimizer is set to “auto”, using the information obtained about the grammar (e.g., number of possibles expressions and maximum sequence length), GrammaticalEvolution uses a heuristic algorithm based on the work by Deb and Agrawal (1999) to automatically determine a suitable value for popSize (i.e., the population size) iterations (i.e., the number of iterations) parameters.
• The ordinary cross-over operator of GA is considered destructive when homologous production rules are not aligned, such as for cyclic grammars (O’Neill et al. 2003). Consequently, GrammaticalEvolution automatically changes cross-over parameters depending on the grammar to improve optimisation results. A user can turn this off by manually setting the optimizer.
• The first generation is made from the suggestions in form of integer chromosomes, and randomly generated individuals.
• Each integer chromosome is mapped using the grammar, and its fitness is assessed by calling evalFunc.
• For each generation, the top \(n\) scoring chromosomes where \(n =\)elitism are directly added to the next generation’s population. The rest of the population is created using cross-over of chromosomes selected with roulette selection operator.
• Each chromosome may mutate by a probability of mutationChance.
• After reaching a termination criteria, e.g., the maximum number of iterations or the desired terminationCost, the algorithm stops and returns the best expression found so far.
• GrammaticalEvolution supports multi-gene operations, generating more than one expression per chromosome using the numExpr parameter.
• The number of integer codons in the chromosome is determined by seqLen times numExpr (i.e., the sequence length per expression, times the number of expressions).
• monitorFunc is then called with information and statistics about the current status of the population.
• plapply is used for parallel processing.
• GrammaticalEvolution automatically filters non-terminal expressions (i.e., expressions that don’t yield a terminal expression even after times of wrappings). Therefore the end-user does not need to worry about them while using gramEvol.

Parallel processing option

Processing expressions and computing their fitness is often computationally expensive. The gramEvol package can utilise parallel processing facilities in R to improve its performance. This is done through the plapply argument of GrammaticalEvolution function. By default, lapply function is used to evaluate all individuals in the population.

Multi-core systems simply benefit from using mclapply from package parallel, which is a drop-in replacement for lapply on POSIX compatible systems. The following code optimises evalFunc on 4 cores:

library("parallel")
options(mc.cores = 4)
ge <- GrammaticalEvolution(grammarDef, evalFunc,
                           plapply = mclapply)

To run gramEvol on a cluster, clusterapply functions can be used instead. The gramEvol package must be first installed on all machines and the fitness function and its data dependencies exported before GE is called. The following example demonstrates a four-process cluster running on the local machine:

library("parallel")
cl <- makeCluster(type = "PSOCK", c("127.0.0.1",
                                    "127.0.0.1",
                                    "127.0.0.1",
                                    "127.0.0.1"))
clusterEvalQ(cl, library("gramEvol"))
clusterExport(cl, c("evalFunc"))
ge <- GrammaticalEvolution(grammarDef, evalFunc,
                           plapply = function(...) parLapply(cl, ...))
stopCluster(cl)

It must be noticed that in any problem, the speed-up achieved depends on the overhead of communication compared with the fitness functions’ computational complexity.

Generating more than one expression

gramEvol supports generation and evaluation of multiple expressions:

• numExpr in GrammaticalEvolution is used to pass a list of more than one R expression
• EvalExpressions offers a simpler interface for evaluating multiple expressions.

The following example show cases EvalExpressions: It uses a dataset for variables defined in the grammar, and evaluates a GE expression object along with a string:

df <- data.frame(c1 = c(1, 2),
                 c2 = c(2, 3),
                 v1 = c(3, 4),
                 v2 = c(4, 5))

quad.expr <- expression(c1 * v1, c1 * v2, c2 * v1, c2 * v2)
EvalExpressions(quad.expr, envir = df)

##   expr1 expr2 expr3 expr4
## 1     3     4     6     8
## 2     8    10    12    15

This is useful in applications when more than one expression is required, or the collective power of several simple expressions outperform a single complex program. For example de Silva et al. (2013) (PDF) used GE for electricity load forecasting; instead of using a complex machine learning algorithm, pools of string expressions were generated in a guided manner and were used as features in a simpler machine learning algorithm to obtain better results.

The idea of generating using GE is further explored in gramEvol’s paper in the Journal of Statistical Software (2016).

Alternative optimisation algorithms

gramEvol also provides a random search and an exhaustive search. Their syntax is similar to the GrammaticalEvolution:

result1 <- GrammaticalExhaustiveSearch(grammarDef, evalFunc)
result2 <- GrammaticalRandomSearch(grammarDef, evalFunc)

Using vectors as rules

gvrule allows members of a vector to be used as individual rules. For example,

gvrule(1:5)

## Rule 0: 1L
## Rule 1: 2L
## Rule 2: 3L
## Rule 3: 4L
## Rule 4: 5L

which is equal to

grule(1,2,3,4,5)

## Rule 0: 1
## Rule 1: 2
## Rule 2: 3
## Rule 3: 4
## Rule 4: 5

Without gvrule, 1:5 would have been interpreted as a single rule:

grule(1:5)

## Rule 0: 1:5

Using commas and assignments in rules

There are two ways to use commas and assignments in gramEvol rules:

1. Rules are defined in character string form using gsrule.
2. Rules are wrapped in .() and defined using grule.

For example, consider the following rules:

<assignment> ::= A = B | A = C
<comma>      ::= A, B  | B, C

Their definition using gramEvol is as follows:

CreateGrammar(list(assignment = gsrule("A = B", "A = C"),
                   comma      = gsrule("A, B", "B, C")))

## <assignment> ::= A = B | A = C
## <comma>      ::= A, B | B, C

or

CreateGrammar(list(assignment = grule(.(A = B), .(A = C)),
                   comma      = grule(.(A, B), .(B, C))))

## <assignment> ::= A = B | A = C
## <comma>      ::= A, B | B, C