GrammaticalRandomSearch {gramEvol}

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)