GrammaticalExhaustiveSearch: Exhaustive Search

In gramEvol: Grammatical Evolution for R

Description

Exhaustive Search within context-free grammar.

Usage

GrammaticalExhaustiveSearch(grammar, evalFunc,
                max.depth = GrammarGetDepth(grammar),
                startSymb = GrammarStartSymbol(grammar),
                max.len = GrammarMaxSequenceLen(grammar, max.depth, startSymb),
                wrappings = 3,
                terminationCost = NA,
                monitorFunc = NULL)

Arguments

grammar	A grammar object.
evalFunc	The evaluation function, taking an expression as its input and returning the cost (i.e., the score) of the expression.
max.depth	Maximum depth of recursion, in case of a cyclic grammar. By default it is limited to the number of production rules in the grammar.
startSymb	The symbol where the generation of a new expression should start.
max.len	Maximum length of the sequences to search. By default it is determined by max.depth.
wrappings	The number of times the function is allowed to wrap around inputString if non-terminal symbols are still remaining.
terminationCost	Target cost. If an expression with this cost or less is found, the algorithm terminates.
monitorFunc	A function that is called at each iteration. It can be used to monitor the search.

Details

GrammaticalExhaustiveSearch performs an exhaustive search, iterating through all possible expressions that can be generated by the grammar, to find the expression that minimises evalFunc.

The search terminates when all possible expressions are exhausted, or when an expression with a cost less than terminationCost is discovered.

If a monitorFunc is given, it is called for each expression, and it receives a list similar to the GrammaticalExhaustiveSearch's return value with the information availabe for that expression.

Value

bestExpression	The Best expresssion.
bestSequence	Best expresssion's generating sequence.
bestCost	Best expresssion's cost.
numExpr	Number of evaluated expressions.

In addition, the monitorFunc receives the following additional slots:

currentExpression	The current expresssion.
currentSequence	Current expresssion's generating sequence.
currentCost	Current expresssion's cost.

See Also

GrammarGetNextSequence, GrammaticalEvolution

Examples

library("gramEvol")

ruleDef <- list(expr = gsrule("<var><op><var>"),
                op   = gsrule("+", "-", "*"),
                var  = gsrule("A", "B"))

# Create a grammar object
grammarDef <- CreateGrammar(ruleDef)         


# use exhaustive search to find the sequence for creating "B - A"
evalFunc <- function(expr) {
  if (as.character(expr) == "B - A") {
    return(0) # Minimum error
  } else {
    return(1) # maximum error
  }
}

res <- GrammaticalExhaustiveSearch(grammarDef, evalFunc, terminationCost = 0)

print(res)

gramEvol documentation built on July 18, 2020, 5:07 p.m.