Just Add Parts and Shake . . .

This column usually focuses on prosaic and proven applications for circuits and sensors. This month, though, I am going to talk about an emerging field called evolvable hardware, which potentially has tremendous applicability to designing robust sensing and control systems.

 Ed Ramsden
Ed Ramsden

Evolutionary Computation

Back in the 1970s, a class of nonlinear mathematical optimization techniques was developed based on evolution in biological systems. These techniques are often referred to as "evolutionary computation." As general-purpose optimization techniques, evolutionary computation can be applied to a variety of problems, including the design of circuits and control systems. Solving a problem using evolutionary computation involves the following steps:
1. Develop a symbolic representation (genome) that can be used to describe multiple versions (genotypes) of the system to be optimized. For example, if the problem is one of optimizing a filter, the genome may consist of a list of resistor and capacitor values.

Free Monthly Newsletter

Compelling read? Subscribe to FierceEmbeddedTech!

The embedded tech sector runs the market’s trends. FierceEmbeddedTech subscribers rely on our suite of newsletters as their must-read source for the latest news, developments and analysis impacting their world. Sign up today to get news and updates delivered to your inbox and read on the go.

2. Define a "fitness function" that allows you to determine how well a particular genotype solves the problem, and, equally important, provides a means of ranking genotypes. To continue with the filter example, the fitness function might be the degree to which the actual response of a filter defined by a particular genotype matches the response defined in your design specification.

Figure 1.  In mutation, "offspring" genotypes  with small random changes are created
Figure 1. In mutation, "offspring" genotypes with small random changes are created

3. Define an initial population of genotypes. Population sizes can range from a handful of separate genotypes to thousands of genotypes. For the filter example, this would involve defining a group of filters with random component values.

4. Apply mutation and crossover operators to the population to create a new "generation." Mutation (Figure 1) consists of creating "offspring" genotypes with small random changes, such as changing a resistor to a capacitor. Crossover (Figure 2) is akin to sexual reproduction, where an offspring filter might get Mom's capacitors and Dad's resistors.

Figure 2. Crossover is akin to sexual reproduction, with the offspring receiving characteristics from  both parents
Figure 2. Crossover is akin to sexual reproduction, with the offspring receiving characteristics from both parents

5. Rank the individual genotypes within the population and weed out those that are less fit. In this step, the fitness function is used to rank all the individual genotypes in the population. A selection function based on some variation of "survival of the fittest" is then applied to eliminate most of the individuals near the bottom of the heap while retaining most of those near the top (Figure 3.)

6. Repeat steps 4 and 5 until satisfactory genotypes emerge. These represent solutions to your problem (viable filters).

Figure 3. "Survival of the fittest" eliminates most of the weaker genotypes and spares the stronger ones
Figure 3. "Survival of the fittest" eliminates most of the weaker genotypes and spares the stronger ones

Initial Doubts

When I first heard about using evolutionary techniques for designing and reconfiguring electronic hardware I thought they were a joke—akin to throwing parts into a bag, shaking it, and taking out assembled products. For many types of design problems, however, evolutionary techniques can work surprisingly well. NASA researchers, for example, have used them to develop logic circuits that operate at ultrahigh temperatures (300°C).

Advantages

Perhaps the primary advantage of evolutionary techniques is that they require very little information about a problem. At a minimum, you have to be able to come up with a format for symbolically representing potential solutions (the genome), and for determining how good a potential solution is (a fitness function). When applied to parametric optimization problems, an evolutionary search can often find very good solutions even on highly nonlinear, discontinuous fitness landscapes that can stymie traditional numerical optimization techniques.

Caveats

Evolutionary techniques, however, are not without issues. The first is that for certain kinds of problems, finding acceptable solutions can take a very long time. And when a solution is evolved, it is often not clear how that solution really works. Researchers have successfully used evolvable computation to do original circuit design, but it is often difficult or even impossible to understand how these circuits function. Many designers, myself included, would get more than a little heartburn using designs whose functions we don't understand.

A related problem is that evolutionary techniques optimize only the objective function you supply. In the case of a filter, you might get a nearly perfect magnitude response, but if you forgot to specify phase as part of the fitness function, then it could potentially be anything.

Fault-Tolerant Systems

Despite the limitations of evolutionary techniques in original design, one area for which they hold out significant promise is in implementing fault-tolerant systems. Because moderately complex systems can fail in numerous and unpredictable ways, it can be difficult or impossible to come up with a priori strategies for recovering from faults. Because evolutionary techniques do not assume deep knowledge about the systems being optimized, they may be very well suited to situations where it is necessary to reorganize a system from a number of potentially faulty components in order to maintain some degree of function. One example is the use of evolutionary techniques in control algorithms for a walking robot. The robot is able to adapt its gait to work around severe damage and remain somewhat functional.

Learn More

Although evolutionary computation has been around for a while, its application to controlling physical hardware is relatively recent and is still in early research phases. Here are some resources for those interested in learning a little more about this fascinating and emerging field:

www.ieee-ssci.org/weah2007
www.cogs.susx.ac.uk/users/adrianth/EHW_groups.html

Ed Ramsden, BSEE, a member of the Sensors Editorial Advisory Board, designs sensors for the heavy-truck industry in Portland, OR.

Suggested Articles

Samsung Electronics Co., Ltd., has added several software enhancements to its PCIe Gen4 solid state drive (SSD) series, improving SSD performance.

New Western Digital cards are built on 3D NAND

The technology and business issues of hybrid and electric vehicles will be open for debate at the Electric and Hybrid Vehicle Technology Expo and Battery Show…