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."

Comments

Source code

[Anonymous Coward]

Is the source code available for this? It'd be a fun project to learn from and play around with.

Re:Source code

[elvstone]

He says in the comments 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.

Re:Source code

[daveime]

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

[darkpixel2k]

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:Source code

[darkpixel2k]

Yeah, but it'd be like 5 lines in Python... ;)

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:Source code

[neomunk]

Calm down, Emacs is getting a macro for it too!

Any GA implementation.. woo

[QuantumG]

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

[martin-boundary]

And afterwards it's just like the creationism vs evolution debate... everybody wonders what God was thinking when he wrote vi.

Re:Any GA implementation.. woo

[Swizec]

Damn it! I'm lagging behind because I've done neither. FUCK. *rushes out of the office to go rot at home coding stuff nobody needs*

Re:Any GA implementation.. woo

[QuantumG]

Be sure to write your own LISP interpreter too.

Re:Any GA implementation.. woo

[QuantumG]

umm, Knuth didn't write vi, Bill Joy did.

Re:Any GA implementation.. woo

[QuantumG]

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. 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. And to focus your search you really need some kind of attention allocation. See http://www.opencog.org/wiki/Attention_allocation. An integrative approach means you can solve real world applications with modest hardware.

Re:Any GA implementation.. woo

[martin-boundary]

Heretic! You think Bill Joy isn't God! Everyone knows that Knuth uses Emacs, you heathen.

Re:Any GA implementation.. woo

[QuantumG]

Knuth uses pen, paper and toggle switches.. the way it's meant to be done.

Re:Any GA implementation.. woo

[ivucica]

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:Any GA implementation.. woo

[TheRaven64]

Nietzsche said 'God is dead,' which eliminates both Knuth and Joy. Obviously God is Dijkstra.

Re:Any GA implementation.. woo

[Bob-taro]

Vi is divine. Emacs is the work of man.

vivivi is the editor of the beast.

Re:Any GA implementation.. woo

[Beezlebub33]

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.

Triangles

[prockcore]

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/

Re:Triangles

[ThatsNotFunny]

Dorito Lisa?

Re:Triangles

[prockcore]

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:Triangles

[iVasto]

Just let it run for a while. In the beginning the car was always tipping over, after a few minutes the car will consistently travel across the terrain. I'm assuming that if I let it run for longer it will keep going farther and farther.

Re:Triangles

[lysergic.acid]

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'll never get better than it was during the first 10 generations. that's because every time it mutates it throws out all the previous data. it's just non-directed randomness.

Re:Triangles

[mweather]

Real evolution works similarly, only instead of checking a source image, it checks whether you're more likely to reproduce. He simply changed the criteria.

Re:Triangles

[syousef]

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

Re:Triangles

[jibjibjib]

you could run this program all day long and it'll never get better than it was during the first 10 generations. that's because every time it mutates it throws out all the previous data

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 killed without colliding with anything, so I'm assuming this is because there's some time or distance limit on each run. That's why the evolution appears to stop after ~10 generations.

Re:Triangles

[LordLucless]

Since we developed medicine. It is very rare now that humans as individuals are eliminated from the gene pool due to poor adaptation to their environments. With the aid of modern medicine, people with genetic disabilities are able to often live relatively normal lives, and reproduce. Birth control means that being succesfully sexually doesn't necessitate being successfully reproductively. The human gene pool is not being filtered by adaptiveness to the environment anymore.

All these things are good, mind. It just means that we're not evolving due to natural selection. We're guiding our own progress. Which is good, cause the old way is slow as hell.

Re:Triangles

[oojah]

I think it's got a fixed time limit rather than a distance limit. This should mean that it selects for speed as well as ability to cross the terrain. Pretty neat either way!

Re:Triangles

[Half-pint HAL]

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:Triangles

[TheRaven64]

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:Triangles

[HungryHobo]

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 artifical world with some kinds of simulated life in it they consider the beings within less as things to be loved and cared for and more as TARGETS.

I love Alife simulations, I've even tried writing my own with little environments but in the end I always seem to get bored and start blasting them or infecting them with some kind of plague to liven things up a bit.I'd prefer a universe without any god resembling people like me.

Not genetic programming

[Anonymous Coward]

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

[usul294]

It doesn't necessarily require crossover, asexual reproduction that selects based on merit and uses mutation will have an evolving population, though generally not as fast as with crossover.

Re:Not genetic programming

[khallow]

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:Not genetic programming

[lysergic.acid]

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.

A million generations..

[crimzunblu]

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 ?

Re:A million generations..

[aiht]

The leap from cave paintings to space travel is trivial compared to the leap from bacteria to mammal.
We're so used to being multi-cellular that we take it for granted - but space travel is still a novelty.

Brilliant!

[evanbro]

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?

Re:Brilliant!

[GravityStar]

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?

Re:Brilliant!

[thermian]

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!

[lena_10326]

1) Image compression

It's cool because of a few reasons.

• 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
• the GP is a dork

Re:Brilliant!

[Alsee]

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:Brilliant!

[Anonymous Coward]

• it uses straight edged polygons as opposed...

...as opposed to these beer drinking, promiscuous polygons.

Re:Brilliant!

[Chapter80]

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.

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!

Not genetic, still a good demonstration

[usul294]

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.

Re:Not genetic, still a good demonstration

[khallow]

Yea, I was wondering why it took a million generations. But since he's just mutating, it makes sense. It'll be interesting to see what sort of speed up he gets from proper genetic programming.

Re:Not genetic, still a good demonstration

[lkeagle]

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.

By mimicking biological evolution, it adds the ability to effectively climb several 'hills' simultaneously, as well as explore new 'hills'. This increases the probability that one of these hills has the highest 'peak'. Without that randomness, the population would never leave the hills they are on, and would almost certainly miss an optimal solution if it existed on another hill.

If your system failed to converge, I would hesitate to blame the GA. It's more likely that your parameters for how much randomness (mutation, crossover) you used in the system was far too large in proportion to your population size.

Re:Pretty Cool But Not Evolution in the Usual Sens

[Roland Piquepaille]

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); ...

If you like this story...

[greg_barton]

...you'll love Picbreeder: picbreeder.org

A similar project

[dmomo]

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.

Re:A similar project

[dmomo]

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

This was all done with Python / Pygame. A great little package for those who are keen to dabble

Re:A similar project

[soniCron88]

Seems like a fun project, but...

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:A similar project

[dmomo]

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 comes down to it... I simply like the way the circles look!

One thing the Mona Lisa example does that I will probably now try is the ability to make arbitrary polygons. Right now, mine are all "regular" polygons: square, triangle, pentagon, hex, octagon, etc.

I was never really concerned with compression so much as the idea, to be honest. Like yours did, my gut tells me the Mona Lisa would indeed compress better. But where one unit is "n points (x,y for each), color, alpha" on the Mona Lisa example, mine is just: x,y,radius,color, alpha.

convex polygons? please

[OrangeTide]

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"

[haggais]

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.

image compression

[polar red]

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:First

[Anonymous Coward]

Yeah, you forgot to tick "Post Anonymously"...

It makes a lot of sense to me

[Anonymous Coward]

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.

Re:Survival of the Fittest

[bmgoau]

Then life would have stopped with bacteria.

Feeding the troll...

[bondsbw]

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...

[darkpixel2k]

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:Feeding the troll...

[tristanreid]

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.

Definitive proof

[Comboman]

Finally we have definitive proof that the Mona Lisa evolved from simple polygons instead of being "intelligently designed" by that fictional Leonardo guy.

Re:Survival of the Fittest

[PhilHibbs]

It did. We're just a very complex bacteria colony.

So what do you think?

[sgt scrub]

ftfa: So what do you think?

She still wouldn't date someone on /.