Sunday, September 13, 2009

Genetic algorithms and Formula 1

The status quo has been rather turned on its head in Formula 1 this year, with the sport's two great leviathans, McLaren and Ferrari, struggling to adapt to the most radical change in technical regulations since 1983. The men and women from Woking and Maranello are generally considered to have the most sophisticated simulation technology in the business, yet it was an open question before the season began whether such a radical change in regulations would be most adequately dealt with by the intuitive and creative mind of an Adrian Newey, or the number-crunching power of inscrutable computer simulation.

The answer, of course, is that on this occasion the programmable calculators were comprehensively blown into the weeds. It appears that the simulation technology which was so successful when the regulations were stable and the cars evolved in a gradual, incremental manner, was decidely leaden-footed when a change of regulations opened a new space of design possibilities. Which begs a rather interesting question about exactly what type of simulation technology McLaren and Ferrari have been using.

To explain, it is necessary to travel back to 1993, when an engineer called Adrian Thompson devised an experiment to test the result of applying Darwinian natural selection principles to the design of electronic circuits. Thompson selected a simple problem: find a circuit design which maps a 1 kHz input signal to an output signal of zero volts, and a 10 kHz input signal to five volts output. The possible circuit designs would be implemented by a Field Programmable Gate Array (FPGA), a microchip containing 100 logic gates, whose connections can be modified by the software code loaded into the memory of the chip.

Thompson randomly generated an initial population of 50 instruction sets, selected the fittest, and then set about cross-breeding the instruction-sets over numerous generations. For each instruction set, a computer fed the two input signals into the FPGA, and recorded the output. Those instruction sets which came closest to satisfying the required map between input and output signals were selected as the fittest, and those instruction-sets were then cross-bred, with some random mutations added, to produce the next generation. The process was then iterated.

The eventual solution, obtained after 4,000 or so generations, was one which no human circuit designer would have conceived:

The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest– with no pathways that would allow them to influence the output– yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones...It seems that evolution had not merely selected the best code for the task, it had also advocated those programs which took advantage of the electromagnetic quirks of that specific microchip environment. The five separate logic cells were clearly crucial to the chip’s operation, but they were interacting with the main circuitry through some unorthodox method– most likely via the subtle magnetic fields that are created when electrons flow through circuitry, an effect known as magnetic flux. There was also evidence that the circuit was not relying solely on the transistors’ absolute ON and OFF positions like a typical chip; it was capitalizing upon analogue shades of gray along with the digital black and white.

As Thompson himself admitted, "really, I don't have the faintest idea how it works!"

A process which obtains an optimal solution to an engineering problem by such natural selection principles of evolution, is called a genetic algorithm. Hence, returning to the subject of Formula 1, it is interesting to raise the possibility that during the period of recent comparative stability in the technical regulations, teams such as McLaren and Ferrari have been evolving their cars using genetic algorithms. Genetic algorithms have been around for a while, and one presumes that the experts who work in Formula 1 simulation technology are well aware of them. Thus, either they've already been using them, or equally, perhaps they just don't work yet because the CFD technology isn't capable of selecting the fittest designs with sufficient speed to make the process practicable.

Applied to Formula 1 aerodynamic design, a genetic algorithm might work as follows: Take an initial design, and then randomly generate an array of variations upon it; feed this array of designs into a CFD simulation, and select a subset which is the fittest, aerodynamically speaking; cross-breed the fittest designs, and add some random mutations, to obtain the next generation; iterate indefinitely.

Such a process might well be very good at gradual development of aerodynamic designs, under a stable regulatory environment, but if there is a radical change in the regulations, it might need a degree of human creativity to orient the genetic algorithm, and pick the correct initial design for the genetic algorithm to begin evolving. Which might just explain the success of Red Bull and Team Brawn this year, and might ultimately explain why Lewis Hamilton crashed on the last lap of Sunday's Italian Grand Prix!


kartmag said...

This approach upon formula one is unique. I am a big fan of formula one, but not only, I like other car races as well, I think they keep your adrenaline high and are very competitive.

John H said...

I've often wondered how much GAs and other optimisation techniques (such as aNNs) are used in conjunction with CFD in F1?

With such a big reg change, human thinking can be very handy in terms of avoiding dead ends.

Thanks for writing this piece it was very interesting.