Slashdot Log In
Evolution of Mona Lisa Via Genetic Programming
Posted by
kdawson
on Tue Dec 09, 2008 02:07 AM
from the but-the-target-was-given dept.
from the but-the-target-was-given dept.
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."
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Source code (Score:5, Insightful)
Is the source code available for this? It'd be a fun project to learn from and play around with.
Re:Source code (Score:5, Informative)
He says in the comments [rogeralsing.com] that he's supposed to release the source today.
The source is apparently C# using .NET 3.5, so might take a bit of work to get running under e.g. Mono, should you be on a non-Windows platform.
Parent
Feeding the troll... (Score:5, Insightful)
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.
Parent
Re:Feeding the troll... (Score:5, Funny)
And it gives a great alternative to Java.
I have a great alternative to being burned alive. It's being beaten to death with a baseball bat.
Parent
Re: (Score:3, Funny)
Yes, the whole thing would have been FAR more accessible as a 40000 character perl regex.
Dumbass, go troll your anti-ms propaganda elsewhere :-(
Re:Source code (Score:4, Funny)
Yes, the whole thing would have been FAR more accessible as a 40000 character perl regex.
Dumbass, go troll your anti-ms propaganda elsewhere :-(
Yeah, but it'd be like 5 lines in Python... ;)
Parent
Any GA implementation.. woo (Score:5, Funny)
Genetic Algorithms are like the AI equivalent of text editors... everybody has spent a weekend writing one at some point.
Re:Any GA implementation.. woo (Score:5, Funny)
Parent
Re:Any GA implementation.. woo (Score:5, Funny)
umm, Knuth didn't write vi, Bill Joy did.
Parent
Re: (Score:3, Funny)
Re:Any GA implementation.. woo (Score:5, Funny)
Knuth uses pen, paper and toggle switches.. the way it's meant to be done.
Parent
Re:Any GA implementation.. woo (Score:4, Funny)
Parent
Re:Any GA implementation.. woo (Score:5, Funny)
Vi is divine. Emacs is the work of man.
vivivi is the editor of the beast.
Parent
Re: (Score:3, Funny)
Re:Any GA implementation.. woo (Score:4, Funny)
Be sure to write your own LISP interpreter too.
Parent
Re: (Score:3, Informative)
One way to boost complexity is to evolve programs.. or neural networks, if you're that way inclined. One way to speed up the evolutionary process is to use probabilistic modeling to produce offspring.. it's must more efficient than just random mutation. See http://www.opencog.org/wiki/MOSES [opencog.org]. Eventually, though, you will reach limits to blind search. At that point you need to complement it with logic. See http://www.opencog.org/wiki/PLN [opencog.org]. And to focus your search you really need some kind of attention a
Re:Any GA implementation.. woo (Score:4, Interesting)
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!
Parent
Triangles (Score:5, Interesting)
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/ [devisland.net]
Re:Triangles (Score:5, Funny)
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
Here it is done with 914400 tiny coloured pixe^H^H^H^Hrectangles:
http://avline.abacusline.co.uk/pictures/jpeg/pics/mona.jpg [abacusline.co.uk]
Parent
Re:Triangles (Score:5, Interesting)
Which brings us to a real use for this kind of thing. Depending on how fast it runs, it could be an interesting form of image compression. 50 polygons is generally a lot less data than 914400 rectangles. For higher quality, you could add more polygons. You then get a resolution-independent version of the original image with some loss of quality. I'm not sure if it's more interesting than topology-based compression, but it's certainly an interesting avenue.
Parent
Re:Triangles (Score:5, Informative)
It does.. for every generation it makes 20 mutations.. so you're seeing each of those 20 mutations run. Takes a while just for one generation to complete.
Parent
Re: (Score:3, Insightful)
Re: (Score:3, Interesting)
it seems pretty random actually (i've run the program like 4-5 times). sometimes it starts off slow and then gets a little better. but sometimes it starts off with a really good design and then just gets worse. it seems pretty random overall.
the point of genetic evolution is for there to be progressive enhancements. it's not just randomly throwing the dice over and over again. you have to retain the positive enhancements of past iterations for it to "evolve." you could run this program all day long and it'l
It makes a lot of sense to me (Score:3, Informative)
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 populat
Re: (Score:3, Insightful)
I'm sorry, but you're completely wrong. Did you even run this program? Did you notice the messages about selection and crossover, which show that it doesn't throw out all the previous data? Or the graphs that clearly demonstrate the performance of the car improving?
After running it for a while, the cars appear to get kille
Re:Triangles (Score:5, Informative)
the point of genetic evolution is for there to be progressive enhancements. it's not just randomly throwing the dice over and over again. you have to retain the positive enhancements of past iterations for it to "evolve."
Not entirely true. Let's get back to basics, and hill-climbing algorithms.
You have a robot and a hill, and you program the robot to always take the steepest uphill slope possible. That's progressive enhancement -- it's always getting "better" (higher).
Except for one type of thing: local maxima.
You see, most hills have more than one summit.
So if the robot ends up on a lower, secondary summit, it will refuse to go down, as it must get better/higher with each step.
But logically, to get from a lower peak to a higher one, you have to descent a short distance and then start ascending the true summit.
Any search strategy has to account for local maxima and other dead ends, and in GA and other evolutionary algorithms, these means introducing the possibility that children are less optimal than their parent iterations.
HAL.
Parent
Re: (Score:3, Insightful)
Re: (Score:3, Insightful)
All these things are good, mind.
Re: (Score:3, Insightful)
Why does it do that? You could say that its a "survival instinct" or that those that don't reproduce better are overwhelmed and annihilated by those that do, but why does that happen? Why must living things always be driven by the need to reproduce? We're on a ball of rock, heat, gas and liquid that revolves around a ball of fusion energy. Why must life propel itself into existing?
this sounds like a variation on the anthropic principle. "isn't it amazing that almost all the living things around us happen to be like/decended-from the ones which happened to be driven to reproduce and as a result had the most kids... this must surely be proof that a god designed the universe"
I think Zero Punctuation said it best. It's a little odd that people believe that we were created in the image of god despite the fact that when you put most humans in a similar position of absolute power over an ar
Not genetic programming (Score:5, Informative)
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.
Re:Not genetic programming (Score:5, Informative)
Parent
Re:Not genetic programming (Score:5, Informative)
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.
But doesn't simulated annealing involve quenching? That is, there's a "temperature" of the system. High temperature means states are more likely to make big random jumps to far from optimal states. Low temperature means the jumps are shorter and more optimal is strongly prefered. Here's what I dimly recall. As the temperature declines, the more fit states become higher prefered. If you cool too rapidly (there is a mathematical view in which that statement makes sense), you risk getting stuck in a suboptimal extreme state. But cooling at a rate of time to the -0.5 power settles to a optimal state as long as the optimal state is isolated, I think. In comparison, the algorithm of the story appears to be constant temperature with respect to time.
Another aspect of simulated annealing is that it doesn't take the best fit at each generation. By randomly mutating at each step and lowering the temperature slowly as above (and making more optimal states increasingly prefered), the problem naturally settles to an optimal state. In comparison, the algorithm mentioned in the story takes the best fit at each generation.
It appears to me not to fit very well in the viewpoint of simulated annealing.
Parent
Re:Not genetic programming (Score:4, Informative)
that depends on what you mean by "population." if by population you simply mean variation, then yes. that's required. but if by population you mean a set of concurrent genetic lineages and breeding individuals then, no, that isn't required. that may be required in biological evolution, but that's an incidental result.
at its core, all evolution really is is directed randomness. biological evolution requires large populations only because sexual selection necessitates it. but non-biological evolution (like the evolution of ideas, designs, language, etc.) do not entail sexual selection.
one good example of this, interestingly enough, is the design process used by an aeronautics engineer to design airfoils in a documentary i saw a while back. he basically described how he started with a rough wing shape and measured its flight characteristics (lift, drag, etc.) and then created a handful of random variations each with a slightly different shape/cambers and angle of attack. he'd then test each of the variations and pick the best one to repeat the process with. there's no crossover operation or horizontal gene transfer, but it still demonstrates the basic principles of evolution, such as evolutionary selection and cumulative/incremental changes.
Parent
Brilliant! (Score:3, Insightful)
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?
Re: (Score:3, Insightful)
he was trying to evolve to fit a required pattern, this is fairly standard GA stuff.
You always need a target.
Also, its damn cool.
Re:Brilliant! (Score:5, Interesting)
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.
-
Parent
Re: (Score:3, Funny)
Shit, I always just say "want to go up to my room to see my etchings?" Good to hear what lines my competition is using!
Re: (Score:3, Insightful)
It's cool because of a few reasons.
Not genetic, still a good demonstration (Score:5, Interesting)
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.
Re:Not genetic, still a good demonstration (Score:4, Interesting)
Parent
If you like this story... (Score:5, Informative)
...you'll love Picbreeder: picbreeder.org [picbreeder.org]
A similar project (Score:5, Interesting)
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/ [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.
Re:A similar project (Score:5, Interesting)
Oh... I forgot to mention. I also tried it against some video. It seems that by adding motion, you percieve even more detail. This is about 20 frames with a resolution of about 1000 generations each.
http://www.eigenfaces.com/img/morphs/anim-100x20.gif [eigenfaces.com]
This was all done with Python / Pygame. A great little package for those who are keen to dabble
Parent
Re: (Score:3, Interesting)
Since the circles are getting iteratively smaller, doesn't this ultimately amount to just guessing the value of the pixels?
Where the polygon Mona Lisa could be compressed to an extremely small number of points, yours is layer upon layer of color data, right?
Wouldn't a more equivalent approach be to weigh the value of the circles on their apparent size; bigger being more valuable?
convex polygons? please (Score:3, Informative)
I think it's cheating to use convex polygons, why not use complex polygons then you could probably do it with 5 polygons?
This is not a "genetic algorithm" (Score:5, Informative)
Sorry, but this is hill climbing [wikipedia.org], 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" [wikipedia.org] 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.
image compression (Score:4, Interesting)
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.
Definitive proof (Score:4, Funny)
Re:Pretty Cool But Not Evolution in the Usual Sens (Score:5, Funny)
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);
Parent
Re: (Score:3, Insightful)
Then life would have stopped with bacteria.