الگوریتم اکتشافی برای محاسبه حداقل و حداکثر رابطه فازی معکوس

The paper addresses a classical problem of computing approximate max–min inverse fuzzy relation. It is an NP-complete problem for which no polynomial time algorithm is known till this date. The paper employs a heuristic function to reduce the search space for finding the solution of the problem. The time-complexity of the proposed algorithm is O(n3), compared to O(kn), which is required for an exhaustive search in the real space of [0,1] at k regular intervals of interval length (1/k).

Let X and Y  r be two universal sets. A fuzzy relation that describes a mapping from X to Y ðX ! Y Þ generally is a fuzzy subset of X  Y , where ‘’ denotes a cartesian product [18]. Formally, a fuzzy relation R is defined by Rðx; yÞ ¼ ððx; f yÞ; lRðx; yÞÞ j ðx; yÞ 2 X  Y g; ð1Þ where lRðx; yÞ refers to the membership of ðx; yÞ to belong to the fuzzy relation Rðx; yÞ. Fuzzy ‘composition’ [8] is an operation, by which fuzzy relations in different product space can be combined with each other. There exist differentversions of ‘composition’. The ‘max–min’ composition, which is most popular among them is defined below. Let X; Y ; Z  r be three universal sets and R1ðx; yÞ; ðx; yÞ 2 X  Y and R2ðy; zÞ; ðy; zÞ 2 Y  Z be two fuzzy relations. The max–min composition of R1 and R2, denoted by R1 R2 is then a fuzzy set, is defined by R1 R2¼ ðx; zÞ; max y fminflR1 ðx; yÞ; lR2 ðy; zÞgg ; ð2Þ where x 2 X; y 2 Y and z 2 Z. For brevity, we shall use ‘^’ and ‘_ ’ to denote ‘min’ and ‘max’ operators, respectively. Thus expression (2) can be re-written as R1 R2¼ ðx; zÞ;_y flR1 ðx; yÞ ^ lR2 ðy; zÞg ( ): ð3Þ We use lR1 R2 ðx; zÞ to denote the membership function of ðx; zÞ in the max–min composition relation R1 R2 is defined by lR1 R2 ðx; zÞ ¼_y flR1 ðx; yÞ ^ lR2 ðy; zÞg ð4Þ

We defined a heuristic function to determine the approximate fuzzy max– min compositional inverse and employed it in classical abductive reasoning problems. The proposed method is fast as the time complexity of the procedure fuzzy-pre-inverse is Oðn3Þ compared to exhaustive search which requires to evaluate Euclidean distance OðknÞ times, where we take k discrete values from ½0; 1 at a regular interval of (1=k). Thus when k ¼ 11 and n ¼ 3, we require a computational time of Oð33Þ and Oð113Þ in the respective two cases and obviously the former is much less than the latter. Further, experimental evidences [12] show that the best matrix we found by our method does not differ much from the globally best inverse.