Design Features March 3, 1997

Genetic algorithms: programs that boggle the mind

Clive "Max" Maxfield, Intergraph Computer Systems

Assume that you construct a simple device consisting of a power source and two potentiometers in series with an incandescent-light bulb (Figure 1). Assume also that you can rotate the potentiometers 180°, from ­90° to +90°, and that the point of least resistance for each potentiometer is in its center (upright) position. Suppose you set the potentiometers to random positions, then you proffer the device to friends and ask them to play with it--using the potentiometers, not the supply voltage--to make the light as bright as possible. Most people select one potentiometer, turn it a little to the left or right, and note the result. If the light gets brighter, they continue to turn the potentiometer in the same direction. Alternatively, if the light dims, they reverse their original action and turn the potentiometer the other way.

After some experimentation, your friends discover the optimal setting for the first potentiometer, at which the lamp's brightness reaches its peak. Your friends then turn their attention to the second potentiometer and perform a similar sequence. Any problem of this type has multiple answers, depending on the controlling variables. The collection of these answers is known as the solution space (sometimes referred to as the problem space, depending on your point of view). You can represent the simple solution space associated with your device as a 3-D graph (Figure 2a).

The x axis corresponds to the first potentiometer, the z axis corresponds to the second, and the y axis reflects the brightness of the light. If you assume the presence of computer-controlled actuators that can rotate the potentiometers and also the presence of a sensor for measuring the bulb's brightness (perhaps a photodetector or a method of measuring the resistance of the potentiometers or the circuit's current), you can write a computer program to automatically determine the optimal settings for the potentiometers.

But what algorithm should your program employ? One approach is a "hill-climbing" algorithm, which is based on the same scenario as the one involving your hypothetical friends. Using this technique, the computer commences at a random point and makes a small modification to one of the potentiometers. The program then checks to see if the solution's quality (as reflected by the sensor measurement) improves. The program continues to effect changes in the same direction, but if the original modification worsens the solution, the computer reverses its direction and tries again. Also, the program requires a way to recognize when it reaches its peak with this potentiometer; that is, when a change in any direction worsens the solution. At this point, the program must realize that it's time to move on to the other potentiometer; otherwise, the program will proceed to oscillate around the first potentiometer's center position without further progressing.

This hill-climbing technique is useful for some problems, but it can run into trouble as the solution space's complexity increases. For example, suppose you add more potentiometers to your device and that the relationships between the potentiometers are nontrivial; that is, turning a potentiometer in one direction may cause the lamp to brighten or dim, depending on the positions of one or more of the other potentiometers. In this case, your solution space may consist of a number of hills and valleys (Figure 2b).

The problem is that your hill-climbing algorithm must commence at a random point. Thus, it's possible for the algorithm to manipulate the potentiometers to locate some local maximum (the top of one of the hills), but the algorithm has no way of "seeing" other hills, which may be higher. A low-level solution is to perform searches, commencing each search from a randomly generated starting point, but this method still fails to provide 100% confidence that your algorithm has discovered the "Mount Everest" of your solution space. Furthermore, as the variables describing the problem increase, the result can be a solution space containing constructs such as "tunnels," "bridges," and even weirder elements, such as "cities in the sky" (the names of these constructs are fairly self-explanatory). As the topology of a solution space approaches these levels of complexity, finding the highest peak (or even being able to tell the difference between up and down) becomes highly problematic.

The hill-climbing algorithm is only one of a variety of search techniques, of which there are three main classes (Figure 3). Calculus-based techniques consist of direct and indirect methods. Direct methods, such as those described by Leonardo Fibonacci and Isaac Newton, skip around the search space and evaluate the gradient at each new point as they trek around looking for peaks. The hill-climbing algorithm falls into this class, which is typically useful only for "well-behaved" solution spaces.

By comparison, enumerative techniques search every point in the solution space, one at a time, so these methods are relatively easy to implement and are applicable to a range of problems. However, these techniques can take an inordinate amount of processing time, which can make them unusable for many problems.

For example, consider another simple circuit involving 100 switches, each of which can be up or down. Now, assume that each switch contributes to a measurable value, such as voltage, current, or resistance, and that the amount of each switch's contribution (and whether this contribution is additive or subtractive) depends on the state of one or more of the other switches. (There's an underlying assumption that the switches' contributions and interactions are nonrandom, and instead reflect meaningful relationships.) This example is applicable to a rudimentary enumerative solution, because you can cycle through every possible combination of switches and measure the result. However, there are 2¹⁰⁰ combinations, and even if you evaluate 10 million solutions/sec, it will be a heck of a long time before you find the optimal result (try working out the math for yourself--the answer will scare you).

The third major class of search algorithms is guided random searches. These searches are similar to enumerative techniques, except that guided random searches employ additional information to guide the search. One subclass of this category is simulated annealing, which is based on the thermodynamic model of cooling metals. (Algorithms based on the simulated-annealing concept have appeared in some surprising applications, such as place-and-route software for circuit boards.) The other major subclass of guided random searches is evolutionary algorithms. Within this subclass, one of the most interesting groups is genetic algorithms.

Genetic algorithms

The key concept underlying genetic algorithms is that they mimic evolutionary processes in the natural world; specifically, those processes of natural selection based on the fitness of individuals in a population that evolves both by exchanging genetic material and by undergoing random mutations. The principles underlying genetic algorithms are quite simple and were first described by JH Holland in the early 1970s (Reference 1).

First, you manipulate the problem under consideration so that its variables are represented as a string of zeros and ones. This task is simple with variables that can occupy limited discrete states, such as the switches in the 100-switch example discussed earlier (a little later, you can consider how to handle analog variables). Next, "seed" your environment with an initial population of randomly generated strings; that is, strings containing random sequences of zeros and ones (Figure 4a). Then, evaluate each string in your population by testing the measurable quantity (or quantities) in your system to see how close you are to a desired result. Use the results of this evaluation to assign a fitness to each string, then rank the strings in order of this fitness (Figure 4b). You may discard low-ranking strings. High-ranking strings represent the individuals that the algorithm permits to "breed," or generate the offspring that will form part of the next generation.

Here's the clever part: The strings that will act as the parents for the next generation undergo "crossover," a process in which you emulate the natural exchange of genetic material to create offspring strings (Figure 4c). The original parent strings remain part of this new population, because you don't want to discard your current best solutions. Note that this example shows only a small initial population and the mating of two pairs of strings; in reality, there would be a much larger population pool and many unions. Furthermore, some algorithms allow strings to mate in proportion to their fitness, in which case a high-ranking string is allowed to mate with more strings than a lower ranking companion. Thus, a key feature of genetic algorithms is "survival of the fittest": The fitter strings generate more offspring and, therefore, have a higher chance of passing on their "genetic information" to future generations.

Now, consider crossover in more detail. First, take two strings that have been selected to mate (for example, strings B and D from Figure 4). Next, randomly select a crossover point, which can occur anywhere throughout the length of the strings, and merge the left side of string B with the right side of string D, and vice versa, thereby generating two new strings (Figure 5). (For simplicity, this example only considers strings containing 10 bits; the strings that genetic algorithms use can be hundreds of bits long).

One problem with crossover is that it's possible to lose valuable genetic material. For example, if strings evolve to have a group of zeros at the same location, mating these strings will never generate ones in those positions. Thus, another important component of genetic algorithms is mutation. Following crossover, every bit in each of the new strings has a finite chance of undergoing mutation (your algorithm might decide to flip its state from a zero to a one, or vice versa). The probability of mutation is maintained at a low level (for example, a probability of 1 in 10,000); the algorithm treats each bit independently, so the mutation of one bit doesn't affect the probability of surrounding bits being mutated. From the above, you can derive a high-level view of the genetic algorithm by establishing an encoding mechanism, a fitness function, a selection mechanism, and crossover and mutation functions. A pseudocode representation would be as follows:

All of the actions in the loop compose one cycle (or generation), and termination of the loop may occur after a specific number of cycles (which could number in the tens of thousands) or when one or more of the solutions comes close enough to the desired result.

The above discussions focus on digital variables, such as switches, but genetic algorithms can easily handle analog variables as well. For example, you can easily encode the angular position of the potentiometers in Figure 1 into a number of bits; a 1-byte field allows you to encode the 180° range of one of the potentiometers to an accuracy of approximately 0.7°, and you can use more bits to increase this accuracy as required. Also, multiple potentiometers simply correspond to more bits in the main string, and you can easily mix both analog and digital quantities because the genetic algorithm sees them as a long string of bits.

So, what are they good for?

Although the concept of genetic algorithms might seem a bit nebulous, their use of pseudonatural selection and mutation directs the search toward regions of high potential in the solution space. These mechanisms also allow genetic algorithms to explore a greater number of potential solutions than do more conventional search techniques, and genetic algorithms also converge on optimal results in complex solution spaces faster and more efficiently than do other search techniques.

One application for genetic algorithms in electronics is fine-tuning analog circuits, which often have contradictory requirements, such as increasing edge rates and reducing power consumption. These problems, which contain many variables (component values) with complex interrelationships, are ideally suited to a genetic-algorithm approach. In this case, you use the algorithm with an analog simulator; the algorithm modifies the variables, and the analog simulator measures the results, thereby determining the genetic population's fitness.

Two other interesting fields are fuzzy logic and neural networks. These disciplines have successfully combined on a number of occasions, resulting in two hybrids: neuro-fuzzy (the neural network establishes the fuzzy rules) and fuzzy-neural (fuzzy logic fine-tunes the neural network). Similarly, genetic algorithms open the doors to four more hybrids: genetic-neuro, neuro-genetic, genetic-fuzzy, and fuzzy-genetic.

However, one of the more exciting areas for future research involves combining the concepts of genetic algorithms with those of adaptive logic. Adaptive logic refers to the latest generation of FPGAs, in which you can reconfigure individual portions of the device on the fly without disturbing the operation of the rest of the device (Reference 2). This option makes it possible to compile new design variations in real time, which you can think of as dynamically creating subroutines in hardware. Thus, you might consider implementing a genetic algorithm in the form of dynamically evolving hardware. The implications of these algorithms may boggle the mind, but they're certainly better than being bored!

References

1. Holland, JH, "Adaptation in natural and artificial systems," University of Michigan Press, Ann Arbor, MI, 1975.
2. Maxfield, Clive "Max," "Logic that mutates while-u-wait," EDN, Nov 7, 1996, pg 137.

Author's biography Clive "Max" Maxfield, is a member of the technical staff at Intergraph Computer Systems (Huntsville, AL), (800) 763-0242, where he gets to play with the company's high-performance graphics workstations. In addition to numerous technical articles and papers, Maxfield is also the author of Bebop to the Boolean Boogie: An Unconventional Guide to Electronics (ISBN 1-878707-22-1). To order, phone (800) 247-6553. You can reach Maxfield via e-mail at crmaxfie@ingr.com.

| EDN Access | Feedback | Subscribe to EDN | Table of Contents |