Forgot your password?
typodupeerror
Programming Graphics Software IT Technology

Evolution of Mona Lisa Via Genetic Programming 326

Posted by kdawson
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."
This discussion has been archived. No new comments can be posted.

Evolution of Mona Lisa Via Genetic Programming

Comments Filter:
  • Source code (Score:5, Insightful)

    by Anonymous Coward on Tuesday December 09, 2008 @02:15AM (#26043843)

    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)

      by elvstone (86513) on Tuesday December 09, 2008 @04:29AM (#26044385) Homepage Journal

      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.

  • by QuantumG (50515) * <qg@biodome.org> on Tuesday December 09, 2008 @02:15AM (#26043845) Homepage Journal

    Genetic Algorithms are like the AI equivalent of text editors... everybody has spent a weekend writing one at some point.

  • Triangles (Score:5, Interesting)

    by prockcore (543967) on Tuesday December 09, 2008 @02:19AM (#26043863)

    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)

      by ThatsNotFunny (775189)
      Dorito Lisa?
    • by syousef (465911) on Tuesday December 09, 2008 @03:17AM (#26044123) Journal

      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)

        by TheRaven64 (641858) on Tuesday December 09, 2008 @10:17AM (#26046061) Journal

        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.

    • by pato101 (851725)

      On reddit, someone posted another neat GA algorithm which evolves a car to match terrain:

      hmmm, it is time to stop trying to beat records at Xmoto.

    • by N Monkey (313423)

      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!

  • by Anonymous Coward on Tuesday December 09, 2008 @02:22AM (#26043871)

    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.

    • by usul294 (1163169) on Tuesday December 09, 2008 @02:41AM (#26043961)
      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.
    • by khallow (566160) on Tuesday December 09, 2008 @03:24AM (#26044141)

      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.

      • by glwtta (532858)
        Yeah, it's not SA either. I think the problem is that he isn't actually doing any kind of optimization, or anything to avoid local minima (though he doesn't mention how the "DNA" is "mutated" so it's hard to say how much of a problem that is here).

        So this is basically what, stochastic hill climbing? Now I'm really curious to see how a real genetic algorithm would perform here.
    • by lysergic.acid (845423) on Tuesday December 09, 2008 @03:49AM (#26044229) Homepage

      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.

    • Ignore the ML evolving part, it's a population of polygons, the picture created by the polygons might not be evolving BUT...

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

  • 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: (Score:2, Insightful)

      by aiht (1017790)
      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.
    • by Rakishi (759894)

      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.

    • Not disputing the evolutionary signifigance of technology but when you compare the complexity of the cell colony (complex organisim) to the complexity within the cells [youtube.com], the organanisim may be the simpler of the two levels.

      Do such leaps happen in such evolutionary algorithms ? - Yes, the 'leaps' concept is called punctuated equilibrium [wikipedia.org].
    • by Arker (91948)

      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 ?

      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,

    • 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

    • Do such leaps happen in such evolutionary algorithms ?

      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)

    by evanbro (649048) on Tuesday December 09, 2008 @02:39AM (#26043949)
    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: (Score:2, Interesting)

      by GravityStar (1209738)
      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: (Score:3, Insightful)

        by lena_10326 (1100441)

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


          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)

      by thermian (1267986)

      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.

      • by srussia (884021)

        Also, its damn cool.

        Oh yeah? Let's see how many iterations it needs to get an image of Kevin Bacon!

        • Oh yeah? Let's see how many iterations it needs to get an image of Kevin Bacon!

          Ummm.. totally wild guess here... 6?

      • Re:Brilliant! (Score:5, Interesting)

        by Alsee (515537) on Tuesday December 09, 2008 @07:14AM (#26045047) Homepage

        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)

          by Chapter80 (926879)

          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!

    • Have you ever built a gadget? (Whatever that might have been.) If so, you didn't feel that warm, fuzzy feeling when it started working? Because, you know, most people feel like that even in the case they knew that it *would* work.
      • 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.

    • In no way are we surprised. I just think it's cool to watch the progression from a bunch of random polygons to a pretty decent approximation of the Mona Lisa.
    • 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.

  • by usul294 (1163169) on Tuesday December 09, 2008 @02:39AM (#26043953)
    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.
    • by khallow (566160) on Tuesday December 09, 2008 @03:02AM (#26044055)
      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.
    • 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.

    • It's often quicker to do straight gradient descent. Just calculate the derivative and do some Euler steps. GA is overkill, unless you're looking for an excuse to waste some time.
      • by retchdog (1319261)

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

  • by greg_barton (5551) <.moc.oohay. .ta. .notrab_gerg.> on Tuesday December 09, 2008 @02:55AM (#26044031) Homepage Journal

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

  • A similar project (Score:5, Interesting)

    by dmomo (256005) on Tuesday December 09, 2008 @03:07AM (#26044073) Homepage

    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)

      by dmomo (256005) on Tuesday December 09, 2008 @03:19AM (#26044127) Homepage

      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

      • by DrEasy (559739)
        This is very cool! You probably get even better compression than by using polygons. Care to share the code?
    • 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)

      by soniCron88 (870042)
      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: (Score:3, Interesting)

        by dmomo (256005)

        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

  • by OrangeTide (124937) on Tuesday December 09, 2008 @03:19AM (#26044129) Homepage Journal

    I think it's cheating to use convex polygons, why not use complex polygons then you could probably do it with 5 polygons?

    • by glwtta (532858)
      They don't seem to be convex to me...
    • by Fëanáro (130986)

      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.

  • by haggais (624063) on Tuesday December 09, 2008 @03:46AM (#26044217)

    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.

  • "Both beautiful to look at adn a striking way"

    Pnu intended?

  • image compression (Score:4, Interesting)

    by polar red (215081) on Tuesday December 09, 2008 @04:04AM (#26044283)

    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.

  • It sounds like it is purely asexual reproduction with a single element per generation. There is no crossover operator and no fitness other than whether the product is closer to the known goal.
  • by Comboman (895500) on Tuesday December 09, 2008 @09:28AM (#26045613)
    Finally we have definitive proof that the Mona Lisa evolved from simple polygons instead of being "intelligently designed" by that fictional Leonardo guy.
  • by sgt scrub (869860) <saintiumNO@SPAMyahoo.com> on Tuesday December 09, 2008 @01:18PM (#26048377)

    ftfa: So what do you think?

    She still wouldn't date someone on /.

"Look! There! Evil!.. pure and simple, total evil from the Eighth Dimension!" -- Buckaroo Banzai

Working...