Ala works at NVidia Corp. as a physical ASIC designer. He can be reached at [email protected].
In a previous article, I discussed how to use the AI::FuzzyInference module to balance a rolling ball on a horizontal rod that is pivoted about its center. This worked because we created a set of fuzzy rules that defined the future behavior of the system based on its current state. (That article, "Fuzzy Logic in Perl," appeared in the June 2003 TPJ, which is available to TPJ subscribers in the "Archives" section of http://www.tpj.com/.) Those rules were of the form:
If $posBall is far_left AND # ball is close to left edge of rod
$velBall is slow AND # ball almost stationary
$thRod is medium_neg # right edge of rod is slightly lowered
THEN $dTheta is large_pos # raise the right edge by large amount
In our system, we had three input variables—$velBall, $posBall, and $thRod—that defined the current velocity of the ball, the position of the ball, and the angle of the rod, respectively; and one output variable, $dTheta, which defined the change in the angle of the rod for the next time step. In addition, each of our input variables had five term sets associated with it, which defined the possible fuzzy sets that each variable can belong to at any instant in time. This meant that there are 53, or 125, different possible states that the system can be in at any one point in time; hence, 125 different rules that need to be specified to define the complete behavior of the system. And this is a relatively simple system. If we require finer control over the system, we can extend the term sets of each variable to seven, for example, which would give us a total of 343 different rules. We can see that the number of rules we have to manually define grows exponentially as we add more input variables and more term sets. Furthermore, we have to manually validate those rules by running the system and observing its behavior, then going back, figuring out which rules need to change, modifying some more, and so on. This is a very tedious process that can be quite time consuming and impractical for more complex systems.
One way to solve this problem is to use a genetic algorithm (GA) to evolve the set of rules for your system. Generally speaking, GAs are search algorithms that borrow techniques from natural genetics to guide the trek through search space. Such applications of GAs to evolve rules for fuzzy systems are referred to as "genetic fuzzy systems." My previous article covered these fuzzy systems. I will now briefly describe GAs in more detail and explain how the AI::Genetic module can be used to evolve the fuzzy rules for our given problem.
Introduction to Genetic Algorithms
As mentioned earlier, genetic algorithms are search algorithms that borrow techniques from natural genetics to traverse a problem's search space more efficiently. The basic idea is to maintain a population of individuals where each individual is defined by a chromosome that represents a candidate solution to the problem whose solution is being sought. Each chromosome is represented by a set of genes that directly correspond to the variables that define the state of the system to be solved. A typical GA strategy looks like this:
initialize GA;
while (not termination condition) do
evaluate fitness;
selection;
crossover;
mutation;
end
A GA typically starts off with a population of randomly generated individuals. Then it enters a loop, trying to improve upon those random solutions. During each iteration of this loop, the GA is said to evolve a generation. Evolution happens in the form of natural selection akin to what happens in nature. In each generation, the individuals are tested and rated as possible solutions to the given problem. This rating is called a "fitness value." Based on this rating, a number of individuals are then selected to undergo crossover and/or mutation. Crossover is similar to sexual reproduction in nature. Here, two individuals are selected for mating, which results in two brand new "child" individuals that share genes from both "parents." Furthermore, these child individuals might undergo mutation where one or more genes switch states. Finally, the new children are injected into the population, marking the end of the current generation. Evolution stops when a certain number of generations have passed or when some other criterion has been fulfilled; for example, when an acceptable solution has been found. Now we'll look into each of the aforementioned steps in more detail.
Fitness Evaluation
Individuals are rated by passing them on to a "fitness function" that simulates the problem to be solved, and returns a positive number that is proportional to how well the given individual's chromosomes adapt to the problem. Users of GAs quickly discover that designing the fitness function is the single most important aspect of using GAs to solve hard problems. There are two main reasons for this:
- Most of a GA's runtime is spent in the fitness function. The fitness function has to be run once for each individual in the population. Furthermore, in each new generation, new individuals are constantly being generated and the fitness function has to be run for those to evaluate their fitness. Typically, a population would consist of hundreds, sometimes thousands, of individuals. It becomes readily apparent that efficient design of the fitness function can result in tremendous speed gains in overall runtime.
- Individuals only adapt themselves to the fitness function. The purpose of the fitness function is to test the adaptability of each individual to the given problem. If, for any reason, the fitness function fails to test some corner case of the problem, then no chromosomes will evolve to take that corner case into account. For example, in one of my first attempts to evolve the rules to solve our problem of balancing a moving ball on a rod, I coded the fitness function such that, for each individual, it would randomly choose six different initial conditions and rate the individual based on how the system reacts under those conditions. The final solution behaved spectacularly well under a large number of initial conditions, but in some cases it failed miserably due to the fact that the fitness function did not test the most-fit individual under all possible conditions.
Selection
Selection simulates the principle of "survival of the fittest." This step basically determines which individuals get to mate with others and pass on their genes in subsequent generations. There are many different selection operators that can be used. Among the most widely used ones are "roulette wheel" and "tournament."
In the roulette wheel selection, the chance of an individual being selected is proportional to the individual's fitness. The name comes from the analogy in which each individual occupies an arc along a wheel. The extent of the arc is proportional to the individual's fitness. The wheel is then "spun" and the individual on which the wheel stops is selected.
In tournament selection, a set of individuals are randomly selected from the whole population and the fittest of those individuals is the one to be ultimately selected.
Crossover
Crossover is the actual mating between two individuals. Typically, a GA defines a crossover rate that defines the probability that two individuals will produce offspring. This probability is usually high because, in practice, we want to explore as many different solutions as possible. If mating does occur, then it will result in two new individuals that will get added to the population.
As with selection, there are many different crossover operators. "Single point" crossover works by choosing a random point along both parents' chromosomes and splitting each in two. Then the head of one is paired with the tail of the other to create two new individuals. In "two point" crossover, each chromosome is broken along two points into three parts, and the middle part of each parent is swapped with the other. In "uniform" crossover, each gene in each parent is looked at independently and randomly assigned to one of the children.
Mutation
Mutation randomly alters the state of a gene. It is a very useful operator but has to be dealt with carefully. The purpose of mutation is to avoid having all the population stuck in a local minimum. Suppose, for example, that in a certain population, the third gene of every individual has the value 0. Then, in the absence of mutation, there is no way for that gene to switch its value only by crossover since both parents will have the same value for that gene, and will hence pass it on to the offspring. Mutation allows, with a small probability, the mutation of genes, which correspond to jumps in the search space. If the jump is large enough, an individual might end up at a potentially lower minimum, yielding a better solution. The probability of a mutation happening is controlled by another variable of the GA called the "mutation rate," and is typically very small. If this value was large, then more genes will be mutated, and the offspring will look less like their parents and more like randomly generated individuals. Thus, a very delicate balance has to be struck where we allow just enough mutation to prevent getting locked up in local minima, but not too much mutation to disrupt the benefits of crossover.
Getting and Installing the Module
You can grab a copy of AI::Genetic from your local CPAN mirror at http://search.cpan.org/~aqumsieh/. The latest version as of this writing is 0.02. You can install it using the traditional method:
perl Makefile.PL make make test make install
If you're on Windows, you can simply type ppm install AI::Genetic at the command prompt. Alternatively, since it's all in pure Perl, you can unpack it in any place where perl can find it.
Using AI::Genetic to Evolve Fuzzy Rules
Before we start describing the code, let's recap the problem very quickly. We are trying to come up with a set of fuzzy rules that can control a fuzzy system, allowing it to successfully balance a rolling ball on a flat rod. The rod is free to rotate about its center, and we assume a two-dimensional environment for simplicity.
I will only outline details essential to developing our application. You can find more information in the AI::Genetic documentation. To better understand the approach I have taken, we need to look at how I decided to represent the problem.
Representation
Our system has three input variables and one output variable. Each of these variables has five term sets:
- input: posBall - Term sets: far_left, left, center, right, far_right
- input: velBall - Term sets: fast_neg, medium_neg, slow, medium_pos, fast_pos
- input: thRod - Term sets: large_neg, medium_neg, small, medium_pos, large_pos
- output: dTheta - Term sets: large_neg, medium_neg, small, medium_pos, large_pos
This means that we have 125 possible rules that correspond to the 125 possible combinations of input states. We will use the GA to select the proper output term set for each of the input states. For example, for the state:
posBall = far_left velBall = slow thRod = medium_pos
the GA should tell us what dTheta should be, which defines how the system will respond to balance the ball.
To represent this, I define each individual to have 125 genes. Each of these genes can assume one of the five possible values for dTheta. The first gene will correspond to the input state far_left, fast_neg, large_neg, the second to far_left, fast_neg, medium_neg, and so on.
Using AI::Genetic
The first thing to do is to create an AI::Genetic object and define its parameters:
use AI::Genetic;
my $ga = new AI::Genetic(
-population => 50,
-crossover => 0.9,
-mutation => 0.05,
-type => 'listvector',
-fitness => \&fitness,
);
This creates an AI::Genetic object that has a population of 50 individuals. The crossover rate is 0.9 and the mutation rate is 0.05. The -type option specifies the type of chromosomes to use. AI::Genetic supports three types of genes:
- bitvector. Each gene is a bit and can be either on or off.
- listvector. Each gene is a string that can take one value from a specified list of possible values.
- rangevector. Each gene is an integer that can take a value from within a range of possible integers.
In this case, we are using listvector because the rules we are trying to evolve are strings. Finally, we pass on a reference to the fitness function, which I have called fitness. Additionally, we can specify a termination subroutine to stop evolution once we reach a certain milestone.
Next, we have to initialize the GA with random individuals. We do that via the init() method:
$ga->init([
map [qw/large_neg
small_neg
zero
small_pos
large_pos/], 1.. 125
]);
This tells the GA that each individual is to have 125 genes, each of which can have one of the five values indicated. This will create 50 AI::Genetic::Individual objects with random genes.
Now we are ready to evolve our population. We do that via a call to evolve():
for my $i (1 .. 10) {
$ga->evolve('rouletteUniform', 50);
my $fit = $ga->getFittest;
print "Fittest so far has score = ", $fit->score, ".\n";
}
The first argument to evolve() is an evolution strategy to use. AI::Genetic comes with nine predefined strategies and allows you to create your own. A strategy defines how evolution will take place; for example, which operators to use for selection and crossover. In this case, I chose the rouletteUniform strategy, which uses roulette-wheel selection and uniform crossover. The AI::Genetic documentation explains the other available strategies and how to create your own in more detail. The second argument to evolve() specifies the number of generations to evolve. Note that we could have specified 500 as the second argument to evolve() and not used the for() loop at all. However, I like to split my evolution like this so that I can get an update every 50 generations to tell me how my population is doing.
To access the fittest AI::Genetic::Individual object, we use the getFittest() method. The AI::Genetic::Individual class defines a number of useful methods, one of which is score(), which returns the fitness value of the individual. This is really where the fitness function is executed, and the result is cached such that subsequent calls to score() will return the cached value. If everything is going fine with our GA, then we should see the score of the fittest individual steadily increase as more generations evolve. Another useful method is genes(), which returns a list of the individual's genes.
Once our evolution is done, we can use the getFittest() method again to gain access to our best solution, and then use the genes() method to access the list of genes of that individual, which directly correspond to our fuzzy rules.
The Fitness Function
Our fitness function is simple in this case. It is passed a list of genes that represent the state of the output variable for each possible combination of input variables. Those genes are used to create the list of rules. Then an AI::FuzzyInference object is created with those rules and a few simulations are run with varying initial conditions. Each simulation is run for a maximum of 1000 time steps, or until the ball either falls to the ground, or is balanced and comes to a halt. A score is kept for each simulation and the total fitness of the individual is the average of the scores of all its simulations. Scores are assigned as follows: If the ball falls at time T, then the score is equal to T. If a ball is completely balanced (i.e., it comes to a halt on top of the rod), then the score will be equal to 1000 plus a bonus that is inversely proportional to the length of time it took to balance the ball; the faster the balancing, the bigger the bonus. If time expires without the ball falling or being balanced, then the score will be 1000.
Results
I ran a simulation of a population of 50 individuals for 25 generations. Typically, you would have a larger population evolving for a larger number of generations, but this problem is simple enough that I can get away with a smaller population and fewer generations to save time. The fitness function tested each individual's behavior under a variety of initial conditions that took into account a large number of possible scenarios. Once the simulation ended, I took the rules defined by the best fit individual, and plugged them into the fuzzy system simulator. A typical result is shown in Figures 1 and 2.
Figure 1 shows the position of the ball plotted on the y-axis versus time on the x-axis. Two curves are shown. The thin line depicts the behavior of the system using the set of rules that I originally came up with manually by trial and error. The thicker line is the corresponding behavior using the genetically evolved rules. Figure 2 shows the corresponding velocity versus time plot. It is evident that the genetically bred rules do a much better job of balancing the ball and bringing it to a halt quicker and with virtually no oscillations.
Final Thoughts
Combining fuzzy systems with genetic algorithms is relatively easy once you understand what is going on. The example I give in this article is rather simple, but should help illustrate how genetic fuzzy systems work and what they could be used for.
One thing I would like to mention here is that I took the liberty of defining the number, shape, and extent of the term sets for each of the fuzzy linguistic variables. This process was iterative in the sense that I kept trying different combinations until I got something that worked well enough and stuck to it. An obvious extension to the system would be to allow it to evolve not only the fuzzy rules, but also the number of term sets per input variable, the shape of the term sets (triangular, trapezoidal, bell curve), and the extent of the term sets. This would make the system much more complicated to code, but would surely result in a more sophisticated and more efficient set of rules.
Finally, I would love to hear from anyone who finds my module useful or uses it in a cool application. Any other comments or suggestions are very welcome.
TPJ
