Genetic programming

monalisa

[Ron Alsing] wanted to try out some genetic programming, so he created a simple test problem: Could you render the Mona Lisa using just 50 semitransparent polygons? The program starts with a random DNA sequence. It then mutates and compares itself to the original image. If the mutation is closer, it becomes the new sequence. The final image he shows looks pretty good after 904,314 iterations.

[prunesquallor] pointed out a genetic algorithm project of his own. It’s a flash program to evolve a car. The car tries to get as far as possible on a set terrain without the passenger circles hitting the ground. The wheel size and positions can change along with the spring length, constant, and damping. A graph tracks the best performance along with the mean. He’s planning on building a version that lets you change the parameters.

[via Waxy]

Comments

  1. cirictech says:

    That’s really cool. I was going to take a genetic programming class, but it trns out that I wont be in town. Sad day but nice work.

  2. skeptic says:

    Interesting, but silly.

    And I say that because you could do a much better job in less time using standard optimization techniques instead of this genetic algorithm nonsense.

    I mean, 900k iterations? Christ.

    That, and there’s no analysis of optimality. The better thing to study is how do you come up with the BEST POSSIBLE representation of the Mona Lisa given N polygons of M points each. Or whatever.

  3. RyanT says:

    I have to agree with skeptic. This kind of “genetic programming” is nothing more than just randomly throwing processing power at a problem that he is unable to solve properly.

    None of these attempts go beyond throwing random solutions at a problem and picking out the best one after a couple hundred thousand iterations.

    Genetic programming wasn’t intended to produce mind blowingly inefficient solutions to problems like this. I would go as far as to say that these are nothing more than trivial toys with the word genetic thrown in for cool factor.

  4. RyanT says:

    Oh wow, I have never seen a website ruin proper capitalization in comments as a feature.

    That’s… interesting…

  5. atrain says:

    I couldn’t agree more with the above comments. I don’t know much about Genetic programming, but I can tell this is ridiculous. There is no algorithm, rather, just random point choosing.

    If this were to be done correctly, the genetic part would only really be useful for adjusting an existing polygon image. (Optimization) Also, is there any point to a “genetic” system with a population of only 1?

    ryant: The whole site is lower case. Its in the CSS, if you really want there are ways around it.

  6. tim0s says:

    Wow,

    how did this end up on hackaday? Genetic algorithms are not new in any way, all of the stuff that _could_ be clever (how did he do the image comparison, what are the parameters for the GA, is the convergence speed “optimal”,..) are not mentioned on the website.

    Regards,
    Timo

  7. just because the program didn’t clone a sheep doesn’t mean it’s completely ridiculous. throw in a few root finding algorithms to minimize the difference between the polygons and the original picture or maybe adapt some of the Knight’s tour ideas mentioned a few days ago and you could have a highly evolved program.

  8. MEAT! says:

    I’m afraid I have to agree with the above posters, and say that this whole genetic programming thing is ridiculous. Billions of lifeforms like squirrels, whales, algae, flowers, insects? A trillion diseases, viruses, parasitic bacteria, genetic disorders, illnesses and ailments? The whole thing is silly.

    I mean, four billion years to develop a walrus? Christ.

    None of these attempts go beyond throwing random solutions at a problem and picking the best one after a couple hundred thousand iterations. This evolution stuff is nothing more than life throwing natural processing power at a solution that it’s too stupid to solve properly.

    The better thing to do would be to come up with the best possible lifeform given n stable molecules of m temperature ranges each, or whatever.

  9. Acedio says:

    While you all may be right that this isn’t a great example of genetic algorithms, I have to disagree with you if you say it isn’t interesting. Another cool article on genetic programming was posted earlier on Reddit:

    http://www.cs.nyu.edu/courses/fall08/G22.2965-001/geneticalgex

    They let designs on an FPGA ‘evolve’ over time using the same sort of randomness this project used. Eventually they arrive at a design that functions, but in a really unconventional way. Interesting stuff if you ask me.

  10. Grovenstien says:

    Evolve a car is bizzarly addictive to watch! Even with no influence over the little buggy, its imposible not to get involved, urging it on its way! Though if the car just elvolved into a bigger car then the track would be easier!

  11. Grovenstien says:

    Also better a long time to evolve a walrus than a snap to become an eggman! coo coo ca choo!!!

  12. haltux says:

    The Mona Lisa example, as describe here and on the website, is not at all genetic programming. It is just a greedy hill-climbing search, the most basic ways to solve an optimisation problem.

    The common point between this and genetic programming is that you use the same cool words to make straightforward and inefficient algorithms looking cool.

  13. sir_flexalot says:

    That’s not a genetic algorithm, that’s an iterative approximation algorithm. A genetic algorithm wouldn’t need to keep comparing to a “source” image, and it would require pairs to breed to get closer to the image.

  14. aztraph says:
  15. Roy says:

    Well, that Mona Lisa example could be used for example in gaming. If you could automaticaly create small DNA-polygons for faces, you can ship your game with a LOT of acurate famous faces in just 50 polygons each. The level of detail is very good IMO.

    This reminds me of a game I once saw, it was only 2k or something but generated all its music and textures at runtime based on just a couple of arguments (and some pseudo-random settings probably).

    So in 2k they were able to put a full 3d fps with amazing sounds and background noise and good looking textures.

  16. _matt says:

    @roy

    is .kkrieger what you’re thinking about?

  17. radon222 says:

    The Mona Lisa demo doesn’t use the genetic algorithm developed by John Holland, but it might fit into the more the more general class of “evolutionary algorithms” I think. The car evolving program seems to use the standard genetic algorithm.

    The title of this article is confusing too, because genetic programming refers to a separate technique. It involves using a genetic algorithm to automatically write a program.

    Genetic algorithms are good for attacking problems when you don’t have a deterministic algorithm. I think in this case there are already deterministic algorithms to solve similar problems, but this solution just looks cool. :)

  18. a says:

    The comments above don’t really show much understanding about the whole point of this experiment. The whole point of this is not to create the most efficient or quickest algorithm. Is to visualise evolution of organisms in nature by means of natural selection. It places polygons randomly and favours the pictures which fit the reference picture best. This is to show how the organisms that survive are the best suited to their environment and that they get to pass down their genes (their DNA). Nothing more. The whole point about it taking so long to get to the solution is a talking point on its own. It takes a bloody long time for an organism to evolve to perfectly suit its environment! Hence the millions upon millions of years it took for humans to come about! Just like it takes almost a million attempts to randomly place polygons to create a near perfect replica of the mona lisa!

  19. ac7zl says:

    I think it would be interesting to establish a colony of 1000 “individuals”, each with a 50-polygon set and a genetic code representing their polygonal characteristics.

    Next, you set up rules for sexual reproduction between “individuals” (polygon sets), such that each of the offspring inherits characteristics from both parents.

    An added twist would be to make certain genetic codes dominant and others recessive.

    The system would be weighted so that in each generation, the individuals who look most like Mona Lisa are afforded preferential opportunity to mate, while those looking least like Mona Lisa wither and die without reproducing (or without reproducing as much).

    It would be very interesting to see how many generations it would take to reach Mona-Lisa-like perfection, particularly compared to simple hill-climbing algorithms.

    I would think it important not to kill off non-Mona-Lisa individuals too soon, because they might simply be stuck in a local minimum. They might, in fact, carry the necessary codes to reach Mona Lisa perfection.

    Another interesting twist would be to set up a mating system where a child can have not two parents, but three. I would think this would offer the potential advantage of faster evolution, but also the potential disadvantage of wider feature excursions. (The latter exposes the offspring to the risk of extinction.)

  20. Roy says:

    @by _matt

    Yeah! That rocks, thanks!

  21. glompix says:

    Genetic/evolutionary algorithms aren’t useless or lazy when applied to the right problems. They really shine on problems with irregular solution spaces. A good example is computer-generated music. There are a shitload of terrible melodies in the set of all possible melodies, and a good melody can be thrown off by a single changed note.

    And yes, genetic programming and genetic algorithms are two separate, tenuously related entities.

  22. m-ocelot-y says:

    @a.
    I would have to argue against that interpretation. Natural selection as a mechanism does not operate within a static environment. This is tinkering, but it is guided towards a particular static ideal. It’s not that a particular organism is “perfect” for its environment – the organism has found a -particular way- of surviving within that environment as it exists at a particular point in time.

    This isn’t natural selection, it is, as sir_flexalot put it, an iteratively derived approximation of specific result.

    //Also, humans aren’t the end-all-be-all of evolution from the perspective of -natural selection- (though not every change is n.s., btw). I might just be in the wrong part of town, but I don’t see too many people filter feeding around volcanic vents. We do a good job in lots of places, but we’re not -physically- adapted for all of them.

  23. Michael says:

    @ac7zl

    you know what would be even cooler? Actually getting 1000 people, locking them in a massive room and getting them to breed. Then every so often, remove the people who looked least like the mona lisa…

    It’d take a long time (perhaps a few too many thousand/million generations), but it’d be impressive seeing a real mona lisa…

    Or perhaps that’d just be silly…

  24. m-ocelot-y says:

    @micheal
    That sounds like fun research. Can you imagine applying for a grant to study that?

  25. J says:

    Ryant doesn’t get it.

  26. J says:

    P.S.

    That’s insane. I would so be there.

    Make as many babies as possible?

    Everyone wins!

  27. jonored says:

    The genetic algorithms they taught us in school were effectively hill climbing with monte-carlo methods applied, multiple points exploring the solution space, the sum of two points being explored as a possible improvements, and the value of a point having the distance to all better points as part factored in as a measure against local maxima. They’re good when you can’t easily get a derivative of the value of a given solution, and have more than a couple continuous parameters to vary. These aren’t the best examples of the technique, but they would be good exercises for learning it. Also, genetic algorithm iterations aren’t directly comparable to more deterministic hill climbing iterations; genetic algorithm iterations are dirt cheap in comparison on the problems they’re actually useful for.

  28. bob says:

    The first example is not a genetic algorithm. There’s no sense of “breeding” different good solutions, just random mutations at every step. It’s like saying “Start randomly somewhere, then take a step in a random direction. If you went in the right way (which I as the oracle will magically tell you), then stay there, other wise undo that step. repeat.” That’s not an algorithm, that’s throwing processing power at a problem (to borrow an earlier commenter’s phrase).

  29. S says:

    another similiarly interesting project, focusing on the ‘blind watchmaker’ myth;

  30. alan says:

    Okay, I haven’t read Dawkin’s books or anything, but to me the glaringly obvious question is, “Who determines the final picture?” I mean, this guy decided that the final objective was going to be the Mona Lisa right? What if at frame 300,000 the circumstances changed and required the final picture to be The Starry Night? And wouldn’t you say that the evolution of the human body would be more like the complexity involved in a work on the magnitude of the Sistine Chapel? Here’s my point, climatology shows that the Earth occasionally undergoes dramatic (sometimes abrupt) changes in environment. If the Genetic Programming model is representative of evolution, how long would it take the program to adjust to the change?

    I guess my points are two-fold:
    1. The program presented here suggests there be a final design goal. The cross connection is that life on Earth is evolving towards an increasing level of complexity with a final goal in sight. The problem with that theory is that given time and left to their own devices, don’t systems move from ordered to less ordered?

    2. The program presented here lacks the complexity needed to represent the systems working together to result in life on Earth. If you were to take into account variables like climate, natural laws (organisms developing to thrive in our atmosphere, with our level of gravity, with our level of solar radiation, etc), species interaction, the program would be much more complex. It would be more like 10 or 20 different programs evolving separately and in conjunction with each other to result in something like the complete architecture of Rome.

  31. wwwilson says:

    This IS genetic algorithm, however it is not cool. It would be cool if it was shown that, on average, it required significantly less computational resouces to create a better mona lisa approximation than other methods (including random search). For now it can only be classified as flashy.

    There does not necessary have to be crossover for it to be genetic algorithm. Some lifeforms do not use crossover as part of their evolutionary process.

  32. sparr says:

    the little car program is quite neat. i feel sad that there seems to be a glitch that causes a run to end prematurely, while the car is still moving and the passengers are not coming close to the ground. some of the best designs fail unexpectedly and are not represented in the next generation.

  33. Gonzalo says:

    sparr, I think it’s not a bug, when the car goes backwards it won’t be able to climb some hill, so the program just erases it!

  34. an says:

    This is not an example of genetic programming. It has no crossover and no ability for the algorithm to move to less optimal points in order to avoid local minima problems. This is just an example of greedy hill climbing. The term “genetic” was most likely thrown in to make this sound better.

  35. metalicaman8 says:

    this is a time limit. it makes the cars faster after they mutate out the bugs that make them crash. The fastest ones go farthest.

  36. metalicaman8 says:

    @an

    This is. Cars that survive longest in the beginning live to procreate. Eventually once all cars are survivors the fastest cars impress the ladies. Cars with defects are thrown out so there is now way to move to less optimal points because they aren’t good enough. Every single car that comes off the line is different but they slowly move toward optimal for whatever shape proves to have the highest survival rate.

  37. Solenoidclock says:

    A hack would be if he made the end result out of tissue paper.

  38. khani3s says:

    I am a researcher in GA field.

    The Bbeautiful thing in GA is that you only need to say how evaluate the best solution and done!
    You don’t need to understand how to resolve the problem, only how to evaluate it.
    It’s no random search.

  39. Chet says:

    The problem with that theory is that given time and left to their own devices, don’t systems move from ordered to less ordered?

    Yes, but the population of living things on Earth taken together over geologic time don’t represent a thermodynamic system. Each one is a system, which is why we all get old and die; but evolution is the change over generations and that change, itself, is not thermodynamic. It has nothing to do with heat or energy.

  40. kyle says:

    this reminds me of the breading mindstorm . it really interests me. does anyone know if there is already a program that has robots move around an enviroment and pass there genetics on and evolve?

  41. Tom Brady says:

    I thought it was funny how my schools website blocking software blocked this because they thought it was porn.

  42. khani3s says:

    Kyle, i work with control of autonomous swarm robots by genetics algorithm

  43. Tj says:

    am i the only person who is amazed by 50 polygons looking like a mona-lisa? If you bought this into the real world you could have 50 layers of glass stacked to look like a mona-lisa which would be pretty amazing…

    anyhoo, to quote khani3s “The Bbeautiful thing in GA is that you only need to say how evaluate the best solution and done!”… even more amazing, Read about it before you dis it

  44. Brandonman says:

    kyle, I remember seeing an article on simple robots that mated genetic code. I don’t think it did much with actually evolving the robots, but stuff was passed on. I’ll see if I can’t dig it up.

  45. Jan says:
  46. gbirbilis says:

    I think it’s a very good one (checkout the gallery link) – http://robotics.mech.upatras.gr/forum/viewtopic.php?f=10&t=102&p=469#p469

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,670 other followers