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.
Alternatively, you can get a nitrous oxide kit fitted. BIG power increase for those rare occasions when you need it( zooming away from lights to impress girls )and stock engine for the rest of the time.
They whose government reduces their essential liberties for temporary security, receive neither liberty nor security.
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)!
F1 is only an absolute maximum of 200 miles or 2 hours, whichever is first. Most races are about 190 miles or 60 - 80 laps.
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
No replacement for displacement. j/k ;-)
If you put bigger valves, camshafts with more lift, etc you will also need a new chip though, as many of the stock chips won't be able to handle the new parameters (like the extra fuel on the exhaust side at low rpm caused by the bigger cam). Thus you really need a tunable chip so you can match your new parameters.
I'd stay away from nitrous unless your doing a dedicated race machine in which case by all means put enough nitrous on it to blow the engine within a year (or sooner depending on how much money you can spend on engines).
Reserved Word.
Formula 1 timing is down to the thousandth of a second and there have been occasions when the difference between pole position and second on the grid has been 0.000 seconds, (in which case the first person to set the time gets the pole).
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.
That's just stupid. There are many, many people who run nitrous on daily driven street cars. In fact, you can buy them in as small as 25 HP shots, so they are by no means something that should be reserved for "dedicated race machines".
Your comments about needing an aftermarket ECU are also misled. Most stock ECUs are programmable to some degree, and some are highly adaptable. I know a guy running a 30 PSI turbo in his 780+ HP Supra and he's on the stock ECU. Granted, if he went aftermarket he could pick up another 50 HP or so, but that's beside the point.
Slashdot quality declines as the number of hot grits posts decreases. - Provolt's Law, Apr-09-2005
I expect I could do a lot better with traditional optimization methods. Genetic algorithms are notoriously slow at converging and are only any good when all other methods fail. I expect that for a racing simulation the output is, almost everywhere, a differentiable function of the input parameters, and hence you can use some kind of calculus based minimization algorithm. People use adjoint methods all the time to differentiate fluid dynamics simulations or orbital manoeuvers so I don't see that these methods would fail for a racing sim. In fact this paper is probably a good place to start.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.