Genetic Algorithms

Genetic Optimization of Fuzzy Functions
Dan Simon
Innovatia Software
dan@innovatia.com
Copyright 1998–2007 Innovatia Software. All Rights Reserved.

Preliminaries

Previous white papers by Innovatia Software discussed the topic of fuzzy filtering in general terms, and how the fuzzy membership functions could be optimized using gradient descent. In this paper, the membership functions are optimized using a genetic algorithm. As before, the application is fuzzy filtering for phase-locked loops (PLLs) in a Global Positioning System (GPS) receiver, although the approach is general enough to be applied to most estimation problems. See the Hybrid Kalman / H-infinity filtering paper for some general information about GPS and PLLs.

Genetic Algorithms

A genetic algorithm (GA) is a mathematical method which is motivated by the concept of "survival of the fittest" in biological evolution. GAs can be used to optimize a fuzzy PLL as follows. First, a "population" of fuzzy membership functions is created. The fuzzy membership functions can be created randomly, or they can be created as random perturbations around some nominal functions. Each member of the population is represented as a binary string. For instance, if symmetric trapezoidal membership functions are used as in the figure below, then each member of the population should have enough "genetic" information in its binary string to represent three parameters for each membership function - one parameter for the center of the trapezoid, one for the width of the base, and one for the width of the top.

Trapezoidal Membership Function

Say we have seven membership functions for both of the fuzzy inputs, and seven membership functions for the fuzzy output. That would make a total of 63 parameters which define the membership functions (3 * [7 + 7 + 7]). Let's say that each parameter will be coded using m bits. That means that each member of the population would be represented as a binary string of 63m bits. The binary representation of a parameter is mapped into the number P in the range [P_min, P_max]. If a linear mapping is appropriate, then the mapping can be performed according to the following equation.

P = P_min + b * (P_max - P_min) / (2^m - 1)

where b is the integer value represented by the m-bit string. For instance, say we are trying to map an 8-bit number into the range [0, 1]. The bit string 00010000 represents the integer 16, so that means that it represents 0 + 16 ´ (1 - 0) / (2⁸ - 1) = 0.063.

Once we have a population of fuzzy membership functions (each member of the population represented by a bit string), the "fitness" of each member of the population is evaluated according to some predetermined method. In PLL design, the most important performance criteria are (in order of descending importance)

§ Probability of loss of lock

§ Probability of cycle slip

§ Phase estimation error

So the fitness of a member of our population can be measured on the basis of a set of simulations of the fuzzy PLL.

Fitness = k₁ * P(loss of lock) + k₂ * P(cycle slip) + k₃ * E_rms

where the k_i's are constants determined by the relative importance of the three criteria above. Unlike gradient descent, a GA can minimize the probability of cycle slips and the probability of loss of lock in addition to minimizing phase estimation error.

Once the fitness of each member of the population is evaluated, the weakest members are killed. The fittest members then reproduce according to two methods: parthenogenesis (cloning) and crossover (mating). In cloning, a the population member is reproduced identically. In mating, two members of the population join with each other to form an offspring which is a combination of the two parents. For instance, if each member has k bits of information, then perhaps bits 1 - r of parent A and bits r+1 - k of parent B could be copied into the offspring, where the number r is randomly generated.

Finally, there is a small but nonzero probability of mutation in the offspring. Each bit of the offspring has a small probability of being flipped. Mutation helps reinject genetic information which may have been lost in the current generation. A cycle of fitness evaluation, reproduction, and mutation, is referred to as a "generation."

Simulation Results

So how does it work? The method outlined above was simulated for a PLL in a GPS receiver located on a missile flying a test flight from California to the South Pacific. The details of the simulation are described in a previous white paper. The population size for the GA described above was fixed at 40 members. The fitness of each member was evaluated on the basis of 100 simulations of 10 seconds each. The fitness function parameters in the fitness equation were fixed at k₁ = 20, k₂ = 10, and k₃ = 1. The fittest 10% of the population was cloned at the end of each generation. The least fit 50% of the population was exterminated. Then the fittest 50% of the population (including the clones) mated to restore the population size to 40. The probability of an offspring undergoing a 1-bit mutation was 1%. Five bits were used for each fuzzy membership function parameter, giving a 1/32 radian (approximating 1.8 degrees) resolution for each parameter. The fuzzy membership functions were constrained to be symmetric trapezoids as shown in the figure above, and the fitness function was optimized with respect to 63 parameters as discussed above. The figure below shows the improvement in fitness as the population evolved.

Training Progress

So how does the genetically optimized fuzzy PLL perform? The table below shows the performance of the optimized PLL filter. The Kalman PLL was designed using Kalman filtering. The Hybrid PLL was designed using hybrid Kalman / minimax filtering. The Nominal Fuzzy PLL was designed using common-sense triangular membership functions for the inputs and output of the PLL. The Gradient Fuzzy PLL was optimized using a gradient-descent method. Finally, the Genetic PLL was optimized using the method described in this paper. The performance of the various PLL methods is shown for three different values of Carrier-to-Noise ratios (in units of dB-Hz).

Probability of Loss of Lock for Various PLL Methods (Percent)

PLL METHOD	CNR = 18	CNR = 19	CNR = 20
Kalman	29	13	4
Hybrid	5	2	0
Nominal Fuzzy	73	45	24
Gradient Fuzzy	38	18	9
Genetic Fuzzy	6	9	0

It can be seen from the above table that the Hybrid and Genetic PLLs perform best as for as loss of lock is concerned. As expected, the Genetic PLL performs better than the Gradient PLL due to the fact that the Genetic PLL has more degrees of freedom in its search for the optimal rules. (The Genetic PLL optimized trapezoidal membership functions, while the Gradient PLL optimized triangular membership functions.)

Conclusion

Genetic optimization is a method which can be applied to any function, diffentiable or not. It is an attractive approach to optimization because the function to be optimized does not have to be differentiable (in contrast to gradient-descent based optimization). In addition, it converges to a global minimum (in general) rather than a local minimum. This paper has shown the benefits which can accrue from optimization using a genetic algorithm.

References

Innovatia Software's previous white paper on fuzzy filtering has several references (both hardcopy and web-based) on the general topic of fuzzy logic. Some good references on genetic algorithms include the following.

· D. Dasgupta and Z. Michalewicz, "Evolutionary Algorithms in Engineering Applications," 1997

· M. Gen and R. Cheng, "Genetic Algorithms and Engineering Design," 1997.

· D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning," 1989 .

· M. Mitchell, "An Introduction to Genetic Algorithms (Complex Adaptive Systems)," 1996.

· R. Haupt and S. Haupt, "Practical Genetic Algorithms," 1998.

The Genetic Algorithms FAQ is a good Internet resource about GAs.

The specific application of genetic algorithms to fuzzy logic as discussed in this paper can be explored further in the following papers, which delve into the topic in more detail.

· D. Simon and H. El-Sherief, "Fuzzy Logic for Digital Phase-Locked Loop Filter Design," IEEE Transactions on Fuzzy Systems, May 1995.

· D. Simon and H. El-Sherief, "Fuzzy Phase-Locked Loops," IEEE Position, Location and Navigation Symposium, April 1994.

Home Credentials Publications White Papers

Last Revised: May 29, 2007