Slashdot Mirror
Evolution of Mona Lisa Via Genetic Programming
mhelander writes "In his weblog Roger Alsing describes how he used genetic programming to arrive at a remarkably good approximation of Mona Lisa using only 50 semi-transparent polygons. His blog entry includes a set of pictures that let you see how 'Poly Lisa' evolved over roughly a million generations. Both beautiful to look at and a striking way to get a feel for the power of evolutionary algorithms."
Is the source code available for this? It'd be a fun project to learn from and play around with.
Genetic Algorithms are like the AI equivalent of text editors... everybody has spent a weekend writing one at some point.
How we know is more important than what we know.
I would've liked to see it done with triangles... complex polygons just feels a bit like cheating. Not that it isn't super cool.
On reddit, someone posted another neat GA algorithm which evolves a car to match terrain:
http://www.wreck.devisland.net/ga/
One individual trying to improve itself isn't evolution, it's simulated annealing. Just because you call your parameters "DNA" it doesn't turn it into genetic programming.
Genetic programming requires a population and a crossover operation.
As someone who has written a few genetic algorithms for optimization in systems I've engineered, this really shows off the inherent power. Yeah, its not going to get a perfect answer, but sometimes its quicker and easier to get genetically optimized than to do the optimization by hand. After reading Selfish Gene and doing GA's, it really gave be an appreciation for the beauty of evolution and its mechanism.
Its not genetic programming because theres only phenotype being evaluated each generation(the image). If the algorithm had 10 individual sets that traded polygons somehow, with a tendency for the pictures closer to the Mona Lisa to get reproduction preference, then it would be genetic.
Evolution with a comparison function is called intelligent design. Here for example is the code snipped that created man (from the good book):
... ...
while(strcmp(image(man),image(god)))
{
free(man);
man=(man_t*)malloc(sizeof(man_t));
}
bless(man);
...you'll love Picbreeder: picbreeder.org
I did something very similar. Instead of random polygons, I used random circles. I would choose the best and then clone it... adding a random circle to each.
http://www.eigenfaces.com/
An interesting thing, I found, was to take a handful of low-quality creations and "average" them out. You end up with more detail.
Sorry, but this is hill climbing, pure and simple. The (very cool) result was achieved by introducing random changes ("mutations", if you like) into a "state" or "temporary solution" (the set of polygons), and keeping the new state only if it increases a target function (the similarity to a target image).
The name "genetic algorithm" is actually used for a more complex situation, more reminiscent of our own genetics: the algorithm maintains a pool of states or temporary solutions, selects two (or more) of them with probability proportional to their target-function score, and then randomly recombines them, possibly with "mutations", to generate a new state for the pool. A low-scoring state is probably removed, to keep the pool at constant size.
Quite possibly, a genetic algorithm would do an even better job here, as it could quickly find, for example, two states which each approximates a different half of the image.
I have hobby expertise in this subject. I've studied the subject in general, I have studied the math behind it, and I have programmed several evolving systems.
You always need a target.
Nope. Evolution works great even when you don't have the faintest clue what a successful "target" might look like. In fact evolutionary methods are most valuable exactly when you lack a lack a target and when you are unable to "intelligently design" a solution yourself.
The technical term for what you need is a 'fitness function'.
However even that overstates what you need. While it is convenient if you have a function to numerically evaluate fitness, all you really need is a comparison ability - some means of comparing individual A and individual B and selecting which on is "better", for any definition of "better". It doesn't even have to be an absolute or accurate comparison - all you need is some means of selection that chooses the "better" individual more than 50% of the time.
As for this article, it is a visually nice demo for introducing people to the subject, but in fact it uses one of the most limited and least powerful aspects of evolving processes. It is a simple asexual hillclimbing of a single individual.
Sexual recombination in an evolving population is almost infinitely more powerful. There's some deep mathematics behind the power of sexual recombination, but it is so powerful that essentially all species above bacteria have seized on it. Asexual reproduction has many obvious advantages and simplicity, but virtually all species abandon it whenever possible because sexual recombination is where the real power lies in evolution.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Had this consumer sheep instead opted to use a superior, Open Source operating system, then he could have posted the source code to Sourceforge or something similar, and had the community as a whole inspect the source.
What's stopping him from doing this using Windows?
This would have led to an algorithm that would have required less generations, and used less polygons.
Really? I never knew Windows caused bad algorithms.
I'm as anti-big corporation and anti-Microsoft as anyone I know, but I'm getting a little tired of these posts that have no thought added. .NET is about as close to open as anything that Microsoft has developed. Just because Microsoft didn't make Mono doesn't mean that they are against it... they just have no business reason to create something that the open source community can do.
.NET/Mono are excellent runtimes, and C# is a very good and powerful language. Multiple languages compile to the same bytecode so that practically anyone can jump in and start. And it gives a great alternative to Java.
All my liberal friends think I'm a conservative, all my conservative friends think I'm a liberal.