Source: http://www.google.com/patents/US6853991?dq=5,815,794
Timestamp: 2013-12-13 13:35:53
Document Index: 273382735

Matched Legal Cases: ['art 1', 'art1', 'art 2', 'art2', 'art 3', 'art3', 'art 4', 'art4', 'art 5', 'art5', 'art 6', 'art6']

Patent US6853991 - Fuzzy logic system with evolutionary variables rules - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThe fuzzy logic system of the present invention creates fuzzy rules in real-time and updates the fuzzy rules dynamically. This is accomplished by continually optimizing the features, qualifiers, cases, and operators of the fuzzy rules. The fuzzy logic system may be utilized in applications requiring...http://www.google.com/patents/US6853991?utm_source=gb-gplus-sharePatent US6853991 - Fuzzy logic system with evolutionary variables rulesAdvanced Patent SearchPublication numberUS6853991 B1Publication typeGrantApplication numberUS 09/427,802Publication dateFeb 8, 2005Filing dateOct 27, 1999Priority dateOct 27, 1999Fee statusPaidPublication number09427802, 427802, US 6853991 B1, US 6853991B1, US-B1-6853991, US6853991 B1, US6853991B1InventorsBahram Ghaffarzadeh KermaniOriginal AssigneeAgere Systems Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (6), Non-Patent Citations (21), Referenced by (7), Classifications (10), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetFuzzy logic system with evolutionary variables rulesUS 6853991 B1Abstract The fuzzy logic system of the present invention creates fuzzy rules in real-time and updates the fuzzy rules dynamically. This is accomplished by continually optimizing the features, qualifiers, cases, and operators of the fuzzy rules. The fuzzy logic system may be utilized in applications requiring constantly-updated fuzzy rules and also in applications where fuzzy rules are difficult to pre-define due to a large quantity of input data, such as, for example, stock market forecasting.
FIELD OF THE INVENTION The present invention generally relates to fuzzy logic systems for conducting a fuzzy inference. In particular, the invention relates to a fuzzy reasoning process and the generation of fuzzy rules using a genetic algorithm which are utilized by the fuzzy logic systems in applications requiring frequent updating, such as stock market forecasting.
BACKGROUND OF THE INVENTION The concept of �fuzzy theory� was introduced by Lofti Zadeh in the 1960's to allow imprecise decision-making and problem-solving tasks, such as medical diagnosis, to be understood quantitatively. Fuzzy theory is specifically designed to mathematically represent uncertainty and vagueness and provide formalized tools for dealing with the imprecision intrinsic to many problems. Unlike traditional computing which relies on precision, fuzzy theory resembles human reasoning in its use of approximate information and uncertainty to generate a decision.
Fuzzy theory implements classes or groups of data with boundaries that are not sharply defined (i.e. they are fuzzy). Any methodology or theory implementing �crisp� (precise) definitions such as classical set theory, arithmetic and programming may be �fuzzified� by generalizing the concept of a �crisp set� to a �fuzzy set� with blurred boundaries. For example, if it is assumed that a vehicle made in the United States is a �domestic� vehicle and a vehicle made elsewhere is a �foreign� vehicle, and if it is assumed that the set �U� is the set of all automobiles in Los Angeles, and it is desired to classify specific cars within the set �U� as being foreign or domestic, using crisp-set theory, this could be accomplished by simply examining the brand name (e.g. rules are set defining a Toyota as �foreign� and a Ford as �domestic�) of each automobile in the set �U�. However, consider a situation where a Toyota is manufactured in the United States using some parts made in Japan and others made in the United States. In fuzzy theory a rule could be set to define the percentage of parts for a specific car made in United States and to assign a degree of similarity to what is perceived to be a domestic or foreign car. For example, if 25% of the car parts for a Ford are made in the United States then the car could be considered similar to a domestic car to the degree of 0.25 and similar to a foreign car to degree of 0.75. In such a case, the fuzzy system could conclude, assuming the existence of appropriate rules, that the car is �foreign�. Thus, in fuzzy theory an element can reside with degrees of similarity.
A traditional fuzzy logic system typically consists of a rule based membership function, and an inference procedure. The predetermined rules of the system are represented in a linguistic format e.g. �If x is A and (y is B and z is not C), then w is D.�
Here the �IF� is referred to as an �antecedent� and the �THEN� is referred to as a �consequent�. x, y, and z are input variables of the antecedent, and A, B, and C are membership functions thereof. w is a variable of the consequent and D is a membership function thereof. Typically, the membership functions, such as A, B, C, and D, are items of vague linguistic information such as �positive�, �negative�, �large�, �medium�, or �small�.
In general, a fuzzy logic rule includes the following variables: Features (e.g., temperature and sky's condition); cases (e.g. cold, hot, cloudy, sunny); operators (e.g., AND, OR, NOT); outputs (e.g. chance of rain); and qualifiers (e.g., high, low, somewhat, medium, very, slightly, none). Thus, for example, using the above examples in a weather prediction program, a rule might read: IF the temperature is hot AND the sky is very cloudy, then the chance of rain is somewhat high.�
SUMMARY OF THE INVENTION According to the present invention, the features, qualifiers, and operators of rules, and the rules themselves, are continually generated and evolved using genetic algorithms, based on real-time data. This invention is especially useful in stock market forecasting and, in particular, day-trading wherein the pertinent data may change many times over a short period of time.
Once the fitness function plateaus for the population (i.e., ceases to improve) the resultant rule (a chromosome) is stored, e.g., in a bin, thereby creating a storage location or �binning pool� in which �optimized� rules are accumulated. The chromosomes then go through further generation (initialization) and evolution to improve their overall fitness function. This process is repeated until adding more chromosomes to the optimized rule pool does not improve the overall fitness of the pool. At this point the algorithm may be stopped and the best chromosomes then define the rules of the system. For example, if it is presumed that a optimized chromosome pool population can contain 15 chromosomes, then once 16 chromosomes have been established, an evaluation is made and the 15 fittest chromosomes are kept while the worst of the 16 is deleted.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram illustrating various components of the fuzzy logic system of the present invention;
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT FIG. 1 is a block diagram illustrating various components of an exemplary embodiment of the fuzzy logic system of the present invention.
The fitness function is a pre-defined parameter measuring an error component between a desired output stored in the database and the actual output (of the fuzzy output set). In an exemplary case, it might be related to a Euclidian Distance. The fuzzy inference engine 140 then forwards the fitness function value to the genetic algorithm processor 160. The genetic algorithm processor 160 uses the fitness function and then creates another set of fuzzy rules which is based on the fitness function value and the previously supplied rules. It then provides another new fuzzy rule set (termed a �better rule�) to the fuzzy inference engine 140.
Next, in step 211, the fuzzy inference engine 140 compares the fuzzy output set to the �predicted� output of the fuzzy output set. The predicted output is calculated in a known manner based on historical data stored in the database. Based on this comparison, the fuzzy inference engine 140 computes a fitness function for use by the GA in step 213. The fitness function is a pre-determined parameter and may be a well known error computation variable. In an exemplary case, this fitness function may be the inverse of a Euclidean Distance.
Assume that the features M, P, and V use fuzzy membership functions with the following possible qualifiers: NA=Not Applicable; S=Small, M=Medium and L=Large. Assume further that the features D1, D2, D3, D4, D5, D7, D30, and output features T can have the following possible membership functions (combination of cases and qualifiers): PL=Positive Large (representing a predicted large rise in today's price); PM=Positive Medium (representing a predicted medium rise in today's price); PS=Positive Small (representing a predicted small rise in today's price); ZE=Zero (representing no change in day's price); NS=negative small (representing a predicted small fall in today's price); NM=negative medium (representing a predicted medium fall on today's price); NL=negative large (presenting a predicted large fall in today's price); and NA=not applicable. One way to arrange the above parameters into a genetic algorithm chromosome is to code them into �binary genes�. Assume for the variables M, P, and V that the fuzzy membership functions are described as follows: NA=00; S=01; M=10; and L=11. Assume further that for variables D1, D2, D3, D4, D5, D7, D30 and T the fuzzy membership functions are described as follows: PL=111; PM=110; PS=101; ZE=100; NS=001; NM=010; NL=001; and NA=000.
M P V D1 D2 D5 D4 D5 D7 D30 T 00 00 00 111 100 001 001 001 001 001 111 The above chromosome is interpreted as follows: regardless of the value of market capital M, price/earning ratio P, and normalized volume V (e.g., each of these values has a binary gene �00� identifying it as �not applicable�) if yesterday's stock value D1 shows a positive change, while the stocks had no change the day before yesterday (D2), and the stock has been monotonically decreasing for the past four days, past week, and past month, then today's value T of the stock will rise by a large amount. Other random chromosomes are created for other possible outcomes and their accuracy for prediction can be checked against historical data as well.
A primary reason for utilizing the present invention in the stock market is that stock market prediction may require many different rules to properly, thoroughly and accurately make a prediction. Since an accordance with the present invention the rules are generated �on the fly� instead of being pre-selected, there is no practical limit on the number of rules that can be used. Thus, for example, while the above discussion gives examples of features based on days or weeks (e.g., D1 and D7), the features can be based on any time frame, e.g., minutes, seconds, years, etc.
Rule 1: If D1 is PL and D2 is NL, then T is PL Rule 2: If D1 is PS and D2 is NL, then T is PS As shown in FIG. 3 in this example a �positive small� PS is deemed to be any value between 0 and 0.75 and a �positive large� PL value is deemed to be any value from 0.5 to 1. It is understood that the ranges from 0 to 1 and 0 to −1 along the X axis are normalized values representing the values that D1 can take. Further, a �negative small� NS is deemed to be any value between 0 and −0.75, and a �negative large� NL is deemed to be any value from −0.5 to −1.
As shown in FIG. 3, when D1 is 0.65 this value intersects both the PS curve at 0.3 and the PL curve at 0.8 along the Y axis. The ranges from 0 to 1 along the Y axis represent normalized values that the membership function of D1 can take. This indicates that the value for D1 is a fuzzy value which can be considered either a positive small or a positive large. As shown in FIG. 4, when D2 is −0.85, it intersects only the NL curve. This indicates, among other things, that the value for D2 is a crisp value. Thus, for the input values of D1=0.65 and D2=−0.85, the following �sets� exist:
Since, as noted above, we know that the rules include Rules 1 and 2 which correspond to these values (e.g., Rule 1 gives us a solution �T is PL� when D1 is PL and D2 is NL; Rule 2 give us the result �T is PS� when D1 is PS and D2 is NL) then we can apply each of these two rules to Sets 1 and 2.
FIG. 5 shows the result of the application of the two rules. As shown in FIG. 5, the PL and PS curves of FIG. 3 have been reduced to reflect the application of Rules 1 and 2 to the input values, so that the PL curve is �cut off� at 0.8, defining a trapezoidal area 1, and the PS curve is cut off at 0.3, defining a second trapezoid defined by area 2. By taking the centroid of these two trapezoids, the projection for today's market can be achieved taking into consideration the fuzzy values associated with the input D1. The centroid can be calculated by adding the area of trapezoids 1 and 2 and dividing them by the length L corresponding to the total span of the bases of the two trapezoids. For example, if we assume that area 1 equals 0.402 and area 2 equals 0.235, and that length L equals 1, then the projection for today's market T equals 0.637.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4875184Nov 5, 1987Oct 17, 1989Omron Tateisi Electronics Co.Fuzzy logic computers and circuitsUS5193144Dec 12, 1989Mar 9, 1993Shimano, Inc.Fuzzy systemUS5335314May 26, 1992Aug 2, 1994Omron CorporationFuzzy inference apparatusUS5604842May 12, 1992Feb 18, 1997Omron CorporationFuzzy reasoning processor and method, and rule setting apparatus and methodUS5727130 *Aug 31, 1995Mar 10, 1998Motorola, Inc.Genetic algorithm for constructing and tuning fuzzy logic systemUS6324529 *May 24, 1999Nov 27, 2001Yamaha Hatsudoki Kabushiki KaishaEvolutionary controlling system* Cited by examinerNon-Patent CitationsReference1"Example Illustrations," http://www.seattlerobotics.org/encoder/mar98/fuz/flcases.html.2"Fuzzy Application Library/Business and Finance Applications/Knowledge-BasedPrognosis," http://www.fuzzytech.com/e/e_ft4bb7.html.3"Fuzzy InferenceSystems," pp. 2-19 to 2-27.4"Introduction to Genetic Algorithms," pp. 3-5, http://www.kneehighs.com/intro.html.5"Other Business Applications," http://www.fuzzytech.com/e_ft4bb8.htm.6"Prognosis with MS Excel," http://www.fuzzytech.com/e_ft4bs2.htm.7"What is Fuzzy Logic?," http://www.emsl.pnl.gov:2080/proj/neuron/fuzzy/what.html.8Alexander Schatten, "Genetic Algorithms,"http://qspr03.tuwein.ac.at/~aschatt/info/ga/genetic.html.9Bahram Ghaffarzadeh Kermani, "Using Neural Networks and Genetic Algorithms to Enhance Performance in an Electronic Nose," IEEE Transactions on Biomedical Engineering, vol. 46, No. 4, Apr. 1999.10David L. Carroll, "A Genetic What?," in: What is a Genetic Algorithm?, http://www.diemme.it/~luigi/ga.html.11 *G. B. Sheble; Market Based Operation and Planning Simulation and Analysis; 1999; IEEE; INSPEC 6282787; 6/1-6/15.*12James F. Brule, "Fuzzy Systems-A Tutorial," http://www.austinlinks.com/Fuzzy/tutorial.html.13Jerry M. Mendel, "Fuzzy Logic Systems and Qualitative Knowledge,"Part III: Articles, pp. 410-413.14Karr et al., "Computer Modelling of Mineral Processing Equipment Using Fuzzy Mathematics," Minerals Engineering, V. 9, No. 2, p. 183-194 (Feb. 1996).15 *N. K. Chidambaran et al; Adapting Black-Scholes to a Non-Black-Scholes Environment Via Genetic Programming; 1998; IEEE; 98<TH>8367; 197-211.*16Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 1, http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part1.html.17Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 2, http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part2.html.18Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 3 http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part3.html.19Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 4, http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part4.html.20Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 5, http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part5.html.21Steven D. Kaehler, "Fuzzy Logic-An Introduction," Part 6, http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part6.html.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7406475 *Jan 8, 2002Jul 29, 2008British Telecommunications Public Limited CompanySoftware tool for heuristic search methodsUS7689620Dec 11, 2006Mar 30, 2010Sizhe TanEfficiently and systematically searching stock, image, and other non-word-based documentsUS8170964 *May 26, 2009May 1, 2012Inotera Memories, Inc.Method for planning a semiconductor manufacturing process based on users' demands using a fuzzy system and a genetic algorithm modelUS8478005Apr 11, 2011Jul 2, 2013King Fahd University Of Petroleum And MineralsMethod of performing facial recognition using genetically modified fuzzy linear discriminant analysisUS20100205127 *May 26, 2009Aug 12, 2010Inotera Memories, Inc.Method for planning a semiconductor manufacturing process based on users' demandsUS20110202389 *Apr 28, 2011Aug 18, 2011Clear Channel Management Services, Inc.Inventory and Revenue Maximization Method and SystemCN101187704BDec 17, 2007Jan 26, 2011奇瑞汽车股份有限公司Reversing radar fuzzy controller* Cited by examinerClassifications U.S. Classification706/52, 706/3, 706/13International ClassificationG06F9/44, G06N7/06, G06N7/02Cooperative ClassificationG06N7/06, G06N7/023European ClassificationG06N7/06, G06N7/02PLegal EventsDateCodeEventDescriptionJul 11, 2012FPAYFee paymentYear of fee payment: 8Aug 7, 2008FPAYFee paymentYear of fee payment: 4Jan 10, 2000ASAssignmentOwner name: LUCENT TECHNOLOGIES, INC., NEW JERSEYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:KERMANI, BAHRAM GHAFFARZADEH;REEL/FRAME:010490/0154Effective date: 20000106RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google