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.
Comments
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.