Evolvable hardware

Toby Howard

This article first appeared in Personal Computer World magazine, April 1998.

BACK IN THE 1950s, John von Neumann conceived the idea of machines that could automatically repair themselves, and even reproduce. It was an idea straight from the pages of science fiction, and has stimulated decades of research into cybernetics and artificial life. Now, some of his ideas are becoming reality, as engineers are starting to create a new species of computer hardware -- not by painstaking design, but by evolving it using the laws of natural selection.

Adrian Thompson, a researcher at the University of Sussex, recently created one of the first working examples of evolved electronics, or "evolware", using a special chip called a Field Programmable Gate Array. The FPGA is a kind of logical Lego set: the chip comprises a 64 x 64 grid of simple logic cells, each of which can perform one of the basic Boolean operations -- such as AND, OR, and NOT.

The operation performed by each cell, and how its inputs and outputs connect with other cells, is completely determined by a string of bits stored in the chip's master memory. This makes the chip incredibly flexible: one particular bit-string might configure the chip to perform as an adder; another might make it a multiplier, and so on. This bit-string is a single sentence of information which completely describes the chip's function. And a new string can be downloaded onto the chip from a host PC at any time. When it arrives, the chip reconfigures itself immediately.

Thompson's experiment involved using only a 10 x 10 corner of the entire grid of logic cells, and he set out to evolve a circuit which would be able to tell the difference between two audio tones applied to its input. Many experts considered that it would be impossible to configure 100 simple binary logic elements to do this job, without giving them access to a clock pulse for providing a timing reference. Thompson proved them wrong, and not only that, the circuit designed itself.

Thompson used a "Genetic Algorithm" -- an extremely simplified model of how biological evolution occurs. The idea is to create a population of individuals, each of which has its own genetic identity, called its "genotype". In terms of the FPGA chip, the genotype is the bit-string that encodes the chip's configuration.

The evolutionary process begins by generating an initial population of individuals, each with a random genotype. Then, the "fitness" of each individual is evaluated by creating the corresponding circuit (by downloading the genotype onto the chip) and checking to see how well the circuit performs. Naturally, at this early stage it is exceedingly unlikely that a randomly created genotype will correspond to a usefully working circuit. But some of the initial circuits will at least do something, even if it is quite unrelated to the desired result -- and some will be better than others.

Having tested all the genotypes of the first generation, the next step is to breed a new generation. The fittest individual is retained, and of the remaining population a few fit specimens are selected to be parents. Their genetic material -- the bits in their genotypes -- are then combined to create the children which will populate the new generation. At this stage a small number of random mutations are also allowed to occur. The process then repeats. What might take millions of years in nature, occurs in a few seconds.

In effect, what the algorithm is doing is searching through all the possible configurations of the circuit, but ignoring vast numbers of configurations which are unlikely to be successful. In Thompson's experiment, the size of the first random population was 50, and each genotype was a string of 1800 bits. The Genetic Algorithm ran on a PC, transferring new genotypes onto the chip as they were generated. Thompson monitored the circuit's behaviour with an oscilloscope, watching the waveforms change as the circuit evolved.

Initially, the circuit produced only a constant output, but after a few hundred generations, it began to copy its input to its output. After 650 generations, it could partially detect one audio tone, but not the other. By generation 1400, the behaviour became more stable, and the circuit gradually began to discriminate between the two tones. After 5000 generations, the circuit worked.

But it was a strange circuit. In effect, it had ceased to be entirely digital, as the underlying analogue nature of the microscopic transistors became apparent. This is something a digital designer -- happy only to shuffle clean 0s and 1s -- would never contemplate. Thompson saw "very strange looking waveforms" on his oscilloscope, wobbly patterns far removed from the flat edges of on-off digital signals. "They would seem utterly absurd to a digital designer", he says. And yet this weird circuit, which according to conventional digital theory was misbehaving wildly, worked.

Evolware is becoming a major international research topic: Thompson has gone on to evolve other, more complex, circuits, including one which successfully controls the wanderings of a small robot; at the Swiss Federal Institute of Technology, researchers have created a complete computer they call "The Firefly", made partially from evolware. And a group at the Electrotechnical Laboratory in Tsukaba, Japan, is studying evolware which changes its function in real time.

Does this all mean that hardware designers will soon be out of a job? Will all hardware eventually become evolware? It's unlikely. Many evolved designs, while working correctly, turn out to be unnecessarily complex and inefficient. Nevertheless, evolware promises to show us circuits we've never dreamt possible. The self-repairing, self-reproducing machines of von Neumann might really be on the horizon.

Toby Howard teaches at the University of Manchester.