Individuals generation procedure

The generation of individuals uses a combination of 2 methods:

• the Full method: produces a tree of depth d

• the Grow method: produces a tree of depth between 1 and d inclusive

Full and Grow are 2 recursive methods. Here is an example for the Grow method (Full is more or less the same):

protected GPNode growNode(final EvolutionState state, final int current,
                          final int max, final GPType type, final int thread ,
                          final GPNodeParent parent, final int argposition, final GPFunctionSet set)
{
    boolean triedTerminals = false;

    // We make the difference between terminal and non-terminal nodes
    int t = type.type;
    GPNode[] terminals = set.terminals[t];
    GPNode[] nonterminals = set.nonterminals[t];
    GPNode[] nodes = set.nodes[t];          

    if (nodes.length == 0)
        errorAboutNoNodeWithType(type, state);   // total failure

    // pick a terminal when we're at max depth or if there are NO nonterminals
    if ((current+1 >= max) &&                     // Now pick if we're at max depth
        (triedTerminals = true) &&                // [first set triedTerminals]
        terminals.length != 0)                    // AND if there are available terminals
    {
        // Pick the node using a random int between 0 and terminals.length-1
        GPNode n = (GPNode)(terminals[state.random[thread].nextInt(terminals.length)].lightClone()); 
        n.resetNode(state,thread);  // give ERCs a chance to randomize
        n.argposition = (byte)argposition;
        n.parent = parent; // Set the parent pointer
        return n;
    }        
    else // else pick a random node
    {
        if (triedTerminals) warnAboutNoTerminalWithType(type, false, state); 
        // we tried terminals and we're here because there were none!
 
        GPNode n = (GPNode)(nodes[state.random[thread].nextInt(nodes.length)].lightClone());
        n.resetNode(state,thread);  // give ERCs a chance to randomize
        n.argposition = (byte)argposition;
        n.parent = parent;

        // Populate the node...

        // This is the part of the Strongly Typed GP. We get the type constraints for the children
        //and pass it recursively to the Grow method
        GPType[] childtypes = n.constraints(((GPInitializer)state.initializer)).childtypes;  
 												
        for(int x=0;x<childtypes.length;x++)
            n.children[x] = growNode(state,current+1,max,childtypes[x],thread,n,x,set);

        return n;
    }
}

The generation algorithm is called Ramp Half and Half. It assigns a 0.5 probability for each generation method. Here is how it works:

• define at the beginning minimum depth for a tree (minD), maximum depth for a tree (maxD) and grow method probability (growP, equals 0.5 in Ramp Half and Half, but user can change it)

• for each individual to be generated:

  • choose a value for d between minD and maxD
  • choose a random value p between 0 and 1
  • generate the tree using Full or Grow according to p (if p<growP use Full, if p>=growP use Grow)

• End when you reach the maximum number of individuals