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."

Comments

It should be noted that...

[mOoZik]

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.

Re:It should be noted that...

[Analogy Man]

This is a very good point. From my experience optimization algorithms are very powerful tools for finding weaknesses in simulations. Using genetic algorithms to optimize wings for supersonic aircraft I ran into some "interesting" solutions. The boundary layer algorithm did not do a very good job of predicting seperation so it over worked some areas of the design beyond what physically would work.

This is not to say that this is not a very powerful tool for complex design spaces. If your design space is not particularly interesting (few localized optimums) gradient methods are more intuitive and efficient.

From the mouth of one in Formula SAE

[Peden]

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.

Genetic Algorithms, Rat Bags and Cheetahs.

[falsemover]

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.