HOME · NEW SCIENTIST · NS+
[Archive: 15 November1997]
http://www.newscientist.com/ns/971115/features.html
http://www.newscientist.com/nsplus/...primordial.html
CREATURES
FROM PRIMORDIAL SILICON
Let Darwinism loose in an electronics lab
and just watch what it creates. A lean,
mean machine that nobody understands.
Clive Davidson reports
"GO!" barks the researcher into the microphone. The oscilloscope in front of him displays a steady green line across the top of its screen. "Stop!" he says and the line immediately drops to the bottom.
Between the microphone and the oscilloscope is an electronic circuit that discriminates between the two words. It puts out 5 volts when it hears "go" and cuts off the signal when it hears "stop".
It is unremarkable that a microprocessor can perform such a task--except in this case. Even though the circuit consists of only a small number of basic components, the researcher, Adrian Thompson, does not know how it works. He can't ask the designer because there wasn't one. Instead, the circuit evolved from a "primordial soup" of silicon components guided by the principles of genetic variation and survival of the fittest.
Thompson's work is not aimless tinkering. His brand of evolution managed to construct a working circuit with fewer than one-tenth of the components that a human designer would have used. His experiments--which began four years ago and earned him his PhD--are already making waves. Chip manufacturers, robot makers and satellite builders are interested because the technique could produce smaller, more efficient devices than those designed today using traditional methods. ...
Looking for inspiration
Computer scientists have long looked to biology for inspiration. ... They have also worked out ways to mate and mutate programs and allow the resulting programs to compete with one another to generate the "fittest" software for a task. These "genetic algorithms" have been used to evolve software that does everything from creating works of art to selecting high-performing shares on the stock market.
Digital computers break down all data into strings of 1s and 0s, which the hardware stores as "ons" and "offs" in its memory. This forces the transistors inside computer chips to work as switches--they're either on or off. But transistors are not intrinsically digital. Between on and off they pass through a smooth series of values, and in these regions they can behave as amplifiers, for example. Computer designers, however, make little or no use of these properties. ...
What would happen, Thompson asked, if it were possible to strip away the digital constraints and apply evolution directly to the hardware? Would evolution be able to exploit all the electronic properties of silicon components in the same way that it has exploited the biochemical structures of the organic world?
"I wanted to see what happens if you let evolution break out of the constraints that humans have," says Thompson. "If you give it some hardware, does it do new things?" ... Thompson found the solution in a field-programmable gate array (FPGA).
the logic gates in an FPGA and their interconnections can be changed at will. The transistors are arranged into an array of "logic cells" and simply by loading a special program into the chip's configuration memory, circuit designers can turn each cell into any one of a number of logic gates, and connect it to any other cell. So by loading first one program, then another, the chip can be changed at a stroke from, say, an amplifier to a modem ("Software, who needs it?", New Scientist, 2 November 1996, p 41).
Mission impossible
Thompson realised that he could use a standard genetic algorithm to evolve a configuration program for an FPGA and then test each new circuit design immediately on the chip. He set the system a task that appeared impossible for a human designer. Using only 100 logic cells, evolution had to come up with a circuit that could discriminate between two tones, one at 1 kilohertz and the other at 10 kilohertz.
To kick off the experiment, Thompson created a population of 50 configuration programs on a computer, each consisting of a random string of 1s and 0s. ... The genetic algorithm tested the fitness of each circuit by checking how well it discriminated between the tones. It looked for some characteristic that might prove useful in evolving a solution. At first, this was just an indication that the circuit's output was not completely random. In the first generation, the fittest individual was one with a steady 5-volt output no matter which audio tone it heard.
After testing the initial population, the genetic algorithm killed off the least fit individuals by deleting them and let the most fit produce copies of themselves--offspring. It mated some individuals, swapping sections of their code. Finally, the algorithm introduced a small number of mutations by randomly switching 1s and 0s within individual programs. It then downloaded the new population one at a time onto the FPGA and ran the fitness tests once more.
By generation 220, the fittest individual produced outputs almost identical to the inputs--two waveforms corresponding to 1 kilohertz and 10 kilohertz--but not yet the required steady output at 0 volts or 5 volts (see Diagram, below right). By generation 650, the output stayed mostly high for the 1 kilohertz input, although the 10 kilohertz input still produced a waveform. By generation 1400, the output was mostly high for the first signal and mostly low for the second. By generation 2800, the fittest circuit was discriminating accurately between the two inputs, but there were still glitches in its output. These only disappeared completely at generation 4100. After this, there were no further changes.
Once the FPGA could discriminate between the two tones, it was fairly easy to continue the evolutionary process until the circuit could detect the more finely modulated differences between the spoken words "go" and "stop".
So how did evolution do it? If a human designer, steeped in digital lore, were to tackle the same problem, one component would have been essential--a clock. ...
In order to ensure that his circuit came up with a unique result, Thompson deliberately left a clock out of the primordial soup of components from which the circuit evolved. Of course, a clock could have evolved. The simplest would probably be a "ring oscillator"--a circle of cells that change their output every time a signal passes through. ... But Thompson reckoned that a ring oscillator was unlikely to evolve because it would need far more than the 100 cells available.
So how did evolution do it--and without a clock? When he looked at the final circuit, Thompson found the input signal routed through a complex assortment of feedback loops. He believes that these probably create modified and time-delayed versions of the signal that interfere with the original signal in a way that enables the circuit to discriminate between the two tones. "But really, I don't have the faintest idea how it works," he says.
One thing is certain: the FPGA is working in an analogue manner. ...
That repertoire turns out to be more intriguing than Thompson could have imagined. Although the configuration program specified tasks for all 100 cells, it transpired that only 32 were essential to the circuit's operation. Thompson could bypass the other cells without affecting it. A further five cells appeared to serve no logical purpose at all--there was no route of connections by which they could influence the output. And yet if he disconnected them, the circuit stopped working.
It appears that evolution made use of some physical property of these cells--possibly a capacitive effect or electromagnetic inductance--to influence a signal passing nearby. Somehow, it seized on this subtle effect and incorporated it into the solution.
...
Thompson's circuits have so far solved only simple problems. If they succeed at more complex tasks, they could prove useful for all kinds of applications. Thompson has evolved controllers for miniature robots for Xilinx, the Edinburgh firm that makes FPGAs. And the American company Motorola is showing interest in his ideas because they may mesh well with a new analogue FPGA the company has produced. British Telecom, which has an obvious interest in the sort of signal-processing problem that Thompson started with, is sponsoring work by Layzell, who is extending Thompson's ideas.
Already, at Napier University in Edinburgh, Julian Miller and Peter Thomson have picked up on Thompson's concept and are evolving their own digital circuits. They do this at a slightly higher level than Thompson, by creating lists of logic gates and connections, and putting evolution to work on these lists. They've evolved simple arithmetic units such as a multiplier. "It uses a lot fewer resources than a human would design," says Thomson.
... At Napier, Thomson and Miller hope that evolution will teach them new design tricks. "It gives us a new way of looking at things," says Thomson. And at Sussex, Adrian Thompson has his own goal. "I'm just trying to explore what evolution will do."
Perhaps this is where the real value of his work lies. Whether or not his approach produces useful devices, it may help us to understand more about how the evolutionary process itself works. But that's another story.
Further reading: A collection of Adrian Thompson's papers is posted on his Web site at
http://www.cogs.susx.ac.uk/ users/adrianth/ade.html
