Evolvable hardware
|
|
Use of evolutionary algorithms (EA) to create electronics.
| Contents |
Introduction
Software configurable hardware, such as Programmable Logic Arrays, are on the market which accept a bit string instruction which is used to configure or “wire up” a hardware circuit to give it a desired architecture. This can be done an indefinite number of times. By treating the bit string instruction as a Genetic Algorithm “chromosome”, one has the means to evolve hardware. [Higuchi, 1992]
Types of hardware EA
Hardware Evolutionary Algorithms can be divided into two types:
- those using extrinsic evolution
- where the genetic algorithm is applied in software to a simulation of the artefact being evolved, and
- those using intrinsic evolution
- where the genetic algorithm is applied to the artefact itself.
They can also be considered as either constrained or unconstrained, terms that are best understood by reading the unconstrained section of this page.
Constrained hardware evolution
Constrained hardware evolution is similar to most other types of EA, although usually much faster. Parameters such as coefficients in a digital filter, or weights in a neural network can be evolved. It is also possible to design complete circuits from the transistor or gate level.
The ultimate aim is to create an intelligent piece of hardware which can be plugged in to any system and start to operate without any explicit programming. It only needs some feedback on how well it is doing the required job (a fitness function).
Naturally this technique is limited to problems for which specifying a fitness function is easier than solving the problem at hand directly.
Unconstrained hardware evolution
While the intrinsic/extrinsic distinction is irrelevant for evolving software, the differences in hardware are very apparent. With most engineering artefacts, evolution in simulation is quicker than building many prototypes of a device, but electronic hardware can be quicker to evolve intrinsically. This has the potential for producing remarkably different results: whereas in simulation, a design is naturally constrained to the programmer's model of the device, intrinsic evolution allows a design to exploit natural features of the device which may not even be understood by the programmer.
This is also known as unconstrained evolution. The concept was pioneered by Adrian Thompson who in 1996 evolved a tone discriminator, using fewer than 40 programmable logic gates and no clock signal in a FPGA. This is a remarkably small design for such a device, and it is still not understood how it works. For example, one group of gates has no logical connection to the rest of the circuit, yet is crucial to its function. It is thought that this group somehow modulates the power supply or influences other connections by generating a Magnetic field.
Limitations
However, the method comes with disadvantages.
- The circuits worked only on the original device and could not be copied.
- They only worked in a limited range of temperatures.
- As yet, the technique has only solved "toy problems".
- Some also consider it a limitation that the designs are not comprehensible, others view this as an important area of research with the potential to reveal futuristic designs or even as yet undiscovered physics.
- As with constrained evolution, it is only a useful engineering technique when specifying a fitness function is easier than directly solving the problem at hand. However, for the reasons mentioned above it is also the subject of scientific study, for which this is not a limitation.
Future research directions
Current evolvable hardware research often focuses on the biological concept of growth. This arises from the need to solve more complex problems. Complex problems require larger circuits, larger circuits require longer genotypes to specify them with an associated smaller probability of finding, through evolution, one that works. Nature's answer to this is growth - whereby evolution designs one small cell which grows to produce an entire organism. Growth of physical hardware is not currently possible, but information growth is possible. An example of this is zygote development, where a number of identical cells exchange signals then differentiate to perform different tasks depending on their position in the organism.
Another research direction is the application of genetic programming techniques to specify connectivity between components, rather than take the configuration bitstream directly as a genome.
Evolvable hardware can be considered a subset of bio-inspired engineering, a wider field which applies biological concepts such as evolution, growth, immune systems and agents to engineering. It is also a subset of Alife which studies the same subjects from a scientific, rather than engineering perspective to answer fundamental questions about life.
See also
Links
- NASA-DoD-sponsored conference (http://ehw.jpl.nasa.gov/events/nasaeh04/)
- Related web page (http://www.etl.go.jp/~ehw/eng/frame/main.html) of the Advanced Semiconductor Research Center in Tsukuba, Japan
- NASA used a genetic algorithm to design a novel antenna (http://www.arc.nasa.gov/exploringtheuniverse-evolvablesystems.cfm) (see PDF (http://www.genetic-programming.org/gecco2004hc/lohn-paper.pdf) paper for details)
- Adrian Thompson's Research Page (http://www.cogs.susx.ac.uk/users/adrianth/ade.html)