| Home Page | Recent Changes

Genetic Programming/Mutation

... continuing on from Genetic Programming/Genes

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 Genetic Programming/Genes I hope to be getting back in the saddle with this stuff soon, watch this space :)

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

FAQs

Help Desk

Mapping Topics

Mapping Lessons

UnrealEd Interface

UnrealScript Topics

UnrealScript Lessons

Making Mods

Class Tree

Modeling Topics

Chongqing Page

Log In