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

При этом второй способ ускорения обработкибазы правил экспертной системы может применяться совместно с первым.38Наиболее популярным синтаксическим методом, реализующим указанныйспособ минимизации сопоставлений, является алгоритм Rete, созданный ЧарльзомФорги из Университета Карнеги Меллона.

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

При удалении некоторогоэлемента из рабочей памяти машина вывода устраняет его из списков всехобразцов, которые с ним сопоставлялись. Таким образом, машина вывода,запоминающая указанную информацию, не сопоставляет всю рабочую память совсеми правилами.Семантические подходы, как правило, применяются на этапе выборки иразрешения конфликтов. На этапе выборки механизм вывода фокусируется наопределенном подмножестве элементов рабочей памяти и подмножестве правилбазы знаний, которые могут быть использованы в текущем цикле [5, 11].Обычно выделяют два типа выборки: простую выборку и иерархическуювыборку.

Простая выборка характеризуется тем, что выбираемые сущностирассматриваются как сущности одного уровня. В случае выборки правил припоявлении нового элемента в рабочей памяти те правила, которые содержат этотэлемент в условии правила (при поиске от данных), помечаются как активные. Приудалении элемента из памяти метки у соответствующих правил снимаются.Выборка в данном случае сводится к выбору из всего множества правил тех,которые помечены.При иерархической выборке объекты (правила, данные) разбиваются наиерархические подмножества (классы).

Выборка в данном случае состоит виспользовании метаправила для выбора одного из классов. При этом классы могутбыть как непересекающимися, так и пересекающимися. Введение иерархии правил39неизбежно влечет за собой и иерархию данных, что не всегда явно признаетсяразработчиками систем. Метаправила в отличие от правил применяются не кобъектам предметной области, а к метаданным.Объекты, подлежащие выборке на текущем цикле, задаются либо по имени,либо по описанию свойств. При задании по имени указывается либо переченьобъектов (данных, правил), либо перечень имен классов, описывающих объекты.При задании объектов через описания свойств указывают не имена объектов(классов объектов), а перечень свойств, которыми эти объекты должны обладать.Необходимоотметить,чтоклассическийалгоритмReteявляетсясинтаксическим средством ускорения поиска [21].

Разрабатываемый алгоритмFuzzy Rete, применяемый к нечёткой базе правил функционирует на стыкерассмотренных подходов к ускорению работы системы, поскольку требуетсявыполнять сопоставление лингвистических и нечётких переменных. По сути,данныйалгоритм сам генерирует метаправила, в которыхуказываютсясоответствия между условиями правил, состоящими из лингвистических инечётких переменных [60-62].2.2. Алгоритм Rete для продукционной базы знаний экспертнойсистемыАлгоритм Rete является алгоритм поиска по шаблону. Он разработан д-рЧарльз Л.

Forgy из Университета Карнеги-Меллона. Rete это латинское слово,которое означает "сеть". Алгоритм Rete является эффективным алгоритмомсопоставления с образцом для продукционных экспертных систем [20]. Rete сталосновой многих популярных экспертных систем, включая CLIPS, Jess, Drools,BizTalk Rules Engine и Soar.Алгоритм Rete имеет следующие характеристики [20]:Уменьшает или исключает избыточность условий за счет объединенияузлов.40Сохраняет частичные соответствия между фактами при слиянииразных типов фактов. Это позволяет избежать полного вычисления всех фактовпри любом изменении в рабочей памяти продукционной системы.

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

Правила объединяются и транслируются, в выполнимуюсеть Rete.Когда факты актуализированы, экспертная система создает записи воперативной памяти для каждого факта в виде кортежей разной длины. Каждаязапись может содержать весь факт или наоборот, факт может быть системойзаписей фиксированной длины, обычно триплетов.Все записи поступают в корневой узел сети. Узлы передают записи подереву, где они сохраняются, либо достигают конечных вершин.2.2.1. Альфа сетьЛевая часть графа образует сортировочную сеть, ответственную за выборзаписей по соответствию их атрибутов установленным константам. Узел можетпроверять несколько атрибутов записи. Если запись соответствует условию, онапередается дальше по графу. В большинстве систем первые от корня узлыпроверяют идентификатор или тип записи, поэтому все записи одного типанаправляются по одной ветви сортировочной сети.Каждая ветвь содержит память, в которой накапливаются записи.

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

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

Каждый узел имеет 2 входа и направляет результат в бета-память.Бета-узлы работают с метками, обозначающими записи в альфа-памяти.Метка является единицей хранения и пересылки между узлами и памятью.Бета-узел в качестве результата может создает новые метки для списказаписей или создавать списки меток.Обычно создаются списки, где каждая метка отражает одну запись, а наборзаписей для частичного соответствия представляется списком меток.

Этот подходне требует копирования самих записей, узел просто создать новую метку,добавляет ее к голове списка и сохраняет в буфере выхода.В описании алгоритма Rete принято говорить о передаче меток в бета-сети,но в данном примере используются записи, так как это более обобщенноепредставление. При прохождении записи по бета-сети к ней добавляются новыеатрибуты. Такая запись в бета-сети представляет собой частичное соответствиеусловиям некоторой продукции.42Записи в конечных узлах бета-сети полностью соответствуют условиюпродукции и передаются в выходы Rete-сети, именуемые ‘п-узлы’ от слова‘продукция’.

При попадании записи в п-узел экземпляр правила продукциипередается в «повестку дня», где они хранятся в списке с приоритетом.Бета-узлы объединяют списки записей бета-памяти и отдельных записейальфа-памяти. Каждый бета-узел связан с двумя входными блоками памяти.Альфа-память хранит записи и активирует бета-узлы ‘справа’ при поступлениикаждой новой записи. Бета-память хранит списки записей и при поступлениизаписей активирует бета-узлы ‘слева’.

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

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