Maybe someone more versed in the state-of-the-art can help me: has the concept of "speciation" ever been applied to genetic algorithms?
In my instance, there are two predominant "types" of cars that are doing approximately equally well--the "rhinoboat" and the "assdragger". But when these two solutions are combined in the crossover, I think they make an offspring that is terrible.
If the algorithm would mate only the rhinoboats with rhinoboats and assdraggers with assdraggers, I'm convinced we'd end up with some superrhinoboats and superassdraggers, but instead I just get an unhappy compromise.
Maybe make "similarity to self" one of the genotype parameters. A high rating here would mean the phenotype would have a bias against being combined with dissimilar creatures. This allows the propensity towards speciation to develop evolutionarily, too.
It's not fancy hmtml, but it's the best genetic simulation I've seen. The "swimmers" exist in 2d space, seek out food and mate. Only the best will reach the food fast enough, and there are colors which a given swimmer will prefer to mate with, and space separating different populations. It's very possible to get several distinct populations which behave in entirely different ways.
Also, I found these algorithms could always go more and more meta. For instance, in some situations a large "clone fraction" was optimal, or large "mutation rate", whilst in other cases it brought chaos and degraded the population.
Successful parameters could also become more immune to mutation with time, a nice improvement along with "speciation" you cited.
> Also, I found these algorithms could always go more and more meta.
Haha, I've had this same thought before. I wrote a genetic algorithm to work on the sphere packing problem (in a periodic box) and I kept thinking about how I could mutate the settings within the program and optimize them, and then mutate the rate at which those settings themselves changed, and so on. I wonder if there's an optimal point to stop being "meta"?
There are information theoretic aspects behind this. You're essentially searching the design space for the fittest and want a fast way to get your answer -- this 'fastest way' is related to the way that 'grants' maximum information.
I say this because this reminded me of a wonderful (and acessible) discussion I once glanced over on the following book: http://www.cs.toronto.edu/~mackay/itprnn/book.pdf
(Page 269, pdf 281) -- it offers answers to this sort of question :)
Yes it has, it's one of the core things you adjust in most real applications.
It's a trade-off between exploration and exploitation. If you speciate then you have little sub-populations exploiting the local maxima, so they might do better. However, now you're not searching such a wide area so you're more likely to spend your time struggling to the top of the molehill that's next to the mountain.
In nature this also happens. Not having crossovers between ludicrously different things is generally a good idea because the landscape is full of tiny maxima. If you change a load of base pairs in your DNA you're less likely to be able to do things like form cells or process glucose than you are to add some awesome new power (unless we're in comic books).
One of the major differences for nature is that it can run all this jazz in parallel. If there are resources, it can happily have 10 trillion bacteria rather than 5 without any cost. When we're simulating, every fitness measurement on a piss-poor crossover is a waste that we should have spent on a more likely solution.
It all depends on the fitness landscape, but both approaches can be better on different real world problems.
Actually, the thing genetic algorithms try to do is break out of this local maximum, mutating past a trait correlated with poor performance in hopes of finding a more fit solution.
In my hypothetcial algorithm, of course mutation would still take place.
But my current instace of the web page is at a point where it's wasting a lot of time on unfit 'mutts' and it seems like I could get to a "best rhinoboat" and "best assdragger" solution faster if it would stop wasting time exploring the mediocre blend.
Yeah, most effective genetic algorithms take a hybrid approach where they only do more dramatic mutations for some of the population, and then optimize the rest with a regular fitness function and small variations. The goal with these systems is to have several different but effective breeds emerge.
I didn't dig into this implementation, but it seems like it doesn't carry many (more than one?) individuals between cycles.
You could introduce speciation by only allowing relatively similar genomes to successfully breed. My guess is that such an operator would be quite expensive, and its benefits would need to be weight against that.
A typical work-around for scenarios like this would be to have the various parameters change as the simulation carries on; e.g. later on it might make more sense to increase the number of elites as a way of limiting crossover.
You're supposing that there is "sex" - i.e. two genders - in this simulation. I can't see that though?
I suspect - would be interested in anyone who's worked it out - that each individual is mutated between each generation.
I tried 10 Elites with high rate of mutation. I'd have expected this to have more "breeding" from the Elites, but it doesn't. It tends to plateau. Occasionally an outlier jumps into the "10", but it's pretty flat.
So.. Is there any concept of "fitness"? If so, it ends up being pretty random, since there is no penalty for a less adaptive mutation.
Sex does not mean two genders, neither in the simulation nor in real life. It just means that offspring inherit genes from two (or more!) parents rather than one.
Well it's a bit more difficult, but you could let the organisms themselves decide who to mate with. Or you could have a smarter genetic algorithm that keeps sufficiently different organisms and tries evolving them for a few generations and see which type is superior.
There is really no advantage in speciation if you only want the single best solution, but it does make sense to try different evolutionary paths as they can end up in totally different places.
That's a bit of a weird assertion. Genetic algorithms are always a greedy heuristic to find a solution for a problem. It is not guaranteed at all that it will find the single best solution faster than straight bruteforcing solutions.
If speciation is a better heuristic for finding a better solution faster than the algorithm used here then its advantage is real and useful in any case.
What I meant by that dividing the population has a cost. Only one evolutionary path is going to end up with the best solution. By best I mean the best one you find, not necessarily the most optimal solution possible, which may never be found.
If you divide the population in two, at least half of your resources are wasted on doing tests and evolving traits which will just be discarded. Resources which could have been used to speed up the evolution of the other population. Even if the evolutionary path you choose isn't the optimal one, by putting twice as much resources too it, it still might end up further. And if you divide it into more than 2 species than it's just getting insane.
That's not to say that speciation isn't a useful heuristic, just that it's a costly one. However there are a lot of cases where just throwing more resources at the problem doesn't help, because it's stuck in a local maxima. In that case, going back to an earlier point in the simulation and running it to see if it ends up somewhere else isn't a bad idea, and that's exactly the same as what speciation is (except that you are doing it after the fact, rather than testing both evolutionary paths simultaneously.)
This happens in nature, actually. When there's a genetic disparity between individuals, although offspring is possible, it ends up infertile. That's nature's way of doing a U-turn.
When the hybridization is managed by humans though, it can be useful (e.g.: citrus, mules).
seriously I got 2 downvotes for saying I thought HN wasn't very funny? what?? It's not like there arn't plenty of other silly comments in this thread, why am I the one being singled-out, I guess it's probable that a comment like that would only offend people who even have the ability to downvote, since it takes 500rep to do so, but what? it wasn't even that offensive...
I remember having lots of fun with a Windows program that doesn't seem to be available anymore... just to give you an idea (not that I ever had anything this cool in my zoo)
That program was really awesome, the things could even have sensors that made muscles move on ground contact; and I so hoped for "underwater movement" to be implemented fully, but it never came to that :(
We now have WebGL, we have local storage... Anyone? I think it's beyond my ken, but for those who know this stuff, the question basically is if you have free time and want to be a superhero. If 2D cars on a canvas can be this fun, imagine sharing 3D virtual creatures with just a link, or even better, having them cooperate or fight each other ^^
Actually, the existence of the person is inferred only by the presence of the text.
As an aside, if this were a dream the inference would still work, but the conclusion would be false (as the poster obviously has no existence independent of the dreamer). But, unfortunately, you will be able to provide no conclusive evidences that this world is not as illusory as the dream world is, as your only sources of evidence are your senses, which are also apparently available to you in the dream state (which you are not able to perceive as illusory whilst dreaming).
Observation: The cars tend to optimize to get over a challenging hurdle (while it's being worked on, the cars converge to a single solution: which works well), but then are no longer general enough to get over later hurdles.
If only we could move freely in four dimensions, as to navigate around events that are difficult hurdles to overcome, such as comet strikes and nuclear holocausts.
that would still be a third dimension since you're just choosing to avoid something entirely within our realm, ever advancing technology is still not advanced compared to forever... or something like that =)
That somewhat depends on the mutation rate. I have it set to 20% and the cars are optimizing down to big wheels connected by what can only be described as a bar, which means they can drive in any orientation and are clearing later and later challenges quite effectively.
I see the religious implication. But that system indeed has a designer. Somebody spent weeks making sure that features are combined and evaluated in a certain way in which the cars can evolve.
Brute force doesn't necessarily mean testing in a dumb way (testing all options).
If you try to crack a password with a wordlist, would you do it randomly, or would you order by word frequency? The later is smarter, but it's still brute forcing (resource/time intensive).
It's a bit smarter still than that though. Brute force still covers the whole space. GAs are far closer to a hill climbing search which I don't think qualifies as anything near a brute force search.
Unless you actually enter a seed string it generates a 256 byte random string each time you open it for the first time. I used firefox debugger to retrieve the string, it is stored in a variable called "floorseed".
Have people actually had the course completed? I've been using 'genghisKhan' as my track seed and they always stop around 2/3 to 3/4 of the way it seems.
Oh man...some hilarious iterations there. Especially funny after playing with the normal version for a while. All of a sudden: "PARDON ME HUGE WHEELS HAULIN' ASS COMIN' THROUGH"
The author mentions it's based on that, but totally rewritten.
"The program uses a simple genetic algorithm to evolve random two-wheeled shapes into cars over generations. Loosely based on BoxCar2D, but written from scratch, only using the same physics engine (box2d).
seedrandom.js written by David Bau. (thanks!)"
I've been iterating over sequential seeds looking for one that contains the most downhill terrain, so far the best is: 24427169 - it descends very rapidly in the later part of the track.
I'll keep this running over night and post results.
Edit: 71044092 beats that (declines 47 units in the distance of the track, which is 220 units long).
This is ridiculously entertaining, and bringing back some fond college lecture memories.
Feature request: Ability to hover over the "Top Scores" and see a snapshot of what the Car looked like.
I am not ashamed to say I was adding dragster sounds, squealing tires, grinding metal, crash sounds, and little driver sounds in my head. Those guys were striving soooo hard to get up that hill. "Ooh ooh ooh, I can make it, I can make it!"
There really is something to this that needs exploration as a multiplayer game. The aleatoric quality makes it infinitely watchable for me. GenetExcitebike.
Yes, and specifically Roger Caillois's use of the term in Man, Play and Games[1]. And I suppose if you want to be technical about it, this simulation appears to have a little piece of each of his four categories of games, to include agon, mimicry, and ilinx with the aforementioned alea.
I was a little confused that you feel that chance isn't a strong enough factor in multiplayer games. It's so widespread and pervasive that I'm willing to "omnipresent" is only a minor exaggeration.
I'm sorry. I did not mean to convey that multiplayer games have no elements of chance, or alea. I was trying to say that I thought this simulation would benefit from adding a multiplayer element to it. And there are probably many implementations of multiplayer-ness that could be explored.
The "aleatoric" part was a separate observation about a quality of the simulation that made it more enjoyable for me. And then upon further reflection, it seemed to me that this simulation had (or could have) all the elements of a game, as classified by Caillois.
Boxcar2d let you save the genome of the car. I spent months running multiple instances, trying to develop a car to beat those tracks (and the others on the forum).
This one has some amazing features. Hopefully Rafael will give us some way to compete!
It says at the bottom: "Create new world with seed: The same seed always creates the same track, so you can agree on a seed with your friends and compete. :) "
Sadly, that is pretty much the only bit I understood, ish...
This is fantastic. There should be a place to enter your own inputs though. The point of genetic algorithms is to find solutions that you can't engineer yourself, right? I'd like to try my hand against evolution.
Believe it or not, my cars evolved into "Flying Cars" (They start with one wheel stuck in the terrain, moving slowly forward, then it releases and goes flying over the track)
Either there's a glitch in the game, or I'm calling JS console shenanigans. The red line on the chart gives it away, as does the mini map since it draws lazily. Playing the same level my top score is 221.12, and my mini map looks the same as yours.
Nah, no shenanigans. It was definitely a glitch, but I'm not sure if I can explain it much better. The "flying cars" start with one wheel on top of the track, and one wheel below the track. As the wheels turn, it makes very little/slow progress, but you can see the car sort of shaking/struggling to release. That release eventually happens as the lower wheel gets to a point where it can cross back to the top of the track, and that twisting motion flings the car up and forward very quickly. The cars never even see the track again. I'm not sure what actually causes the car to stop... the replay wasn't very interesting to watch after the initial 'launch', as it just spins in whitespace for a little while and then eventually just stops spinning in an upright position while travelling forward.
That was the longest run I've done, somewhere between 24 and 36 hours left mostly untouched and forgotten on the settings you can see in the picture (with Surprise! mode on to speed things up). Unfortunately I did mess with it a couple times when I got bored with its progress, cranking up the Mutation rate for a few runs to bring in some extra variety; so it would probably be tricky to reproduce intentionally. I've got a new version up and running again, since this one did eventually crash.
Definitely weird and interesting. The funny thing to me was that it is sort of a "realistic" evolution, since flying cars could be an eventual next step for real-life transportation. Although hopefully with a less violent launch system :)
178.43 at generation 16. That stupid wall at 171 is ridiculous!
199.47 @ gen 22. Now it is just a matter of luck whether or not they get a good jump in.
At the 190 mark the world goes all glitchy and half the track disappears.
It's a shame it's not as deterministic as it could be (according to the blurb at the bottom of the page), since this [probably] means the genetic algorithm can't exploit quirks and things being "just right" optimally. Rather, it has to build something that is a bit more generalised.
This is awesome! When a handful of cars actually make for a good race it's especially mesmerizing.
I feel like it's only a matter of time before some startup implements a genetic driven visualization of the data from their app. If the effect is as compelling, I'd be staring at their marketing page for a long time.
Forgive my wording, but I mean that whatever data is visualized is what would be subjected to fitness test, not the visualization itself.
Just like the shapes of the chassis and the size of the wheels in this demo are essentially numeric data visualized into a series of canvases, some hypothetical startup's data could be visualized in a potentially compelling manner. That's presuming, ofc, that the original data is already suitable for genetic manipulation.
What that data/startup would be? I don't know, just casting an idea.
Ha, you laugh, but human-in-the-loop evolutionary algorithms are well established. And the research communities involved are now looking at applications to cloud computing. So it's just a matter of time before this... recombination.
This seed: "Enter sdfsdfs string" has an almost impossible hill at the end. I've been watching for 20 mins
Edit: This app is very well put together. The "winner"(one that got the furthest) of the previous round is up front for the next and I believes becomes the zero car
By design, every world has an almost impossible hill at the "end". The world keeps extending in a procedurally generated manner (based on the seed) as long as any car keeps moving. And what other than a tough hill will stop a car.
The road will be harder and harder in the end. The code said so:
for(var k = 0; k < maxFloorTiles; k++) {
last_tile = cw_createFloorTile(tile_position, (Math.random()3 - 1.5) 1.5*k/maxFloorTiles);
It took only about 9 generations to the evolve the Tron lightcycle. Way too cool. This is like the marble races down hotwheels tracks we used to do as kids while recording the times, only way less work.
I'm using 5% mutation rate and have 1 elite clone. I thought that meant that the whole population would be based on the winner with a 5% mutation chance (so all 19 are children of the winner). However, I have a track with an "impossible" hill and every round there's one car that almost makes it over but it's never that one which is blue next round.
How does this work exactly?
EDIT: It seems the one that almost made it was a replay ghost or something and not part of the population. Still wondering if I understood it correct though.
No, because it combines cars to generate new ones. Better performing cars have a larger chance to become a 'parent'. You should check out the source, it's suprisingly readable
Speedup improvement should be possible by not actually evaluating the clones as we already know their results - or maybe just show one as a placeholder.
At the moment, if you add "elite clones", the camera follows the stack (but all are exactly on top of each other) and it's a bit slow.
This is very fun, I love playing around with genetic algorithms and watching them evolve. How exactly does the simulation work? Does it stop after a certain amount of time, or do they burn fuel or something? Are they selected for distance, or how long they survive, or what?
I can't answer all the questions but it seems that the current generation is tested until it can no longer make progress for a certain amount of time (displayed as the bar next to its number decreasing, only to be refilled when exceeding its current maximum distance.)
For those of you interested in GAs, I built a small Ruby gem to make building genetic algorithms a little easier: https://github.com/dorkrawk/darwinning
That's my favourite genetic algorithm page , also worth check is this http://boxcar2d.com/index.html where you can create your car and see the best created.
This was a lot of fun. A suggestion for improvement might be to weight where the changes can come (so more or less likely to change wheelbase, or more or less likely to change height, etc) But overall very nicely done.
Hmmm mine just grew into giant two wheels essentially. Started with high mutation, then when I saw one reach about 160 put it to 3% mutations with 5 clones and slowly increasing every time
Awesome! A really cool version of this would let the user write their own algorithm and then have users compete against each other for whose algorithm can evolve the best car.
World seed "schnoo" has a particularly tough hill from 125-145 that several different models can almost but not quite overcome. Anyone able to get over it?
As mentioned already you mean gene, but yes you can and he does already with the wheel density, giving the darker ones more mass than the lighter ones.
In my instance, there are two predominant "types" of cars that are doing approximately equally well--the "rhinoboat" and the "assdragger". But when these two solutions are combined in the crossover, I think they make an offspring that is terrible.
If the algorithm would mate only the rhinoboats with rhinoboats and assdraggers with assdraggers, I'm convinced we'd end up with some superrhinoboats and superassdraggers, but instead I just get an unhappy compromise.
Maybe make "similarity to self" one of the genotype parameters. A high rating here would mean the phenotype would have a bias against being combined with dissimilar creatures. This allows the propensity towards speciation to develop evolutionarily, too.