An earlier article (click on Archives button at the top, go to "Crossbreeding, mutations solve tough optimization problems") introduced the concept of genetic algorithms and showed how the principles of crossbreeding and mutations are well suited to handling optimization problems that might be extremely difficult to solve with traditional methods. To illustrate the point, it showed how to set up and solve the problem of maximizing the sum of three parameters. Although that example helps drive home the basic principles, it has little value in the real world. Thus, this article shows how genetic algorithms can assist in the design of an FIR filter.

Magnitude response first

Suppose you want to design an FIR filter that exhibits a frequency response (more specifically, a magnitude response whose discrete frequency values map across the range 0 to 2π) with the following values: | H(k) | = [ 750.0000, 361.6262, 106.0660, 41.5512, 0, 41.5512, 106.0660, 361.6262 ]. How easily can a genetic algorithm (GA) generate filter coefficients that produce the same or nearly the same magnitude response?

In this example, the author set up a GA with an initial population size of 100 members and a parameter coding of eight bits. In this case, though, the most-significant bit represents a sign to allow for negative coefficients, and the seven least-significant bits represent the integers 0 through 127. Thus possible coefficients can range between ±127.

What happens, you might ask, if the filter coefficients have values above or below that number? In general, you can estimate the number of bits needed to represent the coefficients using several approximations. First, notice that saying | H(0) | = 750 is the same as saying the sum of the filter coefficients h(n) likewise equals 750. This fact gives you a rough idea in some average sense as to what the coefficients might look like.

Note, however, that in theory you could also have a filter with the coefficients h(n) = [ 2,000,000, 750, -2,000,000, 0, 0, 0, 0, 0], which has a sum of 750 but whose coefficient values require more bits than the 750 number indicates.

A better estimator of filter coefficient size uses Parseval's energy theorem, which states

Consider the case, which isn't too unreasonable in practice (remember, we're only looking for an estimate), that the filter coefficient magnitudes are approximately equal. This assumption reduces the above equation to

This formula provides a slightly better approximation of coefficient values because it doesn't get in the positive/negative summing game that the previous method falls into. Instead, it's based on the coefficients' absolute values. For the filter example defined above, that equation evaluates to h(n) approximately equal to 115. This result means that using seven bits of possible magnitude is cutting matters close, but for this example it serves the purpose.

For the GA fitness criterion, I chose the absolute difference between the intended magnitude response given by |H(k)| and the magnitude response that results from the filter coefficients that come from a GA member. Remember that minimizing absolute-error problems is significantly more difficult than the more traditional minimizing of squared-error problems because the former have no closed-form solution while the latter solve in closed form. Complicating the problem is the very nonlinear mapping of the potential filter coefficients h(n) into the error computing domain |FFT(h(n))|. The FFT complicates matters because it's not clear how filter coefficients should change in an attempt to reduce some given error in the frequency domain.

Now run the genetic algorithm as described in the reference and see how it performs over several hundred generations. As expected, the GA improves asymptotically, but at around generation 75 both the graph of the average error (Fig 1a) and minimum absolute error (Fig 1b) show that error has dropped down to a good solution.

Fig 1 -- The first few generations are where the genetic algorithm makes its biggest strides in finding the coefficients for the desired FIR filter as measured by both mean absolute error (a) and minimum absolute error (b).

After 300 generations, the most-fit member from the GA generates the FIR filter coefficients [2 -16 7 80 93 63 51 27] -- but they don't correspond very closely to the target impulse-response values given by [25 50 100 200 200 100 50 25]. Note that the author "cheated" by using these "ideal" FIR coefficients to generate the desired frequency response. Doing so helps you understand what the GA produces for this example.

Despite the coefficient sets' widely divergent values, an overlay of the two frequency-domain magnitude responses (Fig 2a) shows that both sets result in a similarly looking magnitude response. How can such dissimilar coefficients give such similar results? Recall that magnitude doesn't completely describe a filter, so the differences in the filters arise in their phase response (Fig 2b). If you want filters that perform similarly for both magnitude and phase, you could include phase errors along with the magnitude errors in the fitness-evaluation function. GAs make such modifications quite simple.

Fig 2 -- Two seemingly unrelated sets of FIR filter coefficients give remarkably similar frequency responses as shown by the overlay in (a) because their phase responses are so different.

This example illustrates several important GA concepts. First, many numerical representations of a given problem exist. Second, this technique easily exploits interesting error criteria, and it doesn't limit you to traditional methods such as minimizing with least squares. For instance, DSP practitioners rarely use an absolute-error criterion because it's normally difficult to implement, but the GA approach handles that criterion easily. Finally, a GA gives "good" answers to problems. Notice how the GA found relatively fit members quickly. This aspect is where a GA really shines.

Work with fractions

With this example you should have a good grasp of how a GA works, but what else can the algorithm do? Set up properly, for instance, it can readily handle noninteger numbers if you interpret bits differently. One method might apply some of the gene bits as a mantissa and the remaining bits as an exponent. A more widely used method, though, assumes that parameters fall between 0 and 1. Given this condition, you can interpret the bits as a fraction of the maximum value. Thus the noninteger interpretation of the 8-bit gene [0 0 1 1 0 1 0 1 ] would be [0 0 1 1 0 1 0 1] / [1 1 1 1 1 1 1 1] = 53/255 = 0.2078.

Beyond converging on good values for variables, a GA can also tackle other nonmath-related tasks as long as you can describe them in terms of bits. Suppose you control a robot arm only by selecting movement in one of two directions (1 for right and 0 for left). The problem is finding a control strategy that moves the arm from Point A to Point B in the most efficient and esthetic manner.

This extends the GA in several ways. First, it breaks away from parameter-type problems. Second, you can't define the number of genes up front because you don't know how many Ones and Zeros it takes to control the robot arm in the desired fashion. Finally, you need more than two possibilities per bit. In this case, you'd scan a given chromosome from left to right, interpreting each bit as a separate gene. During the scan you send the bit representation (left or right) to the robot. Somewhere, however, you must tell the robot to stop. Do so by extending the bit meaning and assign three possible values for each: right, left or stop--1, 0 or X.

As an example, suppose you generate a random arm-movement chromosome [1 0 0 1 X 1 1 0 X X 1 0], which you interpret as right, left, left, right, stop. Notice that I didn't use the remaining genes. This choice actually produces some interesting results in that chromosomes contain "junk" genes that apparently have no function other than to carry information for future generations. As the GA progresses in this type of problem, the number of robot moves before terminating would increase if that evolution produced better results. In all, applications such as these make GA extremely useful.

As a closing note, you could extend the GA concept even further to produce programs that perform desired functions. This approach, labeled genetic programming, is becoming more noticeable in research communities. Another interesting application uses GAs for neural-network topology generation. I've coded such nets and experimented enough to see that they have some interesting uses.

Matthew Perry is VP and general manager of Cirrus Logic's Embedded Processors Div (www.cirrus.com); Matt was with Motorola Inc when he wrote this article.

This article originally appeared in Personal Engineering & Instrumentation News, Jan 1995, pgs 67-69. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.