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."
I did some research and programming in this field over a decade ago. The really frustrating thing about this field is how slow moving it is and how little it is taken seriously.
When you have constructed an environment and electronic "organisms" that can breed within that environment, and then watched the generations gradually improve and adapt to the environment, you get the feeling of a new kind of power that we haven't really tapped yet - evolution.
I think one of the problems is that people don't get what is happening in these types of projects. When I showed people the projects I was working on - even biologists and computer scientists - the first reaction was that what they were seeing was just a simulation - i.e. that I had programmed in the fact that the organisms adapted to the environment. It took a lot of explaining to convince some people that what they were seeing was actual evolution, albeit in digital form.
The fact that this research is just looking at breeding cars which are used in a computer game just demonstrates how slow moving developments in this area are. Evolution could be used to improve many aspects of cars -- their engineering, efficiency, production and even visual design. It will happen one day, but it's taking us a hell of a time to realise that we can exploit the force that produced all the wonderful things we see in nature.
There is a large difference in evolved behaviour between physical things and models of those same things.
Surely that just means your physical model of the real world is not correct?
One of the classical algorithms to do genetic evolution using floating point values (not bits) as parameters, is Differential evolution.
What's in a sig?
Reminds me, I made this,
which is some very simple code for the uninitated to genetic algorithms.
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.
I work in this field too: :)
I remember some years ago, talking with a coleage, about neural networks, I told him that i was using genetic algorithms for a) select suitable initial conexion values, and b) help to scape local minima.
He as surprised that both methods could succesfully cooperate.
What's in a sig?
88/100th of a second per lap?
Isn't that well within the margin of error that the human drivers would introduce? If the driver takes a turn slightly off of the most optimized route, wouldn't that negate the fraction of a second these algorithms are providing?
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.
For an F1 team, cost's not so much a consideration, though, the trouble is time. To be able to change that many parameters means having someone get under the car, swap a pile of parts, and send the test driver back out on track to collect the info for the next evolution. Computer simulations are neat, but they're not perfect, and when you're talking about shaving fractions of a second, that small imperfection can throw it completely away.
I also wonder if this would actually be useful in the real world with real conditions. The sun going behind a cloud for a while has a measurable effect on lap times. The amount of gas in the tank, the temperature of the track, all those things change the way a car handles on the edge. Often, race setup is to dial in a car to be a little tighter or looser than what you really wanted because you expect the track to come to you.
And then there's a possibly even bigger problem: If you go out and look at two cars that are running identical lap times, chances are they're nothing even close to identically set up, because drivers aren't machines. One driver will like a certain setup, and another won't be able to do anything with it.
Not only is there the performance gap in F1, but compared to Nascar, there's very little following of a safety (aka pace) car. This Sunday was the exception at Indy though. The tracks themselves have a lot of run off area (with the exception of Monaco), so usually when a car crashes, it's off track, or quickly removed from the track. In Nascar, if there's a crash, out comes the pace car, and the cars all bunch up again. Also, again, track design sometimes makes it very difficult to pass in F1, so a faster might get held up by a slower car for a few laps.
:) (Long time Ferrari fan, so I'm just loving the current domination of them rather than McLaren and Williams destroying the field. But such is F1, and another team will dominate eventually, and the cycle will continue.
And actually, on average, you're going to see a red blur every 45 seconds or so, and I love it
WWJD.... for a Klondike bar?
Darwin himself went to great length in his Origin to explain the existence of ants. Having the majority of the population as sterile workers seems to contradict the theory of natural selection. Tautologies cannot be contradicted by evidence, yet ants seem to contradict natural selection. Maybe it's a theory and not a tautology? Darwin found an elegant way out of this by explaining that even though the ants themselves do not reproduce, they do create the environment in which their nieces (future queens) can.
Natural selection is not a tautology. When a few baseline ingredients are there it 'just happens'. Once these ingredients are absent, it doesn't. Some interesting experiments with self-replicators have been performed that identified that for natural selection to take off, initial diversity needs to be there. If not, the first replicator, for a large part irrespective of how inefficient it is, will take over the world. This you can call 'Survival of the firstest'. Also experiments have performed where a diverse set of self-replicators are competing: there you will see 'Survival of the fastest', i.e., the fastest self-replicator wins. Both phenomenon do not point at the open-endedness of evolution as we see in nature. Survival of the first would preclude evolution; survival of the fastest would preclude the existence of complex beings like mammals. For a tautology, it seems to be awfully hard to implement. In effect: even at this point it is unclear how to make open-ended, self-diversifying evolution work. Genetic algorithms are too simple to do that, and even a system like Tierra stopped at some point.
What genetic algorithms do is indeed mimic the exponential growth that is present in the definition of lifetime fecundity; that is what makes the thing perform different from random search. Above average performing individuals will receive more offspring. If and only if this offspring is above average performing, the exponential will take off and the genetic material will take over the resources. Note that both the parents and the offspring need to be fit, implying that also the reproduction mechanism itself needs to be sensible. This is what most EC research is about. It is hardly tautological, but an interesting way to search. Truly open-endedness is not there in the algorithm, and in effect, using lots of degrees of freedom in representational flexibility usually doesn't pay off in solving a single problem. Still, it's one hell of an optimizer: there's no necessity that the fitness (cost) function is continuous, let alone differentiable; it's 'embarassingly parallel', meaning it can run at a highly parallel machine without any significant overhead (linear scaling), and simply performs well for an astonishing range of applications.