Applying the concept of fuzzy logic (an abstract version of Boolean logic) to well-known algorithms generates an abstract version (i.e., fuzzy algorithm) that often results in computational improvements. Precision may be reduced but counteracted by gaining computational efficiency. The trade-offs (e.g., small increase in space, loss of precision) for a variety of applications are deemed acceptable. The fuzzification of an algorithm can be accomplished using a simple three-step framework. Creating a new fuzzy algorithm goes beyond simply converting the data from raw data into fuzzy data by additionally converting the operators and concepts into their abstract equivalents. This paper demonstrates: (1) how to apply the general framework by developing a fuzzy algorithm for a simple linear search algorithm and (2) the success of this process through the development of the Fuzzy Golden Ratio Section Search.
Fuzzy logic is a set of rules and techniques for dealing with
logic beyond a two-value (yes/no, on/off, true/false)
system. In other words, fuzzy logic is an abstraction of
twovalue logic and allows for not only multiple values but also
an overlap of values between fuzzy sets. Therefore, fuzzy
logic can mimic a more human-like approach to decision
making. L. Zadeh introduced fuzzy logic in the 1960s as an
expansion of Boolean logic in his paper entitled “Fuzzy
Sets”
Applying the concepts of fuzzy logic to an algorithm essentially creates an abstract version of the original algorithm. The abstract version allows for faster processing by taking advantage of integer calculations, reduced search trees, etc. A fuzzy algorithm can (potentially) find multiple similar solutions while the non-fuzzy version of the algorithm generates only one solution. Fuzzification of an algorithm is extremely advantageous when components or Copyright held by the author. solutions naturally contain a high level of similarity/symmetry or form natural groups/clusters.
This process has already been successfully applied to the
following algorithms: (1) a concept-oriented fuzzification
for finding fuzzy patterns
There are three main categories of components within an algorithm that can be fuzzified: (1) data, (2) operators, and (3) concepts. As stated earlier, fuzzification is a method of adding abstraction. The fuzzification of data is the process of taking “raw”/non-fuzzy data and converting it into fuzzy data. The fuzzification of operators is the process of converting a mathematical, logical, or comparative operator to its fuzzy counterpart, which operates on fuzzy sets instead of pure numbers. The fuzzification of concepts, the most difficult of the three, is the conversion of an idea into a similar fuzzy idea. These three techniques, together, will be used within the framework to create a fuzzy algorithm.
The process of fuzzifying data (also known as fuzzification of data) is a simple two-step process. The first is scaling or normalizing the data. The second is assigning each data point to a fuzzy set. When the process is complete the data is ready to be used within a fuzzy algorithm.
Begin by scaling each of the data points. For easier conversion from raw data to fuzzy data, scale or normalize the data first. There are many ways to scale data. For example, scale each data point xi, using the following standard normalization equation:
The Normalized value:
xinorm = ((xi – min) / (max – min)), Where: max is the maximum value of all data points min is the minimum value of all the data points
After the data is normalized, the fuzzification process can begin. There are two important decisions that need to be made during this phase: (1) the total number of fuzzy sets and (2) the amount of overlap between the sets. The higher the number of fuzzy sets and the smaller the overlap between the sets, the more precise the system is (i.e., less fuzziness). If each fuzzy set only represents one value and there is no overlap, then the system is essentially the same as the original non-fuzzy version. Often these two values are left as user defined parameters in the final algorithm.
There are numerous ways to define fuzzy sets. It is common to define the fuzzy sets using an equation. It is possible to have “uneven” fuzzy sets (i.e., the fuzzy set size is not a constant or the overlap is not consistent). However, the most common approach to create fuzzy sets is to divide the range of values evenly with consistent overlap.
Any calculation using fuzzy data requires that all operators are also fuzzified. Changing all the operators from the traditional version to the equivalent fuzzy version causes the end calculation to be more abstract. The term operator does not simply refer to mathematical operators, but also logical and comparative operators.
Writing fuzzy operators can be challenging on a number of levels and requires many decisions to be made. For example, when defining the comparative operators, decisions will need to be made regarding what makes two sets equal, not equal, less than, greater than, etc. Additionally, a fuzzy operator needs to deal with the overlap that can exist between fuzzy sets.
Within fuzzy logic there exists several predefined operators – the majority of them are logical operators. Each of these well-defined fuzzy operators’ behavior is based on the equivalent operators from traditional set theory. Operators are most commonly associated with numbers, but in the fuzzy world, operators can deal with a greater range of data representations. Often the user needs to expand these predefined operators into special operators specifically defined for the context of the data.
Fuzzy operators can either be written as an equation or as a set of if/then rules. Both methods are common. Equations are computationally faster than if/then rules, providing greater speed advantages within an algorithm. On the other hand, if/then rules are often easier to write, providing an advantage design-wise.
The fuzzification of a given concept is the most challenging of the three presented in this paper mainly because a concept can be difficult to define. A concept is an essential element from the algorithm. Like the fuzzification of data or an operator, the purpose is to create an abstract version of the non-fuzzy “concept”. To identify concepts that are candidates for the fuzzification process, look for places where items could be represented by a set or look for items that only differ by a small amount. Another way to identify concepts that would benefit from being fuzzified is to notice repeated information or items that could be categorized. Fuzzification (i.e., the creation of fuzzy sets) lends itself well to these types of situations.
Many researchers refer to a “fuzzy algorithm” as one in
which the data has been fuzzified
The following describes the general framework for the fuzzfication of any algorithm and provides the steps to convert any algorithm from a traditional non-fuzzy version to a fuzzy version. The framework is written as a general procedure so it can be applied to a broad spectrum of algorithm types.
The three steps of the framework: 1. Decide what can/should be fuzzified and determine the category of each piece to be fuzzified
2. Fuzzify each piece (identified in step 1) based on the category a. Scale/normalize the data, then fuzzify the data b. Fuzzify the operators c. Fuzzify the concepts 3. Defuzzification (if needed/applicable)
The first step is to make an in-depth examination of the algorithm (which is to be fuzzified) and decide which elements to fuzzify. It is helpful to determine what the solution will look like in the fuzzy form. This will lay the foundation for the entire fuzzified algorithm. Therefore, it can be helpful to work backwards through the algorithm to determine what elements (data, operators, or concepts) need to be changed in order for the solution to be produced.
As mentioned in previous sections, data, operators, and concepts can be fuzzified. Simply fuzzifying the data is not necessarily a complete fuzzification of an algorithm. Conversely, not everything needs to be fuzzified. The challenge is selecting which elements should be fuzzified and which elements should not. Almost everything numeric could be fuzzified (by the process provided in the section on fuzzification of data). Elements that are essential to the fundamentals of the algorithm are generally not fuzzified. For example, in an algorithm for finding the shortest path from a starting location to a destination location, the starting and ending locations should not be fuzzified. However, the distances between locations could be fuzzified and, additionally, the concept of ordering might be fuzzified. Of course, these decisions may depend greatly on the application of the algorithm.
The final optional step is defuzzification. Defuzzification, the opposite of fuzzification, is used to convert the result back to a non-fuzzy result. In some cases, this step might be unnecessary. The determination of needing defuzzification is both problem dependent and usage dependent. If the algorithm is being used to narrow the solution space and the information will be fed into a non-fuzzy algorithm, then it is important to develop a method of defuzzification. Defuzzification can be applied to data or concepts.
In this paper, the Golden Ratio Section Search will be fuzzified. The Golden Ratio Section Search belongs to a class of problems known as the one-dimensional search algorithms. One-dimensional search methods are used to find the minimum or maximum of a function within a particular interval. Other similar searches include: Dichotomous Search (bisection method), Uniform Search Method, Equal Interval Method, Fibonacci Search Method, Quadratic (or polynomial) Interpolation, and Newton’s Method. The Golden Ratio Section Search has the advantage of faster convergence than most simple algorithms without requiring function derivatives making the method more versatile.
For this paper, two problems will be run on both a fuzzy and traditional version of the Golden Ratio Section Search. The two versions will be compared in terms of computation complexity, number of iterations, and an evaluation of advantages and disadvantages. A walkthrough will be provided so the reader and compare the fuzzy and nonfuzzy versions of the algorithm.
There are many types of problems that can be formulated so that searching for a minimum or maximum of a function yields the desired result. Thus, this type of search has far reaching applications. One example is finding the roots of a polynomial, which can be challenging if n>3. Onedimensional searches are used to find the “fixed point” of a function (i.e., given a function f(x), then a fixed point c is a point that satisfies f(c) = c). Similarly, it can be used to find the “zeros” of a function (i.e., given a function f(x), then a zero of the function is any point where f(x) = 0). In non-linear constrained or unconstrained optimization, onedimensional search algorithms are used to find the step size to move in the “improving” direction (e.g., in steepest descent, the improving direction is the gradient).
Golden Ratio Section Search works similar to most bisection searches but there is more than one internal point. (And, thus, more than two segments). One common application of this algorithm is to find the absolute minimum (or maximum) of a mathematical function. The algorithm begins by finding (or calculating) the upper and lower bounds of the area that contains the minimum (or maximum) value. Calculate the two interior points using the bounds forming three sub-segments. The algorithm then decides which sub-segment contains the minimum (or maximum) value. The upper and lower bounds are narrowed and the process is repeated until the minimum (or maximum) value is located within a specific tolerance. The Golden Ratio is defined as follows:
Golden Ratio = φ =
As mentioned in an earlier section, the preliminary
research for fuzzy algorithms began with a fuzzy PSO for
solving the Traveling Salesperson problem
To fuzzify the Golden Ratio Search, we must consider what should and should not be fuzzified. A fuzzy algorithm produces a fuzzy solution (unless a defuzzification process is applied to the solution). The fuzzy solution for this type of problem is a fuzzy minimum (or maximum). Thus, we must ask ourselves if a precise minimum (or maximum) is required. Often, a precise minimum (or maximum) is not required. Generally, the Golden Ratio Search (and other bi-sectioning algorithms) are used as a feeder into other algorithms (e.g., curve fitting, finding minimum of a polynomial) and do not require the absolute best solution – a “good enough” solution is all that is required. In some cases, the fuzzy version of an algorithm can be used to eliminate a significant portion of the search space and then be used as a starting range in a precise non-fuzzy algorithm to find the absolute minimum (or maximum). We can conclude that the concept of fuzzy minimum (or maximum) is an appropriate concept to be fuzzified for the algorithm.
The next concept to consider for fuzzification is the calculated points. For the traditional Golden Ratio Section Search, we calculate 2 precise points (and thus create 3 exact segments). In the fuzzified version, these 2 precise points would be represented by 2 fuzzy sets (and 3 fuzzy segments). These sets are not necessarily distinct and may contain overlap. Earlier, the crisp calculations were provided to find the 2 precise points. These formulas, operators, and values will be converted to an abstract fuzzified version. (A subscript f will be used to denote a fuzzified value or operator. Note that 1f is a “fuzzy” 1 and is actually a set). The value of φ and τ will remain crisp and nonfuzzified as these values are essential to the algorithm.
Golden Ratio = φ = τ = ≈.6180339 x1f =f LBf +f (1-τ) *f (UBf -f LBf) x2f =f LBf +f (τ) *f (UBf -f LBf)
The Fuzzy Golden Ratio Section Search will first be tested using the problem: find the minimum of the polynomial: x2 - y +2 = 0 (see figure 1). The lower bound (LB) and upper bound (UB) will be set to -3 and 3 respectively. This polynomial will be used to provide the reader with a full example for comparison purposes of the non-fuzzy traditional algorithm and the fuzzified version.
Using the bounds -3 and 3, begin by calculating the two points x1 and x2 to subdivide the line: x1 = LB + (1 - τ)(UB-LB) = -3 + (1-.618)(3-(-3)) = -.708 x2 = LB + τ(UB-LB) = -3 + .618(3-(-3)) = .708
There are now three line segments (-3 to -.708), (-.708 to .708), and (.708 to 3). Evaluate the f(UB), f(x1), f(x2), and f(LB): f(UB) = 11 f(x1) = 2.501 f(x2) = 2.501 f(LB) = 11
Since both f(x1) and f(x2) are less than both f(LB) and f(UB), the minimum must be between x1 and x2 and, thus, they will become the new LB and UB respectively. The algorithm continues by repeating the previous process to find the next x1 and x2 but using the new more restricted lower and upper bounds. Using the same formulas, calculate the next x1 and x2: x1 = -.708 + (1 - .618)(.708-(-.708)) = -0.167 x2 = -.708 + .618(.708-(-.708)) = .167 Next we evaluate the f(UB), f(x1), f(x2), and f(LB): f(UB) = 2.501 f(x1) = 2.02 f(x2) = 2.02 f(LB) = 2.501 Using these values, the new lower and upper bounds are determined to be:
LB = -.167 UP = .167
The algorithm proceeds by calculating the next new values of x1 and x2 and the corresponding evaluations: x1 = -.167 + (1-.618)(.167-(-.167)) = -.039 x2 =-.167 +.618(.167-(-.167)) = .039 f(x1) = 2.001 f(x2) = 2.001 Given the above x1 and x2, the new lower and upper bounds become:
LB = -.039 UP = .039
The algorithm will make another pass to further tighten the lower and upper bounds to find the minimum of the polynomial. The algorithm will calculate the next values of x1 and x2 and the corresponding evaluations: x1 = -.039 + (1-.618)(.039-(-.039)) = -.009 x2 =-.039 +.618(.039-(-.039)) = .009 f(x1) = 2.000 f(x2) = 2.000
Given the above x1 and x2, the new lower and upper bounds become:
LB = -.009 UP = .009
One can continue the algorithm further to find a more precise results. Otherwise, the algorithm can be stopped at this point. As can been seen from figure 1, the minimum value of the polynomial is 2 at the point x = 0. The value we calculated is approximately 2.000. For many purposes (as mentioned earlier), this value is accurate enough and we can consider the algorithm complete.
The author will now proceed with the Fuzzy Golden Ratio Section Search to find the minimum of the polynomial: x2 y +2 = 0 with the initial LB (lower bound) and UB (upper bound) of -3 and 3, respectively. All fuzzy data and operators will be denoted with a subscript f. It is important to remember that the fuzzy values represent a set, but for simplification purposes will be represented in the write-up as a single integer value with a subscript f.
During the setup of the algorithm, a few decisions need to be made: (1) size of the fuzzy sets and (2) allowing overlap between fuzzy sets. Both of these values control the level of precision for the algorithm. (For example: crisp, traditional numbers could be represented with a fuzzy set size of only one value with no overlaps). Additionally, the size of the fuzzy sets does not need to remain constant throughout the algorithm execution. Keeping in the spirit of the Golden Ratio Section Search algorithm, this example will hold the size of the fuzzy sets constant at +/- τ and, thus, create an overlap of approximately .236 between fuzzy sets. For example, -1f is defined as -1.618 to -.382, 0f is defined as -.618 to .618, and 1f is defined as .382 to 1.618.
The algorithm begins the same as the traditional algorithm, with the calculation of the internal two points based on the fuzzified lower and upper bounds of -3f and 3f. (As previously mentioned: the value of τ will remain crisp as well as the calculation of 1- τ. The value of τ is essential to the original algorithm and not fuzzified. Additionally, this value is essential to the definition of the fuzzy set size). The values are calculated as follows: x1f =f LBf +f (1 - τ) *f (UBf -f LBf) =f -3f +f (1- .618) *f (3f -f -3f) =f -1f x2f =f LBf +f (τ) *f (UBf -f LBf) =f -3f +f (.618) *f (3f -f -3f) =f 1f
There are now three line segments (-3f to -1f), (-1f to 1f), and (1f to 3f). We now evaluate the f(UB), f(x1), f(x2), and f(LB): ff(UBf) =f 11f ff(x1f) =f 3f ff(x2f) =f 3f ff(LBf) =f 11f
Both ff(x1f) and ff(x2f) are less than both ff(LBf) and ff(UBf). The minimum must be between x1f and x2f and they will become the new LBf and UBf. The process repeats and the next x1f and x2f are calculated: x1f =f LBf +f (1-τ) *f (UBf -f LBf) =f -1f +f (1-τ) *f (1f -f -1f) =f 0f x2f =f LBf +f (τ) *f (UBf -f LBf) =f -1f +f (τ) *f (1f -f -1f) =f 0f
There are now three line segments (-1f to 0f), (0f to 0f), and (0f to 1f). Next, evaluate the f(UB), f(x1), f(x2), and f(LB): ff(UBf) =f 11f ff(x1f) =f 2f ff(x2f) =f 2f ff(LBf) =f 11f
The algorithm will be stopped at this point. As can been seen from figure 1, the minimum value of the polynomial is 2. The value we found is approximately 2 (i.e., the fuzzy set 2). (In general, the algorithm would continue, like the non-fuzzy version, until reaching the desired level of accuracy).
In this example, the Fuzzy Golden Ratio Section Search will be tested with a more complex polynomial. The example was run using two simple Java programs: (1) the traditional Golden Ratio Section Search and (2) the Fuzzy Golden Ratio Section Search. The results of the fuzzy version will be compared to the traditional version.
This second example is to find the maximum of the
polynomial: f(x) = 12x – 3x4 – 2x6
The maximum value of the f(x) = 12x – 3x4 – 2x6 occurs
in the range of 0.828 and 0.843 and is approximately 0.836
The computation complexity of the algorithm is not increased by adding fuzzification to the algorithm. The Java code for the fuzzy algorithm contains only one additional method - a customized Java code to determine the fuzzy equivalence between fuzzy sets. This extra method is called only twice during each iteration and contains 8 lines of code most of which are a series of branching statements. This adds minimal execution time to the overall algorithm.
The programming code for both the Fuzzy and Traditional version of the Golden Ratio Section Search was written in Java. The testing environment is as follows: Eclipse Mars, SDK 4.5.1 using Java version 1.8 on a HP Spectre running Windows 10 with 2.5 GHz Intel Core i7.
The Golden Ratio Section Search algorithm was
successfully converted into a fuzzified version of the algorithm
using the Framework for Fuzzification of Algorithms
There are two disadvantages to using the fuzzy algorithm over the traditional. The fuzzy algorithm often requires scaling (but this scaling can be controlled by the user to their desired level of precision). The second disadvantages is that in cases where precise answers are needed, the fuzzy algorithm would only be able to provide a starting lower and upper bound and is unable to provide extremely high levels of accuracy.
The work done in this paper focuses on only two specific polynomials and provides only the beginning of exploration into the use of the fuzzy framework for this kind of search algorithm. Since these preliminary results show great potential, the next step would be to expand to larger and more varied polynomials as well as non-polynomial functions. Further work could be conducted on other similar algorithms including: Dichotomous Search (bisection method), Uniform Search Method, Equal Interval Method, Fibonacci Search Method, and Quadratic (or polynomial) Interpolation. Additionally, the author would like to expand to other even more general search algorithms (e.g., Tabu search) and sorting algorithms.