Legacy:Genetic Programming/Mutation - Unreal Wiki

# Legacy:Genetic Programming/Mutation

### From Unreal Wiki, The Unreal Engine Documentation Site

< Legacy:Genetic Programming

... 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 :)

##### Views

- Legacy
- Discussion
- Current revision

##### Search