Adventures In GP Episode II

This page introduced the core class and ideas behind breeding a routine using [Genetic Programming.]

Having sorted out the core stuff we need to think about the bigger picture:

The 'outer loop' of GP goes like this:

Pick a candidate from a population of random programmes
Test the candidate, keep track of how well it does
Repeat untill all candidates have had enough trials to get a measure of their fitness for the task in hand
Breed a new population by:
1. Finding the best performing members of the current 'generation'
2. Perform 'genetic operations' on these elite performers to generate members of the next generation by combining or changing their code in some way.
3. Repeat untill you have a new population to test.
Start all over again at 1), repeat until you deem performance good enough.

Now the classical way to do this involves running one large population on one machine and this is what I'll start off with. But this can have some disadvantages as the population can become under diversified as an early partial solution to the problem rises to the top and monopolises all the gene pool.

One way around this is to adopt the so called 'island' model and maintain many populations, each randomised at the start, and to allow those to breed for a while and then periodically allow exchange of members with the others thus ensuring some diversity. These populations can be run on different machines communicating over a network, or as many processes on one machine.

Anyway that's getting a bit ahead of myself... I need some way of storing and manipulating these things so it's time for a fresh class: The GPmaster:

//---------------------------------------------------------
// class that handles breeding, fitness selection etc of GP
// trees
//-----------------------------------------------------------

class GPMaster extends Info config(Genes);

A good start as the only way of storing persistant data in uscript is via ini files we make this use genes.ini as a gene pool database (see Config Vars And .Ini Files ).

Uscript never was meant to be used as a heavy duty database so if the breeding programme takes off and requires the tracking of thousands of individuals then I'll have to look at using TcpLink to talk to an external decent DBMS like MySQL or something. But at this stage in development ini files will do.

To keep track of a member of the population we need to store the code that it uses and its performance in the trials, this sounds like just the job for a struct:

struct gene
  {
    var string code;
    var fitnessstats fitness;
    var int PoolIdx;
    var int trials;  // number of times this has been tested in this run
    var int rank;
  };

At this point I realised that the GP framework I'm putting together could get used for many different tasks, not just breeding something that's good at steering lightcycles. Different tasks will have different ways of measuring success, not just number of frags... perhaps number of hits/bullets fired, or time spent staying alive, or prisoners rescued... whatever, the point is that we don't know what info will be returned by the other game code (the stuff that's actually running the trials ) so we make this gpmaster class somewhat abstract and fill in nitty gritty details in a subclass.

My first thought was along the lines of:

struct fitnessstats    // redefined in subclasses  for different tasks
                      
  {
   
  };

function initfitstats( fitnessstats f)
{
 // called to initialise stats on new gene
 // define in subclass
}



function addfitstats( fitnessStats new, fitnessstats old )
{
  // merges fitness stats from gene returning from trial
  // with those in pool
  // define in subclass
}

function gene best( gene g1, gene g2 )
{
// evaluate and return fittest of the two genes
// submitted.
// Used to sort genes to find the best performers
// define in subclass
}

And all seemed fine, I coded up a subclass, put some actual variables in the struct and all compiled fine.. then I wrote initfitstats to suit and blarrrt! compiler error about redefining initfitstats, probably because even though the number of arguments to that function seemingly haven't changed (there's still just one struct passed) there are now more variables in that struct, hence the confusion No panic, I'll just have to define an object to hold fitness variables and subclass that instead I guess. Actually this is a bit neater as that class can also hold the functions needed to initialise itself and so on, but is messier as storing these variables is a problem... hmmm some more thought needed there, quick workround for now, though is to define all the stuff I need to get *my* task done up here in the superclass and worry about being versatile later So we have the variable definition block in full:

struct fitnessstats    // need to replace this with an object so it can be redifined in subclasses
                       // for different tasks
  {
   var   int gameswonVbots;
   var   int gameslostVbots;
   var   int GameswonVhumans;
   var   int GameslostVhumans;
   var float timespentplaying;
  };


struct gene
  {
    var string code;
    var fitnessstats fitness;
    var int PoolIdx;
    var int trials;  // number of times this has been tested in this run
    var int rank;
  };

var config gene pool[200];
var config int totaltrials,PoolPtr;
var int maxdepth;

So you can see we have an array of genes, size 200 for our population (number 200 pulled out of the air... may grow later), and a couple of persistant variables to keep track of how many trials have been made and which was the last gene plucked fro the pool for testing.

Right, now for some proper meat:

function PullGene(out gpinfo result)
{
// grab a gene from the pool

 local gpnode root1;
 Local int idx;
 log(" *GPM* pullgene called with gpi = "$result);
 // alternate between next gene from pool and random gene
 if(toggler ==0) idx = rand(600);
 else
   {
     idx = poolptr;
     poolptr ++;
     if (poolptr ==601) poolptr=0;
   }
 toggler = 1-toggler;

 result.initialise();
 if( pool[idx].code == "" )
   {
     // grow random tree to fill empty pool position
     root1=spawn(class'gpnode');
     root1.RandomGrow(0,maxdepth);
     root1.WriteToString(result.code);
     log(" GPM new code generated = "$result.code);
     root1.prune();
     pool[idx].PoolIdx = idx;
     pool[idx].trials=0;
     pool[idx].code=result.code;
     root1.Destroy();
   }


 result.code=pool[idx].code;
 result.ID=idx;
 saveconfig();

}

function returngene( GPinfo incoming )
{
 // maybe some sort of hash function for indexing genes later ?
 addfitstats(incoming);
 pool[incoming.id].trials ++;
 pool[incoming.id].rank=eval(pool[incoming.id]);
 totaltrials++;
 if(totaltrials % Trials_per_generation==0)
     breednewpool();
 saveconfig();
}

Pullgene will be used by the game entity that's going to be controlled by the GP tree to request a new brain for testing, it alternately selects either a random gene or the next one in sequence, this was done so I could ensure that as, long as I run at least twice as many tests as there are candidates in the pool, each candidate is guaranteed to be tested but not only against its immediate neighbours as would happen if I were simply to go through the genes sequentially.

Within each gene struct is stored an index to the pool array so that when it comes back from the trial and returngene() is called then the appropriate set of fitness stats gets updated, remember there could be any number of in game bots all requesting new brains at different times during a trial so this is the best way to keep track of things IMO.

Now a break from the higher level logic for an actual genetic operator: the crossover operator. What this should do is take two trees, chose a node at random on each one,and swap over those nodes, along with any sub tree attached to them.

function crossover( gene g1, gene g2, out gene g3, out gene g4)
{
local int n1,n2;
local int nc1,nc2;
local string s1,s2;
local gpnode root1,root2, node1, node2;

log(" crossover: building trees ");
root1=spawn(class'gpnode');
root2=spawn(class'gpnode');

log("code string1 ="$g1.code);
log("code string2 ="$g2.code);
root1.ReadFromString(g1.code);
root2.ReadFromString(g2.code);

// count nodes in candidates
root1.CountNodes(nc1);
root2.CountNodes(nc2);

log(" crossover: nodes counted in tree 1 = "$nc1);
log(" crossover: nodes counted in tree 2 = "$nc2);
// select a couple of nodes at random

n1 = rand(nc1-1)+2;

n2 = rand(nc2-1)+2;

log(" Crossover point 1 = "$n1);
log(" CRossover point 2 = "$n2);

node1 = root1.findnode(n1);
node2 = root2.findnode(n2);

log(" crossover node on tree1 = "$node1);
log(" crossover node on tree2 = "$node2);
//swap over subtrees

node1.parent.children[node1.childnum]=node2;
node2.parent.children[node2.childnum]=node1;

// write out new strings
root1.WriteToString(s1);
root2.WriteToString(s2);

log(" after crossover tree1 ="$s1);
log(" after crossover tree2 ="$s2);

// kill orphans


root1.prune(); root1.destroy();
root2.prune(); root2.Destroy();

// initialise new stats blocks.
initfitstats(g3);
initfitstats(g4);

// assign new code strings

g3.code=s1;
g4.code=s2;
// the end!
}

All those logs are from testing and I'm pleased to say it all worked OK... here's some annotated log snippage to illustrate:

ScriptLog: crossover: building trees

ScriptLog: code string1 =XXERQG

ScriptLog: code string2 =N*HNK0.020814LQ-A+<A+HEA+K0.155583GE

ScriptLog: crossover: nodes counted in tree 1 = 7

ScriptLog: crossover: nodes counted in tree 2 = 21

ScriptLog: Crossover point 1 = 7

ScriptLog: CRossover point 2 = 11

ScriptLog: crossover node on tree1 = UTronCyclebottrainerTEST.GPTlookLeft4180

ScriptLog: crossover node on tree2 = UTronCyclebottrainerTEST.GPFplus5064

So the seventh node on tree1 is the chosen crossover point with the eleventh node on tree2. Counting along the strings (starting from 2 to allow for the root node) gives us the characters 'G' and '+' respectively and the logged node types agree... great! that means the node counting and selecting routines all work.

ScriptLog: after crossover tree1 =XXERQ+<A+HEA+K0.155583GE

ScriptLog: after crossover tree2 =N*HNK0.020814LQ-AG

And checking those resulting strings confirms that the crossover went OK, woot!

Now for the next main genetic operator... mutation, but this page is getting large so hop on along to:

Adventures in GP Episode III

your comments welcome

Tarquin: Suggestions:

move content out of ZedSquared/Developer Journal to be episode I of GP.
change the page names, eg [Genetic Programming/Mutation]? for episode 3.

Zedsquared Cheers for the suggestions Tarq, I'll be doing that sort of thing once I get to the end of my adventure, meanwhile it's somewhat of a shambling pile... bit like me really