“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.
Advertisement
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. Thompson’s experiments have also inspired other research projects and
some serious speculation about whether technology is poised to evolve in ways
that will take it well beyond human understanding.
Looking for inspiration
Computer scientists have long looked to biology for inspiration. From
simplified models of the brain they developed neural networks that have proved
particularly good at recognising patterns such as signatures on credit cards and
fingerprints. 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.
To Thompson, who works with Phil Husbands at the Centre for Computational
Neuroscience and Robotics at the University of Sussex, all these techniques
leave something to be desired. They are too tightly constrained by the rules of
chip designers and software engineers. The behaviour of living neurons, for
example, is inseparable from the biochemicals from which they are made. But it
doesn’t matter what material the circuits of a neural network chip are etched
in, so long as they operate in a digital fashion.
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.
Likewise, programmers are constrained by the digital nature of computers. A
program is a sequence of logic instructions that the computer applies to the 1s
and 0s as they pass through its circuitry. So the evolution that is driven by
genetic algorithms happens only in the virtual world of a programming
language.
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?” These questions could only be answered if a way were
found to combine the “wet” processes of biological evolution with the “dry”
world of silicon chips. Thompson found the solution in a field-programmable gate
array (FPGA).
The transistors in a conventional microprocessor are hardwired into logic
gates, which carry out the processing. By contrast, 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?”, 91av, 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
computer downloaded each program in turn to the FPGA to create its circuit and
then played it the test tones
(see Diagram). 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). 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. The transistors inside a chip need time to flip between on and off, so
the clock is set to keep everything marching in step, ensuring that no
transistor produces an output between 0 and 1. A human designer would also use
the clock to count the number of ticks between the peaks of the waves of the
input tones. There would be 10 times as many ticks between the wave peaks of the
1 kilohertz tone as those of the 10 kilohertz tone.
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. It generates a sequence of 1s and 0s rather
like the ticks of a clock. 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. Up until the
final version, the circuits were producing analogue waveforms, not the neat
digital outputs of 0 volts and 5 volts. Thompson says the feedback loops in the
final circuit are unlikely to sustain the 0 and 1 logic levels of a digital
circuit. “Evolution has been free to explore the full repertoire of behaviours
available from the silicon resources,” says Thompson.
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.
To solve this mystery, Thompson needs to measure the input and output values
of each cell when the circuit is operating. But the FPGA allows only digital
access to these points, so he can’t measure the analogue values. Thompson’s
colleague, Paul Layzell, is building a circuit board that will allow all the
components to be measured with analogue instruments.
However it works, Thompson’s device is tailor-made for a single 10 by 10
array of logic cells. But how well would that design travel? To test this,
Thompson downloaded the fittest configuration program onto another 10 by 10
array on the FPGA. The resulting circuit was unreliable. Another individual from
the final generation of circuits did work, however. Thompson thinks it will be
possible to evolve a circuit that uses the general characteristics of a brand of
chip rather than relying on the quirks of a particular chip. He is now planning
to see what happens when he evolves a circuit design that works on five
different FPGAs.
Another challenge is to make the circuit work over a wide temperature range.
On this score, the human digital scheme proves its worth. Conventional
microprocessors typically work between –20 °C and 80 °C. Human
designers set the clock so that chip components have enough time to settle into
a digital value. As many computer hackers know, they can turn up the clock speed
if they keep the temperature of the microprocessor low because the transistors
settle into their on or off states more quickly when cold.
Thompson’s evolved circuit only works over a 10 °C range—the
temperature range in the laboratory during the experiment. This is probably
because the temperature changes the capacitance, resistance or some other
property of the circuit’s components. Whatever the cause, this is a serious
drawback. If the circuit needs a temperature controller to enable it to operate,
then it is no longer a cheap, low-power device. But evolution could come to the
rescue here as well. In a future genetic algorithm, Thompson plans to score
circuits not only on how well they perform an electronic task, but also on how
well they cope with temperature variation. Evolution might, for example, create
a design that includes a set of subcircuits each of which operates over a
different temperature range. If this fails to solve the problem, Thompson will
try giving the FPGA a clock. But he won’t tell the circuit what to do with it.
“It will be a resource—we’ll see what use evolution makes of it,” he
says.
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.
Suspicious minds
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.
If evolutionary design fulfils its promise, we could soon be using circuits
that work in ways we don’t understand. And some see this as a drawback. “I can
see engineers in industry who won’t trust these devices,” says Thomson. “Because
they can’t explain how these things work, they might be suspicious of them.”
If the chips ever make their way into engine control systems or medical
equipment we could well face an ethical dilemma, says Inman Harvey, head of the
Centre for Computational Neuroscience and Robotics. “How acceptable is a
safety-critical component of a system if it has been artificially evolved and
nobody knows how it works?” he asks. “Will an expert in a white coat give a
guarantee? And who can be sued if it fails?”
This is only a problem for people who don’t understand how today’s
microprocessors are tested, says Pierre Marchal, who leads research into new
computer architectures at the Swiss Centre for Electronics and Microtechnology
in Neuchâtel. “I have no problem with this,” he says. “You never test
every possibility inside a microprocessor.” That is why the bug in Intel’s
Pentium chip was found only a year after the first one was made.
Harvey and Marchal agree that the safety of future chips will have to be
assured through exhaustive testing. If the chip operates properly under all the
likely combinations of inputs and environmental conditions, then it doesn’t
matter how the chip works internally. The great thing about Thompson’s idea,
says Marchal, is that if you find a problem you add another constraint to the
fitness test and evolve a better solution. “You can adapt it, just as the immune
system adapts to new diseases,” he says.
Marchal believes there is a “real possibility” that machines will evolve in
ways that will be beyond human reasoning. To some, this prospect is frightening.
But not to Marchal. “I’m not sure this is a real problem. The risk from a bomb
is higher,” he says. “Humanity can destroy itself far easier than these alien
ٱԴDZDz.”
For the moment, though, the thinking is more down to earth. 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
.”
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
