Adventures In GP Episode III

... continuing on from Adventures in GP Episode II

The mutation genetic operation is used fairly sparingly in the breeding process and works by chosing a node at random then replacing the tree below it by new randomly generated code. It's pretty straightforeward:

function gene mutate( gene g1)
{
 // chose a node at random and replace with new random subtree

 local int numnodes, nodenum,i;
 local gpnode root1,target;
 local gene result;
 Local string s1;


 initfitstats(result);

 // grow tree from gene
 root1=spawn(class'gpnode');
 root1.ReadFromString(g1.code);

 // find out how many nodes are in the tree we're mutating
 root1.countnodes(numnodes);

 // pick one at random
 nodenum=rand(numnodes-1)+2;
 
 // get reference to target node
 target=root1.findnode(nodenum);

 // clear subtree below target node
 target.prune();

 // grow new subtree
 target.RandomGrow(target.depth,maxdepth);

 // write out new tree
 root1.WriteToString(result.code);

 // clean up
 root1.prune();
 root1.Destroy();

 return(result);
}

So, having coded up routines to mangle GP trees in various ways there's a need for something to actually organise the planned orgy of interbreeding. Sorting the array in order of performance sounds like a good idea to start with so why not break out a good old bubblesort, I know there are quicker ways but this only gets done fairly rarely and our array isn't that huge so what the heck:

function sortgenes()
{
  local int i,j;

  for(i=0;i<599;i++)
    for(j=0;j<(599-i);J++)
        if(eval(pool[i+1]) > eval(pool[i])) swap(i,i+1);

}

function float eval( gene g1)
{
// evaluate fitness of gene
// submitted.
// define in subclass

local float result;
local  float playedVhumans, playedVbots;

playedVhumans = g1.stats.GameswonVhumans + g1.stats.GameslostVhumans;
playedvbots = g1.stats.gameswonVbots + g1.stats.gameslostVbots;

if( playedVhumans ==0 ) playedVHumans=1;   // to avoid divide by zeros
if( playedVbots ==0) playedVbots=1;

result = (g1.stats.gameswonVbots / playedvbots) + 2 * (g1.stats.gameswonVhumans / playedVhumans) ;

return(result);
}


function swap( int idx1, int idx2)
{
 // swap over two genes in pool
 // define in subclass
 local gene temp;

 temp=pool[idx1];
 pool[idx1]=pool[idx2];
 pool[idx2]=temp;
 pool[idx1].PoolIdx=idx1;
 pool[idx2].PoolIdx=idx2;
}

That takes care if the sorting, now to code up the routine that makes actual *evolution* happen, so far all we've been doing is randomising everything, now we select our stud stock and breed the next generation of AI... it's a nested loop fest, it's:

function breednewpool()
{
  local gene breeders[16];
  local int i,j;
  // take the top performers and breed a new generation from them
  // first sort them in order of performance
  sortgenes();
  // keep top fifteen performers
  for(i=0;i<16;i++) breeders[i]=pool[i];

  // breed (crossover) the top sixteen against each other in all perms... twice
  for(i=0;i<16;i++)
    for(j=0;j<16;j+=2)
        crossover(breeders[i],breeders[j],pool[16+j+i*16],pool[j+17+i*16]);
  for(i=0;i<15;i++)
    for(j=0;j<15;j+=2)
        crossover(breeders[i],breeders[j],pool[272+j+i*16],pool[273+j+i*16]);


  // throw in a few mutations  each too
  for(i=1;i<16;i++)
    {
     pool[512+i]=mutate(breeders[i]);
     pool[528+i]=mutate(breeders[i]);
     pool[544+i]=mutate(breeders[i]);
     pool[560+i]=mutate(breeders[i]);
    }
//  that makes 576 by my reckoning... blank the code of the lowest performers so they
// get new random code next time
    for(i=576;i<600;i++)
      {
        pool[i].code="";
        initfitstats(pool[i]);
      }

    generations ++;
    saveconfig();
}
 

... to be continued ...

Foxpaw: I didn't see the crossover function listed, I'm curious as to how it works on that tree. Have you written it yet?

Zedsquared: Yep, it's back a page on Adventures in GP Episode II I hope to be getting back in the saddle with this stuff soon, watch this space