Evolvable Hardware
Evolvable Hardware
Dateline: 05/02/00
Machines that can automatically repair themselves, and even reproduce, are the constant obsession of Science Fiction writers, but even the most prominent researchers are now taking this idea seriously. Chances are that you already stumbled across the term of "evolvable hardware" in the past. Being a kind of "umbrella term" (and also known as hardware evolution, evolutionary electronics, evloware, and so on), it is often used to specify different approaches, but it usually refers to reconfiguration of programmable hardware devices under the control of evolutionary algorithms. Early work in this field only dealt with optimization of VLSI (Very Large Scale Integration) circuits, such as cell placement, logic minimization and compaction of symbolic layout, but the circuit functions were not designed/evolved. Recent work, however, concentrates on evolving circuit architectures, resulting in a novel designs which are beyond capabilities of current modelling and synthesis techniques or human designers.
To put it simply, the process starts when a designer describes task to be performed by a reconfigurable hardware in terms of design fitness function.
Two major approaches have been used: indirect (extrinsic) and direct (intrinsic). The indirect approach does not evolve hardware directly, but evolves an intermediate representation which specifies hardware circuits, while evaluations are done using a simulator. The direct approach evolves hardware circuit's architecture directly, and evaluation is done using a test equipment. The big advantage of "hardware evolution" is that it proceeds by manipulating the real physical electronic medium and directly judging the consequences, without the modelling, abstraction or analysis constraints imposed by human experts.
As for the hardware used in these experiments, special chips called Field Programmable Gate Arrays (FPGA) are often used: this is a kind of "logical Lego set", offering the highest logic capacity in its category. FPGA consists of an array of logic blocks, surrounded by programmable I/O blocks, and connected with programmable interconnect elements. A typical FPGA contains from 64 to tens of thousands of logic blocks, but most of them are not fully inteconnected. Instead, a sophisticated software places and routes the logic on the device much like a printed circuit board autorouter would place and route components. Some of the Xilinx, Inc.'s series FPGAs are especially well suited for the evolutionary tasks due to their unique architecture: it is impossible to electrically damage these FPGAs by applying random configuration parameters.
Adrian Thompson at Sussex University was among the first to evolve hardware intrinsically, developing a circuit which should be able to tell the difference between two audio tones applied to its input. The circuit started to work properly after some 5000 generations, although it was very different from anything that conventional digital theory has to offer. Adrian is currently researching ways to improve the robustness of the evolved architectures.
The father of Genetic Programming (GP), John Koza, has recently started working on evolution of analogue circuit designs using a GP-like representations. More information on this can be found at the home page of Genetic Programming Inc., a privately funded research group that does research in applying genetic programming. Tetsuya Higuchi at the Evolvable Systems Lab at the Electrotechnical Laboratory in Tsukaba, Japan is studying evolware which changes its function in real time. Logic Systems Laboratory, Lausanne, Switzerland is also designing novel reconfigurable systems based on high-complexity FPGAs which are able to adapt to changing environments or incomplete specifications. Of course, NASA is also active in this field: see the Evolvable Hardware program led by Adrian Stoica.
Other interesting references include PhD thesis on evolvable hardware by
Peter Andersen, University of Aarhus; Evolutionary Electronics Web Links from Adrian Thompson; The Programmable Logic Jump Station; "Reconfigurable Processors" from BRASS group at Berkeley; and conferences/workshops on evolvable systems, including Third International Conference on Evolvable Systems: From Biology to Hardware (ICES2000) (don't miss the list of links at the bottom of the page) and The Second NASA/DoD Workshop on Evolvable Hardware.