I reimplemented the algorithm from [1] in JavaScript using canvas.getImageData for fitness computation.
It's far from perfect, but it seems to work. So far I'm at around 1/30th of the original iterations (took ~1 hour) and it already looks a bit like Mona Lisa :).
I'll be updating the page with more evolved images.
Note: it works only in few browsers: so far I'm aware of Firefox 3.0.4 and Opera 9.61. Firefox is significantly faster.
I've created a number of variations on this, including a black&white one which does a good job of Darwin.
The biggest improvement I've made is in limiting the size of the mutation. Now I have a 1 in 50 chance of executing your mutation code, else the changes are limited to within about 10% of their existing value. This gave me a very nice Velociraptor.
I'm also playing with triangles instead of polygons, but I'm impatient and trying to run them all simultaneously. Time to upgrade...
From the description, your algorithm sounds like it would hit this case very quickly:
A polygon overlaps another polygon and improves fitness by N.
It gets mutated and fitness goes down, so that is not kept.
The polygon stays in a local maxima position, when one mutation lowering fitness might allow much better fitness in future.
Yet the images look like that doesn't happen - have you deliberately avoided it, or isn't it a problem in practise?
I don't do anything smart. These are just brute force mutations, always the same.
The only parameter tuning I did was to try several numbers of vertices per polygon for about 15 minutes and from there on I just used the one (6 vertices) that produced image I liked the most.
10 vertices produced too much noise, 4 vertices was kind of rough.
I started coding with possible variable number of vertices (that seems to be the case in the original algorithm), but it was just too slow in JavaScript.
Anyway, optimization can eventually collapse vertices, so basically I just hardcoded an upper bound.
And mutations are kind of soft, always just one element (R,G,B,A,X,Y).
I guess there is some place for improvement, for example by using HSV comparision for fitness. Though this may be slow. Raw canvas image data are RGBA.
Ah yes, I remember also that at the beginning it didn't want to converge at all when starting with random colors. It works when it can gradually build up from a blank slate.
I tried with HSB. It didn't produce good results. The image was always too dark.
In HSB, colors that are far apart in our perception can have close distance. For example two colors with the same Brightness, Saturation but a different Hue.
Using HSB in the DNA was perfect. It's hard to mutate a RGB color in the right direction. You have to get 3 composants right. In HSB a single modification can change everything.
BTW, I coded a Java version after seeing the original. It works, but first, it doesn't converge very fast, second, it's stuck at: http://i33.tinypic.com/2yycdc8.jpg
On the bright side, I can easily switch the population size to 50. Java is very good at this. I piggy back on automatic hardware acceleration for rendering.
From what I have seen, he is doing extra type of mutations that I was too lazy to implement: move polygons in the stack (in addition to changing colors and moving points around).
Also how you do mutations matters: it seems smaller deltas are better, though they shouldn't be too small.
Simulated annealing moves to locations with lower fitness with some probability each iteration, with the probability of moving to a lower fitness location changing with time and the size of the moves changing with time. My understanding was that the size of the changes and the probability of moving to lower fitness fitness levels did not decrease uniformly but moved down then up then down and up in a humped-shaped pattern, but the wikipedia page disagrees with me.
I was trying to do that by saving locally, but FireFox refuses to allow getImageData on an image loaded from the filesystem by a web page loaded from the filesystem, with an NS_ERROR_DOM_SECURITY_ERR
Anyway, I will now try with your set-your-own-image version.
Now we just need "someone" to implement a real GA algorithm with a real pool of possibilities and real crossover of some kind, and you can get a visual sense of which is faster.
All this (very clever by the way) reminds me of an idea I had a while back that plays to the internet's true strengths:
Create a rendering algorithm such as this but with the fitness function calculated by presenting a set of the output images to web visitors and having them choose the one(s) that they like the most.
My thesis is that with enough iterations/visitors you'd eventually generate a load of highly tuned pornography.
You might want to chuck a copyright on that code, in case some fellow hackers want to take the idea and run with it. (That assumes you want other folks messing with it!)
The genetic algorithm technique is often used to solve a problem just because it's cool, and not necessarily because it is the best way to solve the problem.
Is this the case with this "Mona Lisa" problem? Is there an alternative algorithm for finding the polygons that would be more efficient and give better results?
It's likely that there is a better way. There already exist deterministic bitmap rasterizers which might yield decent results, and almost instantly. A greedy algorithm that tries to place the "most necessary" polygon first would almost certainly find a reasonable solution in a very short amount of time. Even a hybrid approach -- where the algorithm randomly picks a solution parameter and does a line search for the best value -- would converge faster than random hill-climbing alone.
Is there any C++ code for this? There's something interesting I would like to try, but JS is not my beast. If there is none, I'll port, but perhaps someone already has written this in C or C++, saving me some trouble.
Yes, but it's hit and miss. Sometimes it counts but does nothing sometimes I can see the shapes flickering, but it never picks any as "best", and sometimes it looks like it's still working on the mona lisa or on a different size canvas.
None that I've found on Flickr have worked.
I googled for "200x200" and found the Firefox logo in that size, and it's evolving that... fitness has just crossed under 1,000,000 after about 15 minutes, but it isn't recognisable yet...
Another half hour, and it's just above 900,000 after 43,000 steps - it still looks nothing like the FF logo though.
That is, it looks nothing like it. It has, for example, no dark blue, orange, yellow or white - and only a smidgen of pale blue in completely the wrong place. The whole square is shades of hessian brown/pale green/caucasian artificial limb with a blotch of pink.
Thanks so much for making your code available. I've reimplemented your app in java with the idea of improving the speed. Unfortunately java2d rendering speed is not so hot - I'm getting about 2k iterations/minute on a 2ghz p4m with 90% of the time being spent rendering polygons. As for optimizations, I am going to experiment with some of the mutations from Mr. Alsings code -- I'm also thinking about adding multiple worker threads or possibly distributing to multiple machines.
I've tried to play build the idea cubicle67 mentioned to use relative mutations instead of absolute ones. What I've implemented is a function that does not limit the change at all, but simple makes it more likely to be small and less likely to be large.
The new value becomes either (MAX - current) * P or current * P (50% chance on each), where P is the product of two random variables between [-1, 1]. I'm not sure how that is distributed (been a while since that statistics course), but it obviously favors numbers closer to 0.
This optimization looks rather efficient, as the same image seems to get about 67% more beneficient mutations in the same interval of generations.
Another change I would like to implement (but haven't yet) is a low chance of changing multiple values at once, which may eventually escape from a "dead end".
The best improvement of all would be to allow users to airbrush "priority" onto different regions, which then get weighted in the fitness score. If I'm generating a portrait, I care a lot more about the eyes than the background, for example.
I will try your function in my code this evening. Another strategy I thought about is to have a small chance of replacing a polygon with a random new polygon. It seems that it would help get out of dead end situations.
Ok, I tried it and it converges much faster. My dna data is all integers so the update function is something like
constrained update( int existing_value, int limit ) {
new_value = random( limit )
constraining_value = random_float
difference = ( new_value - existing value ) * ( constraining_value * constraining value )
return difference
( apologize if code doesn't format correctly).
I also tried randomly replacing a poly with a new random shape and color poly 5% of the time to get away from local minima... didn't seem to help. I'm still doing a bit on this in my spare time if anyone is interested.
