Tuesday, 24th November 2009
Mutation rate analysis
In a continued attempt to find optimum parameters for evolving a image using circles, I have been investigating the effect of mutation rate on the rate of evolution. In previous runs of evolution, there were between one and four mutations per generation, (a mutation alters a single parameter (x-, y-, z- coordinate, diameter, transparency or colour) of a circle). I have now re-run evolution four times with one mutation per generation and four times sixteen mutations per generation. I used 256 circles, which appears to be optimum for this time scale of ~250 000 generations.
The graph above the result of evolution over 262144 (two to the power of 18) generations. It shows that with sixteen mutations (which means that up to 1/80th of the genome can change) per generation, images evolve very quickly to start with, whereas with one mutation per generation, there is very little evolution for the first 256 generations. (Averages are shown by the thicker line.) However, by ~16 000 generations, the rate of evolution slows when there are sixteen mutations per generation, while with one mutation per generation, evolution continues at about the same rate. As a result, by the end of the simulation, the images evolved with a one mutation per generation are beginning to catch up and resemble the target image more closely than images evolved with sixteen mutations per generation.
The graph below shows, in part, why the 1-mutation per generation images catch up. The graph shows how the chance of a daughter out-competing her mother changes with mutation rate (and over time). In the early generations, with sixteen mutations per generation, there is a higher chance of a successful daughter: the circles that make up the image are still fairly randomly distributed at this point, so there is a good chance of a change improving the image. Therefore, the more mutations, the better. However, at later generations, when the images start to have a closer resemblance to the target image, there is a more of a chance that a random change with make the image less like the target. With sixteen mutations per generation, there is a good chance that even if several mutations improves the image, one will greatly degrade the image. The higher mutation rate is less likely to create a successful daughter.
However, this also suggests that the reason that there is a greater chance of success with one mutation per generation after ~4000 generations have passed, is that the images generated with sixteen mutations per generation are about twice as close as those generated with one mutation per generation (d = ~40 vs ~80). It might therefore be worth normalising the ‘chance of daughter out-competing mother’ to the images’ current d-value. Further supporting this idea, is the fact that despite the fitness of images being approximately equal by the end of the simulation, there were an average of 6660 successful generations when the mutation rate was one per generation, compared to 2570 successful generations when the mutation rate was sixteen per generation.
Overall, this analysis suggests that I might be able to evolve images more quickly by starting with a high mutation rate and then dropping it over time.
This reduction in mutation rate over time would mimic what has probably happened in real life, as cells have evolved to become better at replicating their genomes accurately.