Don’t invent, evolve

Oct 3rd 2007
From Economist.com

The inventor’s trial-and-error approach can be automated by software that mimics natural selection

“I HAVE not failed. I have just found 10,000 ways that won’t work.” So said Thomas Edison, the prolific inventor, speaking of his laborious attempts to perfect the incandescent light bulb. Although 10,000 trial-and-error attempts might sound a little over the top, an emerging technique for developing inventions knocks even Edison’s exhaustive approach into a cocked hat. Evolutionary design, as it is known, allows a computer to run through tens of millions of variations on an invention until it hits on the best solution to a problem.

As its name suggests, evolutionary design borrows its ideas from biology. It takes a basic blueprint and mutates it in a bid to improve it without human input. As in biology, most mutations are worse than the original. But a few are better, and these are used to create the next generation. Evolutionary design uses a computer program called an evolutionary algorithm, which takes the initial parameters of the design (things such as lengths, areas, volumes, currents and voltages) and treats each like one gene in an organism. Collectively, these genes comprise the product’s genome. By randomly mutating these genes and then breeding them with other, similarly mutated genomes, new offspring designs are created. These are subjected to simulated use by a second program. If a particular offspring is shown not to be up to the task, it is discarded. If it is promising, it is selectively bred with other fit offspring to see if the results, when subject to further mutation, can do even better.

The idea of evolutionary algorithms is not new. Until recently, however, their use has been confined to projects such as refining the aerodynamic profiles of car bodies, aircraft fuselages and wings. That is because only large firms have been able to afford the supercomputers needed to mutate and crossbreed large virtual genomes—and then simulate the behaviour of their offspring—for perhaps 20m generations before the perfect design emerges.

What has changed, in this as in so much else, is the availability and cheapness of computing power. According to John Koza of Stanford University, who is one of the pioneers of the field, evolutionary designs that would have taken many months to run on PCs are now feasible in days.

The result is that the range of applications to which the principles of evolutionary design are being applied is growing fast. Among those revealed at the Genetic and Evolutionary Computation Conference held in London this summer were long-life USB memory sticks, superfast racing-yacht keels, ultra-high-bandwidth optical fibres, high performance Wi-Fi antennae (evolved to avoid patent fees), cochlear implants that can optimise themselves to individual patients and a cancer-biopsy analyser that was evolved to match a human pathologist’s tumour-spotting skills.

How can evolution help improve a USB stick? It turns out that the storage transistors in these flash-memory devices are prone to being gummed up with electrostatic charge that they cannot dissipate. That prevents them being erased, limiting the stick’s useful life. A team at the University of Limerick in Ireland therefore evolved new signal-timing patterns that minimise the build-up of the disabling charge. The result: USB sticks that last up to 30 times longer than their predecessors. At the University of Sydney, in Australia, Steve Manos let an evolutionary algorithm come up with novel patterns in a type of optical fibre that has air holes shot through its length. Normally, these holes are arranged in a hexagonal pattern, but the algorithm generated a bizarre flower-like pattern of holes that no human would have thought of trying. It doubled the fibre’s bandwidth.

Meanwhile, Pierrick Legrand of the University of Bordeaux has used the method to optimise individual devices to the user. The devices in question are cochlear 耳蝸 implants, which help those hard of hearing to hear better. One of the hardest tasks facing those who fit these devices is working out the precise choreography of the voltages and timings that need to be applied to the 20 or so electrodes embedded in the auditory nerve, in order to make them work properly. The signals required vary from patient to patient and some people go many years before an audiologist gets it right. Dr Legrand, however, has developed an evolution-based system that works on the fly. It co-evolves several channels at a time, allowing a patient to tell his doctor how each pattern of electrode stimulation is faring. Dr Legrand says that one patient, who had experienced a decade of trouble with his implant, had it fixed in a couple of days by the evolutionary method.

Perhaps the most cunning use of an evolutionary algorithm, though, is by Dr Koza himself. His team at Stanford developed a Wi-Fi antenna for a client who did not want to pay a patent-licence fee to Cisco Systems. The team fed the algorithm as much data as they could from the Cisco patent and told the software to design around it. It succeeded in doing so. The result is a design that does not infringe Cisco’s patent—and is more efficient to boot. A century and a half after Darwin suggested natural selection as the mechanism of evolution, engineers have proved him right once again.