Class: Wallace::Koza::Builder::GrowBuilder

Inherits:
Wallace::Koza::Builder show all
Defined in:
lib/modules/koza/builder/grow_builder.rb

Overview

The Grow builder constructs Koza trees according to a slight variant of Koza’s GROW method. Unlike Koza’s original GROW method, this GROW method allows single node trees to be constructed.

A random integer d is selected as the depth of the tree, between the minimum and maximum depth limits inclusively. A tree of up to depth d is then generated. At each stage we determine whether a node should be terminal or not by checking if the maximum depth has been reached, or some random number falls within the bounds of probability that a terminal should be selected.

Instance Attribute Summary collapse

Attributes inherited from Wallace::Koza::Builder

#depth_limits, #non_terminals, #terminals

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Wallace::Koza::Builder

#prepare

Constructor Details

#initialize(probability_terminal) ⇒ GrowBuilder

Constructs a new GrowBuilder.

Parameters:

  • probability_terminal, the probability that a terminal node will be built when using the GROW method.



69
70
71
 
# File 'lib/modules/koza/builder/grow_builder.rb', line 69

def initialize(probability_terminal)
  @probability_terminal = probability_terminal
end

Instance Attribute Details

#probability_terminal ⇒ Object

The probability that a terminal will be selected when constructing a node using the GROW method.



13
14
15
 
# File 'lib/modules/koza/builder/grow_builder.rb', line 13

def probability_terminal
  @probability_terminal
end

Class Method Details

.grow_subtree(terminals, non_terminals, max_depth, probability_terminal, opts = {}) ⇒ Object

Builds a full subtree of a given maximum depth using a variant of Koza’s GROW method (where single element sub-trees are acceptable).

Parameters:

  • probability_terminal, the probability that a terminal node will be created at each stage.

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the subtree.

Returns: The root node of the built sub-tree.



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/modules/koza/builder/grow_builder.rb', line 25

def self.grow_subtree(terminals, non_terminals, max_depth, probability_terminal, opts = {})

  opts[:random] ||= Random.new

  # If the maximum depth of the sub-tree is zero then we simply return a node with a value
  # sampled from the set of terminals. If the maximum depth of the sub-tree is greater than one
  # then we check if the first node is a terminal and if so, we also return a single terminal
  # node.
  if max_depth == 0 or opts[:random].rand <= probability_terminal
    return Wallace::Koza::KozaNode.new(terminals.sample(random: opts[:random]))
  end

  # Construct the children of each node in the queue until there are no nodes
  # left to process. We decide whether each child is terminal or non-terminal according to the
  # associated probability of a terminal being selected. If the maximum depth has been reached then
  # we force the child to be a terminal.
  root = Wallace::Koza::KozaNode.new(non_terminals.sample(random: opts[:random]), depth: 0)
  queue = [root]
  until queue.empty?

    parent = queue.shift
    parent.children = Array.new(parent.arity) do

      if opts[:random].rand <= probability_terminal or (parent.depth + 1) == max_depth
        value = terminals.sample(random: opts[:random])
      else
        value = non_terminals.sample(random: opts[:random])
      end

      node = Wallace::Koza::KozaNode.new(value, parent: parent, depth: parent.depth + 1)
      queue << node unless node.terminal?
      node

    end unless parent.terminal?

  end
  return root

end

Instance Method Details

#build_subtree(max_depth, opts = {}) ⇒ Object

Builds a full subtree of a given maximum depth.

Parameters:

  • max_depth, the maximum depth of the sub-tree.

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the subtree.

Returns: The root node of the built sub-tree.

See FullBuilder.full_subtree



99
100
101
 
# File 'lib/modules/koza/builder/grow_builder.rb', line 99

def build_subtree(max_depth, opts = {})
  self.class.grow_subtree(@terminals, @non_terminals, max_depth, @probability_terminal, opts)
end

#build_tree(opts = {}) ⇒ Object

Selects a random integer d, where d is between the minimum and maximum tree depth inclusively, and creates a tree of up to depth d.

Parameters:

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the tree.

Returns: The built tree.



82
83
84
85
 
# File 'lib/modules/koza/builder/grow_builder.rb', line 82

def build_tree(opts = {})
  opts[:random] ||= Random.new
  Wallace::Koza::KozaTree.new(build_subtree(opts[:random].rand(@depth_limits), random: opts[:random]))
end