Genetic algorithm evolves a better car in Flash
Matthew sez, "This is a GA I wrote to design a little car for a specific terrain. It runs in real-time in Flash. The fitness function is the distance travelled before the red circles hit the ground, or time runs out. The degrees of freedom are the size and initial positions of the four circles, and length, spring constant and damping of the eight springs. The graph shows the 'mean' and 'best' fitness."
Genetic Algorithm (Thanks, Matthew!)
the latest
latest episodes
Okay, screw LittleBigPlanet, I want this game for Christmas!
Does it ever stop?
Matthew, any chance you're interesting in releasing the source for this? It's absolutely fantastic, and I let it run for hours... now I want to play with it more, and I'm wondering what the code looks like.
How "genetic" is this really?
I mean, it doesn't really seem to evolve by weighting the mutations to "inherit" traits of successful models. The mutations seem random; even after many generations, it still makes some stupid evolutionary missteps.
What selection method does he use? Roulette wheel? What are the mutation rates? Does he use "throwback" techniques when previous generations had a better fit than the current one (apparently not)?
I wonder what it would do with the VW Gold TwinDrive plug-in hybrid.
Golf* :/
Very nicely done.
But good heavens, that's tedious and seemingly inefficient in this example. There has GOT to be a better way.
You could save the Big 3 automakers with this! They're probably not running flash/java-enabled browsers though.
The relevant reddit discussions, for those interested in more info.
@3 kilo, he does not mention open sourcing it (as far as i can see) but he does plan to update the app to some extent.
one
two
that's what they should teach in schools when talking about evolution.
Not about wether or not your cousin waldo resembles more or less an ape, not either jesus met dinossaurs, not about fossils or all that hard biology.
They should teach about evolution the universal law, the universal process, the 'algorithm' (maybe not saying that a-word) and how it can be universally applied to anything.
That's when evolution stops being something abstract that may have happened billions of years ago and may or may not contradict you beliefs, and evolution becomes a useful everyday tool.
will wright must be mad right now. this is funnier to look at than most spore planets...
Thanks God for intelligence: all those 'evolutionary' concept really need that nudge from time to time to work.
TRY IT YOURSELF!!
An amazingly similar game is on Addicting Games:
http://www.addictinggames.com/fantasticcontraption.html
"that nudge" is usually supplied by your dumber neighbors being eaten or eating the wrong kind of food, themselves.
My G-d created a marvelous Universe that runs itself just fine from His first principles -- and He doesn't need to constantly tinker with it. I'm so sorry to hear that yours in still in Beta. "Intelligent Design" is not -- it's an apologia for Flawed Creation from a minor deity.
Ah - the blind watchmaker itself, in action.
Brilliant. This x deep time = no need for "intelligent design"
It makes for a wonderful "generative" narrative. I like the accessibility of the concept.
Here's another version, but in 3D:
http://www.spiderland.org/screensaver
It takes longer to get anywhere, but it's more interesting to see what it evolves towards.
@Padster123
Who designed the fitness function?
Who designed the way the inviduals combine and create offspring.
The "intelligence" behind this example is the guy who developed it.
Filled under "Yet another software example that supports ID"
yay! well done! i was looking for something like this to explain GA to a n00b friend of mine.
the only tweak i would make would be to display the top one or two designs. that way you could see what design the current one was competing against.
and for the person who commented about the app's inefficiency.. i think the main purpose for this app is to demonstrate GA in general, not to be the most efficient at what it's doing.
@#9 Alexandre Van de Sande
Exactly!
And what would even drive the point home even further, would to have the failed car generations remain stuck in piles of wasted iterations.
Slowly zoom out to reveal the many, many broken versions in comparison to the few successes. Evolution doesn't have end goals-- there's results based on the functional survival of mutations. Giraffes didn't grow longer necks from straining to reach the top leaves, the descendants of mutants that had longer necks were simply eating more, living longer, and procreating more often.
Interactive mediums and animated illustrations seem to be the best tools toward explaining such an abstract concept, including the many thousands of years abbreviated to a human scale.
I wish there were these kind of examples and COSMOS type programs in development-- this type of "layman explanation" is just what the world needs to increase scientific literacy.
The algorithm seems to find itself in local maxima or minima quite often. I'd suggest the inclusion of a simulated annealing process in order to break free.
Citation to a combined SA-GA method: http://www.ingentaconnect.com/content/els/03772217/2003/00000145/00000003/art00218
As I'm working directly in a project that will be using computer models to teach evolution to 4th-8th graders in Massachusetts, Texas and Kansas, I can say with (some) confidence that this kind of model will *not* help most kids understand evolution.
The problem is that it's very easy for those of us who *do* understand evolution to look at this and say "see!!! Evolution is universally applicable! It's just a algorithm which, given variation and selective pressure can eventually adapt a population, no matter what the domain!"
The problem is that most students, and many adults as well, won't be able to transfer this idea to the world of pigs and carrots. This is a problem of transference in models in general, of course, but is also a major problem in evolution, where people think a pig is a pig is a pig.
This is indeed the root of the problem for many IDers, who cheerfully accept "microevolution," but won't accept speciation, and won't accept that a pig and a carrot share the same ancestor. (Indeed, I can guarantee you that if you showed this model to many IDers they'd say "But it will never evolve into a tractor! Ha!"
It also fails to address what many IDers call the "artificiality" of models (after all, if you think that Dembski has never heard of a GA before you're wrong). Why are some of these "cars" dying? Who is doing the selection? What is this "roulette wheel selection" or "tournament selection" anyway? Can you show me that happening in nature?
Of course, *we* know that these various selection algorithms are just efficient models for reaching the same ends, but a kid learning this for the first time just won't make the connection, and a parent who believes in ID will never accept the connection. As far as they're concerned, you just "programmed in" evolution.
BTW: This is only in response to the idea that this would make a good learning tool. The model itself is a very fun way of showing GAs, and, indeed, would make a great demo for an AP Bio class that already had a grounding in evolution.
There are indeed many ways of avoiding the local-maxima problem: SA, island models, exaptation... The interesting difficulty would be representing them visually in this visually-rich easy-to-understand example.
Alexandre Van de Sande: No, it would just be stupid, as the evolution of a technology has nothing to do with evolution as a biological theory. For starters, technology has an intelligent designer. And since when has it been a universal law, either?
i would love to tweak some of the variables to see how it changes ... like:
gravity
bias towards speed of completion
bias towards smoothness of ride
maximum mass
maximum speed
target distance
simulation speed
i'd like to see:
the best ride so far
the best ride in each genration
the generation number
I'm anxiously waiting for the release of this code to start tweaking, tho i never worked with actionscript before. I'd love a game that pitched selection algorithms (criteria) against one another on a random course.
Ok, i'm sorry. Would someone please explain this to me. Whats going on? As near as i can figure the program is designed to create the most efficient little car possible, is that right?
thank you for saying "damping" and not "dampening"
This is amazing.
Even after over 70 generations or so, it's far from done. The mutation algorithm seems to be effective enough to keep the variables changing. (Yes, this program can get out of local minima! There is usually still one vehicle that will fall apart immediately in every generations. Some do on the track, because their red circles are too low (faster because of a low center of mass, but bad for safety ...) )
What is also quite interesting, is that while the best individuals performance is remarkably steady, the average of the population keeps changing at random, though never quite falling through the floor, instead staying between 2/3 and 3/4 of the top performance. This value actually peaked at about generation 30 with an average performance of the generation at 90% of top performance. (And was reached again, JUST when I typed this ... in generation 80 or so ...)
Awesome. Also check out this very similar vehicle simulator in flash that lets you design any kind of vehicle and has a goal:
http://www.ingenuitywelcome.com/game/#/ingenuity_welcome/
I've been letting this run in the background all day, it is pretty neat to see the vehicle spend a lot of time first trying to beat the "cliff of doom", and once it accomplishes that, trying to crest the next hill before time expires.
If this was intended to trigger interest in genetic programming, it worked because I think when next I get some free time it'll be worth investigating.
I think the only tweak I'd like to see is some way to increase the timeout. I understand it would cause generation to take longer.. but watching the little guy bounce over the terrain is half the enjoyment.
skatanic: The model doesn't explain much, so no worries about not understanding.
What is happening is this: Some 20 random configurations of springs and wheels are created and dropped into an environment, one at a time. Each random "car" spins its wheels to the right. If either of the red balls touches the ground, it dies.
You then take the X best of those "cars" (those that traveled the furthest) and you breed them together through some algorithm, which both combines their traits and probably introduces random mutations. This creates a new generation of 20 cars, which will, through the magic of evolution, probably be slightly better than the previous generation.
All that the model requires is some variation in the individuals, some way to produce new individuals from old, and some selection pressure, in this case choosing those that travel furthest.
It's actually, for certain problems, a very efficient algorithm -- it only looks slow here because we're watching each individual, but this whole thing could be done in milliseconds.
re my own comment @15 - I reacted to the reactionaries without commenting on the post at hand; love it! I saw a ref to this previously on HackerNews but it lacked the context. Thanks.
Anyone has a car that gets past the downhill after the notch in the picture above? All my cars (I have 5 instances running) manage to go down the hill, and then it resets..
I see all my cars taking on similar attributes...big wheel and weight? (red circles) in front, little wheel in back.
Would someone explain the diff between the mean and the best? Overall? Per family? I'm kinda lost.
It eventually figures out how to get over the hill, I took to calling it the "hill of doom" after seeing the term in another thread.
I think it took about 45 minutes of run time before it could do it reliably.
It's then spent most of the day trying to be efficient enough to get over the top of the next hill in the series.. which it started doing reliably about an hour ago.
One of the more fascinating things I've seen in a while, it needs to be able to save state and run as a screensaver. ;)
And maybe fifteen minute snapshots so you can see the evolution of the vehicle.
GAAHR! Don't use the link (http://www.ingenuitywelcome.com/game/#/ingenuity_welcome/)
from CWIGGINS01 without the following caveat:
LEFT-clicking on the game crashed my firefox, losing several hours of GA!
...You've been warned...
@37 hockeyrink: ARGHHHH now why o why didnt i read your post BEFORE i left clicked on the game...
12 hours of GA down the drain ...
Oh well... let's see if it evolves in the same direction...
with all the comments about hours and hours running this, it would be cool to have a distributed version. We could finally create the Eschaton!
You could run this thing for a hundred years and never come up with a suitable model for crossing the whole terrain. On the other hand, people have built vehicles capable of conquering far more difficult terrain with a little know-how and the right materials.
Amazing how far a little "intelligent design" will go isn't it?
"intelligent design" only goes so far here because the game's "universe" is very basic, which offers a challenge easily met by our collective "know-how" - not to mention the number of centuries since the start of civilization that it's taken humanity to master the physics of off-terrain vehicles.
Try augmenting the game's universe with another spacial dimension, multiple competitors, dozens of goals, and about an infinite number of parameters - along with the benefit of several billion years worth of generations to improve upon the design. The results would undoubtedly be more diverse, more efficient, and more creative than anything we humans could come up with.
Certainly applying some analysis and logical problem solving can be faster than GAs for tasks that are already partially understood, but even then a whole range of alternative solutions are usually missed.
Wow, Assume@40, way to set up a false dichotomy.
can it pick stocks?
@Michael #42 — Nothing I said was false.
I let it run all day, and it got stuck. The result isn't that far off of what I'd build given the same problem: long wheelbase, red circles close together.
But there are some fairly simple edits that anyone can see will make it better.
screen grab
Interestingly (to me, anyway) this one started off much less fit than the first time I ran the program: for about 3 or 4 sets of 20, it was stuck with a giant red wheel that would touch as soon as it was dropped. That's why I let it run so long.
One of my instances got stuck on the hill of doom.. it was so front heavy every time it made it over the top it would just flip over.
Was interesting in the sense that it was unable to evolve out of this state.. it kept flipping over until I finally closed the tab.
The instance that's been running since yesterday morning has conquered two mountains, and is now working on the third.
I wonder how far that line goes. ;)
#40 Assume:
Yes, and?
I don't think any evolutionary biologist would disagree with the idea that, IF an awesome intelligent designer existed, and IF He wanted to continuously tinker with living organisms because His design wasn't able to adapt by itself to new environments, THEN He could probably create a Human.
It's just that it isn't necessary, because evolution can do it without outside help.
So... what was your point?