Mine just reached generation 6 with a previous score of 367.4 ...

Does mutation rate even do anything? I set it to 0 and it's still completely random.

"The colors show the crossover and mutation for each member of the population." Is that referring to the colors of the polygons?


Red line graphs distance travelled for that generation. My generation 6 was almost at 400, my generation 12 is at like 200, and the latest addition to the red line is half that of the previous spike.

Post has been edited 4 time(s), last time on Jan 22 2011, 3:29 am by FaRTy1billion.

Quote from O)FaRTy1billion[MM]

"The colors show the crossover and mutation for each member of the population." Is that referring to the colors of the polygons?

Yep. If you refresh, you'll notice that the first generation all has the same sets of colors per iteration. After that, it starts randomizing and/or logically recombining the polygons, wheel struts, and wheel sizes. Randomization of 0 means eventually it'll even out, with the averages and the totals eventually being the same...no mutation, no chance for additional progress...

The red line and the score at the bottom can't be the total score of the previous generation, it must be modulated somehow, as I was watching a generation that should've scored over 500 based on raw score but it only came out as ~390 or so.

I've left mine running all day while I was at work, for about 8 hours now since I last commented in this thread. I'm now at generation 150 and mutation rate has been pegged at 8% this entire time. I still get quite a few non-starters or cars that score only 10 before failing, so really this is quite a shitty algorithm. If you follow the link MrrLL posted you'll see the original program this was based on, where he says he tweaked the settings for entertainment rather than being a serious solution generation. In that line-based one, usually within 3-4 generations you'd get 90%+ of the cars starting with their wheels directly on the ground, whereas with this polygon one I still got duds at the 20th gen mark and are still getting some now at #150. Interestingly enough though, almost all of my wheels are very large now, so there is a clear genetic improvement over time with regards to wheel size.

My red line is quite high but still shows quite a lot of variation, and the black line has only gradually trended up but has shown much more fluctuation than the red. On average, the black line is 1/2 the red line and has stayed that way the whole time - it hasn't improved, which shows a real failure to distribute good genetic code amongst the population.

Like I said in my post above, I think the problem with this polygon one is that it's mixing the pieces up randomly between all candidates in the previous generation, whereas the stick-based one I'm pretty sure will be doing breeding only between the best few solutions from each generation (or possibly just culling the worst few completely and breeding between the remaining ones). In any event, it isn't aggressive enough in weeding out bad traits and selecting for good ones.

I find occasionally turning up the mutations then bumping them back down again after a time works to squeeze out a bit more mileage. Keeping mutations too high prevents the algorithm from refining what might already be viable solutions, whereas turning it too low eventually stagnates the designs and they start to homogenize.

When I last posted around generation 150, my black line had been bumping around 50% of the red line for a long time, between then and 173 it got up to about 66%. At generation 173 I set my mutation rate down to 0%, and now at generation 178 my black line has shot up to about 80% (so far) and the red line has ticked up a little also. In the last full generation I watched, there were 0 non-starters (compared to a usual 2 or 3) and the lowest score was 53 and the rest were all over 100.

So it seems that the non-starters and shitty performers were a result of the mutation rate, rather than the genetic combination going on. I guess this suggests that the worst performers of any generation are culled and not used as ancestors for the next.

Edit:
Up to generation 189 now, and about 4 generations ago I set my mutation rate to 1% (from 0%). This made an immediate impact on the black line, and also on the red. The black line was up to about 90-95% of the red one, and all cars were getting over 150 with quite a few getting to 190-212 range. Immediately with a mutation rate of 1% I got non-starters, or cars that would only get to 50 or so. It seems that a mutation in this program means "select a variable and completely randomize it", with apparently (my theory only) your nominated chance of this happening for any independent variable. So rather than 1% chance of your car having some mutation, it's a 1% chance for each individual polygon, of which there are 8, and presumably 1% chance for each of the wheels and the springs that hold the wheels to the rest of the frame. So a 1% mutation rate gives you a much higher rate than you might've expected - if I'm right, this would be 99%^12 of no mutation (~88.6%) or actually 11.4% chance that any single car would have some mutation present, which seems about right because out of 20 cars I'd get 1 or 2 with obvious performance degradations compared to leaving the rate at 0%.

So I guess this explains why it seems so wonky - the mutation rate is higher than what you might expect, and a mutation apparently means "completely randomize this value for me", rather than the more useful "randomize this value within +/- 5% of its current value".

So once you get to a good base population, turning your mutation rate down to 1 or 2%, and then finally 0%, seems to be the way to get the fittest cars possible.

Also I suspect the steep hill around 210 points is probably unclimable - I think any car that is capable of driving that far into the course, will be designed in such a way that it can't climb the hill. I could be wrong of course, and maybe leaving it running for long enough with a 1% mutation rate you'd manage it, but I wouldn't count on it. Actually Kaias above says at generation 16 he apparently had 2 cars get to 240, which is interesting. I'm going to leave mine going over night at 0% mutation, I'll see what it's like in the morning.

Post has been edited 4 time(s), last time on Jan 22 2011, 10:36 am by Lanthanide.

Double post, but the last one was getting pretty long.

I started a new simulation in parallel and figured out a few things. Turns out the red number is double the best score in the previous generation. The number is also used as a cap, which is visible early on, and explains my complain earlier in the thread of cars being ended prematurely. As soon as a car reaches the current red number (twice the previous best score), its attempt it cancelled, to within a few decimal points. Presumably cars that reach this threshold are so far ahead of others in the same generation that they will definitely be used when generating the next?

Also the track is randomly generated, following some rules for difficulty. So in my post above I speculate that the hill around 210 will be unclimable - this looks to be the case in the terrain I've spawned, whereas Kaias spawned terrain that he was able to overcome very quickly.

In my new simulation I immediately set the mutation chance to 0%. The cars are now all blue/grey in colour as they were the winning cars in the first generation, and so all descendants came from them. With 0% mutation, they also very rapidly become excellent at traversing the course - every generation up until the 5th they were meeting the red cap number and ending prematurely, and the 5th generation has 6 out of 10 cars that have gotten a score of 173-177. My graph is almost a vertical red line from the start.

So it seems that because of the (IMO, poor) way the mutation rate has been implemented, you'd be best to leave it at 1% or maybe 2%, but no higher.

Maybe it is self correcting to eliminate outliers? On top of this, what if each sample has its own kill switch, so regardless of behavior when xyz happens the program is terminated. Assuming this is showing evolution, it is feasible.

I played with the mutation rate a bit. Had a 250+ earlier but didn't screenshot it. I climbed the same big hill at around 210, I'm pretty sure it's not random.



edit:

Obvious to you, perhaps. You're not a machine.

You're not quite getting why this is called a genetic algorithm. It simulates evolution. Imagine that we have an animal that's trying to figure out how to run for the first time. If you just pick the first evolved animal that is capable of running and essentially clone it with very subtle differentiation between generations, you're never going to get far from that animal, because it was the first thing that worked. So you might have a turtle and this conservative approach is essentially saying, "it works, perfect!" and is what a low mutation rate is doing. A high mutation rate, by contrast, says "I don't know if this is going to work, but we're going to try it!" So yeah, you might get some animals with four legs on one side that can't run at all and die immediately, but you're also far more likely to get a jaguar. That's the nature of the beast: you have to fail- repeatedly- to find what works best.

I just started 5 different trials that I'm going to run for a few hours with varying levels of mutation, I used 0%, 5%, 20%, 60%, and 100%. About 10 generations in the default 5% is outperforming the others tenfold. It would be interesting to narrow down exactly what rate is ideal.

Post has been edited 3 time(s), last time on Jan 22 2011, 5:18 pm by FaZ-.

My Generation 6 got 234 O_O;

EDIT: Attachment of some kind of box car I didn't know was possible.

Attachments:

Post has been edited 1 time(s), last time on Jan 22 2011, 4:53 pm by Raitaki.

Cool.

Result of generations of inbreeding and kick-ass mutation rates perhaps?

Boxcars similiar to it are present in new generations, but none could make that far :3

The first time I ran it at 5% mutation the program seemed to think that the best mode was to have a larger front wheel and a tiny back wheel. I got a few car-like shapes. The successful ones had fins on the back to counteract the weight on the front - which was rather heavy, otherwise the whole structure would topple over. Then FireFox crashed Pretty fun, though. I'm starting it again.

20%, 60%, and 100% mutation all crapped out, they maxed like 10 it seemed like from the graphs, except one time that massively blew everything away, probably ~200, but evidently wasn't selected for.

0% mutation was pretty funny and pretty much proves exactly what I said above:




I think we could actually have a contest to see how good our recognition skills of what works are by seeing who could get the furthest average distance on the 15th or so generations simply by toying with the mutation rate. =D

The courses are definitely randomly generated, following a formula obviously. That's called 'procedural generation', just so you know.

Um, no. I understand *perfectly* what a genetic algorithm is, thanks. I do have a CS degree. You entirely missed my point.

I was saying that a 1% mutation rate doesn't do what you might think from the name - it doesn't appear to be 1% that an organism will have any 1 single change - eg out of 5 generations of 20 cars each, 100 cars in total, you'd expect with a mutation rate of 1% that only 1 single car will have been mutated. My observations show otherwise - I had a population of cars, where every car would get a score of at least 150 with a mutation rate of 0%, and changing the mutation rate to 1% would result in 1 or 2 cars out of those 20 having obvious performance degrading mutations, such that my black line performance dropped noticeably. This shows that a 1% mutation rate is not mutating 1 out of 100 cars, but more like 5-10 out of 100 cars, and I proposed a way by which a 1% rate could mean this - by subjecting each of the 12 individual parts on the car to the rate independently, rather than the car as a whole, you end up with a 'car has at least 1 single mutation' rate of about 11.4%

Further, I used this observation to show that "mutation" means "completely randomize this part", as in pick a whole new random number between 1 and 100 say, rather than "take the existing number and randomly adjust it up or down by 5%". It was doing the former because I went from cars with a score of 150+ to 0-10 instantly. These non-performers were landing in terribly positions or had tiny wheels, while the rest of my population always landed perfectly and have big fat wheels. If it were a simple 5% skew on the current value, I definitely would not have gone to 1-2 non-performers instantly.

So you completely misunderstood what my post was about - I was giving data on how I have observed the mutation system to work:
A) it affects cars piece by piece and
B) it seems to completely randomise the piece, rather than just skewing the value a little.

Both of these aren't very good implementations - it means that a 1% mutation rate actually mutates things much faster than may be expected, and also by completely randomizing a piece in a population that is already achieving well, you are much more likely to degrade performance than you are to improve it. If a mutation meant "skew the value of this variable by a small amount" then with a highly performing population you'd be more likely to have a chance at increasing performance, or only decrease performance by a small amount. Basically genetic algorithms perform simulated annealing and attempt to find a local maxima of performance against the fitness function. The trap is that you'll end up stuck at a non-optimal maxima (see below where I note that my cars perform 197.5 now, whereas I used to get a few at 212) and need mutation to get you out of that maxima - the problem is that completely randomizing a variable, rather than skewing it, is likely to throw you so far away from your local maxima that it's a useless thing to do.

Having said that, this is supposed to be for entertainment, rather than serious modelling to solve a problem. But I think adjusting either point A or B would make this more consistent and interesting - certainly when I had an 8% mutation rate I had a plethora of non-starters, which simply wasn't fun. I'd be more in favour of introducing another slider, "mutation degree" with a scale between 1% and 100% which would indicate the degree of mutation you want. At the beginning you'd probably want a mutation rate of 5-10% and a degree of 100%, and then fairly quickly drop the degree down to 20% or so, and slowly reduce from there, along with the rate. Essentially simulated annealing with a lowering temperature.

And because the track is randomly generated each time, this is a meaningless test. Also, if you get a good population to begin with, then your 0% mutation rate has a good chance of easily beating out the other tests, as has happened in my test.

The left one is my simulation that I left running with 8% mutation for about 8 hours, then where the big spike up on the left occurs I had set the mutation rate to 0. A short while later you see a large dip down in the black line - I had set the mutation to just 1% and it made a massive difference in outcomes (lots of non-starters). Putting it back to 0% restored the performance, and as you can see there is now a flat line for red and black and all cars are identical. Interestingly enough, I used to have a few cars that were performing around 212 or so, but it seems they got themselves selected against somehow.

The one on the right is where I tested with 0% mutation from the first generation, you can see the score results very rapidly shot up to about 177. The black line eventually meets the red one and all cars are almost identical now. If I leave it for a few more hours it'll probably winnow out the poor ones.

Attachments:

Post has been edited 6 time(s), last time on Jan 22 2011, 8:46 pm by Lanthanide.

My mistake, I had thought that was standard, I don't know if it's the acceptable way to mutate genetic algorithms but that is normal in actual biology. Either a part is entirely mutated or it's not, you can't control actual degree of mutation in real life. Still, if you only have a chance of mutating a single part on a car, it would be a pretty useless genetic algorithm because you could never change more than one thing at a time; fitness isn't always boolean like that.

Definitely meaningless with a single trial, over many it could be interesting. The randomness of the mutations is also a big factor, I wonder if there's some way to seed it.

Using my uniform population where all members get 197.5 exactly, I decided to turn the mutation rate up to 1% for a single generation, to see what came out. Of the 20 cars, 5 of them did not score 197.5 any more, so we can say these cars had at least 1 mutation each. So setting a rate of 1%, actually resulted in 5/20 or 25% of cars having at least 1 mutation - this holds with my theory that the selected mutation rate is applied on a per-piece basis, rather than on the car as a whole.

Of the 5 mutated cars, I got scores of 206.5, 197.3, 196.9, 196.9 and 0.3. So one of the cars did clearly better - it's wheels were much closer together, 3 cars were about the same - the polygons on the back were in a different shape, and 1 car was a non-starter - it had a polygon striking down between the wheels, such that it never took off at all. Clearly the mutations of 206.5 and 0.3 made quite extreme differences in the performance of the car, and visually they looked like quite large changes. I didn't get any cars with tiny wheels, though.

My previous supposition that there would be a 1% chance of 12 pieces changing appears incorrect, as that should result in 11.4% of cars, or 2/20 having at least 1 mutation, but I have observed 5/20 which is more than twice as high. If instead we assume that each of the 8 polygons can randomly have one of their 4 points changed, then we get 0.99^36 chance of 0 changes, or 30.3% chance that any individual car will have at least 1 mutation. This is fairly close to my observed 5/20, so is likely to be how it is calculated. This means the mutation rate is even more deceiving that you would think just by looking at it, and also means the chances of any individual car having 1 mutation rises very sharply as you increase the rate: at 2% mutation we would expect 51.6% of cars to have a mutation, at 3% we would expect 66% of cars to have a mutation, at 5% we'd expect 84% of cars and at 10% we expect 98% of cars would have *at least 1* mutation.

I set my mutation rate back to 0% for the next generation, and although I missed the final scores, I can see that the mutations that lead to scores of 197.3 and 206.5 are still present in the population, but no cars scores the abysmal 0.3 again. So clearly the worst performers of the previous generation are culled and not considered when producing the next generation. Also the mutation rate is only taken into account at the start of the generation - I set it to 100% between car #15 and #16, and #16 looked identical to all the others and achieved a score of 197.5.

The degree of mutation is controlled a lot in real life, though - sure there are lots of genetic diseases, or simple pregnancies that never complete due to a serious genetic mistake, but at the same time there are lots of minor mutations that make bugger-all difference in real life (crooked thumbs, 'double jointed' fingers etc). In my test above I got 5 mutations, of which 2 were significant - this is an acceptable rate I think, but there's no indication that I couldn't have easily just have had all 5 of them with significant mutations.

Also the presence of radiation does make a big difference to mutations in real life - you get a big increase in miscarriages and still-births, and a big increase in significant birth defects. Clearly if real-life worked as you indicated, where any random mutation of any degree was the standard case, these sorts of radiation-induced problems would be the norm, rather than the outlier.

Attachments:

Post has been edited 2 time(s), last time on Jan 22 2011, 9:57 pm by Lanthanide.

I figure that the way to create the perfect car is this:

1) Set mutation rate to 0% and let the test subjects breed until the best breed becomes dominant
2) Expose the subjects to slight radiation, and observe the population for any mutant that evolved better traits
3) Stop the radiation and continue letting the population evolve
4) Rinse and repeat 2 + 3

Radiation causes tons of mutations even in babies that are born healthy. Post-nuke Japan shows this pretty clearly. Most of these mutations just don't immediately affect anything, like your 3/20 that didn't really change. The number of "parts" is just massively higher in real life, to the point where our resiliency to single mutations is huge. That's why exposing yourself to radiation or carcinogens is such a dice roll; the mutations have to hit the small parts that actually matter. If they do, enter cancer.

Essentially, except you're rolling the dice at the start. Instead you'd be better off starting with a small mutation rate until you see something that looks close to what you'd like, then lowering it. I assume the algorithm would pick up on the maximal scoring car.

No, I don't think so. Natural selection is much more reliable than mutation. The Flash generates cars by picking all of the cars the distance travelled of which is closest to/reaches the distance quota of each generation (the number in the brackets right of the score) and crossover their traits. That way all the lame and terrible traits, which can be introduced by mutation (e.g. wheels at the top, spike pointing forward, tiny wheels, etc.) will be excluded from the population.

Look at the image I posted earlier. That was established after a few generations and was then further "refined." But it's a terrible place to start from, it's actually probably worse than completely restarting. I don't see how that could be better than mutating until you found a good base and then refining that.