Package ec.gp.build

# Class PTC2

java.lang.Object
ec.gp.GPNodeBuilder
ec.gp.build.PTC2

All Implemented Interfaces:
  `Prototype`, `Setup`, `Serializable`, `Cloneable`

public class PTC2 extends GPNodeBuilder
PTC2 implements the "Strongly-typed Probabilistic Tree Creation 2 (PTC2)" algorithm described in

Luke, Sean. 2000. Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat. Ph.D. Dissertation, Department of Computer Science, University of Maryland, College Park, Maryland.

...and also in

Luke, Sean. 2000. Two fast tree-creation algorithms for genetic programming. In IEEE Transactions on Evolutionary Computation 4:3 (September 2000), 274-283. IEEE.

Both can be found at http://people.cs.gmu.edu/~sean/papers/

PTC2 requires that your function set to implement PTCFunctionSetForm. The provided function set, PTCFunctionSet, does exactly this.

The Strongly-typed PTC2 algorithm roughly works as follows: the user provides a requested tree size, and PTC2 attempts to build a tree of that size or that size plus the maximum arity of a nonterminal in the function set. PTC2 works roughly like this:

1. If the tree size requested is 1, pick a random terminal and return it.
2. Else pick a random nonterminal as the root and put each of its unfilled child positions into the queue Q.
3. Loop until the size of Q, plus the size of the nodes in the tree so far, equals or exceeds the requested tree size:
   1. Remove a random position from Q.
   2. Fill the position with a random nonterminal n.
   3. Put each of n's unfilled child positions into Q.
4. For each position in Q, fill the position with a randomly-chosen terminal.

Generally speaking, PTC2 picks a random position in the horizon of the tree (unfiled child node positions), fills it with a nonterminal, thus extending the horizon, and repeats this until the number of nodes (nonterminals) in the tree, plus the number of unfilled node positions, is >= the requested tree size. Then the remaining horizon is filled with terminals.

The user-provided requested tree size is either provided directly to the PTC2 algorithm, or if the size is NOSIZEGIVEN, then PTC2 will pick one at random from the GPNodeBuilder probability distribution system (using either max-depth and min-depth, or using num-sizes).

PTC2 also has provisions for picking nonterminals with a certain probability over other nonterminals of the same return type (and terminals over other terminals likewise), hence its name. To change the probability of picking various terminals or nonterminals, you modify your PTCFunctionSetForm function set.

PTC2 further has a maximum depth, which you should set to some fairly big value. If your maximum depth is small enough that PTC2 often creates trees which bump up against it, then PTC2 will only generate terminals at that depth position. If the depth is *really* small, it's possible that this means PTC2 will generate trees smaller than you had requested.

Parameters

base.`max-depth` int >= 1 | maximum allowable tree depth (usually a big value)

Default Base
gp.build.ptc2

See Also:
  - Serialized Form

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `int`
  `maxDepth`
  The largest maximum tree depth GROW can specify -- should be big.
  `static final int`
  `MIN_QUEUE_SIZE`
  `static final String`
  `P_MAXDEPTH`
  `static final String`
  `P_PTC2`

  ### Fields inherited from class ec.gp.GPNodeBuilder

  `CHECK_BOUNDARY, maxSize, minSize, NOSIZEGIVEN, P_MAXSIZE, P_MINSIZE, P_NUMSIZES, P_SIZE, sizeDistribution`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `PTC2()`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Parameter`
  `defaultBase()`
  Returns the default base for this prototype.
  `GPNode`
  `newRootedTree(EvolutionState state, GPType type, int thread, GPNodeParent parent, GPFunctionSet set, int argposition, int requestedSize)`
  `void`
  `setup(EvolutionState state, Parameter base)`
  Sets up the object by reading it from the parameters stored in state, built off of the parameter base base.

  ### Methods inherited from class ec.gp.GPNodeBuilder

  `canPick, clone, errorAboutNoNodeWithType, pickSize, warnAboutNonterminal, warnAboutNonTerminalWithType, warnAboutNoTerminalWithType`

  ### Methods inherited from class java.lang.Object

  `equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Field Details

  - ### P_PTC2

    public static final String P_PTC2
    See Also:
      - Constant Field Values

  - ### P_MAXDEPTH

    public static final String P_MAXDEPTH
    See Also:
      - Constant Field Values

  - ### maxDepth

    public int maxDepth
    The largest maximum tree depth GROW can specify -- should be big.

  - ### MIN_QUEUE_SIZE

    public static final int MIN_QUEUE_SIZE
    See Also:
      - Constant Field Values

- ## Constructor Details

  - ### PTC2

    public PTC2()

- ## Method Details

  - ### defaultBase

    public Parameter defaultBase()
    Description copied from interface: `Prototype`
    Returns the default base for this prototype. This should generally be implemented by building off of the static base() method on the DefaultsForm object for the prototype's package. This should be callable during setup(...).

  - ### setup

    public void setup(EvolutionState state, Parameter base)
    Description copied from interface: `Prototype`
    Sets up the object by reading it from the parameters stored in state, built off of the parameter base base. If an ancestor implements this method, be sure to call super.setup(state,base); before you do anything else.

    For prototypes, setup(...) is typically called once for the prototype instance; cloned instances do not receive the setup(...) call. setup(...) may be called more than once; the only guarantee is that it will get called at least once on an instance or some "parent" object from which it was ultimately cloned.

    Specified by:
      `setup` in interface `Prototype`
    Specified by:
      `setup` in interface `Setup`
    Overrides:
      `setup` in class `GPNodeBuilder`

  - ### newRootedTree

    public GPNode newRootedTree(EvolutionState state, GPType type, int thread, GPNodeParent parent, GPFunctionSet set, int argposition, int requestedSize)
    Specified by:
      `newRootedTree` in class `GPNodeBuilder`