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.
So 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. I call these runs of evolution P4-M1 as they have a population of 4 and a mutation rate of one parameter per generation.
Compared to the P1-M1 runs of evolution, P4-M1 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 (P1-M16, described in detail here). This graph shows how P1-M16 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 P4-M1 is shifted so that this into account (the transparent purple line) , P4-M1 follows P1-M1 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.
Comments (2)
Anonymous on 16 Jul 2013, 11:44 a.m.
I love your work, excellent article.
Nigel on 22 Aug 2015, 1:32 p.m.
hi, very interesting article. I wrote a program in matlab following the pseudo code you provided. I chose 250 circles and a mutation rate of between 3 and 10 for the encoded chromosome. However, after running for 16 hours, the result was a very approximate version of the target image. Probably around 33000 generations with 3000 successful mutations. My question is regarding the method of mutation. My method simply generates a random number and then alters either position/size/transparency etc. within each mutation of the chromosome, several attributes will change and not just one. What method did you employ? Did your method employ a more gradual shift with the mutations as with my method, abrupt changes to the elements of the chromosome due to the nature of the random variable. Many thanks for any feedback :)