Evolution of Mona Lisa Via Genetic Programming 326
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."
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.
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.
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.
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... ;)
Re: (Score:3, Funny)
It'll be a single function call in the next Mathematica release :)
Hey--this is slashdot. You can't talk about proprietary software in here unless you are bashing it! Hand in your geek card.
Re: (Score:3, Funny)
Calm down, Emacs is getting a macro for it too!
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)
Re:Any GA implementation.. woo (Score:5, Funny)
umm, Knuth didn't write vi, Bill Joy did.
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.
Re:Any GA implementation.. woo (Score:4, Funny)
Re:Any GA implementation.. woo (Score:5, Funny)
Vi is divine. Emacs is the work of man.
vivivi is the editor of the beast.
Re: (Score:3, Funny)
Re:Any GA implementation.. woo (Score:4, Funny)
Be sure to write your own LISP interpreter too.
Re: (Score:2)
The main thing you learn from GAs is that we know a lot already and to get useful information from a simulation it has to be VERY complex. Finding a sensible fitness measure is often a big problem too. It can be a good idea to set up two or more different populations and ha
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!
Re: (Score:3, Interesting)
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
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: (Score:2, Funny)
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]
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.
Re: (Score:2)
hmmm, it is time to stop trying to beat records at Xmoto.
Re: (Score:2)
On reddit, someone posted another neat GA algorithm which evolves a car to match terrain:
http://www.wreck.devisland.net/ga/ [devisland.net]
Nice. Just we just need to cross that with Fantastic Contraption [fantasticcontraption.com] and we might get some really strange solutions to the puzzles!
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.
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.
Re: (Score:3, Insightful)
Re: (Score:2)
Either that, or idiocracy is right.
Your incredibly flawed reasoning proves your point (Score:2)
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)
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.
Re: (Score:2)
So this is basically what, stochastic hill climbing? Now I'm really curious to see how a real genetic algorithm would perform here.
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.
Meta-evolution? (Score:2)
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
"Computer Paints Mona Lisa" (Score:2)
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.
A million generations.. (Score:2, Interesting)
Re: (Score:2, Insightful)
We're so used to being multi-cellular that we take it for granted - but space travel is still a novelty.
Re: (Score:2)
Humans have pretty much short-circuited traditional evolution due to our very heavy reliance on learned information. It's sort of like suddenly switching your genetic algorithm from a Pentium 1 to a modern super computer. Regular evolution using DNA gets slower as an organism becomes more complex, for a variety of reasons. A bacteria can, for example, evolve immunity to antibiotics in weeks while it'd take humans centuries to evolve an even minor resistance to a disease.
Re: (Score:2)
Do such leaps happen in such evolutionary algorithms ? - Yes, the 'leaps' concept is called punctuated equilibrium [wikipedia.org].
Re: (Score:2)
You are confusing biological evolution with cultural development. While there are enough parallels that the latter is sometimes even referred to as "social evolution" or similar phrases, they are entirely different things. And yes,
Re: (Score:2)
Space travel took no evolution at all. Humans didn't adapt to space travel in order to survive, nor did their intelligence increase enabling to 'invent' space travel.
Basically you can take a baby from cavemen and raise it to be a modern human being.
That's because there's been little evolutionary pressure on mankind to evolve into something slightly different in order to have a slightly better chance of survival/reproduction.
Chances are the cavemen baby will die of disease we're now all imune to though
Re: (Score:2)
All the time apparently. Typically in the evolutionary algorithms I have seen, the solution will march along making only slight improvements for a few generations then, "Boom!", makes a big order of magnitude or greater improvement in one or two generations, then settles down to incremental improvements again.
This page [geneura.ugr.es] has a good graph of the behavior I'm talking about, as well as some code snippets.
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:2, Interesting)
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?
Re: (Score:3, Insightful)
It's cool because of a few reasons.
Re: (Score:2)
* it's overlapping polygons for maximal reuse of corners
* it uses straight edged polygons as opposed to bezier edges, lines are computationally simpler to rasterize
* it's yielding some mad compression
To get a natural looking picture with as little data as possible, shouldn't it skip the straight edged polygons though? I can see how rendering is simpler this way, making for some interesting possibilities with moving / shape changing polygons for ultra-co
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: (Score:2)
Also, its damn cool.
Oh yeah? Let's see how many iterations it needs to get an image of Kevin Bacon!
Re: (Score:2)
Ummm.. totally wild guess here... 6?
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.
-
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:2)
Re: (Score:2)
When I'm done building my gadget, it doesn't hit the front page of Slashdot. So I do see GP's point.
But it did manage to generate a fair number of comments. It's held my interest, for one.
And simplicity of algorithm doesn't make it any less cool. Take z=zz+c [wikipedia.org], for instance.
Re: (Score:2)
Re: (Score:2)
No quite right. You need:
2a) Randomly change those polygons for a number of copies
2b) Choose the "fittest" group based on its likeness to the Mona Lisa.
Natural selection of random mutation is what is going on here. Just Random mutation will simply get you a random result.
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)
Re: (Score:2)
I prefer the one where the researcher evolved a speech recognizer out of FPGAs, and the result took advantage of the nonlinearities inherent in the line of FPGAs he used.
Re: (Score:2)
Re: (Score:2)
Yeah, but you have to spend all that time learning (shudder) calculus... and for what? So you can solve the problem efficiently and in a way which explicitly makes use of structure in the problem statement, instead of ZOMG TEH MAGIC GENETIC BLINDWATCHMAKER DARWIN C0DE?!
Like seriously, why would anyone learn all that hard math just so they can make their project sound less 'leet? I mean which of these sounds more badass: "genetic programming" or "regularized energy minimization"?
Re: (Score:2, Insightful)
The power of GA's, and of most AI research that has ever led to anything useful, is simply to search through spaces that are too large for brute force or heuristic algorithms to cover exhaustively. GA's work very well for optimizing problems with large numbers of dimensions, but in the end, it's just a hill climbing algorithm, albeit a really cool one. In this regard, you're right. We usually only use GA's when we have no clue how to optimize a complicated multi-variable problem using standard algorithms
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
Re: (Score:2)
Re: (Score:2)
Nice! The circles look sorta like bokeh, which feels natural to the eye.
I wonder how a neural approach would fare using the same basic rendering emthod...
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?
Re: (Score:3, Interesting)
Yes indeed. It turns out the more detailed things get, the smaller the circles get. Obviously. I set the software so that the minimum circle radius is larger than a pixel. Because of the alpha blending, color is not determined by just the circle, but also the overlap of other circles.
The first experiment I did was to actually randomize all pixels... and mutate a different pixel in each child. Not as nice as the circles. BTW, the code can just as well draw polygons. I made one with triangles. When it
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?
Re: (Score:2)
Re: (Score:2)
convex polygons at least have some mathematical properties that make them easier to handle.
For example you can more easily determine wether a given point is inside the polygon or not.
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.
Misspelling? (Score:2)
"Both beautiful to look at adn a striking way"
Pnu intended?
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
I thought so too.
It should even be possible to use postscript as the storage format for this compressed picture
Asexual (Score:2)
Definitive proof (Score:4, Funny)
So what do you think? (Score:3, Funny)
ftfa: So what do you think?
She still wouldn't date someone on /.
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);
Re: (Score:2)
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.
Re: (Score:2)
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)
Re: (Score:2)
That's why it was released into the wild without SQA testing.
-dZ.
Re: (Score:2)
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
Re: (Score:2)
Re: (Score:3, Insightful)
Then life would have stopped with bacteria.
Re: (Score:3, Insightful)
It did. We're just a very complex bacteria colony.
Re: (Score:2, Funny)