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."
Awesome. That is all.
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/
Wont evolution speed up as the organism becomes more complex ? It took over a billion years for a single cell to evolve into a complex organism. But it took only 30000 years for us to jump from cave paintings to space travel. Do such leaps happen in such evolutionary algorithms ?
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.
No, we are not surprised. Some of us are just wondering about practical implementations. ...?
1) Image compression
2) Games (video cards use polygons to render 3D scenes, right?)
3)
The thing I'm also wondering is, is the output better or worse than a expert algorithm? Could the output of a expert algorithm be used as the input to get this genetic algorithm a head-start?
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.
Genetic algo's are a great thing to do at home. I've been tinkering with Avida for the last few days, trying to get these programs to grow instead of shrink. Maybe they will gain some kind of structures then.
http://devolab.cse.msu.edu/
See also
http://www.framsticks.com/
http://www.stellaralchemy.com/lee/virtual_creatures.html
http://www.spiderland.org/
Any of which are fun if you get them going. The joy in these things is sort of in tuning them. But I think a lot lately about GA's on GA's to adjust the parameters within certain windows. A lot of these models aren't open-ended enough to demonstrate intelligence. But you never know. Check out Polyworld, Achilles, and Critterding, too, if you're in Linux
Could this be used as a new way to compress pictures? I would guess the compression itself would be computationally expensive, but the compression would be amazing.
Yes, I'm left. You have a problem with that?
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.
Real world application?
At our Faculty (www.fer.hr), reservations for "lab practices" is done via genetic algorithms. It's kinda hard to assemble over 500 people for your class to be assigned times when they don't have any other class (there are numerous combinations of classes one can take), and to reduce the time which they have to wait after their last class ends before they are meant to go to the "lab practice".
In case I didn't make much sense -- optimal schedules for students!
GA's can find some very bad solutions to poorly created problems. I once used a GA to solve a combat problem where the problem, meaning the evaluation function, was largely based on the length of the combat. Unfortunately, the solution it found was to kill it's own side, and the combat was over almost immediately.
There's usually a simple heuristic (for example, nearest neighbor for TSP) that does better than a random. You should check your GA solution compared to the heuristic to make sure that it's not doing something completely stupid.
The more people I meet, the better I like my dog.
WORD!
I know there's no good karma to be had here (both figuratively and literally) by going after someone else's grammar, or by replying to a post rated zero. But I'm going to throw my lot in with the parent. The proliferation of misuses of "its" and "it's" is accelerating. I saw a post on WSJ the other day that corrected the writer of the article on this matter, only the correction was incorrect!
-t.