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.
Comments
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.
[1] http://news.ycombinator.com/item?id=389727
What a timesink :)
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.
for example by using HSV comparision for fitness
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.
How did you get yours to converge sooo fast?!
Mine is nothing, try the original program from Robert Alsing. He already released the source code and binaries:
http://rogeralsing.com/2008/12/11/genetic-programming-mona-l...
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.
Didn't know an .getImageData() existed! (Sometime I need to look at the bleeding edge APIs.) Very cool hack!
Very cool. I'm running WebKit nightly 49090 and it's blazingly fast -- 1683965 fitness in 30 minutes
I envy you :).
You may try to run it on different images, I just added new experimental feature: you can set your own target image.
This does crash JavaScript sometimes on some images (for unknown reasons). If this happens, just reload the page.
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.
You can run it locally if it is on your local webserver (http://localhost) instead of just filesystem (file://).
That's how I work on it (XAMPP).
http://en.wikipedia.org/wiki/Xampp
That would be 39090. I'm sure 49090 would be even more faster, in a year or so =)
Oops! Yes =)
You should have it automatically upload images so everyone doesn't have to start at nothing.
How do you compute the similarity, pixel by pixel?
Yes, I try to do it as cheaply as possible.
Typically, distance between multiple samples of stuff uses the minimize-the-sum-of-squares technique, maybe it applies here too?