GrammaticalRandomSearch: Random Search

In fnoorian/gramEvol: Grammatical Evolution for R

Random Search

Description

Random Search within context-free grammar.

Usage

GrammaticalRandomSearch(grammar, evalFunc,
                        max.depth = GrammarGetDepth(grammar),
                        startSymb = GrammarStartSymbol(grammar),
                        wrappings = 3,
                        iterations = 1000, 
                        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.
wrappings	The number of times the function is allowed to wrap around inputString if non-terminal symbols are still remaining.
iterations	Number of random expressions to test.
terminationCost	Target cost. If an expression with this cost or less is found, the algorithm terminates.
monitorFunc	A function that is called at each generation. It can be used to monitor evolution of population.

Details

GrammaticalRandomSearch performs a random search within expressions that can be generated by the grammar, to find the expression that minimises evalFunc.

The search terminates when either the predetermined number of iterations are reached, 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.
population	A matrix of sequences that were tested.
populationCost	Numeric value of cost of sequences that were tested.

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
  }
}

# search and terminate after getting to cost = 0
res <- GrammaticalRandomSearch(grammarDef, evalFunc, terminationCost = 0)

print(res)

fnoorian/gramEvol documentation built on July 5, 2023, 6:38 p.m.