Tuesday, 5th January 2010
Analysing population size
My genetic algorithm has been slowly ticking over in the background. Most recently, I have been re-run evolve with a population size of four instead of one. In previous runs of evolution, in each generation, a organism competed with a mutated version of itself (its daughter); the organism closest to the target image survived to the next generation. This is the simplest way to write the program. However, in real life no species has so few organisms and it is well known that the smaller the population size of an species, the less genetic variation it has, and so the less able it is to adapt.
Thus, I re-ran the genetic algorithm with a larger population to see how the rate of evolution changed. The program started with four random genomes, each of which produced a daughter organism with a genome of its parent with one of the parameters randomly mutated. Of the eight organisms, the four that produced an image closest to the target image went forward to the next generation. If refer to these runs of evolution as Pop4, Mut1 as they have a population of 4 and a mutation rate of one parameter per generation.
Compared to the Pop1, Mut1 runs of evolution, Pop4, Mut1 produced images that were significantly closer to target image for all the generations in the experiment. This advantage lasted over whole time of the experiment (although the difference is closing towards the end). This contrasts with the effect of increasing the mutation rate to sixteen (Pop1, Mut16, described in detail here). The graph below shows how Pop1, Mut16 runs of evolution, are fastest to start with, but slows at around generation 100,000.
However, the problem with increasing the population by four times, is that the program takes about four times longer per generation. If the line for Pop4, Mut1 is shifted so that this into account (the transparent purple line) , Pop4, Mut1 follows Pop1, Mut1 very closely after the thousand generations or so. It therefore seems that increasing the population size does not increase the rate at which the program can increase the accuracy of the image.
It would be interesting to see whether a faster rate of evolution can be achieved with a larger population, since a population of four is very small. As ecologists know, population size is very important and populations become dangerously inbred when small; a species of four would basically be extinct. I suspect that after a couple of generations, the Perhaps, above a threshold population size there would be a sort of phase transition, but that is pure speculation. The difficulty is the time it would take to run a program with a much larger population size. Another possibility is to introduce sex, or at least the ability of to combine the information of two successful genomes.
If we look at a graph of how often the top organism is usurped, we see that with an increased population, the top organism is more likely to be overthrown at each generation. This is unsurprising since in each generation there will be four new contenders. However, I suspect that each new top organism improves on the previous one by a smaller amount, though I’ll have collect the data to show that.