Автор: Трегубова Ю.А.
Источник: Інформаційні управляючі системи та комп’ютерний моніторинг (ІУС КМ - 2013) - 2013 / Матерiали IV Всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених. – Донецьк, ДонНТУ – 2013, Том 2, С. 366–369.
Трегубова Ю.А. Обоснование выбора алгоритма Rete для построения экспертной системы определения кулинарного блюда. Рассмотрена проблематика применения экспертных систем, в частности, применительно к кулинарной отрасли. Приведена структура разрабатываемой системы и требования к исходным данным, представлено обоснование выбора алгоритма Rete для реализации компонента поиска решения.
Ключевые слова: экспертная система, база знаний, логический вывод, решатель, rete.
Экспертные системы (ЭС) возникли как значительный практический результат в применении и развитии методов искусственного интеллекта (ИИ) – совокупности научных дисциплин, изучающих методы решения задач интеллектуального (творческого) характера с использованием ЭВМ.
ЭС – это компьютерная система, выполняющая функции эксперта при решении задач из некоторой предметной области. ЭС выдают советы, проводят анализ, дают консультации, ставят диагноз. Практическое применение ЭС на предприятиях способствует эффективности работы и повышению квалификации специалистов.
Большая часть разрабатываемых экспертных систем предназначена для решения проблем в отраслях за пределами нашего повседневного быта. Если рассмотреть кулинарную отрасль, то для нее на данный момент существует множество программных продуктов, предоставляющих функционал для хранения, изменения и обмена информацией о рецептах различных блюд (среди наиболее популярных: eChef, Resort Chef, IT CHEF). Также существует экспертная система CHEF, предназначенная для помощи пользователю в поиске рецептов китайской cычуаньской кухни [1]. Данная экспертная система на основании информации об ингредиентах, способе приготовления и некотором описании требуемого результата также позволяет составлять новые, ранее не существующие в базе знаний рецепты.
Ввиду большого разнообразия существующих национальных кухонь и огромного количества блюд актуальной задачей становится создание экспертной системы, предоставляющей пользователю возможность поиска готовых блюд по различным критериям. На данный момент не существует ни одной системы предоставляющей подобную возможность. Особенностью данной ЭС является необходимость выполнения поиска по базе знаний, содержащей большое количество правил.
Целью данной работы является определение основных правил и алгоритмов, позволяющих выполнить разработку экспертной системы, предоставляющей пользователю возможность поиска кулинарных блюд на основании информации об их типе, составе и принадлежности к определенной национальной кухне.
Для достижения цели решаются следующие задачи:
Типичная ЭС состоит из следующих основных компонентов [2].
1. База знаний. Содержит совокупность знаний о предметной области и способы решения поставленной задачи (правила). Каждое правило представлено в виде «ЕСЛИ <условие 1> И <условие 2> И <условие 3> И … ТО <результат>» и хранится в специальной базе данных.
2. Рабочая память. Предназначена для хранения исходных и промежуточных данных в процессе поиска решения. В разрабатываемой ЭС предполагается размещение данных в ОЗУ.
3. Решатель (интерпретатор). Данный компонент, используя исходные данные из рабочей памяти и знания из базы знаний, формирует такую последовательность правил, которые, будучи примененными к исходным данным, приводят к решению задачи. Для реализации решателя существует множество алгоритмов: прямого и обратного логического вывода, поиска по графу, эвристического поиска. В разрабатываемой ЭС возможно наличие более чем одного решения для текущего набора фактов. В алгоритмах прямого и обратного вывода и поиска по графу при изменении рабочей памяти необходима проверка всех правил, которая требует много времени на выполнение и недопустима. Алгоритмы эвристического поиска не подходят для решения задачи ввиду отсутствия оценочной функции для поиска решений. Для поиска решений в поставленной задаче требуется алгоритм, который имеет полную информацию о правилах и способен быстро находить решения без необходимости проверки всех правил. Таким алгоритмом является Rete, разработанный Чарльзом Л. Форги.
4. Компоненты приобретения знаний, объяснения полученного результата и диалога с пользователем предназначены для редактирования базы знаний и поиска решений и будут реализованы с помощью единого компонента пользовательского интерфейса, предоставляющего доступ и для редактирования базы знаний и для поиска решений. В процессе работы с ЭС, пользователю необходимо будет вводить ответы на указанные вопросы. Тип блюда и название национальной кухни – переменные с максимальным приоритетом и будут запрошены у пользователя в первую очередь. Затем пользователю будет предложено указать наличие тех или иных продуктов в составе искомого блюда и желательное время приема. Результатом работы экспертной системы будет список названий блюд, которые соответствуют указанным условиям. В случае если ни одно правило системы не выполнилось, будет отображена информация по тем правилам, в которых соответствуют истине одно или несколько условий.
В разрабатываемой ЭС предполагается возможность доступа двух типов пользователей: эксперта и конечного пользователя. Эксперт будет иметь возможность редактировать существующие и добавлять новые правила. Конечный пользователь будет работать с ЭС в режиме консультации (поиска решения).
На данный момент в мире существует огромное количество рецептов блюд (тысячи, десятки тысяч). Исходя из этого факта, для разрабатываемой ЭС необходим алгоритм, который позволит получать ответ с высокой производительностью и эффективностью при поиске в базе знаний, содержащей огромное количество правил без последовательной проверки каждого из них.
Алгоритм Rete представляет собой очень быстрое средство сопоставления с шаблонами, высокое быстродействие которого достигается благодаря хранению в оперативной памяти информации о правилах, находящихся в сети. Этот алгоритм предназначен для повышения быстродействия систем с прямым логическим выводом, основанных на правилах, благодаря ограничению объёма работы, требуемой для повторного вычисления конфликтного множества после запуска одного из правил [3].
При инициализации данный алгоритм выполняет построение префиксного дерева (сети) по всем правилам, которые присутствуют в базе знаний ЭС. В случае если есть части условий, которые повторяются для различных правил – они могут быть объединены в один узел дерева [3].
В алгоритме воплощены два описанных ниже эмпирических наблюдения, на основании которых была предложена структура данных, лежащая в его основе.
1. Временная избыточность. Изменения, возникающие в результате запуска одного из правил, обычно затрагивают лишь несколько фактов, а каждое из этих изменений влияет только на несколько правил.
2. Структурное подобие. Один и тот же шаблон часто обнаруживается в левой части более чем одного правила.
Недостатком алгоритма является высокое потребление памяти для хранения построенного префиксного дерева. С другой стороны, данный недостаток нивелируется тем, что в настоящее время большинство ПК имеют достаточный объем оперативной памяти, а низкая стоимость микросхем практически полностью избавляет от данного недостатка.
Преимущества алгоритма:
Для ускорения процесса поиска решений между сессиями работы ЭС будет реализована система кеширования (временного хранения в специальном файле) текущей сформированной структуры префиксного дерева без фактов для быстрой инициализации следующего сеанса работы с экспертной системой.
Проведенный анализ позволит выполнить разрабатываемую экспертную систему, которая предоставит пользователям возможность поиска блюд в зависимости от типа, принадлежности к определенной национальной кухне и наличия определенных продуктов в составе. Использование алгоритма для реализации машины логического вывода Rete позволяет заносить в базу знаний большое количество блюд без ущерба для производительности последующего поиска.
Данная система позволяет гибкую настройку под нужды пользователя. Так, например, если экспертами будет внесена информация о рецепте для каждого блюда, то конечный пользователь системы сможет использовать её как домашнюю кулинарную книгу или как источник информации для составления меню заведения общественного питания.
Если в качестве дополнительной информации указать вместо рецепта приготовления интересное описание блюда, его историю, либо другую полезную маркетинговую информацию, то тогда данную систему можно использовать в качестве интерактивного электронного официанта.