Machines with Minds of Their Own
Can people build machines capable of evolving into something better — able, perhaps, to invent solutions beyond human imagination? Using brute-force methods of calculation, computers can nowadays play a passable game of chess. In 1997, an IBM supercomputer called Deep Blue defeated Garry Kasparov. The world champion described the experience as being every bit as gruelling as playing a top-notch human challenger. In so doing, Deep Blue satisfied at least one of the criteria for artificial intelligence set in the 1950s by Alan Turing, the mathematical genius behind the Enigma code-breaking effort in wartime Britain.
Yet Deep Blue's victory left the world's artificial-intelligence community unimpressed. That was because the machine performed its feat merely by crunching numbers faster than any other computer had managed before. Its enormous processing power enabled it to predict a game's possible course up to 30 moves ahead, while its clever programming allowed it to work out which of the millions of possible moves would strengthen its position best. On its own, all that Deep Blue could do — and do brilliantly — was the mathematics. What it could not do was devise its own strategies for playing a game of chess.
But what if Deep Blue could have been given the ability to evolve and learn to improve itself using its trial-and-error experiences? A new technology called "evolvable hardware" (EHW) attempts to do just that. Like Deep Blue, EHW seeks solutions through trying billions of different possibilities. The difference is that, unlike Deep Blue, EHW continually crops and refines its search algorithm — the sequence of logical steps it takes to find a solution. It selects the best each time and tries that. And it does all this on its own accord, not according to some programmed set of instructions.
Conventional wisdom has long held that a machine's abilities are limited by the imagination of its creators. But over the past few years, the pioneers of EHW have succeeded in building devices that can tune themselves autonomously to perform better. In some cases, the mechanical progeny appear to outstrip even their creators' abilities. In the field of circuit design, for instance, EHW is coming up with creative solutions to problems that have defied human beings for decades.
The first thing EHW needs is for the hardware in question to be reconfigurable. There is no way that a device can evolve if it cannot change its shape or way of doing things. Take a Swiss Army knife. Given the task of, say, opening a bottle, the user identifies the correct tool in the knife, opens it, and thereby transforms the device into an implement that can pry off a bottle cap.
In this case, the actual customisation is crude: no matter what the size and shape of the bottle cap, the shape of the bottle-opener does not alter. For a Swiss Army knife, the "program" (the decision about which implement to use) can be adapted, but the "hardware" (the bottle-opener) cannot. What EHW engineers are trying to do is invent a knife that can customise its shape to any bottle cap — and perform this adaptation on its own recognizance.
The trick with evolvable hardware lies in creating a device that knows how to make the correct structural adaptation at the correct time. To search out the best-suited design, engineers make use of a programming tool called a "genetic algorithm" — a software technique that deploys trial-and-error learning to mimic the process of natural selection that powers evolution in the living world.
The first step that a genetic algorithm takes is to generate a set of random blueprints which are used, one by one, to configure the device. After each reconfiguration, the device is tested to see how well (or otherwise) it carries out the desired task. The highest-scoring designs are retained as guidelines ("parents") for a new generation of designs. These "offspring" designs are created by swapping portions of the parents' blueprints with one another, or by making some random changes. This marginally improved population of designs then undergoes further testing, and the cycle then repeats itself until the device achieves an optimal level of performance.
The target could be determined right at the beginning of the device's operation or it could be adjusted continually. Either way, the device alters its structure to perform the task in the best way possible. In the case of the Swiss Army knife, it would work out what shape to morph into on its own and leave its "processor" (the user's brain) free to address other matters.
Today, it is possible to contain the entire genetic algorithm — blueprint creation, fitness evaluation and reconfiguration — within a single microchip, and to run thousands of evolutionary trials in a fraction of a second. Although they were invented some 30 years ago, genetic algorithms have hitherto been run generally in software, where they placed a large and often prohibitive burden on the processor's time. EHW avoids this problem by running its genetic algorithms in hardware.
That is the crucial difference. In any digital device, wiring instructions into the actual hardware, rather than running them as part of the software, invariably boosts the speed of operation. In EHW, the speed advantage is so significant that the genetic algorithm for problems that could not have been solved in software can be cracked in real time — i.e., with the solutions being produced as fast as the problems are fed in. This speed and flexibility makes EHW ideal for handling situations that vary rapidly.
The most notable application of EHW so far is in the design of analogue circuits. While digital devices have become ubiquitous, they still have to communicate with the real world — and the real world remains stubbornly analogue. The fact is that people do not talk, hear, see, touch and taste in the ones and zeros of digital computerspeak. Analogue circuits are needed to measure or produce the wave-like signals of light, sound or temperature. Other analogue circuits known as A-D and D-A converters are needed to translate these continuous wave-like signals to and from the discrete language used by digital devices. Analogue circuitry is thus an essential part of the sensors, receivers and display units that play such a vital role in the modern wireless world.
It is no surprise that, with so much emphasis on digital circuitry these days, the design of analogue devices is becoming a serious problem. First, coming up with an efficient analogue circuit has as much to do with instinct as with physics. John Koza of Stanford University in California claims that analogue-circuit design is the domain of engineers "wearing purple hats with gold stars." Second, engineers with the necessary skills are in short supply. Texas Instruments, for instance, needs to recruit 500 analogue engineers a year — more than the number that graduate from all the universities in America.
A third problem is that even when a good circuit architecture is conceived, a large proportion of the devices fabricated turn out to be defective. In order to make a complicated job manageable, designers of analogue devices tend to assume that the components used in their circuits work in a uniform and predictable manner.
In the real world, however, environmental factors such as temperature and humidity can cause the electrical properties of a micro-circuit's resistors and capacitors to vary by as much as 20%. Such discrepancies matter far less in digital circuits, which simply have to detect whether an electrical current is more or less on or off. But such variations in analogue circuits can render them unusable. For instance, a cellular telephone will not work properly if its analogue filter allows the transmission frequency to vary by more than 1%. Until now, designers of analogue chips have tried to circumvent the problem by using larger components whose physical properties are more easily measured and controlled. Unfortunately, that leads to bulkier circuits that gobble power.
Tetsuya Higuchi and his colleagues at the Electro-Technical Laboratory in Japan have solved the stability problem by using EHW to accommodate the natural variations that occur between the components. His team use genetic algorithms to tweak the irregular analogue circuit components until they conform to the design specification. By testing the performance of each chip, the algorithm evolves an architecture that can adjust automatically for all the variations in its resistors and capacitors. The group has found that 95% of analogue chips can eventually be coaxed into acceptable performance. That is a higher yield than most digital chip plants achieve. Dr Higuchi expects the first cellular telephones exploiting evolutionary hardware to be on the market by next September. Output of such EHW chips will then be running at hundreds of thousands per month.
Machines that invent
But it is the work done by Dr Koza at Stanford that gives a real glimpse of the future. By running genetic algorithms on analogue circuits that have been simulated in a computer, Dr Koza's machines have already produced seven circuit designs that he calls "human-competitive" because they infringe on patents previously issued to human inventors. Currently, each circuit design costs around $10,000 to simulate, which means that it is still cheaper to do the job manually. But as Dr Koza points out, processing power is becoming less expensive all the time, while human designers are becoming scarcer to find and costlier to keep. Dr Koza is optimistic that, given time, a design for a wholly novel and commercially viable circuit will emerge from his "invention machine".
While Dr Koza's simulated circuits are recognizable variations on human inventions, Adrian Thompson of Sussex University in Britain has evolved a circuit that is literally incomprehensible. Four years ago, Dr Thompson performed a seminal "proof of principle" experiment which described the evolution in hardware of a simple analogue circuit that could discriminate between two different audio tones.
The type of chip that Dr Thompson selected to carry out the evolution was a field-programmable gate array (FPGA). Unlike an ordinary chip, an FPGA's architecture is not "hardwired". Instead of being fixed, a string of bits specifies the chip's design by telling it what linkages to forge between its various components (in this case, groups of transistors known as logic cells). By changing this bit string, the FPGA's circuitry can be altered on the fly. Thus, when a genetic algorithm runs on the chip, the effectiveness of each configuration can be measured directly on the circuit rather than in some costly simulation.
As it turned out, conducting the evolution in hardware produced some results that could not have emerged through mere simulation. After around 4,000 generations of bit strings, a unique circuit emerged. The surprising thing was that, while the new circuit relied directly on only a few of the FPGA's logic cells, it appeared somehow to take advantage of clusters of other cells nearby. These unconnected neighbouring cells could not be removed without damaging the circuit's performance. Further investigations revealed that these detached cells exerted some subtle electromagnetic influence on the wired-up part of the circuit, allowing it to perform its task efficiently.
Remarkably, the circuit had adapted itself in a way that allowed it to exploit the underlying physics of the FPGA's semiconductor material. And it had done this despite the fact that the human experimenters were completely unaware of the physical quirks in the semiconductor that the genetic algorithm was taking advantage of. Four years on, this bizarre circuit has still not been completely deciphered. What has become clear, however, is that EHW's ability to adapt automatically means that it can exploit the physics of materials in ways that researchers do not even consider, let alone understand.
Beyond the realm of analogue and digital electronics lie all manners of unconventional physical systems — including the microscopic world of nanotechnology and quantum dots — where there are no well-developed design rules. By testing layouts that would never occur to humans, EHW can capitalise on the physical properties of these unconventional materials — even when engineers cannot fully account for their behaviour.
It may seem ironic that the direction being taken with evolvable hardware speaks so eloquently of the ignorance of the human architect. But, then, the use of evolution in design is really an admission that researchers have not as yet found anything better. Over the next few years, evolutionary machines could show humans the way.
From The Economist print edition