## Oh no, not more populations : overlapping generations.

### July 21, 2007

I promised, a while ago now, to show a version of the simulation with overlapping generations. This basically means that not all the individuals in the population die every season, so some remain in the next ‘generation’.

OK, so starting with the simple stuff.

Our original non-overlapping generation, only had one method to run every season:

DoOneSeasonOfReproduction()

All this did was to reproduce continually into a new, empty population until the new population became full.

Overlapping populations will need an extra method:

DoOneSeasonOfMortality()

The mortality phase is when individuals are killed off to make space on the population for new individuals that are created in the reproduction phase. We could combine this into one method, but somehow I feel they should be kept separate.

So I mentioned creating spaces in the population. This is the real secret of this simulation. When I first wrote this type of simulation, I used linked lists to hold the population so that you could remove nodes from the list easily and then add new individuals easily. It ran like a dog. I mean it was really, really, *really* slow. Like, start the simulation off and come back tomorrow to see the results of the first couple of runs.

Writing a simulation is *not* like writing a normal application. You don’t care about using too much memory and you do care about speed (your probably going to run hundred of replicates, so you don’t want to have to wait weeks for if to complete).

The secret is to use only arrays. I used an array in the non-overlapping population version and it was the obvious choice because the population size is always static. Using arrays in the overlapping version is a little more involved because, like I said, we make spaces in the population.

The first version of the array only simulation was probably the natural first design that anyone would come up with without spending too much time thinking about it. When adding new offspring to the population, iterate through the array to find the spaces. This works for small populations, but when you keep having to iterate through an array of 10,000 indices it get slow again.

So to speed up the finding of spaces, we’re going to use a simple stack. The stack is also an array-based implementation for speed. Essentially, we create an integer array of the same length as the population size (so that if the random numbers dictate it, the *entire* population can die off which would indicate the end of the simulation).

Every time an individual is killed, it’s index is pushed onto the top of the ‘spaces stack’. Whenever an individual is added to the population, it’s new index is popped from the spaces stack. When the spaces stack is empty our population is full.

Here’s a diagram:

So the space stack speeds up the process of finding a space in the population into which new offspring can be inserted, and the use of fixed size arrays means there’s not much by way of pesky memory allocations to slow things down.

So, lets implement this:

///<summary> /// Does one season of mortality. ///</summary> ///<remarks>Performs probability-based deletions of individuals in the population.</remarks> public void DoOneSeasonOfMortality() { System.Random rand = new Random(); for (int i = 0; i < mPopulationSize; i++) { // Find random double chance = rand.NextDouble(); // 0.25 probability of death for each individual. if (chance <= 0.25) { // Push index into stack then delete individual. stackTop++; stack[stackTop] = i; population[i] = null; } } }

In this example, we’re just using a fixed probability of 0.25 to determine if an individual dies. I could probably do without actually setting the individual in the population to null and rely entirely on the stack to hold which individuals were dead, but frankly that idea worries me.

So now we’ve got a population with vacant spaces, we need to fill them back up with reproduction. Here’s the new reproduction code:

///<summary> /// Does one season of reproduction. ///</summary> ///<remarks>This updates the Population with one season of reproduction.</remarks> public void DoOneSeasonOfReproduction() { System.Random rand = new Random(); // While stackTop >= 0 there are still vacant indices in the population while (stackTop >= 0) { // Find two random parents (non null entries) int idxParentOne = rand.Next(0, mPopulationSize - 1); while (population[idxParentOne] == null) { idxParentOne = rand.Next(0, mPopulationSize - 1); } int idxParentTwo = rand.Next(0, mPopulationSize - 1); while (population[idxParentTwo] == null) { idxParentTwo = rand.Next(0, mPopulationSize - 1); } // Populate the space at the top of the stack and then pop that // space from the stack. population[stack[stackTop]] = population[idxParentOne].Cross(population[idxParentTwo]) as T; stack[stackTop] = -1; stackTop--; } }

This is pretty much the same as for the non-overlapping population code, except we put the new offspring into the same population as the parents and keep going until the population is full.

The final change that I have made is to create an interface for the population objects, so that we can swap between non-overlapping (simple) populations and overlapping (complex) populations. Here’s the interface:

interface IPopulation<T> where T : class, IIndividual, new() { void DoOneSeasonOfMortality(); void DoOneSeasonOfReproduction(); T[] Population { get; } int PopulationSize { get; } DescriptiveStatistics.Histogram TakeCensus(); }

The simple population has a mortality method that does nothing and only exists to satisfy the interface (not great design, but it will do for now).

This interface means that our main simulation loop looks like this :

System.IO.StreamWriter sw = System.IO.File.CreateText("c:\\Log.txt"); stats = new DescriptiveStatistics.Histogram(0, 500, 10); WriteHistogramHeader(sw, stats); int repCount = 10; IPopulation<Individual> population = new ComplexPopulation<Individual>(500, 20); DescriptiveStatistics.Histogram histo = population.TakeCensus(); int generationCount = 0; while ((histo.Statistics.StdDev > 0) || (generationCount == 0)) { generationCount++; population.DoOneSeasonOfMortality(); population.DoOneSeasonOfReproduction(); histo = population.TakeCensus(); Console.WriteLine("{0}\t{1}\t{2}", generationCount, histo.Statistics.Average, histo.Statistics.StdDev); sw.Write("{0}\t{1}\t{2}", generationCount, histo.Statistics.Average, histo.Statistics.StdDev); WriteHistogram(sw, histo); sw.Flush(); } sw.Close(); sw.Dispose(); }

We can easily switch population types by replacing the line

IPopulation<Individual> population = new ComplexPopulation<Individual>(500, 20);

with

IPopulation<Individual> population = new SimplePopulation<Individual>(500, 20);

to change the population type that we are simulating.

I have put all of the code for this post over on the Channel 9 sandbox so you can download and have a play.

If you're interested in writing software, check out my other blog: Coding at The Coal Face