In searching for how to drawing transparent shapes in Pygame, I happened across a website describing how an approximation of the Mona Lisa had been evolved using overlapping transparent polygons. It sounded like a fun, and so once again, I started a new project. For simplicity and to speed up computation, I used circles, and for the most part, I used grey scale images.
In order to use a genetic algorithm to solve a problem, you need a method of converting a string of numbers (or symbols) into possible solutions to the problem. This allows solutions to be mutated by changing symbols at random. Importantly, every possible string of symbols must generate a valid solution. You also need a way of measuring the fitness of a solution - how close is it to completely solving the problem? This allows you to compare two potential solutions so you can select the better solution.
A simple genetic algorithm works in the following way:
Obviously, this program will loop forever. You can stop it after it reaches an arbitrary number of loop (generations), after the fitness reaches an arbitrary level (though bear in mind that the program might get stuck in a dead-end and never reach this level), or until a genome is undefeated for an arbitrary number of generations.
For each run of evolution, I fixed the number of circles. The reason being that the more circles an image has, the more able it will be to mimic the target image, so I figured that the number of circles would keep increasing. I might be interesting to allow the number of circles to change, but have a penalty for each circle, thus tending to select images made of the fewest circles.
Each circle has six parameters:
The z-coordinate does not have a value as such, but is represented by the order of the circles in the genome. Circles are drawn in the order they appear in the genome onto a white background that has the same dimensions as the target image. Mutations in the z-coordinate therefore require the genome to be rearranged, allowing a circle from the back to be brought to the front. With 128 circles, a genome therefore consists of 6400 numbers.
The fitness of the genome is measured by comparing each pixel of the generated image with the corresponding pixel in the target image. For grey scale images, each pixel has a value 0 corresponding to pure black and 255 corresponding to pure white. For each pixel I square the difference between the value from the target image and the generated image. I can therefore calculate the difference between two images by summing the squared difference of all the pixels. The lower this value is, the closer the two images are, and the ‘fitter’ the genome. In the subsequent updates I use this distance value (which I call d), though I've divided it by one million to make it more manageable. In general, a random genome have a d value around 200-300, and a highly evolved image have a d value around 8-12.
After some false starts with mutations not being saved (I forgot that in Python, a list of lists needs to be explicitly copied), I finally got a program running using Pygame. Then I spent several hours watching an image of my cat (what else), slowly evolve. After a while I decided I wanted to experiment with changing the parameters for the program so I wanted a standard image for all my tests. I wanted to start with a greyscale image to keep things simple at first, but the cat picture was a bit too dark and indistinct. I decided on a famous photo of Charles Darwin, which seemed appropriate. I got a smallish (152 x 200 pixels) version to speed up computation.
Below are two images evolved over ~150,000 generations; one image is made up of 128 circles, the other from 256 circles. The images are far from exact replicas of the original, though I think they are recognisably Darwin. To me, the images look a bit like impressionistic reproductions of the original, and from a distance of 4-5m (or 40-50cm without my glasses), both images are almost indistinguishable from the original. The overall shape and shading of the evolved images is approximately right, while the details are missing. As you might expect, the image built from 256 circles has more details (specifically the eyes and nose) than the image built from 128 circles.
In the first runs through my evolutionary search for an approximation of Darwin, I had no way of saving the result. I later started to record every genome that was more successful that its predecessor. As a result I can re-run an evolution path at an accelerated rate. In one run of evolving 256 circles for ~150,000 generations, 3010 daughter genomes were 'fitter' (i.e. less distant from the image of Charles Darwin), than the preceding genome. I generated and saved the 3010 images corresponding to each of these genomes (luckily they are very small PNG files), then imported them into ImageJ as an Image Sequence. This created a huge stack of images, which I saved as a QuickTime movie, showing 24 images per second.
I now have re-run the evolution of an image Darwin using 128 circles, this time recording the genome and the distance the resulting image is from the true image (which is the inverse of a genome's fitness) for every generation in which an improvement is found. Below is a graph showing how the evolved images become a closer and closer match to the true image. I’ve also added example images from generations 1, 10, 100, 1000, 10000 and 100000 with their corresponding measure of distance (d, in arbitrary units).
As a side note, the graph is only an approximation of the full set of results, based on the values from 21 evenly spread (on a log scale) generations. The reason for this is that I drew the graph in Adobe Illustrator, to see what it’s graph-drawing function was like. It’s not too bad. Though it is obviously quite limited, Illustrator does let you draw distracting circles in the background.
The graph shows that largest decrease in the distance value (and therefore the largest increase in fitness) occurs approximately between generations 100 and 1000. However, I would say that the biggest increase in subjective image quality is between generations 1000 and 10000. There is relatively little change between the images of the first 100 generations, suggesting that not much improvement can be seen on that timescale. By generation 1000, the distance value has decreased significantly, but the most we can say about the image is that there is a general area of lightness in the centre with darker regions at the periphery. By generation 10000, the general shape of darwin’s head is in place, and by generation 100000, the outline is sharpened and some of the details, such as the nose and mouth can be seen. Who knows how close the image could get by the millionth generation? Not me, it would take too long on my computer, but if I could use the GPU…
These images are from generations 2000 to 10000 with their distance values. This looks like the time when Darwin’s image begins to take shape.
I have made a slightly more in-depth analysis of an evolution with 128 circles, looking at individual mutations. I've identified the mutation that caused the largest improvement in fitness (that is to say, the largest (in absolute and relative terms) decrease in distance between the evolved image and the target image). The mutation occurred in the 36th generation and caused the distance value to decrease by ~42 units, or ~13%. The result of the mutation was to swap gene 10 with gene 115, and the effect of the image can be seen below.
In generation 35, gene 10 encoded a large dark circle towards the bottom of the screen and gene 115 encoded a very transparent circle near the top of the screen. The two circles are shown in the third image above (on a blue background so the transparent, light grey circle is visible), which I made when I tired of playing spot-the-difference. Because gene 10 is one of the earliest genes, it was covered by many other circles, which happened to be lighter. In generation 36, the large dark circle towards the bottom of the screen was now gene 115, so was drawn later, over some of the lighter circles. The result is that the bottom of the screen is darker, and so more similar to the target image. If you look at the previous post, you can see that this circle is basically unchanged at generation 100.
This analysis shows that even the most successful mutation in evolutionary history makes a relatively modest difference to the overall image.
All of the largest (successful) mutations occurred in the first few hundred generations as the large regions of shading were becoming settled. It seems that this single gene analysis is unlikely to be informative, but I now have the tools to compare genomes so I could try comparing genomes from more distance generations.
I have re-run the evolution of Darwin’s image using 128 circles four time now. Below is a graph showing the decrease in distance between the evolved and target image over time for each of the runs (the darkest line is the first run). The initial distance value varies quite a lot between the four different runs, but by about 1000 generations, the values are approximately the same. I plan to compare this rate of evolution with the rate of evolution when there are more circles or a different rate of mutations.
Click on the image above to see selected images from the four runs of evolution, showing the first and final distance values (d).
It may seem that I have been neglecting this genetic algorithm project, but my computer has been busy crunching numbers, repeatedly evolving images with 128, 256 or 384 circles. Below shows the average distance values from four separate runs of evolution with 128 circles, 256 circles and 384 circles. It is purely bad luck that the Darwins evolved from 256 circles started with a much higher distance from the target images. However, by ~500 generations, the 256-circle Darwins had caught up with the 384-circle Darwins.
The more circles the image has, the slower it evolves. This is what one would expect because the circles that make the most difference to the distance from the target image are those on top. The more circles there are, the less chance there is that a mutation will affect one of the more important circles. However, we would expect that while evolution is slower when there are more circles, the rate at which evolution slows should also be slower, such at that, at some point, the images with more circles will overtake those with fewer circles. I will have to analyse the actual numbers to see if this really holds.
One idea I had, based on this result, is to start evolution with one or two circles, allow those to evolve until there are no successful mutations for a while, and then adding an additional random circle (or perhaps have a random circle replicate).
The image above is a collection of the resulting images from each run of evolution after 100 000 generations, with their d values. I also averaged the four images with a given number of circles. Again shows that the 128-circle images are slightly better than the 256-circle images, while the 384-circle images are considerable worse.
It appears that by 100 000 generations, the 256-circle Darwins are beginning to catch up with the 128-circle Darwins. To see whether the predict that they will eventually ‘overtake’ the 128-circle Darwins, I continued evolution. I took the best 128- and 256-circle images of Darwin (thereby allowing the fittest to survive and reproduce) and allowed evolution to continue for another 900 000 generations (~4 days on my laptop). This generated a couple of pretty decent images, particularly the 256-circle image. You can see the detail of the coat (the start of which can be seen at 100 000 generations), the mouth, the nose, and various wisps of hair. I’ve included the target image below in case you’ve forgotten what it looks like.
I’ve worked out how to write images in the SVG file format, so I can create scaleable images with smooth circles. It turns out that SVG very similar to (or maybe a type of) XML, so learning XML has turned out to be quite helpful already. Being able to create SVG images using Python should be very useful in the future. The images is of the SVG version of Darwin evolved using 256 circles over a million generations, showing how much smoother the circles are compared to the PNG images I have been using. I zoomed out to show the surrounding circles, which I think creates a very organic image, whatever that means.
|Darwin256 1000000.svg||21.54 KB|
Now I have some images that have evolved over a million generations, I thought I’d do a bit of analysis on the resulting genomes. I predicted that the distribution of circle sizes and transparencies would not be random. The graph on the left shows a histogram of transparencies for the 256-circle genome after a million generations. It shows that ~6% of circles are in the most transparent group (you would expect 12.5% for a random distribution), while nearly five times as many circles are in the most opaque group. I predicted that the first circles in the genome (those drawn first), would be more likely to be larger and more opaque compared to the circles drawn later. Unless there is an large circle in the target image, there should not be a large opaque circle towards the end of the genome; there may, however, be large opaque circles in the background.
To test this hypothesis, I plotted the transparency of each circle against its position in the genome (which can be considered its position in the z-axis: circles are drawn in the order they appear in the genome, so the first circle in the genome is the first to be drawn, thus at the bottom of the 'stack' of circles, most likely to be covered by later circles). I’ve been experimenting with different ways of visualising data (and playing with SVG files generated by python scripts), so I thought I’d try to display additional information. Rather that plotting the graph as points or a line, I have used circles whose size and colour reflects the size and colour of the circle being plotted.
Alternatively, I could have plotted, say, circle size along the y-axis and plotted transparency by plotting circles with the corresponding transparency, but I figured that transparency would be the hardest value to gauge by site, especially since a dark grey circle would be indistinguishable from an opaque light grey circle unless it overlapped with another circle. Instead each circle in my plot has a transparency of 05. to allow overlapping circles to be seen.
I hope you agree that the plot above actually shows that there is a slight increase in transparency as you go along the genome. The early part of the genome appears to consist mainly of large, dark, opaque circles, which presumably make up the background. This is also true, perhaps more clearly, for a genome of 128 circles evolved for over a million generations (below). It appears therefore, that the nearer circles are to the end of the genome (thus the ‘top’ of the stack), the more transparent they are, and thus the less likely they are to completely overwrite previous circles.
Both graphs show that many of the circles near the start of the genome are nearly completely opaque.
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.
I started to write about the difficulties of creating a system that is ‘evolveable’, or, seen another way, the problem of converting a problem into one in which a solution can be evolved. However, I got slightly sidetracked into discussing the limits of what images can be evolved in my genetic algorithm to evolve and image of Darwin. I’ll continue writing about evolving solutions to a problem in a later post.
It may well be that not all the possible solutions to a problem can be encoded into a particular scheme, though this is not necessarily a problem. In the case of life, there may be many solutions to the problem of self-replication that do not involved proteins. It is also conceivable that there are some groups of proteins that cannot be encoded into DNA (though I’ll have to think further about this to come up with a convincing example – perhaps a restriction enzymes that digests its own gene). In the case of my genetic algorithm to evolve an image of Darwin, I’m is almost certain that it is impossible to evolve a perfect likeness using 384 or fewer circles.
Clearly, if one were to use one circle per pixel (30400 for my image), then a perfect image could be generated. It would be interesting to know (but very difficult to calculate) the smallest number of circles required to generate any image of 30400 pixels. Since there are 256^30400 (2^243200 or ~10^73000, where “^” means “to the power of”) possible 8-bit greyscale image of this size, and there are ~1.3 x 10^11 possible circles in this size and shape of an image (choosing from 152 x-coordinates, 200 y-coordinates, 67 diameters, 256 shades of grey and 256 transparency), then at least 6300 or so circles would be needed. However, of the possible images made of 6300 circles, a huge number would be pure white (if the transparency of each circle was 100% or colour was 100% white, then any combination of sizes and x, y and z coordinates would be white. In addition, if a few large white opaque circles were drawn last, it wouldn’t matter what the first circles were like).
If I wanted, instead of encoding an image as a list of properties of circles, I could have simply encoded it as a list of the colour of every pixel (which is how digital images are normally encoded). It might have been of some interest to evolve an image based on this encoding, pixel-by-pixel, but not much. In this case, the solution to the problem of creating an image of Darwin is obvious – just copy the image you’re aiming at. In contrast, I think it’s far from obvious how to create that same image using overlapping circles. In this case, the limitation of the encoding system is what makes the problem worth evolving.In fact, there may even be a practical application of an image-evolution scheme to compress image data: encoding a 152 x 200 pixel, 8-bit, greyscale image normally requires 30400 x 8 bits, but using 256 circles, it would require about 9200 bits. However, as I showed above, this is likely to be a very lossy compression. However, a similar system has been discussed.
Having spent so long evolving grey scale images, I thought I’d see how much harder it is to evolve a colour image using the same method (described here). Since it’s now approaching Christmas, I thought I’d try to evolve a Christmas scene, which could perhaps be used on a Christmas card. I spent some time searching for a sufficiently simple scene with a good range of colours, but in the end I just drew a Christmas tree and present.
After more half a million generations, the image made from 256 circles had evolved to form the above. Since the image is small, the program didn’t take too long to reach 500,000 generations and the simple shapes meant that a good approximation to the target image was reached. The main issue was that due to some flaw in my program, the red and blue colours have become reversed: the pot is supposed to be red and the present blue. I’ll try to fix that and maybe create a more complex target image.
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.