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

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

If you like this story...

[greg_barton]

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

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