Temperature Fan Speed Relative Motor
Current
------------------------------------------
Cold Off 0
Cool Slow 15
Warm Medium 50
Hot Fast 100
Organization of a Fuzzy System
Figure 1 illustrates the flow of data through a fuzzy system. System inputs undergo three transformations to become system outputs. First, a fuzzification process that uses predefined membership functions maps each system input into one or more degrees of membership. Then, the rules in the rule base (also predefined) are evaluated by combining degrees of membership to form output strengths. And lastly, the defuzzification process computes system outputs based on strengths and membership functions.
Fuzzification of Inputs
Fuzzification is the process of assigning or calculating a value to represent an input's degree of membership in one or more qualitative groupings, called "fuzzy sets." Figure 2 shows a system input, temperature, with fuzzy sets cold, cool, warm, and hot. Each temperature value has a degree of membership in each of these sets. The degree of membership is determined by a membership function, which is defined based on experience or intuition. Figure 9 illustrates the degree of membership calculation for a trapezoidal membership function. It is accepted that membership functions change several times as the system is tuned to achieve desired responses to given inputs.
Generally, once the system is in operation, the membership functions do not change. Simple shapes such as trapezoids and triangles are often used to define membership in fuzzy sets, but any suitable function can be used. In addition, you must decide upon the number of fuzzy sets per system input.
In Figure 2, a fuzzy set labeled comfortable could be inserted between cool and warm. The number of fuzzy-set membership functions and the shapes you choose depend on such things as required accuracy, responsiveness and stability of the system, ease of implementation, manipulation, and maintenance, and so on. The trapezoidal and triangular membership functions are most common and have proven to be good compromises between effectiveness and efficiency. The fuzzy sets must span the X-axis covering the entire range, or universe of discourse, for a system input. Mapping to the Y-axis ranges from 0 to 1 and represents the degree to which an input value is a member of that particular fuzzy set. Overlapping between set boundaries is desirable and key to the smooth operation of the system. It permits membership in multiple--even seemingly contradictory--sets. In Figure 2, 63 degrees can be both cool and warm, but it is cool to a greater degree. An overlap of 25 percent between adjacent fuzzy sets is a general rule of thumb.
The fuzzification process permits a binding to take place between linguistic terms (cold, nearby, active, large, and so on) and membership functions, making the terms meaningful to a computer. As a result, a designer can express or modify the behavior of a system using such natural language, thus enhancing the possibility of clear and concise descriptions of complex tasks.
Evaluation of Rules
To govern the system's behavior, the designer develops a set of rules that have the form of If-Then statements. The If side of a rule contains one or more conditions, called "antecedents;" the Then side contains one or more actions, called "consequences." The antecedents of rules correspond directly to degrees of membership calculated during the fuzzification process.
For example, consider a potential rule from the stock-market system shown in Figure 3: If share price is decreasing And trading volume is heavy, Then order is sell. The two conditions "share price is decreasing" and "trading volume is heavy" are the rule's antecedents. Each antecedent has a degree-of-truth (membership) value assigned to it as a result of fuzzification. The action of the rule (or "fuzzy output") is to sell shares. During rule evaluation, strengths are computed based on antecedent values and then assigned to the rules' fuzzy outputs. Generally, a minimum function is used so that the strength of a rule is assigned the value of its weakest or least true antecedent. Other methods to compute rule strength can be used, such as multiplying antecedent values together. The action of selling shares is carried out to a degree that reflects the rule's strength. In other words, the amount of shares sold is based on the degree to which share price is decreasing and trading volume is heavy. Often, more than one rule applies to the same specific action, in which case the common practice is to use the strongest or most true rule; see Figure 4.
Figure 4: Rule-evaluation computation.
Defuzzification of Outputs
Even though the rule-evaluation
process assigns strengths to each specific action, further
processing, or "defuzzification," is required for two reasons. The
first is to decipher the meaning of vague (fuzzy) actions, such as
"order is sell," using membership functions. The second is to
resolve conflicts between competing actions such as "order is sell"
and "order is hold," which may have been triggered by certain
conditions during rule evaluation. Defuzzification employs
compromising techniques to resolve both the vagueness and conflict
issues.
One common defuzzification technique, the "center-of-gravity
method," consists of several steps. Initially, a centroid point on
the X-axis is determined for each output membership function. Then,
the membership functions are limited in height by the applied rule
strength, and the areas of the membership functions are computed.
Finally, the defuzzified output is derived by a weighted average of
the X-axis centroid points and the computed areas, with the areas
serving as the weights. The center-of-gravity method is illustrated
in
Figure 5.
Sometimes, "singletons" are used to simplify the defuzzification
process; see
Figure 6.
A singleton is an output membership function represented by a
single vertical line. Since a singleton intersects the X-axis at
only one point, the center-of-gravity calculation reduces to just a
weighted average calculation of X-axis points and rule strengths,
with the rule strengths used as weights.
To implement a fuzzy system in C, the following types of data
must be accommodated:
Rule 1: if A & B then Z & X
Rule 2: if C & D then Z & Y
Strength of Rule 1 = min (A,B)
Strength of Rule 2 = min (C,D)
X = Strength of Rule 1
Y = Strength of Rule 2
Z = max (Strength of Rule 1
Strength of Rule 2)
= max (min(A,B), min(C,D))
Figure 7
illustrates an overall linked-list arrangement of system-input
and membership-function nodes. The details of these structures are
shown in
Figure 8.
The system-input node is straight-forward and contains an
input name, a membership-function pointer, and a next-input pointer.
More interesting is the membership-function structure, which
contains two X-axis points and two slope values that describe a
trapezoidal membership function. This information is used to
calculate antecedent values (degrees of membership), as shown in
Figure 9
and
Listing Three
(page 94). The resulting antecedent value is stored in the
"value" field of the membership-function structure. Rules can be
represented by two sets of pointers; see
Figure 10.
The first set indicates which antecedent values are used to
determine the rule's strength, and the second set points to output
locations where the strength is to be applied. Finally, a data
arrangement similar to the input-data structure handles outputs and
output membership functions; see
Figure 11.
Listing One
(page 94) includes the C-code definition of these data
structures. Articles by James M. Sibigtroth (see "References")
explain the implementation of fuzzy systems at the assembly language
level.
Inverted-pendulum Example
Figure 12 shows a classic two-dimensional control problem known as the "inverted pendulum." The idea is to keep a pole vertically balanced. The pole is weighted at the top and attached at the bottom by a movable base. If the pole falls to the right or left, the base moves in the same direction to compensate. By monitoring the angle and angular velocity of the pendulum, a fuzzy system can determine the proper force to apply at the base to keep it balanced. Figure 13 shows the fuzzy sets associated with the system inputs and output. The exact set of rules depends on the dynamics of the physical components, required robustness, and range of operating conditions.
Theoretically, the rule base in Figure 14 is sufficient to balance the pendulum, but other solutions exist. A general-purpose fuzzy inference engine like that in Listings One through Four can be applied to many applications. Listing One provides the header and data structures, Listings Two and Three (page 94) present the major fuzzy processes, and Listing Four (page 94) lists the math-support functions. The input-configuration files describing system input/output, the membership functions, and the rule base differ from application to application. Figures 14 and 15 contain the necessary information to implement the inverted-pendulum problem.
Figure 14: Inverted pendulum rule base.
Figure 15: Sample membership function input file.
Figure 15
repeats the input/output and membership information shown
Figure 13
in a format that can be easily parsed by an initialization
routine. Such an initialization routine (not shown in the listings)
sets up the required data structures, converting the four points
describing a membership function into two points and two slopes; see
Figure 16.
Generally, four points describe a trapezoid, but a triangle can
be formed by making the two midpoints identical, as in
Figure 16.
Closing Remarks
The emergence of fuzzy logic is exciting because it is readily
applicable to many problems too awkward to solve with conventional
techniques. Any programmer can easily write code to implement a
fuzzy inference engine like the one presented here. However,
excellent fuzzy development tools exist which allow the designer to
focus more on the application and behavior of the system and less on
the implementation. These tools provide user-friendly, graphical
interfaces with a rich set of support functions for analyzing,
debugging, and simulating the system. Examples of such tools are:
FIDE from Aptronix (San Jose, CA), CubiCalc from Hyperlogic
(Escondido, CA), and TILShell from Togai InfraLogic (Irvine, CA). In
addition, Motorola distributes free fuzzy development tools through
their electronic BBS. "Freeware Data Services," at 512-891-3733 (in
the subdirectory amcu/amcull).
Implementing the fuzzy engine manually, however, affords the
ability to understand, optimize, or customize the fuzzy inference
engine. This is especially important when experimenting with new
fuzzy paradigms, such as rulebase hierarchies and adaptive or hybrid
systems.
References
Brubaker, David I. Introduction to Fuzzy Logic Systems. Menlo
Park, CA: The Huntington Group, 1991.
Kosko, Bart. Neural Networks and Fuzzy Systems. Englewood
Cliffs., NJ: Prentice-Hall, 1990.
Self, Kevin. "Designing with Fuzzy Logic." IEEE Spectrum
(November, 1990).
Sibigtroth, James M. "Creating Fuzzy Micros." Embedded Systems
Programming (December, 1991).
Sibigtroth, James M. "Implementing Fuzzy Expert Rules." AI Expert
(April, 1992).
Williams, Tom. "Fuzzy Logic is Anything but Fuzzy." Computer
Design (April, 1992).
[LISTING ONE]
[LISTING TWO]
[LISTING THREE]
[LISTING FOUR]
Greg Viot, 1993:
Fuzzy logic in C,
Dr. Dobb's Journal,
February 1993
(special issue on Cognitive Computing),
pgs. 40-49 and 94.
Rule 1: IF (angle is NL) AND (velocity is ZE) THEN (force is PL)
Rule 2: IF (angle is ZE) AND (velocity is NL) THEN (force is PL)
Rule 3: IF (angle is NM) AND (velocity is ZE) THEN (force is PM)
Rule 4: IF (angle is ZE) AND (velocity is NM) THEN (force is PM)
Rule 5: IF (angle is NS) AND (velocity is ZE) THEN (force is PS)
Rule 6: IF (angle is ZE) AND (velocity is NS) THEN (force is PS)
Rule 7: IF (angle is NS) AND (velocity is PS) THEN (force is PS)
Rule 8: IF (angle is ZE) AND (velocity is ZE) THEN (force is ZE)
Rule 9: IF (angle is ZE) AND (velocity is PS) THEN (force is NS)
Rule 10: IF (angle is PS) AND (velocity is ZE) THEN (force is NS)
Rule 11: IF (angle is PS) AND (velocity is NS) THEN (force is NS)
Rule 12: IF (angle is ZE) AND (velocity is PM) THEN (force is NM)
Rule 13: IF (angle is NM) AND (velocity is ZE) THEN (force is NM)
Rule 14: IF (angle is ZE) AND (velocity is PL) THEN (force is NL)
Rule 15: IF (angle is PL) AND (velocity is ZE) THEN (force is NL)
input: angle input: velocity output: force
NL: 0 31 31 63 NL: 0 31 31 63 NL: 0 31 31 63
NM: 31 63 63 95 NM: 31 63 63 95 NM: 31 63 63 95
NS: 63 95 95 127 NS: 63 95 95 127 NS: 63 95 95 127
ZE: 95 127 127 159 ZE: 95 127 127 159 ZE: 95 127 127 159
PS: 127 159 159 191 PS: 127 159 159 191 PS: 127 159 159 191
PM: 159 191 191 223 PM: 159 191 191 223 PM: 159 191 191 223
PL: 191 223 223 255 PL: 191 223 223 255 PL: 191 223 223 255
/* General-purpose fuzzy inference engine supporting any number of system
inputs and outputs, membership functions, and rules. Membership functions can
be any shape defineable by 2 points and 2 slopes--trapezoids, triangles,
rectanlges, etc. Rules can have any number of antecedents and outputs, and can
vary from rule to rule. "Min" method is used to compute rule strength, "Max"
for applying rule strengths, "Center-of-Gravity" for defuzzification. This
implementation of Inverted Pendulum control problem has: System Inputs, 2
(pendulum angle and velocity); System Outputs, 1 (force supplied to base of
pendulum); Membership Functions, 7 per system input/output; Rules, 15 (each
with 2 antecedents & 1 output). If more precision is required, integers can
be changed to real numbers.*/
#include <stdio.h>
#define MAXNAME 10 /* max number of characters in names */
#define UPPER_LIMIT 255 /* max number assigned as degree of membership */
/* io_type structure builds a list of system inputs and a list of system
outputs. After initialization, these lists are fixed, except for value field
which is updated on every inference pass. */
struct io_type{
char name[MAXNAME]; /* name of system input/output */
int value; /* value of system input/output */
struct mf_type /* list of membership functions for */
*membership_functions; /* this system input/output */
struct io_type *next; /* pointer to next input/output */
};
/* Membership functions are associated with each system input and output. */
struct mf_type{
char name[MAXNAME]; /* name of membership function (fuzzy set) */
int value; /* degree of membership or output strength */
int point1; /* leftmost x-axis point of mem. function */
int point2; /* rightmost x-axis point of mem. function */
int slope1; /* slope of left side of membership function */
int slope2; /* slope of right side of membership function */
struct mf_type *next; /* pointer to next membership function */
};
/* Each rule has an if side and a then side. Elements making up if side are
pointers to antecedent values inside mf_type structure. Elements making up then
side of rule are pointers to output strength values, also inside mf_type
structure. Each rule structure contains a pointer to next rule in rule base. */
struct rule_element_type{
int *value; /* pointer to antecedent/output strength value */
struct rule_element_type *next; /* next antecedent/output element in rule */
};
struct rule_type{
struct rule_element_type *if_side; /* list of antecedents in rule */
struct rule_element_type *then_side; /* list of outputs in rule */
struct rule_type *next; /* next rule in rule base */
};
struct rule_type *Rule_Base; /* list of all rules in rule base */
main()
{
initialize_system();
while(1){
get_system_inputs();
fuzzification();
rule_evaluation();
defuzzification();
put_system_outputs();
}
}
/* Fuzzification--Degree of membership value is calculated for each membership
function of each system input. Values correspond to antecedents in rules. */
fuzzification()
{
struct io_type *si; /* system input pointer */
struct mf_type *mf; /* membership function pointer */
for(si=System_Inputs; si != NULL; si=si->next)
for(mf=si->membership_functions; mf != NULL; mf=mf->next)
compute_degree_of_membership(mf,si->value);
}
/* Rule Evaluation--Each rule consists of a list of pointers to antecedents
(if side), list of pointers to outputs (then side), and pointer to next rule
in rule base. When a rule is evaluated, its antecedents are ANDed together,
using a minimum function, to form strength of rule. Then strength is applied
to each of listed rule outputs. If an output has already been assigned a rule
strength, during current inference pass, a maximum function is used to
determine which strength should apply. */
rule_evaluation()
{
struct rule_type *rule;
struct rule_element_type *ip; /* pointer of antecedents (if-parts) */
struct rule_element_type *tp; /* pointer to consequences (then-parts) */
int strength; /* strength of rule currently being evaluated */
for(rule=Rule_Base; rule != NULL; rule=rule->next){
strength = UPPER_LIMIT; /* max rule strength allowed */
/* process if-side of rule to determine strength */
for(ip=rule->if_side; ip != NULL; ip=ip->next)
strength = min(strength,*(ip->value));
/* process then-side of rule to apply strength */
for(tp=rule->then_side; tp != NULL; tp=tp->next)
*(tp->value) = max(strength,*(tp->value));
}
}
/* Defuzzification */
defuzzification()
{
struct io_type *so; /* system output pointer */
struct mf_type *mf; /* output membership function pointer */
int sum_of_products; /* sum of products of area & centroid */
int sum_of_areas; /* sum of shortend trapezoid area */
int area;
int centroid;
/* compute a defuzzified value for each system output */
for(so=System_Outputs; so != NULL; so=so->next){
sum_of_products = 0;
sum_of_areas = 0;
for(mf=so->membership_functions; mf != NULL; mf=mf->next){
area = compute_area_of_trapezoid(mf);
centroid = mf->point1 + (mf->point2 - mf->point1)/2;
sum_of_products += area * centroid;
sum_of_areas += area;
}
so->value = sum_of_products/sum_of_areas; /* weighted average */
}
}
/* Compute Degree of Membership--Degree to which input is a member of mf is
calculated as follows: 1. Compute delta terms to determine if input is inside
or outside membership function. 2. If outside, then degree of membership is 0.
Otherwise, smaller of delta_1 * slope1 and delta_2 * slope2 applies.
3. Enforce upper limit. */
compute_degree_of_membership(mf,input)
struct mf_type *mf;
int input;
{
int delta_1;
int delta_2;
delta_1 = input - mf->point1;
delta_2 = mf->point2 - input;
if ((delta_1 <= 0) || (delta_2 <= 0)) /* input outside mem. function ? */
mf->value = 0; /* then degree of membership is 0 */
else
mf->value = min( (mf->slope1*delta_1),(mf->slope2*delta_2) );
mf->value = min(mf->value,UPPER_LIMIT); /* enforce upper limit */
}
/* Compute Area of Trapezoid--Each inference pass produces a new set of output
strengths which affect the areas of trapezoidal membership functions used in
center-of-gravity defuzzification. Area values must be recalculated with each
pass. Area of trapezoid is h*(a+b)/2 where h=height=output_strength=mf->value
b=base=mf->point2-mf->point1 a=top= must be derived from h,b, and slopes1&2 */
compute_area_of_trapezoid(mf)
struct mf_type *mf;
{
int run_1;
int run_2;
int base;
int top;
int area;
base = mf->point2 - mf->point1;
run_1 = mf->value/mf->slope1;
run_2 = mf->value/mf->slope2;
top = base - run_1 - run_2;
area = mf->value * ( base + top)/2;
return(area);
}