Journal influence
Bookmark
Next issue
Formal model development for a process of finding solutions by the modified Rete algorithm for fuzzy expert systems
Abstract:The paper considers the basic concepts of fuzzy production expert systems. This type of expert systems is based on a set of rules presented in terms of linguistic variables. The authors propose a developed Rete algorithm modification for fuzz y rule base. It allows creating rules and solutions in the limited natural language and it provides system acceleration due to a single compu-ting the same conditions in the various rules. The authors proposed a decision tree formal model of a modified Rete algorithm for a fuzzy production knowledge base. The model consists of a set of vertex-conditions, vertex-solutions, relations between vertices and relations describing the fuzzy expert system rules. Rete algorithm modification graph is formed in such a way that in each ca se not a correct rule condition value is calculated, but linguistic variable values in the rule.The proposed algorithm processes rules from the fuzzy rule base and converts them into the formal model of a modified Rete algorithm decision tree. The difference between Rete al-gorithm modification and the classical algorithm is application to fuzzy variables. Therefore, the building of fuzzy truth values of decision tree vertices is performed by fuzzy operators at each stage of the algorithm. It allows formulating the conditions a nd conse-quences in the rule base as well as the solutions in the limited natural language. The same conditions are combined during decision tree construction. It provides acceleration of decision tree processing comparing to the sequential viewing of the expert sys tem rules.
Аннотация:Рассматриваются основные понятия нечетких продукционных экспертных систем. Данный тип экспертных систем базируется на наборе правил, представленном в терминах лингвистических переменных. Предлагается разработанная модификация алгоритма Rete для нечеткой базы правил, позволяющая формулировать правила и заключения на ограниченном естественном языке и обеспечивающая ускорение процесса работы системы за счет однократного вычисления одинаковых условий в различных правилах. Приводится созданная формальная модель дерева решений модифицированного алгоритма Rete для нечеткой продукционной базы знаний. Модель состоит из множеств вершин-условий, вершин-следствий, отношений между вершинами и отношений для описания правил нечеткой экспертной системы. Граф модификации алгоритма Rete формируется таким образом, что в каждом случае проверяется не точное значение условия правила, а значения лингвистических переменных в данном правиле. Предложенный алгоритм обрабатывает правила нечеткой базы правил и преобразует их в формат формальной модели дерева решений модифицированного алгоритма Rete. Модификация алгоритма Rete отличается от классического алгоритма тем, что он применяется для нечетких переменных. Поэтому на каждом этапе работы алгоритма выполняется построение не-четких оценок истинности вершин дерева решений с помощью нечетких операторов, что позволяет формулировать условия и следствия в базе правил, а также результаты работы алгоритма поиска решения на ограниченном естественном языке. Одинаковые условия объединяются и при построении дерева решений, что обеспечивает ускорение обработки дерева решений по сравнению с последовательным просмотром правил экспертной системы.
Authors: Zaw Min Htike (zawgyi86@gmail.com) - National Research University “MPEI”, Moscow, Russia, Mikhailov I.S. (fr82@mail.ru) - National Research University “MPEI”, Moscow, Russia, Ph.D | |
Keywords: rete algorithm modification, fuzzy expert system, fuzzy rule base, rete algorithm |
|
Page views: 8491 |
Print version Full issue in PDF (4.84Mb) Download the cover in PDF (0.35Мб) |
В основе функционирования экспертных систем (ЭС) лежит модель знаний. Она содержит набор принципов, которые описывают состояние и поведение объекта исследования [1]. Наиболее широко применяемой моделью ЭС является продукционная модель в силу своей простоты обработки и понятности конечному пользователю [2].
Однако в последнее время большое распространение приобретают нечеткие ЭС [3]. Данный тип ЭС базируется на наборе правил, в которых используются лингвистические переменные и нечеткие отношения для описания состояния и поведения исследуемого объекта [4]. Правила, представленные в таком виде, наиболее приближены к естественному языку, поэтому нет необходимости в отдельном специалисте – инженере по знаниям для создания и редактирования правил [5]. Они могут быть отредактированы самим экспертом практически без специальной подготовки [6]. В данной работе была поставлена задача разработки и реализации модифицированного алгоритма Rete для нечеткой продукционной базы правил, а также разработки нечеткой продукционной ЭС, механизм вывода которой будет функционировать на основе созданной модификации алгоритма Rete. Необходимо было разработать формальную модель дерева решений модифицированного алгоритма Rete. При работе решателя нечеткой продукционной ЭС все правила из базы правил применяются последовательно. При этом заново анализируются все условия, которые содержатся в данных правилах. Разрабатываемый алгоритм позволит проверять каждое условие только один раз. Таким образом, обеспечивается ускорение работы решателя нечеткой ЭС, и, следовательно, решение будет найдено быстрее. Нечеткие ЭС В основе правил работы нечетких ЭС лежит понятие лингвистической переменной [7]. У каждой из них есть набор значений – нечеткие переменные, образующие ее терм-множество [8]. Лингвистическая переменная L характеризуется следующим набором свойств: L = (X, T(X), U, G, M), (1) где X – название переменной; T(X) – терм-множество переменной X, то есть множество названий лингвистических значений переменной X, причем каждое из таких значений является нечеткой переменной x’ со значениями из универсального множества U с базовой переменной u; G – синтаксическое правило, порождающее названия x’ значений переменной X; M – семантическое правило, ставящее в соответствие каждой нечеткой переменной x’ ее смысл M(x’), то есть нечеткое подмножество M(x’) универсального множества U. Нечеткая переменная характеризуется тройкой , где x – название переменной; U – универсальное множество; X – нечеткое подмножество множества U, представляющее собой нечеткое ограничение на значение переменной uÎU, обусловленное x [3]. Поведение исследуемой системы описывается на ограниченном естественном языке в терминах лингвистических переменных. Входные и выходные параметры системы рассматриваются как лингвистические переменные, а описание процесса задается набором правил. Формальная модель базы правил разработанной ЭС имеет вид: L1 : A11 и/или A2 и/или ... и/или A1m ® B11 и/или ... и/или B1n, L2 : A21 и/или A22 и/или ... и/или A2m ® B21 и/или ... и/или B2n, (2) … Lk : Ak1 и/или Ak2 и/или ... и/или Akm ® Bk1 и/или ... и/или Bkn, где Ai,j, i = 1, 2, …, k, j = 1, 2, …, m – нечеткие высказывания, определенные на значениях входных лингвистических переменных; Bi,j, i = 1, 2, …, k, j = 1, 2, …, n – нечеткие высказывания, определенные на значениях выходных лингвистических переменных. Эта совокупность правил носит название нечеткой базы знаний. В общем случае нечеткий вывод решения происходит за четыре этапа. 1. Фаззификация. Преобразование с помощью функций принадлежности ϻ точных входных данных в нечеткие значения лингвистических переменных. 2. Непосредственный нечеткий вывод. На основании набора правил нечеткой базы знаний вычисление значения истинности для условий каждого правила по правилам вычисления Т-норм, Т-конорм и отрицаний. 3. Композиция. Формирование значений выходных лингвистических переменных для каждого сработавшего правила. 4. Дефаззификация. Преобразование нечетких значений выходных лингвистических переменных в точные значения. Для вычисления T-норм и T-конорм были выбраны следующие правила: TM(x, y) = min{x, y} и ^M(x, y) = max{x, y}. Для вычисления отрицания утверждения был выбран вариант классического отрицания Ø(x) = 1 – x. Формальная модель дерева решений модифицированного алгоритма Rete Алгоритм Rete является эффективным алгоритмом сопоставления с образцом для продукционных ЭС [9]. Rete стал основой многих популярных ЭС, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar. Классический алгоритм работы ЭС заключается в проверке применимости каждого правила вывода к каждому факту базы знаний при необходимости его выполнения и в переходе к следующему правилу с возвратом в начало базы знаний в случае исчерпания всех правил [10]. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность [11]. При использовании Rete ЭС формирует специальный граф, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции. В процессе работы каждый узел хранит список фактов, соответствующих условию. При добавлении или модификации факта он обрабатывается графом, при этом отмечаются узлы, условиям которых данный факт соответствует. При выполнении полного условия правила, когда система достигает листа графа, правило выполняется. В большинстве случаев скорость работы систем с использованием алгоритма Rete возрастает на порядки. Однако данный алгоритм реализован для ЭС с классическими продукционными правилами. В настоящей работе рассматривается модификация алгоритма Rete для работы с нечеткой базой правил. Граф модификации Rete-алгоритма для нечетких ЭС формируется таким образом, что в каждом случае идет проверка не точного значения условия правила, а значений лингвистических переменных в данном правиле. Формальная модель дерева решений будет иметь вид: M = (X, R, P, Y). (3) X – множество вершин-условий графа; каждая вершина представляет собой условия из правил нечеткой базы знаний, X = {
|
Permanent link: http://swsys.ru/index.php?page=article&id=3996&lang=&like=1&lang=en |
Print version Full issue in PDF (4.84Mb) Download the cover in PDF (0.35Мб) |
The article was published in issue no. № 2, 2015 [ pp. 44-47 ] |
Perhaps, you might be interested in the following articles of similar topics: