Slashdot Mirror
Breeding Race Cars With Genetic Algorithms
smack-pot writes "Wired News has an article about how the Digital Biology Interest Group at University College, London is using genetic algorithms to breed superfast Formula-One race cars. 68 design parameters were configurable in the cars, and the generated designs were tested using the racing simulation software developed by the game developer Electronic Arts. According to the research it is possible to shave off 88/100th of a second per lap by using genetic algorithms to tune the cars. In an industry where a tiny fraction of a second matters, that's significant."
Here's a good link for people who don't know what genetic algorithms are:
It should be noted that the "research" was done with a video game and no actual tests have been conducted on real cars and situations. This does not mean the techniques cannot be applied in real situations, but just that it has not been done yet.
A blog like any other.
88/100 = 0.88
So it's about one second.
500 lap race = 440s. Not insignificant.
AKA "chipping". At the expense of engine life, this can get huge power gains out of turbocharged cars by increasing the maximum boost. Normally aspirated cars can be pushed up a few bhp by messing with the fuelling, but generally the gains are less obvious so they're sold as "driveability improvements" for non-turbos. To get a decent power increase from a non-turbo engine you need to make it breathe better. Porting and gasflowing the head is most effective (and expensive). Fitting bigger valves, hotter camshafts etc will all still do a lot more than a chip!
When I am king, you will be first against the wall.
As a member of a raceteam which is about to enter the formula SAE competition. (A global university based competition aimed at building the fastest racecar) I find that 68 parameters are not nearly enough. Modern racecars have that many in the suspension alone. And all those phony calculation with determination of how many seconds are spared cannot be used for anything concrete.
The advantage is not slim in Formula One. They are routinely fighting for single hundredths of a second. Official timing is down to the hundredth and there was actually one race where 3 cars qualified with the same time down to the hundredth.
Revolutions are never about freedom or justice. They're about who's going to be top dog. -- Kilgore Trout
All that aside, do you watch NASCAR much? I'm not what you'd call a NASCAR junkie, but I do watch at least every other race. Tenths of a second in lap times are frequently the determining factor between pole and, say, 10th qualifier. Races are often decided on margins approaching less than one second.
All that said, yes, one bad pit stop can and does ruin a race. So does one unseen oil slick. Kasey Kahne should have won Dover, period. The officials were loathe to call a caution so late in the race, after so many cautions had already been called, and cost Kasey his first win.
Sucks.
And tenths of a second did it.
"BSD: Free as in speech. Linux: Free as in beer. Windows 10: Free as in herpes." --Man On Pink Corner in #52607549.
The to five finished i i the same second.
2 .html
1: Pether Gethin 1:18:12.60
2: Ronnie Petterson +0.01s
3: Francois Cevert +0.09s
4: Mike Hailwood +0.18s
5: Howden Ganley, +0.61s
See http://www.formula1.com/archive/grandprix/1971/52
for complete results.
For a nice date: Call strftime(3C)!
Interestingly enough, Peter Bentley's group results on car racing would not be considered human competitive, unless the results obtained in the simulation will be tried in the real world, or if the simulator is something experts actually use to shave of seconds. In any case, it seems the Evolutionary Computation world is starting to obtain very strong results, for a part due to Moore's law. It's possible that this is caused by the fact that the field simply tries to solve things, instead of first proving that it works (AI/ML), or proving that it doesn't work (Operations Research).
Ok, having done a lot of work in Genetic Algorithms here is the elevator pitch.
A genetic algorithm is an algorithm that manipulates encoded problem solutions using a population of potential solutions. Each solution, or population member, in this case, is a set of racing car parameters. The genetic algorithm selects a couple of solutions and recombines parts of each to produce two new solutions using a recombination operator. Mutuation is normally added as well. The two new solutions are then "measured" for fitness; in the racing scenario a full scale simulation of the actual car is carried out. This produces a single value of fitness that is associated with the newly generated member.
The algorithm proceeds by selecting a couple of candidate parents; normally with random bias weighted toward fitter parents. The parents mate, new chidren produced, the children are measured, then integrated back into the population and they cycle continues.
The end result of all of this is that small "above average" solution components "accumulate" in the population at an exponential rate as time goes on. Of course, this only happens early in the first few generations before high "saturation" / convergence levels are reached. This is kind of cool because something good is happening at an exponential rate as time goes on; this is very useful when trying to solve problems with vast state spaces; eg the problem of finding a good racing car model where you need strong brew to find a resonable solution. Later on, most of the population members can often encode very fit solutions. This mathematical property (exponential accumulation) explains why the genetic algorithm is the algorithm of choice in nature, and also why an alarming proportion of PhD students are now studying genetic algorithms. This technique isn't new either, as Ratbag games have been using these techniques and other cool machine learning techniques for years to evolve the AI on their car titles such as "Dirt Track Racing" and "Powerslide".
Of course, we already know that this stuff works; as a quick trip to the zoo will show you what evolution has done to optimize the cheetah.
This is a very simplified view; there are a bunch of design issues such as encoding, premature convergence, crossover (recomination), reproduction methods, method of generation, population sizing, operator adaptation that make this whole field very interesting and addictive. Having written a dozen genetic algorithms and solved many many problem types using GAs they never cease to suprise me how powerful these methods are.
consider coffee a lubricant that helps one penetrate the coding zone
Foremost from my amateur racer point of view is the cost: Being able to tune any one of 60 some-odd parameters probably means being able to swap out any one of 60 some-odd parts with some other part, so you've got to have one of every possible part on hand or be able to fabricate it.
Well, no, not exactly. Do you use adjustable dampers on your car? Simple bump/rebound adjustment is 8 parameters (each wheel is a seperate system) right there alone. Roll bar lever arm length adustment, another two. Tire pressure, another four. Camber, another four. Toe, another four.
We're up to 22 so far and haven't spent a penny or changed a part, nor have we yet exhausted simple suspension settings. Toe, 26. Castor, 28. Anti dive/squat, 30. Half way there already.
Front and rear wing angles, brake bias, weight distribution. More stuff that simple adjustable.
Ok, let's look at some of the parts that are commonly changed. Tires. Did you think of tires as a part? They are. They're a parameter. How many compounds have you got, hard/soft/wet? Maybe you're poor and only have three sets of springs, hard/medium/soft
We're over our 60 parameters now and are still well within the range of changes that an amatuer racer would consider common and haven't touched the gearbox yet.
Which is why we are also still within the range of simple car adjustments allowed in a video game which doesn't allow for fabrication of unique parts.
Assuming you race in a catagory that allows these changes. Many amatuer, and even "entry level" pro catagories deal with the issue by simply disallowing changes. If you race Formula Vee/Star Mazda/Spec Miata/Barber Dodge you aren't going to be doing anything like changing suspension arms.
60 parameters is nothin'.
KFG
That's why for problems with very expensive fitness functions, it's often better to use a simulated annealing technique. In SA, there is only one individual, not a whole population, so you only have to evaluate fitness once per iteration instead of potentially hundreds or thousands of times.
Simulated annealing works like this: make a random (or in some implementations, a heuristically guided) change to the current individual. Evaluate the new fitness. If the change has improved the fitness, accept the change. Otherwise, choose at random whether to accept the change, with the chance of acceptance slowly decreasing over time. Hence the term "simulated annealing," named after the process of annealing steel by cooling it slowly, which allows the crystal domains to enlarge.
This means that sometimes changes are accepted which actually decrease the fitness, with the hope that you might perhaps be able to escape a local maximum on the fitness landscape.
In my experience, simulated annealing often works well in the same situations that a GA works well. And it's much easier to implement, too.