Диссертация (Методы и программные средства ускорения поиска решения в базах знаний нечетких экспертных систем), страница 6

Лингвистическая переменнаяВ основе правил работы нечётких экспертных систем лежит понятиелингвистической переменной [15]. У каждой лингвистической переменной естьнабор значений – это нечёткие переменные, которые образуют её терммножество [16, 24].Лингвистическая переменная L характеризуется следующим наборомсвойствL = (X, T(X), U, G, M),(1.2)в котором:X - название переменной;T(X) обозначает терм-множество переменной X, т.е. множество названийлингвистических значений переменной X, причем каждое из таких значенийявляется нечеткой переменной (x`) со значениями из универсального множестваU с базовой переменной u;G - синтаксическое правило, порождающее названия значений переменнойX;M - семантическое правило, которое ставит в соответствие каждойнечеткой переменной x` ее смысл M(x`), т.е.

нечеткое подмножество M(x`)универсального множества U.31Конкретное название x`, порожденное синтаксическим правилом G,называется термом. Терм, который состоит из одного слова или из несколькихслов, всегда фигурирующих вместе друг с другом, называется атомарнымтермом. Терм, который состоит из более чем одного атомарного терма,называется составным термом [25, 26].1.7.3.

Нечёткая база правил экспертной системыПоведение исследуемой системы описывается на ограниченном естественномязыке в терминах лингвистических переменных [27, 28]. Входные и выходныепараметры системы рассматриваются как лингвистические переменные, аописание процесса задается набором правил [29, 30]. Формальная модель базыправил разработанной экспертной системы имеет вид [31, 32]:R1 : A1,1 и/или A1,2 и/или ... и/или A1,m1 B1,1 и/или ...

и/или B1,k1,R2 : A2,1 и/или A2,2 и/или ... и/или A2,m2 B2,1 и/или ... и/или B2,k2,(1.3).....................Rn : An,1 и/или An,2 и/или ... и/или An,mn Bn,1 и/или ... и/или Bn,kn,где Ai,j, i = 1, 2, …, n, j = 1, 2, …, mi - нечеткие высказывания, определенные назначениях входных лингвистических переменных, а где Bi,q, i = 1, 2, …, n, q = 1, 2,…, ki - нечеткие высказывания, определенные на значениях выходныхлингвистических переменных.В общем случае нечеткий вывод решения происходит за четыре этапа [33 35]:1. этап фаззификации (преобразование с помощью функций принадлежности ϻточных входных данных в нечёткие значения лингвистических переменных);2. этап непосредственного нечеткого вывода (на основании набора правилнечеткой базы знаний вычисляется значение истинности для условийкаждого правила по правилам вычисления Т-норм, Т-конорм и отрицаний);3.

этап композиции (формируются значения выходных лингвистическихпеременных для каждого сработавшего правила);324. этап дефаззификации (преобразование нечётких значений выходныхлингвистических переменных в точные значения).1.7.4. Нечёткий логический выводНа рисунке 1.3 представлена схема работы основных модулей нечёткойэкспертной системы [36 - 38].ИсходныеточныеданныеРезультатПополнение базы правилРис.1.3. Схема работы нечёткой экспертной системыРассмотрим этапы нечеткого вывода решения более подробно [39, 40]:1) Этап фаззификации. С помощью функций принадлежности всех термоввходных лингвистических переменных и на основании задаваемых четкихзначений из универсумов входных лингвистических переменных определяютсястепени уверенности в том, что выходная лингвистическая переменнаяпринимает конкретное значение [41, 42].2) Этап непосредственного нечеткого вывода.

На основании набора правил(нечеткой базы знаний) вычисляется значение истинности для предпосылкикаждого правила на основании конкретных нечетких операций, соответствующихконъюнкции или дизъюнкции термов в левой части правил. В большинствеслучаев это либо максимум, либо минимум из степеней уверенности термов,33вычисленных на этапе фаззификации, который применяется к заключениюкаждого правила. Используя один из способов построения нечеткой импликации,формируется нечеткая переменная, соответствующая вычисленному значениюстепени уверенности в левой части правила и нечеткому множеству в правойчасти правила [43, 44].3) Этап композиции (агрегации, аккумуляции).

Все нечеткие множества,назначенные для каждого терма каждой выходной лингвистической переменной,объединяются вместе, и формируется единственное нечеткое множество значение для каждой выводимой лингвистической переменной. Обычноиспользуются функции максимума или суммирования [45, 46].4) Этап дефаззификации.

Используется тогда, когда полезно преобразоватьнечеткий набор значений выводимых лингвистических переменных к точным.Имеется достаточно большое количество методов перехода к точным. Наиболеечасто используются метод полной интерпретации и метод интерпретации помаксимуму.

В методе полной интерпретации точное значение выводимойпеременнойвычисляетсякакзначение"центратяжести"функциипринадлежности для нечеткого значения. В методе максимума - в качестветочного значения выводимой переменной принимается максимальное значениефункции принадлежности [47 - 49].Наибольшие вычислительные затратывозникают на этапе нечёткогологического вывода. В связи с этим в работе рассматривается предложенныйметод ускорения поиска решения (этапе нечёткого логического вывода) [50, 51].1.8.

Задача ускорения поиска решения в нечётких экспертныхсистемахДля формулировки постановки задачи ускорения поиска решения вводитсяопределение одной итерации логического вывода [52, 53]. Предлагаетсяпредставить её в виде функции F, которая преобразует множество условий вомножество следствий и имеет вид:34F: { A1,1, A1,2, … , A1,m1, Ai,1, Ai,2, … , Ai,mi , An,1, An,2, … , An,mn}  { B1,1, B1,2, … , B1,k1, Bi,1, Bi,2, … , Bi,ki , Bn,1, Bn,2, … , Bn,kn}(1.4)Задача ускорения поиска решения заключается в минимизации вычислений,осуществляемых при обработке матрицы условий А нечётких правил, то есть впостроении множества нечётких условий A*, такого что |A*| < |A|, при условиисохранения результата, а именно: если F(A)B, то F(A*)B.Ускорения поиска решения можно достигнуть двумя способами [54 - 56].1.

Исключение некоторых правил из обработки.Допустим, что исключаются правила i1, i2, …, is. В этом случае:(1.5)2. Поиск одинаковых условий и исключение их повторного вычисления.Допустим в базе знаний найдено p соответствий между условиями вида Ai,j= Av,w, где i = 1, 2, …, n, j = 1, 2, …, mn, v = 1, 2, …, n, w = 1, 2, …, mn. Тогда:(1.6)В работе предлагается подробное рассмотрение второго способа ускоренияпоиска решения в нечётких экспертных системах.

Исходными данными дляразрабатываемого способа являются правила из нечёткой базы правил.Результатом работы должна стать сокращённая база знаний, обеспечивающаяускорение поиска решения.В следующей главе будет приведена разработанная классификацияспособов ускорения работы экспертных систем. Будет рассмотрен универсальныйалгоритм Rete, а также выполнена разработка алгоритма Fuzzy Rete, который35позволяет осуществлять ускорение поиска решения в нечётких экспертныхсистемах.

Дляегоиспользованиябудетвыполнена разработкамоделипредставления знаний и алгоритма преобразования исходной нечёткой базыправил в разработанную модель дерева решений. Также будет предложенаархитектура механизма поиска решения, предусматривающая использованиеалгоритма Fuzzy Rete.1.9. Выводы по главе 11.Сформулированы основные понятия экспертных систем и классификацияэкспертных систем. Выполнен анализ структуры экспертной системы,согласно которой будет разработан прототип нечёткой экспертной системы.Рассматриваются этапы разработки экспертных систем, в соответствии скоторыми будет выполняться создание экспертной системы, и основныепреимущества применения экспертных систем.2.Выполнен анализ моделей представления знаний, обоснованы достоинстваприменения продукционного представления знаний в экспертных системах.3.Приводятся основные понятия нечётких экспертных систем, на основекоторых предложена формальная постановка задачи ускорения поискарешения в базе правил нечёткой экспертной системы.

Выполнен анализэтапов нечёткого логического вывода.36ГЛАВА 2. КЛАССИФИКАЦИЯ МЕТОДОВ УСКОРЕНИЯ ПОИСКАРЕШЕНИЯ В ЭКСПЕРТНЫХ СИСТЕМАХ2.1. Классификация методов ускорения обработки правил вэкспертных системахПри простой схеме просмотра правил в экспертной системе осуществляетсяпросмотр всех правил из базы правил, до тех пор, пока не будет найдено правило,содержащее условия, которые подходят под значения входных параметров.

В этомслучае правило срабатывает и поиск завершается. Однако, при таком подходеприходится выполнять достаточно большой объём вычислений, что приводит кувеличению времени, необходимого на обработку входной информации. Особенноданный факт актуален для систем реального времени [10].Существуют два подхода к уменьшению вычислительных затрат наобработку правил из базы знаний [11, 12]: использование синтаксических средств, сокращающих на каждомцикле работы машины вывода перебор при выполнении операциисопоставления; использование семантических средств, сокращающих перебор привыполнении операции выборки и разрешении конфликтов путемиспользования метапланирования и фокусирования на объектах илиправилах.Суть синтаксических подходов ускорения процесса сопоставления сводитсяк следующему.

В общем случае в каждом цикле работы машины вывода дляполучения означиваний (конфликтного набора) требуется заново сопоставить всеправила из БЗ (из ее активного подмножества) со всеми экземплярами объектов израбочей памяти (из ее активного подмножества). Задача синтаксических методовсостоит в том, чтобы избежать на каждом цикле работы машины выводаповторных сопоставлений правил и данных, так как значительная частьозначиваний текущего цикла может быть использована в следующем цикле [11,12].37В настоящее время существует несколько способов ускорения обработкиправил в экспертных системах [58,59].

Указанные методы основываются наследующих преобразованиях базы знаний:1) Классификация правил в базе правил. Данная классификация можетвыполняться для следующих элементов:• для значений входных переменных (например, при определённомзначении заданного параметра в дальнейшем рассмотрении будутучаствовать только правила из определённой секции базы правил);• для различных ситуаций применения правил (например, в случаерассмотрения определённой ситуации, далее будут рассматриватьсяправила, помеченные, как относящиеся к выбранной ситуации);• дляразличныхправиламиэлементов,(например,еслиактивизируемыхправилопривелоопределённымикактивацииопределённого промежуточного решения, то далее рассматриваютсятолько правила, соответствующие ему).2) Объединение элементов различных правил во взаимодополняющиенаборы(например, при наличии одинаковых условий в различных правилахвыполняется объединение данных правил в сеть и указанное условие проверяетсятолько один раз).Первый способ классификации позволяет сокращать объём обрабатываемойбазы знаний на основе разделения её на блоки правил, которые будутобрабатываться при возникновении определённых условий.

Данный способпредусматривает детальный анализ правил экспертом по знаниям и формированиеуказанных блоков.Второй способ является универсальным и может применяться автоматическипри обработке базы правил с помощью специальной программы, формирующейсетьправилсодинаковымиусловиями,котораявдальнейшембудетпреобразована в дерево решений.