Communications of the ACM
Home/Magazine Archive/April 1999 (Vol. 42, No. 4)/Following the Path of Evolvable Hardware/Full Text
Communications of the ACM
Following the Path of Evolvable Hardware
There are differing views on the definition of EHW. Some regard it as the application of evolutionary computation techniques to electronic hardware design, for example, filter design. Some regard it as hardware that is capable of online adaptation by reconfiguring its architecture dynamically and autonomously. The former emphasizes evolutionary computation techniques as potential design tools, while the latter emphasizes adaptation of hardware. It is worth pointing out that EHW is quite different from the hardware implementation of evolutionary algorithms, in which hardware is used to speed up various evolutionary operations. The hardware itself does not change or adapt.
There are two major aspects to EHW: simulated evolution and electronic hardware. The simulated evolution can be driven by genetic algorithms, genetic programming, evolutionary programming, or evolution strategies. There is no uniform answer as to which type of evolutionary algorithm would be the best for EHW. Different evolutionary algorithms would suit different EHW. The electronic hardware used in EHW can be digital, analog, or hybrid circuits. One of the advantages of evolutionary algorithms is that they impose very few constraints on the type of circuits used in EHW.
Most EHW relies heavily on reconfigurable hardware, such as field-programmable gate arrays (FPGAs). The architecture and functionality of an FPGA are determined directly by its architecture bits. These bits are reconfigurable. EHW makes use of this flexibility and employs an evolutionary algorithm to evolve these bits in order to perform certain tasks effectively and efficiently.
Figure 1 shows the major steps in an evolutionary cycle of EHW. An initial population of architecture bits encoded as chromosomes are generated either at random or heuristically. They are then downloaded into FPGAs for fitness evaluation. In order to cut costs and save space, some EHW has only one set of FPGA hardware that will be used to evaluate the fitness of every chromosome sequentially. The fitness of an FPGA, which is normally equivalent to the fitness of its chromosome, is evaluated through its interaction with the environment. Such fitness is then used to select parent chromosomes for further reproduction and genetic operation. Crossover and mutation are often used to generate offspring chromosomes from the parents. These offspring will then replace their parents according to certain replacement strategies. Some replacement strategies may retain a parent and discard its offspring. A new generation of chromosomes are formed after replacement.
There has been an increasing number of articles in various journals and conference proceedings on EHW recentlythis special section provides a single source for discussing major issues related to EHW. The articles included here represent the state of the art in this emerging field. Sipper, Mange, and Sanchez approach EHW from a very broad point of view. They regard EHW as one of many possible bio-inspired hardware systems, and argue that simulated evolution can be harnessed to design robust silicon systems, just as natural evolution has designed many carbon-based systems. Two examples are given in their article illustrating the ideas and approaches that can be applied to evolve electronic circuits.
The short article by Marchal provides an overview of the state of the art of FPGAs. The motivation and benefits behind these highly versatile devices, which combine the advantages of general-purpose processors and specialized circuits, are succinctly explained.
Traditional hardware is notorious for its inflexibility. It is impossible to change the hardware's structure and functions once it is made. However, most real-world problems are not fixed. In order to deal with these problems efficiently and effectively, different hardware structures are necessary.
While Sipper, Mange, and Sanchez offer two artificial examples of EHW that expose new ideas and illustrate new approaches, Higuchi and Kajihara present some real-world applications of EHW. Four practical industrial applications of EHW are discussed, ranging from analog to digital chips and from data compression to adaptive control. These applications demonstrate EHW's great potential to provide novel solutions to difficult real-world problems.
Hikage, Hemmi, and Shimohara have been working on the AdAM system, which uses the idea of progressive evolution. In order to evolve this complex EHW system, the complexity of the environment is progressively increased so that EHW will be evolved gradually with more and more complex functionalities. They explain their methods in their contribution to this section.
A simple yet effective approach to evolve analog circuits is presented in the short article by Lohn. Instead of using a complex chromosome encoding scheme, a linear representation and a simple unfolding technique are introduced. Although the evolvable circuit topologies were constrained by the representation, it did evolve many of the useful topologies seen in hand-designed circuits.
There have been some concerns in recent years over the black-box nature of EHW, since it is often very difficult to analyze and understand circuits evolved by evolutionary algorithms. These concerns are natural and appear in other bio-inspired systems as well, such as in artificial neural networks. Thompson and Layzell address this important issue in the final article in this section, in which a number of tactics that can be useful in analyzing EHW are described. They have also carried out a case study analyzing an evolved FPGA circuit for discriminating between two different input frequencies. Their study shows that evolved circuits can be analyzed and understood, with insights into evolved circuits gained through analyses. The practical application of these insights will be very useful in guiding the design of other novel circuits.
There is much more EHW work than can be covered in this special section. For example, Koza et al. [2] have been applying genetic programming to electronic circuit design, especially analog circuits. The articles in this section represent one phase in the process of EHW development, which continues to evolve at a very rapid rate.
References
1. Yao, X. and Higuchi, T. Promises and challenges of evolvable hardware. IEEE Trans. on Systems, Man, and Cybernetics, Part C 29, 1 (1999), 8797.
2. Koza, J.R., Bennett III, F.H., Andre, D., and Keane, M.A. Reuse, parameterized reuse, and hierarchical reuse of substructures in evolving electrical circuits using genetic programming. In Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware (ICES'96) (T. Higuchi, M. Iwata, and W. Liu, Eds.), vol. 1259 of Lecture Notes in Computer Science, (Berlin), Springer-Verlag, 1997, 312326.
©1999 ACM 0002-0782/99/0400 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 1999 ACM, Inc.
No entries found