Genetic programming

posted Dec 8th 2008 8:00pm by Eliot Phillips
filed under: downloads hacks, misc hacks

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 [44]

tagged: car, evolve, flash, genetic algorithm, programming, prunesquallor, ron alsing, waxy

Reader Comments

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.

Posted at 8:46 pm on Dec 8th, 2008 by cirictech

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.

Posted at 9:05 pm on Dec 8th, 2008 by skeptic

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.

Posted at 9:52 pm on Dec 8th, 2008 by RyanT

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

That’s… interesting…

Posted at 9:53 pm on Dec 8th, 2008 by RyanT

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.

Posted at 10:02 pm on Dec 8th, 2008 by atrain

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

Posted at 11:54 pm on Dec 8th, 2008 by tim0s

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.

Posted at 11:59 pm on Dec 8th, 2008 by thejameshimself

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.

Posted at 12:05 am on Dec 9th, 2008 by MEAT!

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.

Posted at 12:52 am on Dec 9th, 2008 by Acedio

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!

Posted at 1:45 am on Dec 9th, 2008 by Grovenstien

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

Posted at 1:46 am on Dec 9th, 2008 by Grovenstien

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.

Posted at 2:43 am on Dec 9th, 2008 by haltux

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.

Posted at 4:27 am on Dec 9th, 2008 by sir_flexalot

jamie and adam did it better
http://hackaday.com/2008/08/29/1100-barrel-paintball-gun/

Posted at 4:44 am on Dec 9th, 2008 by aztraph

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.

Posted at 5:03 am on Dec 9th, 2008 by Roy

@roy

is .kkrieger what you’re thinking about?

Posted at 6:47 am on Dec 9th, 2008 by _matt

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

Posted at 6:53 am on Dec 9th, 2008 by radon222

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!

Posted at 7:17 am on Dec 9th, 2008 by a

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

Posted at 8:10 am on Dec 9th, 2008 by ac7zl

@by _matt

Yeah! That rocks, thanks!

Posted at 8:10 am on Dec 9th, 2008 by Roy

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.

Posted at 9:28 am on Dec 9th, 2008 by glompix

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

Posted at 9:31 am on Dec 9th, 2008 by m-ocelot-y

@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…

Posted at 9:47 am on Dec 9th, 2008 by Michael

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

Posted at 9:51 am on Dec 9th, 2008 by m-ocelot-y

Ryant doesn’t get it.

Posted at 10:44 am on Dec 9th, 2008 by J

P.S.

That’s insane. I would so be there.

Make as many babies as possible?

Everyone wins!

Posted at 10:48 am on Dec 9th, 2008 by J

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.

Posted at 12:46 pm on Dec 9th, 2008 by jonored

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

Posted at 1:13 pm on Dec 9th, 2008 by bob

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

Posted at 1:28 pm on Dec 9th, 2008 by S

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.

Posted at 2:01 pm on Dec 9th, 2008 by alan

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.

Posted at 2:09 pm on Dec 9th, 2008 by wwwilson

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.

Posted at 2:30 pm on Dec 9th, 2008 by sparr

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!

Posted at 5:24 pm on Dec 9th, 2008 by Gonzalo

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.

Posted at 5:49 pm on Dec 9th, 2008 by an

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.

Posted at 7:04 pm on Dec 9th, 2008 by metalicaman8

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

Posted at 7:16 pm on Dec 9th, 2008 by metalicaman8

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

Posted at 8:11 pm on Dec 9th, 2008 by Solenoidclock

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.

Posted at 4:17 am on Dec 10th, 2008 by khani3s

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.

Posted at 8:20 am on Dec 10th, 2008 by Chet

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?

Posted at 8:31 pm on Dec 10th, 2008 by kyle

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

Posted at 6:23 am on Dec 11th, 2008 by Tom Brady

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

Posted at 8:16 pm on Dec 11th, 2008 by khani3s

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

Posted at 7:19 am on Dec 13th, 2008 by Tj

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.

Posted at 10:15 pm on Dec 22nd, 2008 by Brandonman

Genetic programming

Recent Posts

Reader Comments

Leave a Reply

Hacks

Resources

RSS newsfeeds

Most commented on (30 days)

Recent comments