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.
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.
Evolution does not use a comparison function.
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 ?
Next time remember to tick "Post Anonymously"....
Did I forget something?
Wait...let me see if I've got this right.
1) Take a random group of polygons
2) Randomly change those polygons until they're more like the Mona Lisa
3) Repeat
And people are surprised that the end result is something that looks more like the Mona Lisa than when he started?
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);
As everyone else keeps saying, this isn't evolution. Evolution has no "end point" or supreme goal. We're not constantly getting better, per se.
It does seem fair to call this "survival of the fittest" though.
...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.
I think it's cheating to use convex polygons, why not use complex polygons then you could probably do it with 5 polygons?
“Common sense is not so common.” — Voltaire
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
Albeit, textured...
there is no way that code is gonna pass review.
Well, maybe. Who knows? I wonder what would happen if you allowed for catenaries... I mean, look at the top of her head.
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.
"Both beautiful to look at adn a striking way"
Pnu intended?
Rome taught me patience and assiduous application to detail. Virtues which temper the boldness of great, general views.
Citation needed.
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?
Ignore the ML evolving part, it's a population of polygons, the picture created by the polygons might not be evolving BUT...
/IANAB
The resulting picture could be compared to an ants nest where all the individual ants/polygons in a poulation work together to create something more than a pile of ants/polygons. Each of the million pictures in the program is analogous to an individual nest built by exactly one generation of polygons (a nest usually has one queen and dies when she does).
The overall structure and behaviour of the nests that ants build definitely changes over a long period of time in order to compete with other nests built and stocked with different ants. The populations of polygons competed with each other to fit their target environment. The question is: Is a single ants nest (the final Mona Lisa) analogous to an individual in an evolving population? If the answer is no, then why is it accepted that human culture evolves?
"it's simulated annealing"
As far as I can tell the Universe is some sort of (in)finite state machine, how anyone labels the progression and configuration of those states is kinda arbritrary but understandable with enough practice. I agree the concept of evolution may has a strict definition in biology but the concept of evolution also directly applies, or is useful in explaining, a wide range of systems that seem to be more than just the sum of their parts.
Dare I suggest that the concept of evolution has evolved since Darwin's time?
And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.
Yeah, you forgot to tick "Post Anonymously"...
Shouldn't you be filling man with data at some point ? I mean, with this design, there's no guarantee that it won't simply allocate/free the same memory block at each iteration, making no changes to the contents, leading to an infinite loop.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
Each generation is a population of 20. A given generation is a combination of a weighted breeding of the previous generation based on success plus some random mutation.
I ran it 3 times for a substantial amount of time. It always started from a population where most or all of the cars failed. It always evolved to one where most(all?) succeeded, in that they ran for the full ~10s without toppling and crashing. It was extremely effective, though it required a bit of patience.
One singular exceptional population member doesn't ensure that all of the next generation will be exception, we're not talking about cloning. You would expect it to be possible to have an aberration like that, but not necessarily common.
If I'm interpreting the plot correctly, the x axis is iteration and the y is the success metric. I'm assuming the lower line is the population average while the higher is the best of that generation. You can see both of them grow. On a population where you have one exceptional success, you see the one line spike high above the other.
At some point, it just gets a ^C and is declared "good enough"?
Explains quite a bit, I think...
It sounds like it is purely asexual reproduction with a single element per generation. There is no crossover operator and no fitness other than whether the product is closer to the known goal.
I'm gonna need a spec.
You can be sure that this "amazing" discovery will be touted in the newspapers as "using the breakthrough technique of Genetic Algorithms that uses human DNA to make computer think" (or some similar BS).
And when this guy actually does put together a proper GA, it will be ignored - because on the outside it's the same thing. Even though it will actually be interesting.
Genesis 1:32 And God typed
But I'm not a coward ;)
Evolution with a comparison function is called intelligent design.
That depends on the comparison function.
Pseudocode for the comparison function in natural evolution:
return (reproduces before dying)
http://facemaker.redshiftmedia.com/
Get real. Roger Alsing doesn't even exist. The algorithm wrote itself. Sheesh.
I haven't seen a more sound argument that evolution can go horribly wrong in a long time :-)
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
Sure it does. Evolution evaluates an organisms fitness in what turns out to be a binary function, "can you live long enough to reproduce?". This is equivalent, if somewhat abstracted to "if (fitness > minimumFitness)".
Regards
elFarto
Ah, but do you not see? The only explanation must be that God's malloc is buggy. It must be picking up different data each time, otherwise there would be no point in the comparison. The function searches the memory until eventually it comes up with something that matches God's image, i.e. "vmunix".
We can deduce from this that God's computer not only has a buggy C library but also poor memory protection between kernel and user space. Things have certainly improved in the past 6000 years!
The tao of democracy: the government you can vote for is not the real government.
It's not really binary, it's how many times you reproduce before you die.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
What's the value of man before the first iteration of the loop?
Boy: Do not try and search for the code, instead realize the truth.
Geek: What truth ?
Boy: There is no code.
Geek: There is no code !!! ?
Boy: Then you'll see, itt is not the code that produces Monalisa, it is only your mind.
If you don't succeed at first, try again. If you still don't succeed, try harder. If nothing works, try reality shows.
while(strcmp(image(man),image(god)))
{
free(man);
man=(man_t*)malloc(sizeof(man_t));
}
bless(man);
bless: fatal error 42 - man is null.
What you don't think God would check his return codes?
These posts express my own personal views, not those of my employer
As malloc is not required to clear the memory it returns, it not doing so does not make it buggy. If it was calloc, then yes, it would be buggy; but for malloc, the only requirement is that the returned memory chunk has the size given to malloc.
And no, there is no point in the comparison. The code is buggy, as it relies on undocumented (and unlikely) assumptions about how malloc works.
But we're still using C, and enjoying all the "clever" hacks l33t c0d3rs come up with to avoid writing a few lines of code :(.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
chimp
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.
Finally we have definitive proof that the Mona Lisa evolved from simple polygons instead of being "intelligently designed" by that fictional Leonardo guy.
Support Right To Repair Legislation.
No, you're just a 13 year old tit. Go back to digg.
Evolution is about competition, and ultimately about the long term not the short term. so...
1) It's not about meeting any fixed threshold of fitness (although obviously you leave to leave a least one descendent to still be in the game), but rather about how your fitness compares to the rest of the population. If you're fitter than average then the percentage of your DNA will be increasing in the communal genepool, else it will be decreasing.
2) Evolution is optimizing long term success rather than short term success. It doesn't matter how many descendents you directly leave if they all die out in a few generations, but alternatively you may only leave a few descendents that then become incredibly successful in the future. Note Homo Sapiens "Genetic Eve" for example, or similar evolutionary bottlenecks... the reproductive success of all females predating her, but not on her bloodline, was ultimately for nought (you could say they were climbing a local fitness peak, while Genetic Eve was ascending a higher one that ended up assuring her survival).
Doesn't God create man in his own image with execve()?
I am TheRaven on Soylent News
This is really cool. Does somebody know a good (introductory) book on genetic algorithms?
So now rocks and paintings are alive? Where's my wing-flapping flying car?
"Evolution is about competition"
No, competition is usually involved, but evolution isn't about competition.
"Evolution is optimizing . . . success"
See, that's different than your opening statement.
". . . the reproductive success of all females predating her ["Genetic Eve"], but not on her bloodline . . "
There you show a lack of understanding about the mitochondrial inheritance (hint: it's failure doesn't preclude the chromosal DNA from being successful) and the statistical nature of cladistic "evidence" speculating on generations past.
And that's why it took much longer to evolve from Australopitecus to Homo Sapiens than it took to get from stone age to space age. Human technology evolves by intelligent design, not just by exchanging random genes.
When two organisms reproduce, their chromosomes get mixed at random, there's no selection for the best genes from each. When two technology products are merged, the best parts from each are selected.
This isn't an example of evolution in action; this is closer to a simulated annealing because there is a set goal - make a set of transparent polygons look like the target image. Mutate-and-iterate is not enough to make this evolutionary.
Evolution does not have a stringent end-goal - there is no finish line, and no qualification of perfection. Evolutionary algorithms must merely out-compete their peers and survive for the next round.
That doesn't make the article bad - the idea is interesting and the results are impressive. However, whoever titled this Evolution is clearly confused.
Cheers,
Toby Haynes
Anything I post is strictly my own thoughts and doesn't necessarily have anything to do with the opinions of IBM.
sizeof(man_t)
I hear that value gets exaggerated a lot, though, and others have declared it as irrelevant.
who thinks the Mona Lisa is a crappy painting? I've never understood why it's regarded as one of the best ever made. The girl is not attractive and nothing about the image seems revolutionary compared to other works of the time. What is supposed to make it the best ever?
For my master's thesis, I wrote up a GA that evolved Neural Networks that controlled embodied agents in a virtual reality.
Though the scope of GA's and Evolutionary Algorithm's is somewhat limited, within their domain they can be quite powerful, as attested to the video's linked above and the OP. Developing a fluid/lifelike control system for virtual creatures or a system that approximates images without the benefit of Evolutionary Algorithms would likely require much more code.
O.K., this is bogus.
If the images he is creating are 200x200 then it would take
a similar number of iterations just to methodically move polygons
and perform correlation calculation between source and destination
images. Genetic algo or not, it's not an accomplishment unless
he's trying to prove that genetic algorithms are a pile of crap.
People get so excited over pretty pictures that their brains turn off
completely.
ftfa: So what do you think?
She still wouldn't date someone on /.
Having to work for a living is the root of all evil.
animated
http://s488.photobucket.com/albums/rr245/solstitium/?action=view¤t=MonaLisa.gif
[ No prescription needed ]
Oh, there's a lot of words that are completely fucked-up. What about the use of "prolly" instead of "probably?" That's one I could do without, ironic use in the title notwithstanding.
I thought the interntubes were supposed to make people more literate?
As malloc is not required to clear the memory it returns, it not doing so does not make it buggy. If it was calloc, then yes, it would be buggy; but for malloc, the only requirement is that the returned memory chunk has the size given to malloc.
This is true; what I mean by "buggy" is that malloc isn't returning the area of memory that was recently freed, but rather progressing through the available memory space, hence obtaining different data each time. I'm implying that free isn't working, or maybe...
Hang on a minute, this whole thread is based on a very silly premise. It's time to stop talking :).
The tao of democracy: the government you can vote for is not the real government.
I would have to agree. This project assumes that genetic evolution knows what it wants to be ahead of time. And that would support the idea that we were all somehow designed.
But it serves as a good illustration for how random organization COULD organize, so if we imagine that a person with 3 legs was not as symmetric as a person with 2 legs, and therefore not similar enough to an ideal prey (that could escape a predator), then this could serve as an analogy. I.e. the tiger, having already evolved the ability to eat anyone who doesn't look like mona lisa, results in only an image that looks like mona lisa being safe.
You idiot, everyone knows that God used Perl.
Even bacteria don't just rely on mutation. They exchange genes, both with closely related and more distantly related bacteria.
When can we expect the xscreensaver graphics hack to draw our images?
I think the point the OP was making is that evolution is blind and thus cannot predict or determine the desired future state of a population. Therefore, it cannot use a comparison function to decide whether or not current results are approaching a desired future state. This is what the Mona Lisa program is doing and this is the reason it is not evolution in the Darwinian sense.
Some of the earlier generations start to resemble the finished product if you squint hard. For styles that deliberately distort and obfuscate, some of these might be more desirable than the finished product. This might be a way to take a photograph and turn it into cubist art "automagically".
Mal-2
How is the Riemann zeta function like Trump rallies? Both have an endless number of trivial zeros.
No, competition is usually involved, but evolution isn't about competition.
Wrong. It's competition (more fit wins) that introduces the population bias towards greater fitness. Without competition you've just got a single random walk who's direction is unrelated to fitness.
This could be a hoax. Take the mona lisa image and slowly fuck it up backwards and then show the images in the reverse order.
Are slashdotters so guilible?