Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

JVM Languages

Comparing Fuzzy Numbers


Dec02: Algorithm Alley

Bogdan is a graduate assistant at Rutgers University. He can be contacted at [email protected].


Fuzzy set theory has changed how ambiguity and imprecision are considered. In traditional theories, world representations are forced to comply with extremely precise models, avoiding and rejecting imprecision as a perturbational factor. However, imprecision plays an important role in information representation in real processes where the increase in precision would otherwise become unmanageable. Fuzzy set theory allows the formalization of approximate reasoning and preserves the original information contents of imprecision.

The fuzzy sets defined on the set R of real numbers are used in many applications of fuzzy theory. Their membership functions of the form A:R[0,1] have quantitative meaning and may be considered fuzzy numbers or intervals when they capture concepts of approximate numbers or intervals (such as "numbers that are close to a given real number" or "numbers that are around a given interval of real numbers"). Those concepts are used to describe states of fuzzy variables in many applications in fuzzy control, fuzzy decision making, approximate reasoning, statistics with imprecise probabilities, and optimization.

The methods of fuzzy decision making use the comparison of fuzzy numbers or sets to choose among alternatives, referred to as "fuzzy mathematical programming." The linear ordering of real numbers does not extend to fuzzy numbers, and fuzzy numbers can only be partially ordered, hence, they cannot be compared.

However, when used in practical applications or when a decision has to be made among alternatives, the comparison of fuzzy numbers is essential. Variables—processing times, release dates, and due dates in fuzzy scheduling systems, for example—are used as decision variables. When they are represented in fuzzy format, a ranking procedure based on fuzzy number comparison needs to be applied. The quality of decision making directly relates to the quality of the chosen comparison method.

Several fuzzy number comparison methods and indices have been researched; for instance, see "A Review of Some Methods for Ranking Fuzzy Subsets," by G. Bortolan and R. Degani (Fuzzy Sets and Systems, 1985), and "A Decentralized Reactive Fuzzy Scheduling System for Cellular Manufacturing Systems," by A.S. Dadgostar (Ph.D. Thesis, University of New South Wales, Australia, 1996). Among the methods reviewed were Yager's First, Second, and Third Indexes; Chang's algorithm; Adamo's method; Baas and Kwakernaak's method; Baldwin and Guild's method; Kerre's method; Jain's method; and Dubois and Prade's Four Grades of Dominance. Most of these ranking methods suffer from lack of discrimination among alternatives in regard to fuzzy number comparison. The choices resulting from these methods are occasionally inconsistent, even though some have shown more consistency and better performance in difficult cases.

However, Dadgostar proposed a consistent method called "the partial comparison method" (PCM). With PCM, the shapes of convex fuzzy numbers do not require special computations during comparisons because the method relies on the representation of fuzzy numbers as ordered sets of confidence intervals.

In this article, I present a fuzzy number comparison method (implemented in Java), which is based on the fuzzy arithmetic described by Dadgostar. The source code is available electronically from DDJ (see "Resource Center," page 5) and at http://www.caip.rutgers.edu/~dbogdan/ARC/fn.html, along with documentation and an executable applet.

Fuzzy Number Comparison

Fuzzy arithmetic allows for precise management of uncertain values—those occurring when choosing among alternatives, produced by measurement tools, or resulting from expert subjective judgments. Fuzzy arithmetic is an extension of standard arithmetic and is based on two properties of fuzzy numbers:

  • Each fuzzy set and fuzzy number can be fully and uniquely represented by its -cuts.
  • -cuts of each fuzzy number are closed intervals of real numbers for all [0,1].

These properties enable arithmetic operations on fuzzy numbers to be defined in terms of arithmetic operations on their -cuts; for instance, arithmetic operations on closed intervals, which are the subject of the closed-interval analysis area of mathematics.

A confidence interval is an interval of real numbers that provides a representation for an imprecise numerical value by means of its sharpest enclosing range. A presumption level is an estimated truth-value about some knowledge. Presumption levels belong to the [0,1] interval: You assume the maximum of estimated truth to be at level 1.0, and minimum at level 0.

To qualify as a fuzzy number, a fuzzy set A on real numbers must be normal and convex. The fuzzy set must be normal, since the concept of a set of real numbers close to a given real number r is fully satisfied by r itself. Hence, the membership grade of r in any fuzzy set that attempts to capture this concept (a fuzzy number) must be 1. The bounded support of a fuzzy number and all its -cuts for 0 must be closed intervals to allow definition of arithmetic operations on fuzzy numbers in terms of standard arithmetic operations on closed intervals. Since -cuts of any fuzzy number are required to be closed intervals for all [0,1], every fuzzy number is a convex fuzzy set.

A fuzzy number is represented as an ordered set of confidence intervals, each providing the related numerical value at a given presumption level [0,1]. These confidence intervals should comply with the relation '>A'A where ,',[0,1] and A and A' are the confidence intervals at presumption levels and ', respectively. This definition follows the natural (and often implicit) mechanism of human thinking in the subjective estimation of a numerical value when reasoning in one dimension.

The four basic arithmetic operations on fuzzy numbers—addition, subtraction, multiplication, and division—can be described as sequences of operations among confidence intervals. In particular, let A and B be fuzzy numbers and let • be a generic arithmetic operator. The fuzzy number AB is obtained by computing the operation AB for each [0,1], where A and B are the confidence intervals of A and B at presumption level .

You can represent a fuzzy number by means of a sequence of numbers of presumption levels (NOPL) of confidence intervals, or by explicitly providing its membership function. NOPL may be constant or computed by special functions in order to achieve the maximum available precision. Each arithmetic operation among fuzzy numbers is computed by applying the given operation, once at a time, to all the confidence intervals used to represent the fuzzy operands.

In Fuzzy Sets and Systems (Academic Press, 1980), Dubois and Prade pointed out that, when comparing fuzzy numbers, it is important to compute the truth-value of the statement "A is greater than B," where A and B are fuzzy numbers and ">" is a fuzzy relation defined on the set of fuzzy numbers. The method I propose here is based on the idea of determining the degree of membership to which fuzzy relation "A is greater than B" belongs to the set of "greater than." This fuzzy set contains pairs whose membership degree depends on [0,1]. The values of indicate the degree of confidence in the statement "A is greater than B" (high for values closer to 1, and low for values 0). The task of determining a value for each fuzzy relation can be subjective, or an analytical method can be applied.

Consider two confidence intervals A and B represented as A=(a1,a2) and B=(b1,b2). If A and B do not overlap (Figure 1), you can confidently say whether A is greater than B; that is, the relation "A is greater than B" stands with a degree of confidence A>B=1 or A>B=0.

If they overlap (Figure 2), the fuzzy relation "A is greater than B" stands to some degree, and it can be evaluated to some degree A>B(0,1) using a simple comparison procedure. If two intervals are not overlapping, you can confidently say whether one is greater than another. In the case of overlapping intervals, if you translate A on the right side of B to a point from which the two intervals do not overlap (Figure 3), you can say that the new fuzzy number AR is larger than B with a grade of membership of 1.0. Similarly, if you translate A to a point on the left side of B so that the two intervals do not overlap (Figure 3), you can say that the new fuzzy number AL is larger than B with a grade of membership of 0.0.

Assume the linearity of the "greater than" relationship while translating A between the positions of two intervals, AL and AR (Figure 4). If a'1 (the new position for a1) is located at b2, is equal to 1.0; and if a'1 is located at b1-(a2-a1), is equal to 0.0. Using interpolation, you obtain Example 1(a) for [a1,a2]. Examples 1(a) through 1(e) stand for any two confidence intervals A and B.

The fuzzy number comparison method presented here is based on the fuzzy number representation in fuzzy arithmetic. It has a variant based on the fuzzy number division in comparison, used in PCM. Because it relies on the representation of fuzzy numbers as ordered sets of confidence intervals, the shapes of the convex fuzzy numbers do not need special computations during comparisons.

In many applications, triangular fuzzy numbers (TFNs) have been used for processing dates and due times. Therefore, I use TFNs to describe this method. Comparison of other fuzzy numbers, such as trapezoidal fuzzy numbers (TrFN), can be done in a similar manner.

Consider two normal TFNs, A and B, and represent them by the triplets: A=(a1,a2,a3) and B=(b1,b2,b3). Now consider the situation in Figure 5, where A and B overlap. The right and left sides of these linear curves are the upper and lower limits of the confidence intervals at their levels of presumption.

The Method and Its Variant

If two normal fuzzy numbers A and B do not overlap, you can confidently say whether the fuzzy number A is greater than B. But if they overlap or the normality assumption does not stand (amax(i)1.0), the fuzzy relation "A is greater than B" stands to some degree aA>B(0,1).

To compute this value, the following algorithm is applied: For each level of presumption, p, the corresponding confidence intervals, Ap and Bp, are compared and the degree that Ap is greater than Bp is computed as Ap>Bp. The degrees of membership that fuzzy number A is greater than fuzzy number B are computed by Example 2, where NOPL is the number of presumption levels, and length (confidence interval) denotes the length of the respective confidence intervals.

From Examples 1(b) through 1(e) for confidence intervals, Examples 3(a) through 3(d) result for any two convex fuzzy numbers A and B.

In the variant of the method, each part of the constant monotony of fuzzy number A is separately compared with fuzzy number B:

1. Fuzzy number A is decomposed into two fuzzy intervals: A1 and A2 (Figure 6).

2. The first interval (A1) will be compared with fuzzy number B, and the degree that A1 is greater than B(A2>B) will be computed; see Example 1(e).

3. The second interval (A2) will be similarly compared with fuzzy number B, and the degree that A2 is greater than B(A2>B) will be computed; see Example 1(e).

4. The mean of these two resultant values, which is proportional to their average levels of presumption, will be considered the degree that A is greater than B(A>B); see Example 4(a).

The generalization of this procedure for determining the degrees of membership that "A is greater than B" for two convex fuzzy numbers, A and B, is shown in Example 4(b), where n represents the number of distinctive intervals of absolute monotony (absolute increasing, constant, or decreasing intervals) of fuzzy number A. The equations in Example 3 are preserved.

Comparison with Other Methods

Table 1 summarizes five difficult cases where different methods deliver conflicting answers. Dadgostar proposed the PCM of fuzzy numbers and compared his results with the results of the other methods.

Case (a) is straightforward and all methods give the same ordering. However, some methods (Yager, Chang, Kerre, and Jain) are unable to deliver a clear preference to the same degree as some other methods (Baas-Kwakernaak, Baldwin-Guild).

Case (b) represents a partial overlap of A1 and A2. While some methods prefer A1, others prefer A2. To be exact, 14 indices prefer A1, and 9 indices prefer A2. The method also prefers A1. All multiple indices (for instance, Adamo's 0.9M and 0.5, and Lee-Li's U.m. and P.m.) contradict each other. This adds to the confusion rather than providing a solution.

All the methods give an obvious ranking for Case (c), which is A1>A2>A3.

In Case (d), two fuzzy numbers have the same central tendencies but different dispersions. Some methods prefer A1, others are unable to discriminate, and the rest prefer A2. The Lee-Li method prefers A1 because of the greater dispersion, although they are aware of the result's dependency on the actual framework of the physical situation. It is necessary to emphasize that higher dispersion does not mean a better or worse comparison than lower dispersion. It is strictly dependent on the context of the physical situation. Therefore, it seems that the best methods are those that do not discriminate between these numbers (Yager's F1 and F3, Baas-Kwakernaak, Kerre, Dubois-Prade's PD and NSD) and, subsequently, leave this matter to be decided according to their contexts. On the other hand, while discrimination power seems to be essential in other cases, in Case (d), discrimination without the need for further information would probably result in a wrong decision.

In Case (e), A1 is preferred by most methods, but the Baas-Kwakernaak method and two of the Dubois-Prade indices do not discriminate.

The methods with multiple indices often contradict each other, and the selection of one of these indices for our application may be a rather long procedure. Moreover, examples have shown that each of these methods has shortcomings in special cases; for example—Yager's indices: Case (a); Chang: Cases (a) and (d); Adamo's index: Case (b); Baas-Kwakernaak: Case (e); Baldwin-Guild: Case (b); Kerre's index: Case (a); Jain: Cases (a) and (b); Dubois-Prade's indices: Cases (b) and (e); and Lee-Li's indices: Cases (b) and (d). Among the nine methods presented by Dadgostar, PCM proved to be the most consistent method, as it was the only method that gave the right answer in all cases.

The method presented here produced comparable results with those obtained by PCM (Table 1). Moreover, the equations in Example 3 stand without needing postnormalization. Further decompositions of fuzzy numbers during the comparison are error prone in the approach with levels of presumption (as in the variant).

Conclusion

Except for PCM, the methods of comparing fuzzy numbers suffer from three major drawbacks:

  • They are often insensitive to small differences.

  • They occasionally result in choices inconsistent with intuition.

  • They often have to be performed in multiple steps, which result in multiple indices that are occasionally conflicting.

The comparison method I present here has two possible advantages over existing methods:

  • It is very sensitive to minor differences because it uses the modern approach of fuzzy numbers in fuzzy arithmetic.
  • It is a consistent method (compared with other methods reported in the literature). The method calculates a single index with specific and clear results rather than vague and multiple indices such as Dubois and Prade's indices. These indices are designed to describe the respective locations of two fuzzy numbers. Therefore, they are more descriptive rather than providing an answer to the inequality question. In practical situations and in computer programming, where a clear choice must be made, using multiple indices can be difficult or impossible.

Additionally, the method works with both triangular (TFN) and trapezoidal (TrFN) fuzzy numbers.

DDJ


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.