دانلود مقاله ISI انگلیسی شماره 7947
ترجمه فارسی عنوان مقاله

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

عنوان انگلیسی
A heuristic algorithm for computing the max–min inverse fuzzy relation
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
7947 2002 17 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : International Journal of Approximate Reasoning, Volume 30, Issue 3, September 2002, Pages 131–147

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

#### چکیده انگلیسی

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.