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.

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

[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

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

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

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.

Re:Any GA implementation.. woo

[QuantumG]

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

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

[Bob-taro]

Vi is divine. Emacs is the work of man.

vivivi is the editor of the beast.