Legacy:Genetic Programming/Nodes

First off, read the introduction on Genetic Programming, and go look at the animated tutorial at www.genetic-programming.com/gpanimatedtutorial.html or all of this is all going to be nonsense :)

OK, by now you should know that GP uses a tree structure of linked objects to do its 'thinking' these objects are either 'Terminals' (i.e. 'leaves' at the end of the tree branches which return either sensor input or constant values) or 'Functions' which take one or more values and return another.

In my implimentation all nodes take and return floats as arguments so it doesn't matter how much you mix things up, no node gets presented with data it can't cope with.

Here's a simple node that adds together its two inputs:

//-----------------------------------------------------------
// arithmetic addition function
//-----------------------------------------------------------
class GPFplus extends GPnode;
 
 
function float evaluate()
{
  return( children[0].evaluate() + children[1].evaluate());
}
 
function string makemytoken()
{
  return("+");
}
 
 
DefaultProperties
{
 childcount=2
}

It extends GPnode which is the base class of all the nodes and includes lots of baggage to be explained later, for now just notice that the nodes below it in the parse tree are referenced by the children[] array and that the evaluate method is called on these children in order to get the values that need to be added together. This is the basic magic, all the objects in the tree are linked together and control flows down the branches until something that actually returns a value is evaluated. Some nodes are conditional and branches get evaluated or not depending on conditions... in this way we can produce a program that actually varies its behavior according to conditions, unlike any of the simple examples in the tutorial linked to above which are more like equations than anything we'd call 'code'.

As an example here's evaluate for the 'less than' node:

function float evaluate()
{
  local float arg1,arg2;
  arg1=children[0].evaluate();
  arg2=children[1].evaluate();
  if(arg1<arg2) return(children[2].evaluate());
  else
    return(children[3].evaluate());
}

Notice how sometimes children[2] gets evaluated and other times it's children[3] that gets to see some action.

Now in order to get any of this to work we need a way of storing the tree so it can be passed around and manipulated, this is where makemytoken() comes in, its job is to return the string representation of that node... pretty simple here but nodes which hold values need something more... here's evaluate and makemytoken for the 'constant' terminal node:

var float val;
 
function float evaluate()
{
    return(val);
}
 
function string makemytoken()
{
  return("K"$val);
}

As you can see I use the character K to flag a constant and then append the value to is using uscripts really rather useful built in type conversions.

Enough specifics, I hope that conveys the gist, here's the core GPnode code in it's glory:

//-----------------------------------------------------------
// Genetic Programming parse tree node root class
//-----------------------------------------------------------
class GPnode extends Actor;
 
 
Var int Childcount;
var GPnode children[4], parent;
var int childnum, depth; // self = parent.chilren[childnum]
var string mytoken;
var actor mypawn;            // might not be always be a pawn, hence type = actor for now
var const string terminators, functions;
var const string alltypes;
 
 
function float evaluate()
{
  return(children[0].evaluate());
}

Variables and a very empty evaluate method.

Now more recursion: this is how the tree gets written out as a string: the node writes it's own token to the string then calls writetostring on its children, those children in turn get their children to write a token to the string and so on... somehow satisfyingly cool to someone like myself who's never been beyond a simple recursive factiorial function before :)

function WriteToString( out string genome )
{
 local int i;
 genome = genome$MakeMyToken();
 if(childcount == 0) return;
 else
  {
    for(i=0;i<childcount;i++)
     {
       children[i].WriteToString(genome);
     }
  }
}
 
function string makemytoken()
{
//log("makemytoken called on "$self);
// null token for base class, make this return the string that represents
// any subclass (mostly one char but constant terminators need to write out
// their value forinstance)
return("");
}

Notice also cunning use of an 'out' declaration there so all that needs to be done to create the genome string is simply call WriteToString(s) on the root node of the tree and as if by magic, S gets an encoded version of the object tree written to it.. by now I'm really starting to grock recursion properly and feel like I'm on a run, the elegence of these objects all describing themselves is appealing but in the background I can't help wondering if it all might fall apart somehow...

Doubts or not, this is how most of the functionality has shaped up, simply call a method on the root node and all else follows for various tree manipulation tasks.

Now having written this string we neeed a way of reading it back in and creating an object tree out of it... so let's go all recursive again and we have the imaginatively named:

Function ReadFromString( out string genome)
{
  local int i;
  local string char;
  local GPnode node;
  for ( i =0; i<childcount;i++)
  {
    // eat and analyse first (leftmost) char of string
 
    char = left(genome,1);
    genome = right(genome,len(genome)-1);
    node = addchild( char,i);
    node.ReadFromString(genome);
 }
}

So basically you start by spawning a gpnode as the root, feed it the string of gobbledegook generated by writetostring and it reads (and discards) the first character, spawns the appropriate node actor, makes that its first child and passes the rest of the string to it so it can make any children it might need in turn... and so it goes on down the tree.

Addchild is a big switch that takes care of spawning the right sort of node type according to the character token that has been read in:

function gpnode addchild(string childtype, int i)
{
  local class<actor>  childclass< SEMI >
  local gpnode node;
 
   switch(childtype)
   {
    // functions first
      case "+":
          childclass = class'GPFplus';
          break;
      case "-":
          childclass = class'GPFminus';
          break;
      case "*":
          childclass = class'GPFmultiply';
          break;
      case "%":
          childclass = class'GPFsafeDivide';
          break;
      case "<":
          childclass = class'GPFlessThan';
          break;
      case "Q":
          childclass = class'GPFSqrt';
          break;
      case "N":
          childclass = class'GPFMin';
          break;
      case "X":
          childclass = class'GPFMax';
          break;
      // then the terminators
      case "R":
          childclass = class'GPFrightTurn';
          break;
      case "L":
          childclass = class'GPFleftTurn';
          break;
      case "K":
          childclass = class'GPTconstant';
          break;
      case "A":
          childclass = class'GPTlookAhead';
          break;
      case "B":
          childclass = class'GPTlookAheadRight';
          break;
      case "C":
          childclass = class'GPTlookRight';
          break;
      case "D":
          childclass = class'GPTlookBackRight';
          break;
      case "E":
          childclass = class'GPTlookBack';
          break;
      case "F":
          childclass = class'GPTlookBackLeft';
          break;
      case "G":
          childclass = class'GPTlookLeft';
          break;
      case "H":
          childclass = class'GPTlookAheadLeft';
          break;
      default:
          log( " *gennode* Uh Oh! unknown token! "$childtype);
          break;
    }
   // log(" childclass = "$childclass);
    node = gpnode( spawn(childclass));
    children[i]=node;
    node.mypawn = mypawn;
    node.parent=self;
    node.childnum=i;
    node.depth=depth+1;
    return(node);
}

... and the sands of time draw a close to the first session editing this page... things are already a lot clearer in my head thanks to explaining a little to you, dear reader... till the next time I leave you with the remainder of the gpnode class which deals with things like growing random sub trees and other housekeeping. You can view the rest of the classes so far on CVS at the home of UTron on sourcefore here: [1] click on 'browse CVS' and look for classes in the package 'UTron' with names beginning with GP.

function RandomGrow ( int depth, int maxdepth )
{
local int i,j,r;
local string char;
local GPnode node;
  //log(" random grow called on "$self@"depth = "$depth);
  for ( i =0; i<childcount;i++)
  {
   //log(" randomgrow on "$self$"choosing child"$i);
    if(depth == maxdepth) {
     // log("max depth reached");
      char = mid(terminators,rand(len(terminators)),1);
  //    log("char = "$char);
      node = addchild(char,i);
    //  log("new terminator node = "$node);
    }
    else
      {
       if(depth <4) char = mid(functions,rand(len(functions)),1); // add a bit of depth to start with for testing
        else char = mid(alltypes,rand(len(alltypes)),1);
      // log("char = "$char);
       node = addchild( char,i);
      // log("new node = "$node);
       if(node.Childcount >0)  node.RandomGrow(depth+1,maxdepth);
      }
  }
 
}

RandomGrow is the function that creates random trees for seeding the initial population and for use in the genetic 'mutation' operation too. Note the plentiful commented out log statments... no more than curious fossils now, they were useful in the extreme when debugging this stuff, a comment after every line is usually a sign that I was tracking down an accessed none... I really should get round to deleting them :)

Since there are currently quite a few more terminal nodes defined that there are functions the tree had a habit of being very small most of the time so you'll notice that I make sure that all nodes up to depth 4 are chosen from the set of functions in order to give it a bit of depth... strictly speaking this is biasing what should be a totally random process, the fitness selection and evolution should take care of any runts, so this will probably go once things are fully set up. For now though it's a handy feature for testing.

Sometimes we might need to prune off the branch of a tree before replacing it with something else (like a branch chosen randomly from a tree that performs well at our chosen task, or just another random growth when mutating ) so the prune function recursively destroys nodes below the one on which it is first called.

It still feels a little crufty, that first check on childcount should be redundant really as the parent of any nodes with childcount == 0 will destroy them so that will go soon methinks. In fact a more elegant system would have terminal nodes destroy themselves but at the time I wasn't confident that a function in a node that called that nodes destroy() function would actually return, so nodes destroy their children instead (after having called prune on child nodes to ensure that their children get destroyed in turn ).

function prune()    // remove objects below this node
{
  local int i;
  if(childcount == 0 ) return;
  else
    for(i=0;i<childcount;i++)
      if(children[i].Childcount==0) children[i].Destroy();
        else
           {
             children[i].prune();
             children[i].Destroy();
             children[i]=none;
           }
  return;
}

All of the tree manipulation functions used in creating new trees from an exisiting one need to chose a node at random and then do stuff to it. So the two functions below are used to:

1. Count the nodes in the tree so that correct range can be used when a random number is generated to pick a node.
2. Actually return a reference to that random node

function countnodes(out int nodecount)
{
 local int i;
 //recursively count nodes in tree below this one
 nodecount ++;
 for (i=0;i<childcount;i++)  children[i].countnodes(nodecount);
 return;
}
 
function gpnode findnode(out int nodenum) 
{
  local int i;
  local gpnode result;
  nodenum --;
  if(nodenum ==0) return(self);
  else
    {
       for (i=0;i<childcount;i++)
         {
           result = children[i].findnode(nodenum);
           if(result != none)
              return(result);
         }
       return(none);
    }
}

last but not least, cloneme() spawns a duplicate of a node and all the tree below it... yet more recursive majick :)

function gpnode cloneme()
{
  // clone this object, used recursively to duplicate subtrees
  local int i;
  local gpnode newnode;
 
  newnode = spawn(class);
  for(i=0;i<childcount;i++)
    newnode.children[i] = children[i].cloneme();
    newnode.mypawn=mypawn;
  return(newnode);
}

The most interesting things in the deafult properties are the strings which are used to hold lists of the tokens of the different types of nodes. Add to these when new nodes are made (my current one character per token scheme is nice and simple and I reckon if you find yourself running out of characters as node types undergo runaway expansion you need to think again about how much control you're willing to hand over to the evolution process... stick to minimal building blocks and let complexity sort itself out... another lesson from mr Turing :) )

DefaultProperties
{
DrawType=DT_none
bCollideWorld=false
bCollideActors=false
bProjtarget=false
childcount=1
Terminators="RLKABCDEFGH"
AllTypes="+-*%<RLKABCDEFGHQNX"
functions="+-*%<QNX"
}

So there you have it, the core node class. But for this to do any good we need a way of storing 'genes' and keeping track of which ones are doing well at our trials, as well as performing the actual 'breeding' and mutation of those high performers. Find the class that does this and further ramblings over at:

Genetic Programming/Genes

Your Comments Welcome

DJPaul: Blimey.

Zedsquared heh! I'll take that as a good 'Blimey' then ;) food for thought I hope?

Chazums: Strangely enough, just stumbled onto the idea of using this kind of thing for AI today. Nicely written walk through, makes things clearer in my mind too.

Zedsquared Cheers Chazums, glad my explanations make some sense to you, here's a good link to a page full of such goodies (the whole site is good for AI too) GameAi.com