автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели и алгоритмы функционирования продукционных баз знаний

На правах рукописи

ИВАНОВ АЛЕКСАНДР СЕРГЕЕВИЧ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ ПРОДУКЦИОННЫХ БАЗ ЗНАНИЙ

05 13 18-Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003178040

Саратов - 2007

003178040

Работа выполнена в ГОУ ВПО «Саратовский государственный университет им Н Г Чернышевского»

Научный руководитель- доктор технических наук, профессор

Сперанский Дмитрий Васильевич

Официальные оппоненты доктор технических наук, профессор

Кушников Вадим Алексеевич

Защита диссертации состоится 23 января 2008 г в 15 00 часов на заседании диссертационного совета Д 212 242 08 при ГОУ ВПО «Саратовский государственный технический университет» по адресу 410054, г Саратов, ул Политехническая, 77, Саратовский государственный технический университет, корп 1,ауд 319

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет»

Автореферат разослан 21 декабря 2007 г

кандидат физико-математических наук, доцент Сагаева Ирина Дмитриевна

Ведущая организация Санкт-Петербургский университет

информационных технологий, механики и оптики

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Системы баз знаний давно признаны одним из самых эффективных инструментов в проектировании информационных систем различного назначения, в том числе систем управления, экспертных систем и т д При этом большая часть систем, встречающихся на практике, используют продукционную модель как наиболее подходящую для решения практических задач Термин «продукция» введен Е Постом Модель использует представление знаний правилами вида ЕСЛИ ТО Теоретическое обоснование принципов

функционирования продукционных систем, описание продукционной модели и традиционных алгоритмов логического вывода было осуществлено в работах таких зарубежных и отечественных ученых как Фейгенбаум Е , Ньюэлл А , Саймон М, Поспелов Д А, Ларичев О И, Вагин В Н, Попов Э В , Стефанюк В Л, Кирсанов Б С и другие

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

Предметом исследования является продукционная база знаний

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

Для достижения указанной цели поставлены и решены следующие задачи

- разработка новой математической модели представления продукционных баз знаний,

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

- доказательство корректности и эффективности разработанных алгоритмов

Методы исследований. В работе использованы методы теории управления, теории искусственного интеллекта, теории графов, теории алгоритмов, теории формальных языков и грамматик.

Научная новизна. В работе впервые получены следующие результаты

- разработана новая математическая модель представления продукционных баз знаний, существенно ускоряющая

проведение логического вывода, отличающаяся тем, что представляет собой гиперграф специального вида, объединяющего в себе все сущности и зависимости, представляемые в базе знаний,

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

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

- разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе,

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

Практическая ценность Основных результатов диссертационного исследования связана с созданием типового математического и программного обеспечения Оно может использоваться при оперативном управлении производственными процессами предприятия, в экспертных системах и др Реализованный на основе предложенных в диссертации разработок комплекс программ «интеллектуальный помощник» используется в учебном процессе на факультете компьютерных наук и информационных технологий Саратовского государственного университета

Тема диссертации непосредственно связана с приоритетными направлениями развития науки и техники в Российской Федерации, а также с критическими технологиями в следующих разделах и пунктах

Приоритетные направления развития науки, технологий и техники в Российской Федерации

04 Информационно-телекоммуникационные системы

Перечень критических технологий Российской Федерации

01 Базовые и критические военные, специальные и промышленные технологии

23 Технологии создания интеллектуальных систем навигации и управления

Кроме того, диссертационная работа соответствует темам основных научных исследований, проводимых в течение ряда лет на кафедре математической кибернетики и компьютерных наук Саратовского государственного университета (темплан НИР, выполняемый по §47) Положения, выносимые на защиту:

1 Модель представления продукционных баз знаний для реализации прямой цепочки рассуждений позволяет существенно ускорить проведение прямого логического вывода Модель отличается тем, что представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в базе знаний

2 Алгоритм прямого вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении баз знаний Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе

3 Модель представления продукционных баз знаний, разработанная для реализации обратной цепочки рассуждений, позволяет существенно ускорить проведение обратного логического вывода Модель отличается тем, что представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в базах знаний

4 Алгоритм обратного вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении баз знаний Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.

5 Алгоритм проверки продукционной базы знаний на полноту на предложенной модели выполняет автоматическое разбиение правил из базы на группы и, анализируя каждую группу отдельно, позволяет определить недостающие для полноты правила

6 Алгоритм проверки базы знаний на избыточность на предложенной модели отличается тем, что выполняет автоматическое разбиение правил из базы знаний на группы и, анализируя каждую группу отдельно, позволяет определить пары дублирующих друг друга правил

Все результаты, вошедшие в диссертационную работу, получены соискателем самостоятельно

Апробация. Результаты работы докладывались и обсуждались на следующих конференциях Международной конференции «Экспертные и обучающие системы» (Саратов, 1995), Международных конференциях «Компьютерные науки и информационные технологии», посвященных памяти проф А М Богомолова (Саратов, 2002, 2007), 5-м Международном

симпозиуме «Актуальные проблемы машиностроения и механики сплошных и сыпучих сред» (Москва, 2003), ежегодных научных конференциях профессорско-преподавательского состава СГУ (Саратов, 2003-2007), научно-технической конференции «Информационные системы и технологии 2007» (Обнинск, 2007), Международной конференции «Интеллектуальные системы» (Дивноморск, 2007)

Публикации. По результатам работы опубликовано 12 работ, одна из которых в соавторстве

Структура и объем диссертации. Диссертация содержит 117 страниц, состоит из введения, трех основных глав, приложения и списка использованной литературы

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность диссертационного исследования автора, формулируются цели и задачи исследования

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

На основе проведенного анализа современного состояния продукционных систем сформулированы возможные направления их совершенствования, которые и реализованы в последующих главах диссертации

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

Основное содержание диссертационной работы составляют вторая и третья ее главы

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

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

На каждом из перечисленных этапов интерпретатор работает с базой знаний и рабочей памятью

Схему одного цикла работы интерпретатора можно описать следующим образом

Этап выборки. На этапе выборки производится активизация той части данных и знаний, на основании которых может быть реализован запрос пользователя

Рис 1

Этап сопоставления. Выбранное на предыдущем этапе множество активных правил Ру приводится в соответствие выбранному множеству элементов рабочей памяти Л> и определяется конфликтный набор правил, то есть правил из Ру и данных из на которых эти правила определены В результате сопоставления получается конфликтный набор {Рг, Р), ,Рк}

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

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

Этап выполнения. Этот этап заключается в активизации выбранных правил и внесении соответствующих изменений в рабочую память

Модель продукционной БЗ предлагается представить в виде конечного мультиграфа где V - множество вершин, а Е -

множество дуг Множество V является объединением двух непересекающихся множеств множества О вершин-объектов и множества В вершин-ветвлений Таким образом, У=ОиВ Каждая вершина-объект о, соответствует конкретному объекту предметной области, для которой создана используемая БЗ

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

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

Остановимся подробнее на том, каким образом продукционная БЗ будет представлена мультиграфом О

Пусть объект имеет разрешенные значения оц, оп, о/ п,, о2 -021,02 2, 02 п2, и так далее В дальнейшем множество разрешенных значений для о* будем обозначать через /е#(о*) Пусть продукция Р имеет вид

ЕСЛИ о,=11М И ог=(г,и И

о*=/*,,* ИЛИ 0'М'щ И

0\=1\ы ИЛИ

ТО Ог=/,,„.

Из структуры продукции видно, что она является объединением нескольких ИЛИ-компонент, каждая из которых представлена набором пар (о,, 11п), соединенных логической связкой И Каждый набор пар, составляющий ИЛИ-компоненту, далее интерпретируется как вершина-ветвление Ь Множество всех вершин-ветвлений и есть упомянутое выше множество В

Опишем теперь тип вершин мультиграфа <?, составляющих множество О Вершина-объект о^еО является иерархической Сама она считается вершиной нулевого уровня В ее состав входит конечное число вершин 1-го уровня ¡и> > взаимно однозначно соответствующих возможным значениям объекта ок

Приведенной выше продукции Р в мультиграфе С=(У, Е) будет соответствовать подграф, конструируемый следующим образом

Вначале среди вершин множества О выбирается вершина оп которая фигурирует в части «ТО» продукции Р № вершины 1-го уровня этой вершины-объекта 1Г11Г проводятся дуги во все вершины-ветвления, порожденные продукцией Р.

Пусть 6={(о/=// ц), ..,(рк~1к.1к)} является одной из упомянутых вершин-ветвлений Для каждой пары (о/=/, у), где /=1, ,к, из этой вершины проводится дуга в вершину 1-го уровня \ч вершины-объекта о, Если в объекте о1 значение отсутствует, то это свидетельствует об ошибке в

описании продукции Р Аналогичные построения проводятся для всех остальных вершин-ветвлений

Для рассматриваемой в качестве примера продукции Р соответствующий ей подграф мультиграфа 0=(У, Е) изображен на рис 2

Or

j ¡г,„ ir.n-y

01 /я

V-1 А/1 V

П

Г 01 / /

h,2

f Ок \

'к,2 hs^J

< //

'V

Г 7 Л

*J

Рис 2

Модель БЗ в целом представляет собой объединение всех подграфов описанного вида, каждый из которых соответствует некоторой продукции, входящей в состав БЗ

Как видно из изложенного, в построенном подграфе имеется два типа дуг К первому типу относятся дуги, ведущие из вершины-объекта в вершину-ветвление, ко второму - дуги, ведущие из вершины-ветвления в вершину-объект Условимся дуги первого типа обозначать в виде тройки ((ок, ¡¡¿к), b„), где ок - вершина-объект, конкретное значение из множества leg (ок), Ът - вершина-ветвление, являющаяся одним из ЙЛИ-компонент в продукции Р Отметим, что начало этой дуги однозначно определяется парой (ок, Далее, дуги второго типа условимся

обозначать тройкой (Ьт,(ок, 4,*)), где Ьт - вершина-ветвление, из которой исходит дуга, ок - вершина-объект и входящая в ее состав вершина 1-го уровня в которую дуга заходит При этом должно удовлетворяться

следующее условие среди всех пар, составляющих вершину-ветвление Ьт, есть пара (оь 1Ы)

Введем следующие определения

Вершину-объект о назовем невыводимой, если из нее не исходит дуг первого типа Все остальные вершины-объекты будем считать выводимыми

Каждой вершине о* поставим в соответствие множество VL(oi)c legiot), которое формируется в процессе проведения ЛВ и представляет собой множество установленных значений объекта о*

Отметим, что для выводимых вершин имеет место следующее утверждение

(lklke ок) <->3((оь /ы), bj) V( bp (ор, lp, ,р)) (/р, ор) Условимся, что для невыводимой вершины о множество ее значений Fifo,) должно быть запрошено у пользователя до начала ЛВ

В диссертации разработан алгоритм А1 1 для проведения обратного логического вывода На вход алгоритма подается стартовая вершина По окончании его работы множества VL(o) будут содержать в себе результаты проведенного вывода Если для некоторой йершины-объекта о множество VL(o) пусто, то это означает, что значение для данного объекта при проведении консультации установить не удалось

На рис 3 изображен способ представления правил продукций на ЭВМ для проведения логического вывода путем построения обратной цепочки рассуждений

Рис 3

Множество всех объектов БЗ будем представлять в виде линейного односвязного списка objjist вершин-объектов графа G Каждый элемент списка взаимно однозначно соответствует вершине-объекту модели и включает в себя поля

- пате - название объекта,

- question - вопрос о значении объекта, задаваемый пользователю,

- legal-list - ссылка на список разрешенных значений (соответствует множеству leg),

- value-list - ссылка на список полученных в результате консультации значений (соответствует множеству VL)

Перед началом консультации все списки VL должны быть пусты Их заполнение будет происходить во время проведения ЛВ

Список разрешенных значений состоит из двух составляющих

- legal-value - разрешенного значения,

- or-list - списка ссылок на вершины-ветвления, в которые ведут дуги первого типа, начинающиеся в вершине первого уровня legal_yalue вершины-объекта пате

Вершина-ветвление на рис 2 обозначена как and-hst и представляет собой список пар вида [объект] = [значение], являющихся частью дуг второго типа, исходящих из данной вершины-ветвления Каждая пара [объект] = [значение] из списка, в дальнейшем называемая просто парой, есть пара ссылок на соответствующую вершину-объект obj и соответствующее ей разрешенное значение value

Для предложенных модели и алгоритма доказаны следующие утверждения

Теорема 2 1 Вычислительная сложность алгоритма А1 1 проведения обратного JIB есть величина порядка 0(n+t), где п - количество вершин графа, т е количество объектов в предметной области, at- количество ребер графа, т е правил в БЗ

Теорема 2 2 Пусть имеется п объектов, т разрешенных значений для всех объектов, / троек в части «если» продукции и к троек в части «то» продукции Тогда общее количество ссылок в модели равно Q(n+m+l+k)

Приведенная теорема определяет емкостную сложность модели, то есть размеры памяти, требующейся для хранения БЗ Основу модели составляют ссылки на различные элементы модели Поэтому размер модели определяется количеством ссылок в ней и пропорционален размеру БЗ

Для прямого ЛВ аналогичным образом строится модель представления и разрабатывается алгоритм вывода

Отличия этой и предыдущей модели рассмотрим на списочном представлении Для реализации этого представления выберем структуру -списки На рис 4 представлены основные элементы модели и отношения между ними

Множество всех объектов БЗ будем представлять в виде линейного односвязного списка objjist вершин-объектов графа G Каждый элемент списка взаимно однозначно соответствует вершине-объекту модели и включает в себя поля

- пате - название объекта,

- question - вопрос о значении объекта, задаваемый пользователю,

- legal-hst - ссылка на список разрешенных значений,

- value-list - ссылка на список полученных в результате консультации значений

Рис 4

Перед началом консультации все списки VL должны быть пусты Их заполнение будет происходить во время проведения ЛВ.

Список разрешенных значений состоит из двух составляющих

- legal-value - разрешенного значения,

- rule-list - списка ссылок на вершины-ветвления, в которые ведут дуги первого типа, начинающиеся в вершине первого уровня legaljyalue вершины-объекта паше

Вершина-ветвление обозначена как fact-list и представляет собой два списка Первый - список пар вида [объект]=[значение], являющихся частью дуг первого типа, входящих в данную вершину-ветвление и пометки окрашенности дуги znach Второй - список пар вида [объект]=[значение], являющихся частью дуг второго типа, исходящих из данной вершины-ветвления Принадлежность к одному из этих списков определяется полем If_Then Если поле имеет значение «истина», то элемент относится к первому списку, если «ложь» - ко второму Каждая пара [объект]=[значение] из этих списков - это пара ссылок на соответствующую вершину-объект obj и соответствующее ей разрешенное значение value

Для предложенных модели и алгоритма доказаны следующие утверждения

Теорема 2 3 Пусть имеется п объектов, т разрешенных значений для всех объектов, I троек в части «если» продукции и к троек в части «то» продукции Тогда общее количество ссылок равно 0(п+т+1+к)

Теорема 2 4 Пусть р - средний размер правила, / - количество участвовавших в выводе правил, а / - количество правил, в части «если» которых присутствует хотя бы один из установленных фактов Тогда время работы алгоритма А1 2 будет 0(f*p*l)

Таким образом, время работы алгоритма А1 2 в худшем случае будет иметь порядок 0(t*p*t), где t- общее количество правил в БЗ

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

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

- время, затраченное на конвертирование базы знаний из текстового файла в предложенную модель,

- время, затраченное на проведение ЛВ на предложенной модели,

- время, затраченное на проведение ЛВ без использования предложенной модели

Поскольку время может колебаться в зависимости от исходных данных, алгоритм выполнялся многократно при различных наборах входных данных В таблице приводится среднее время В последнем столбце приведено отношение времени проведения ЛВ на предложенной модели ко времени такого же ЛВ, но без ее использования

Таблица 1

Кол-во Кол-во Время, Время Время Отношение

правил объектов затрачен- проведения проведе;ния времени

в базе в базе ное на JIB на традици- проведения

знании знании создание предложен- онного JIB традицион-

модели ной модели (мс) ного JIB ко

(мс) (мс) времени JIB

на модели

5621 1728 10420 17 12420 731

2805 864 3807 11 2802 255

1397 432 1560 5 613 123

693 216 685 2 135 68

341 108 165 1 33 33

165 54 70 1 9 9

На рис 5 приведены графики зависимости времени, затраченного на выполнение трех описанных выше алгоритмов, от количества правил в БЗ На этом рисунке на горизонтальной оси откладывается количество продукционных правил в БЗ, на вертикальной - натуральный логарифм времени, затраченного на выполнение соответствующего алгоритма (время измеряется в миллисекундах)

In(t)

.«o3.^ Л? ¿s dp ф 1МТ

-----Создание модели

ЛВ на модели -Традиционный ЛВ

Рис. 5

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

- время, затраченное на конвертирование базы знаний из текстового файла в предложенную модель;

- время, затраченное на проведение JIB на предложенной модели;

- время, затраченное на проведение ЛВ без использования предложенной модели;

- в последнем столбце приведено отношение времени проведения ЛВ на предложенной модели ко времени такого же JTB, но без ее использования.

___ _ Таблица 2

Кол-во Кол-во Время, Время Время Отношение

правил объек- затрачен- проведения проведения времени

в базе тов в ное на ЛВ на традицион- проведения ЛВ

знаний базе создание предложен- ного JIB на модели ко

знаний модели ной модели (мс) времени тра-

(мс) (мс) диционного ЛВ

5621 1728 11423 37 18420 497

2805 864 4215 19 4169 219

1397 432 1675 9 952 105

693 216 737 4 168 г42

341 108 188 1 ' 38 38

165 54 84 1 8 8

1п(<)

-----Создание модели ......■ Л В на модели -Традиционный ЛВ

Рис. 6

На рис. 6 приведены графики зависимости времени, затраченного на выполнение трех описанных выше алгоритмов, от количества правил в БЗ. На этом рисунке на горизонтальной оси откладывается количество продукционных правил в БЗ, на вертикальной - натуральный логарифм времени, затраченного на выполнение соответствующего алгоритма (время измеряется в миллисекундах).

Анализ приведенных экспериментальных данных показывает, что время, затрачиваемое на построение модели, имеет тот же порядок, что и время, необходимое для проведения традиционного логического вывода.

Эти данные также наглядно демонстрируют, что время проведения ЛВ на предложенной модели значительно ниже, чем без ее использования. Отсюда вытекает, что применение такой модели представления продукционной БЗ на ЭВМ позволит существенно повысить эффективность логического вывода.

В третьей главе диссертации рассматриваются вопросы контроля продукционных БЗ.

Работы в области контроля БЗ традиционно ведутся в двух направлениях. Одно из них основано на использовании статического анализа БЗ, когда проверка качества БЗ осуществляется без запуска интерпретатора системы. Второе направление — тестирование БЗ, предполагающее анализ результатов работы машины логического вывода на достаточно большом множестве различных наборов исходных данных.

На различных этапах жизненного цикла продукционных систем источниками ошибок в БЗ являются:

- ошибки, возникающие при непосредственном внесении информации в БЗ пользователем;

- ошибки, появляющиеся в процессе поступления запросов к БЗ непосредственно от пользователя;

- ошибки, возникающие в процессе вывода решения и добавления к БЗ новых знаний,

- ошибки, являющиеся результатом недостаточной проработки предметной области

Принято выделять следующие основные классы ошибок в продукционных БЗ

1 Избыточность, т е наличие нескольких цепочек рассуждений, позволяющих сделать один и тот же вывод

2 Неполнота, т е невозможность получения результата при некоторых наборах исходных данных

3. Противоречивость, т е возможность при одном и том же наборе исходных данных получить несколько противоречащих друг другу результатов

Заметим, что в процессе проведения логического вывода может возникнуть ситуация, когда некоторое значение рассматриваемого объекта выражается через какое-либо значение (возможно, то же самое) этого же объекта Появление такой ситуации говорит либо о появлении ошибки, либо о наличии ряда эквивалентных утверждений вида «Если А то В» и «Если В то А» или более длинных цепочек В диссертации предложены алгоритмы А3.1 - АЗ 3 поиска таких циклических зависимостей Алгоритмы АЗ 1 и АЗ 3 рассматривают нахождения некоторого множества циклических зависимостей на моделях для обратного и прямого ЛВ соответственно Алгоритм АЗ 2 производит поиск всех возможных циклических зависимостей

Теорема 3 1 Вычислительная сложность алгоритмов АЗ 1 и АЗ 3 равна 0(и*/), где п - количество объектов, ъ. г - количество правил в базе знаний

В этой главе диссертации также предлагаются два алгоритма (АЗ 4 и АЗ 5) проверки на неполноту в продукционной базе знаний Алгоритмы разбивают базы знаний на группы связанных друг с другом знаний Анализируя каждую группу отдельно, алгоритмы выводят комбинации входных данных, при которых невозможно получение результата При этом алгоритм АЗ 5 работает быстрее, чем алгоритм АЗ 4, но требует больше оперативной памяти Алгоритм АЗ 4, напротив, требует оперативной памяти меньшего объема, но он уступает алгоритму АЗ 5 по быстродействию Таким образом, пользователю предоставляется возможность выбора 'подходящего алгоритма в зависимости от критичности двух упомянутых параметров - времени и оперативной памяти

В этой же главе предложен алгоритм АЗ 6 проверки БЗ на избыточность Идея алгоритма заключается в поиске среди множества правил БЗ таких их комбинаций, для которых имеет место теоретико-

множественное включение одной в другую Этот факт является подтверждением избыточности информации

Для предложенных алгоритмов получены оценки их временной сложности Пусть в БЗ имеется г объектов, влияющих на целевой объект, причем каждый из этих объектов имеет г„ (п= 1 г) разрешенных значений Тогда справедливы следующие утверждения

Теорема 3 2 Время проверки БЗ на полноту алгоритмом АЗ 4 равно

г

+1 ))*Н), где Н - количество правил, влияющих на данный объект

»=1

Теорема 3 3 Время проверки БЗ на полноту алгоритмом АЗ 5 равно 0((\1„ *г)

Теорема 3 4 Время проверки на избыточность алгоритмом 3 6 равно

0(П«„ *г)

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

В табл 3 приведено время работы трех алгоритмов

- проверки БЗ на полноту полным перебором (алгоритм АЗ 4),

- проверки БЗ на полноту ускоренный (алгоритм АЗ 5),

- проверки БЗ на избыточность (алгоритм АЗ 6)

Так же как и в табл 1-2 время приводится в миллисекундах Тестирование проводилось при тех же условиях

Таблица 3

Кол-во Кол-во Проверка Проверка Проверка на Сокращение

правил объектов на на полноту с времени

в базе в базе избыточ- полноту ускорением проверки на

знании знании ность (мс) полным (мс) полноту за

перебо- счет

ром (мс) ускорения

5621 1728 114 1198 101 в 11 раз

2805 864 57 403 51 в 8 раз

1397 432 28 158 24 в 7 раз

693 216 12 67 12 в 6 раз

341 108 7 32 6 в 6 раз

165 54 4 16 3 в 5 раз

На рис. 7 приведены графики зависимостей времени выполнения алгоритмов A3.4, A3.5 и A3.6 от количества правил в БЗ.

мс

1500

1000 500 0

165 341 693 1397 2805 5621 шт

-----полнота с повышением эффективности

—— полнота с перебором

неизбыточность_________.

Рис.7

Приведенные данные свидетельствуют, что предложенные в диссертации алгоритмы позволяют эффективно проводить статическую верификацию продукционной БЗ.

Заключение

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

К числу основных результатов работы относятся:

1. Разработана новая математическая модель представления продукционных баз знаний на ЭВМ, представляющая собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в £3. Это позволяет существенно ускорить проведение логического вывода.

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

3. Предложены новые, более совершенные алгоритмы проверки продукционной базы знаний, построенной на основе предложенной в диссертации математической модели, на полноту и избыточность. Алгоритмы выполняют автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяют определить недостающие для полноты правила или пары дублирующих друг друга правил.

4. Разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе.

5. Получены оценки вычислительной (временной и емкостной) сложности предложенных в диссертации алгоритмов работы продукционной системы. На их основе доказано, что работа продукционной системы на

7, : 1 Д : .....

. --...... : .

предложенной математической модели эффективнее, чем основанная на существующих представлениях, что также подтверждается статистическими данными, полученными на основе проведенных экспериментов

6 Создано программное обеспечение, реализующее разработанную модель и предложенные алгоритмы

Перспективным направлением развития данной тематики автору

видится создание аппаратно-программного обеспечения для работы

продукционных систем.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

I Публикации в изданиях, рекомендованных ВАК РФ

1 Иванов АС Модель представления продукционных баз знаний на ЭВМ /А С Иванов //Известия Саратовского университета Серия «Математика Механика Информатика» 2007 Т 7 Вып 1 - С 83-88

II Публикации в других изданиях

2 Иванов А С Синтаксический и семантический анализ продукционных баз знаний /А С Иванов, С П Шевырев //Искусственный интеллект сб трудов - Саратов- Изд-во Сарат ун-та, 1995 - С. 40-45

3 Иванов А С Анализ семантики продукционных баз знаний /А С Иванов //Теоретические проблемы информатики и ее приложений 1997. Вып 1.-С 74-79

4 Иванов А С Конвертирование баз знаний /А С Иванов //Теоретические проблемы информатики и ее приложений 2001 Вып 4 - С 82-88

5 Иванов АС Представление продукционных баз знаний в экспертных системах /А С Иванов //Компьютерные науки и информационные технологии сб трудов - Саратов Изд-во Сарат ун-та, 2002 - С 30-31

6 Иванов А С Модель представления продукционных баз знаний на ЭВМ /А С Иванов //Теоретические проблемы информатики и ее приложений

2003 Вып 5 - С 63-68

7 Иванов А С Модели представления продукционных баз знаний на ЭВМ /А С Иванов, Сарат гос ун-т им H Г Чернышевского - Саратов, 2004 -16 с- Библ 5 -Рус -Деп в ВИНИТИ 27 02 2004, № 350-В2004

8 Иванов А С Модель представления продукционных баз знаний на ЭВМ /А С Иванов //Теоретические проблемы информатики и ее приложений

2004 Вып 6-С 95-100

9 Иванов АС К вопросу верификации продукционных баз знаний /А С Иванов //Теоретические проблемы информатики и ее приложений 2006 Вып 7 - С 52-59

А/у

1'Ь

10 Иванов А С Графовая модель продукционной базы знаний /А С Иванов //Информационные системы и технологии 2007• сб трудов - Обнинск Изд-во ИАТЭ, 2007 - С 33-34

11 Иванов А С Модель представления продукционных баз знаний /А С Иванов //Компьютерные науки и информационные технологии- сб трудов - Саратов Изд-во Сарат ун-та, 2007.-С 50-51

12 Иванов А С Графовая модель представления продукционных баз знаний /А С Иванов //Труды конф А18'07 в 3 т - М .Физматлит, 2007 Т 2 - С 176-182

Подписано в печать 18 12 07 Формат 60x84 1/16

Бум офсет Уел печ л 1,0 Уч -изд л 1,0

Тираж 100 экз Заказ 439 Бесплатно

Саратовский государственный технический университет

410054, Саратов, Политехническая ул , 77 Отпечатано в РИЦ СГТУ 410054, Саратов, Политехническая ул , 77

Введение.

Глава 1. Принципы функционирования продукционных баз знаний.

1.1. Системы продукций.

1.2. Формальное определение продукции.

1.3. Логический вывод в продукционных системах.

1.4. Области применения продукционных систем.

1.6. Выводы к первой главе.

Глава 2. Модели представления продукционных баз знаний на ЭВМ.

2.1. Синтаксис продукционной базы знаний.

2.2. Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации обратной цепочки рассуждений.

2.3. Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации прямой цепочки рассуждений.

2.4. Обобщенная модель представления продукционных правил на ЭВМ

2.5. Программный комплекс «Интеллектуальный помощник».

2.6. Выводы ко второй главе.

Глава 3. Контроль продукционных баз знаний.

3.1. Методы контроля продукционных БЗ.

3.2. Противоречивость.

3.3. Полнота.

3.4. Избыточность.

3.5. Выводы к третьей главе.

Актуальность темы. Системы баз знаний давно признаны одним из самых эффективных инструментов в проектировании информационных систем различного назначения, в том числе, систем управления, экспертных систем и т.д. При этом большая часть систем, встречающихся на практике, используют продукционную модель как наиболее подходящую для решения практических задач. Термин «продукция» введен Е. Постом. Модель использует представление знаний правилами вида ЕСЛИ . ТО. Теоретическое обоснование принципов функционирования продукционных систем, описание продукционной модели и традиционных алгоритмов логического вывода было осуществлено в работах таких зарубежных и отечественных ученых как Фейгенбаум Е., Ныоэлл А., Саймон М., Поспелов Д.А., Ларичев О.И., Вагин В.Н., Попов Э.В., Стефанюк В.Л., Кирсанов Б.С. и другие.

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

Предметом исследования является продукционная база знаний.

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

Для достижения указанной цели поставлены и решены следующие задачи:

- разработка новой математической модели представления продукционных баз знаний;

- разработка и обоснование для предложенной математической модели новых, более совершенных алгоритмов проведения логического вывода и проверки продукционных баз знаний на полноту и избыточность;

- доказательство корректности и эффективности разработанных алгоритмов.

Методы исследований. В работе использованы методы теории управления, теории искусственного интеллекта, теории графов, теории алгоритмов, теории формальных языков и грамматик.

Научная новизна. В работе впервые получены следующие результаты:

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

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

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

- разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе;

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

Практическая ценность основных результатов диссертационного исследования связана с созданием типового математического и программного обеспечения, используемого при оперативном управлении производственными процессами предприятия. Реализованная на основе предложенных в диссертации разработок оболочка продукционной системы используется в учебном процессе на факультете компьютерных наук и информационных технологий Саратовского государственного университета.

Тема диссертации непосредственно связана с приоритетными направлениями развития науки и техники в Российской Федерации, а также с критическими технологиями в следующих разделах и пунктах. Приоритетные направления развития науки, технологий и техники в Российской Федерации.

04 Информационно-телекоммуникационные системы

Перечень критических технологий Российской Федерации. 01 Базовые и критические военные, специальные и промышленные технологии

23 Технологии создания интеллектуальных систем навигации и управления

Кроме того, диссертационная работа соответствует темам основных научных исследований, проводимых в течение ряда лет на кафедре математической кибернетики и компьютерных наук Саратовского государственного университета (темплан НИР, выполняемый по §47).

Положения, выносимые на защиту:

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

2. Алгоритм прямого вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении БЗ. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.

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

4. Алгоритм обратного вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении БЗ. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.

5. Алгоритм проверки продукционной БЗ на полноту на предложенной модели. Алгоритм выполняет автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяет определить недостающие для полноты правила.

6. Алгоритм проверки БЗ на избыточность на предложенной модели. Алгоритм выполняет автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяет определить пары дублирующих друг друга правил.

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

Апробация. Результаты работы докладывались и обсуждались на следующих конференциях:

- «Экспертные и обучающие системы» (Саратов, 1995);

- Международные конференции «Компьютерные науки и информационные технологии», посвященные памяти проф. А.М. Богомолова (Саратов, 2002,2007);

- 5-ый международный симпозиум «Актуальные проблемы машиностроения и механики сплошных и сыпучих сред» (Москва, 2003);

- Ежегодные научные конференции профессорско-преподавательского состава СГУ (Саратов, 2003-2007);

- Научно-техническая конференция «Информационные системы и технологии 2007» (Обнинск 2007);

- Международная конференция «Интеллектуальные системы» (Дивноморск, 2007).

Публикации. По результатам работы опубликовано 12 работ, одна из которых в соавторстве.

3.5. Выводы к третьей главе

1. Анализ работ в области контроля продукционных БЗ показывает, что основное внимание исследователей направлено на обнаружение противоречий. Этот вид ошибок считается самым важным, ему посвящена большая часть работ в этой области. Неудивительно, что здесь достигнуты значительные результаты.

2. В диссертации обоснована важность обнаружения циклических зависимостей между объектами БЗ и предлагаются алгоритмы обнаружения этих зависимостей.

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

4. Отмечается, что избыточность, хотя и не оказывают такого влияния на качество функционирования продукционных систем как наличие противоречий или неполнота, тем не менее, способна существенно замедлить время проведения JIB. Предлагается алгоритм нахождения избыточности в БЗ и обосновывается его эффективность.

Заключение

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

Более детально основные результаты диссертационной работы можно сформулировать следующим образом:

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

2. Разработана новая математическая модель представления продукционных баз знаний на ЭВМ, представляющая собой гиперграф специального вида объединяющего в себе все сущности и зависимости, представляемые в БЗ. Это позволяет существенно ускорить проведение логического вывода.

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

4. Предложены новые, более совершенные алгоритмы проверки продукционной базы знаний, построенной на основе предложенной в диссертации математической модели, на полноту и избыточность. Алгоритмы выполняют автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяют определить недостающие для полноты правила, или пары дублирующих друг друга правил.

5. Разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе.

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

7. Создано программное обеспечение, реализующее разработанную модель и предложенные алгоритмы.

Перспективным направлением развития данной тематики автору видится создание аппаратно-программного обеспечения для более эффективной работы продукционных баз знаний.

1. Апухтин Д.Ю. Опыт внедрения различных SCADA-систем основа разработки системы «АТЛАНТ» /Д.Ю. Апухтин //Автоматизация в промышленности.- №4.- 2007.

2. Астахова О.А. Проблемы обеспечения релевантности баз знаний в экспертных систем /О.А. Астахова, В.В. Сипко //Материалы XXXVII отчетной конференции за 1998г.- Воронеж.- Изд. ВГТА, 1999.

3. Ахо А. Построение и анализ вычислительных алгоритмов /А. Ахо, Дж. Хопкрофт., Дж. Ульман.- М.: «Мир», 1979.

4. Башмаков А.И. Стратегии разрешения противоречий в базах знаний /А.И. Башмаков, И.А. Башмаков //Вестник МЭИ.- 2001.- №3.- С. 8087.

5. Бек Л. Введение в системное программирование /Л. Бек.- М.: "Мир", 1988.

6. Вагин В.Н. Параллелизм в продукционных моделях представления знаний /В.Н. Вагин, А.П. Еремеев //Изв. АН. Техническая кибернетика.- 1994,- №2,- С.48-55.

7. Гаврилов Д.А. Управление производством на базе стандарта MRP II: Принципы и практика /Д.А. Гаврилов.- СПб: Питер, 2002.

8. Гиляров В.Н. Формализация знаний в нечетких экспертных системах /В.Н. Гиляров, А.Н. Токмаков //Приборы и системы: Управление, контроль, диагностика.- 2001.- №9.

9. Джексон П. Введение в экспертные системы //П. Джексон.- М.: Изд. дом «Вильяме», 2001.

10. Динамический подход к анализу структур, описываемых графами (основы графодинамики) /М.А. Айзерман, JI.A. Гусев, И.М. Смирнова и др.1 //Изв.АН СССР Автоматика и телемеханика.- 1977.-№7.- С.135-151.

11. Довгаль В.М. Алгебра продукций //В.М. Довгаль.- Курск, КГТУ, 1996,- 7 с.

12. Долинина О.Н. Тестирование продукционных баз знаний экспертных систем /Д.Ю. Голембиовский, О.Н. Долинина //тезисы докладов XVIII межреспубликанской школы семинара «техническая диагностика и технология банковских расчетов».-Пермь, 1994.- С. 11-12

13. Долинина О.Н. Отладка продукционных баз знаний экспертных систем /О.Н. Долинина //Математические методы в технике и технологиях ММТТ-12. Сборник трудов 12 международной конференции.- Изд. Новгородского государственного университета, 1999.

14. Долинина О.Н. Обнаружение ошибок типа «забывание об исключение» в продукционных базах знаний экспертных систем /О.Н. Долинина //Саратовский государственный технический университет.- Саратов, 1997.- Деп. в ВИНИТИ №678В97.

15. Долинина О.Н. Разработка метода тестирования продукционных баз знаний экспертных систем с учетом ошибок типа «забывание об исключении»: Автореф. кфмн /О.Н. Долинина; Саратов, СГТУ, 1999.

16. Донской В.И. Логические продукционные системы: анализ и синтез /В.И. Донской //Кибернетика и системный анализ,- 1994.- №4.- с. 1122

17. Еремеев А.П. Организация параллельных вычислений на основе моделей потока данных /А.П. Еремеев //Изв. РАН. Техническая кибернетика.- 1993.- №3.

18. Еремеев А.П. Продукционная модель представления знаний на базе языка таблиц решений /А.П. Еремеев //Изв. АН СССР. Техническая кибернетика.- 1987.- №2.

19. Еремеев А.П. Параллельная модель для продукционной системы табличного типа /А.П. Еремеев // Изв. АН СССР. Техническая кибернетика.- 1990.- №5.

20. Жожикашвили А.В. О понятии продукции в искусственном интеллекте /А.В. Жожикашвили, B.JI. Стефанюк // Изв. РАН. ТиСУ.-2002.- №4.

21. Жожикашвили А.В., Стефанюк B.JI. Теоретико-категорные образцы для задач искусственного интеллекта. Новые результаты /А.В. Жожикашвили, В.Л. Стефанюк //Изв. РАН. ТиСУ.- 1999.- №5.

22. Иванов А.С. Синтаксический и семантический анализ продукционных баз знаний /А.С.Иванов, С.П. Шевырев //Искусственный интеллект.- Саратов,. 1995.- С. 40-45.

23. Иванов А.С. Анализ семантики продукционных баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. Вып. 1.- Саратов, 1997.- С. 74-79.

24. Иванов А.С. Конвертирование баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. Вып. 4-Саратов, 2001.-С. 82-88.

25. Иванов А.С. Представление продукционных баз знаний в экспертных системах /А.С.Иванов //Компьютерные науки и информационные технологии.- Саратов, 2002.- С.30-31.

26. Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С.Иванов //Теоретические проблемы информатики и ее приложений. Вып. 5.- Саратов, 2003.- С. 63-68.

27. Иванов А.С. Модели представления продукционных баз знаний на ЭВМ /А.С.Иванов; Саратовский государственный университет им. Н. Г. Чернышевского.- Саратов, 2004.- 16 с.-, библ. 5. Рус. - Деп. в ВИНИТИ 27.02.2004, № 350-В2004.

28. Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С.Иванов //Теоретические проблемы информатики и ее приложений. Вып. 6.- Саратов, 2004.- С.95-100.

29. Иванов А.С. К вопросу верификации продукционных баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. Вып. 7.- Саратов, 2006.- С.52-59.

30. Иванов А.С. Графовая модель продукционной базы знаний /А.С.Иванов //Информационные системы и технологии 2007.-Обнинск, 2007.- С.33-34.

31. Иванов А.С. Модель представления продукционных баз знаний /А.С. Иванов //Компьютерные науки и информационные технологии.- Саратов, 2007.- С. 50-51.

32. Иванов А.С. Графовая модель представления продукционных баз знаний /А.С. Иванов //Труды конференции AIS'07. Т.2.-М.гФизматлит, 2007.- С. 176-182.

33. Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С. Иванов //Известия Саратовского университета. Серия «Математика. Механика. Информатика» Т.7. Вып 1.- Саратов, 2007.-С.83-88.

34. Искусственный интеллект и экспертные системы /Новосибирск, 1996.- Вып. 157 Вычислительные системы.- 257 с.

35. Керов J1.A. Экспертные системы. Инструментальные средства разработки / JI.A. Керов.- Спб. Изд. «Политехника», 1996.

36. Красноженов Ю.Б., Шумаков П.В. Введение в экспертные системы / Ю.Б. Красноженов, П.В. Шумаков //М.: МГАПИ, 1995.- 11 с.

37. Ларичев О.И. , Моргоев В.К. Проблемы методы и системы извлечения экспертных знаний // Изв.АН СССР. Автоматика и телемеханика. 1991. №9.С.З-27.

38. Липский В. Комбинаторика для программистов /В. Липский.- М.: "Мир", 1988.

39. Люгер Дж.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем /Дж.Ф. Люгер.- М.: Изд. дом «Вильяме», 2003.- 864 с.

40. Маренко В.А. Способы представления данных в экспертных системах /В .А. Маренко // Математические структуры и моделирование.- 2001.- №8.

41. Маренко В.А. Представление знаний в экспертных системах /В.А. Маренко, В.А. Шапиев.- Сургут.- РИО СурГПИ, 2002.- 73 с.

42. Методы обнаружения знаний в «зашумленных» базах данных /A.M. Бериша, В.М. Вагин, А.В. Куликов, Н.В. Фомина//Известия РАН. Теория и системы управления.- 2005.- №6.- С. 143-158.

43. Нариньяни А.С. Системы продукций как модульный программный комплекс ,А.С. Нариньяни //Прикладные и экспериментальные процессоры.- Новосибирск, 1985.- с. 125-152.

44. Нариньяни А.С. Продукционные системы /А.С. Нариньяни, Т.М. Яхно //Представление знаний в человеко-машинных и робототехнических системах.- М.: Изд. ВИНИТИ, 1984.- с. 136-177

45. Нильсон Н. Принципы искусственного интеллекта /Н. Нильсон.-М.: Радио и связь, 1985.

46. Попов Э.В. Особенности разработки и использования экспертных систем /Э.В. Попов //Искусственный интеллект. Системы общения и экспертные системы. Под ред. Попова Э.В.- М.: Радио и связь, 1990.-Кн. 1.-е. 261-290.

47. Попов Э.В. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта //Э.В. Попов, Г.Р. Фирдман.- М.: Наука, 1976.- 235 с.

48. Попов Э.В. Статические и динамические экспертные системы (классификация, состояние, тенденции) /Э.В. Попов, И.Б. Фоминых, Е.Б. Кисель. М.: ЦЦРЗ, 1995.- 126 с.

49. Попов Э.В. Экспертные системы // Э.В. Попов.- М.: «Наука», 1987.

50. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии //Г.С. Поспелов.- М.: Наука, 1988.280 с.

51. Поспелов Д.А. Ситуационное управление. Теория и практика /Д.А. Поспелов.- М.: Наука, 1986,- 288 с.

52. Поспелов Д.А. Сетевые и продукционные модели /Д.А. Поспелов //Представление знаний в человеко-машинных системах. Т.А: Фундаментальные исследования в области представления знаний.-М:Наука,1984.- С.77-83.

53. Поспелов Д.А. Продукционные модели /Д.А. Поспелов //Искусственный интеллект. Кн. 2.- М.: «Радио и связь», 1990.

54. Поспелов И.Г. Динамическое описание систем продукций и проверка непротиворечивости продукционных экспертных систем //И.Г. Поспелов, Л.Я. Поспелова.- Известия АН СССР, Техническая кибернетика.- 1987,- №1.- с. 184-192

55. Пунков К.А., Коньков В.Г. Интеллектуальные системы /К.А. Пунков, В.Г. Коньков.- М: Изд. МГТУ им. Н.Э. Баумана, 2003.348 с.

56. Пшеничников И.С. Модели и алгоритмы системы оперативного управления мостостроительной организацией /И.С. Пшеничников, В.А. Кушников, Е.И. Шлычков //Вестник Саратовского государственного технического университета.- №3 (15). Выпуск 2.2006.- С.72-78.

57. Райли Д. Абстракция и структуры данных /Д. Райли,- М.: «Мир», 1993.

58. Рассел С. Искусственный интеллект: современный подход, 2-е изд. Пер.с англ /С. Рассел, П. Норвиг.- М.: Издательский дом «Вильяме», 2006,- 1408 с.

59. Рудакова Г.М. Искусственный интеллект. Экспертные системы /Г.М. Рудакова.- Красноярск.- СибГТУ, 2002.- 88 с.

60. Силич М.П. Метод формирования гибридных моделей для построения экспертных систем /М.П. Силич // Автоматическое и автоматизированное управление сложными системами. Сборник трудов НИИАЭМ.- Томск.- ТГУ, 2001.

61. Соломатин Н.М. Семантические аспекты организации экспертных систем /Н.М. Соломатин // Вестник МГТУ. Сер. Приборостр.- 1994.-№1.-с. 15-22.

62. Статические и динамические экспертные системы /Э.В. Попов, И.Б. Фоминых, Е.Б. Кисель, М.Д. Шапот.- М.: Финансы и статистика, 1996.-354 с.

63. Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ /К. Таунсенд, Д. Фохт.-М.: «Финансы и статистика», 1990.

64. Титенко Е.А. Продукционный подход к проектированию экспертных систем /Е.А. Титенко, Ф.А. Стариков //Известия Курского государственного технического университета.- 2002.- №2.

65. Уотерман Д. Руководство по экспертным системам /Д. Уотерман.-М.: Мир, 1989.

66. Уэно X. Представление и использование знаний /X. Уэно, М. Исидзука.-М.: «Мир», 1989.

67. Хейес-Рот Ф. Построение экспертных систем /Ф. Хейес-Рот ,Д. Уотерман, Д. Ленат.- М.: Мир. 1987.

68. Хоар Ч. Взаимодействующие последовательные процессы /Ч. Хоар.- М.: Мир, 1989.

69. Цыпков П.В. Двухслойный принцип построения диагностических экспертных систем /П.В. Цыпков // Вопр. радиоэл. Сер. Электрон, вычисл. техника.- 1992.- №9.- с. 23-36.

70. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS /А.П. Частиков, Т.А. Гаврилова, Д.Л. Белов.-Спб: БХВ-Петербург, 2003.- 608 с.

71. Шлычков Е.И. Модели и методы поиска данных по производственным ситуациям в информационно-измерительных и управляющих системах /Е.И. Шлычков, В.А. Кушников, А.Ф. Резчиков.- Саратов: Изд-во СГТУ, 2002.- 112 с.

72. Экспертные системы. Принципы работы и примеры /Под редакцией Р. Форсайта.- М.: Радио и связь, 1987

73. Экспертные системы: состояние и перспективы /М.: Наука, 1989.152 с.

74. Яхно Т.М. Потоковые вычисления в системах продукций /Т.М. Яхно //Труды всесоюзной конференции «Параллельное программирование и высокопроизводительные структуры»,- Киев, 1988.- с. 124-146.

75. Яхно Т.М. Представление знаний в системах ограничений /Т.М. Яхно //Актуальные проблемы информатики, прикладной математики и механики. Часть III.- Красноярск.- Изд. СО РАН, 1996.- с. 158-170.

76. Яхно Т.М. Системы продукций как средство представления и обработки знаний в интеллектуальных системах: Автореф. дис. к-та физ. мат. наук/Т.М. Яхно; Новосибирск, 1986.

77. Яхно Т.М. Системы продукций как стиль программирования задач искусственного интеллекта /Т.М. Яхно //Предпринт 499.-Новосибирск, 1984.

78. Яхно Т.М. Системы продукций: структура, технология, применение /Т.М. Яхно.- Новосибирск.- Изд. ВЦ СО АН СССР, 1990.

79. Яхно Т.М. Создание экспертных систем на основе систем продукций /Т.М. Яхно //Теоретические проблемы обработки информации.-Новосибирск, 1986.-е. 144-152.

80. Яхно Т.М. Средства представления и методы обработки знаний в интеллектуальных системах: Автореф. дис. д-ра физ. мат. наук /Т.М. Яхно; Новосибирск, 1997.

81. Яхно Т.М. Управление выводом в системах продукций /Т.М. Яхно //Теоретические и прикладные вопросы обработки параллельной информации.- Новосибирск, 1984.- с. 34-43.

82. Яхно Т.М. Формальная модель вычислений в системах продукций /Т.М. Яхно //Известия АН СССР. Техническая кибернетика.- 1988.-№2.- с. 76-81.

83. Besem M. Semantic and consistency of rule-based expert-system /М. Besem.- Proc. of the 9th conf. on Automated Deduction Springer Lectures Nodes in Computer science.- Springer-Verlag, Berlin, 1987.-p.151-161.

84. Checking Expert System Knowledge bases for consistency and Completeness Checking /Т. Nguyen, W. Perkins, T. Laffey, W. Pecora //Proc. of the 9th Int. Joint Conf. on AI, Los.Ang.- August, 1985.- p. 375378.

85. Cragun В.J. A decision-table-based processor for checking completeness and consistensy /В J. Cragun, HJ. Stendel // Int. J. Man.-Mach. Stud.-1987.-№5.- p.633-648.

86. Davis R. Knowledge-based systems: The view in 1986 /R. Davis.- AI 1980s and Beyond: MIT Surv.- Cambridge, London, 1987.- p. 13-41.

87. Dung Phan Minh, Mancarella Paolo. Production system with negation as failure /P.M. Dung, P. Mancarella // IEEE Trans, knowl. and Data Eng.-2002.-14 №2.

88. Erman L. at al. The Hersay-II. Speech Understanding System. Integrating Knowledge to Resolve Uncertainty //L. Erman.- Computer survey.-12(2), June, 1980.- p. 213-253.

89. Feigenbaum E. The handbook of artificial intelligence /Е. Feigenbaum, A. Barr //NY: Academic Press.- 1982.

90. Forgy C. RETE: A fast algorithm for the many pattern / many object pattern match problem /С. Forgy //Artificial Intelligence. 1982. VI9.

91. Georgeff M. A framework for control in production systems /М. Georgeff// In: Proc. of IJCAI-6.- Tokyo.- 1979.- p. 328-334.

92. Goldstein I. Annotated production system: a model for skill acquisition / I. Goldstein // In: Proc. of IJCAI-5.- Cambridge, Massachusetts, USA, 1977.

93. Miroguchi R. et al. Hierarchical production system. / R. Miroguchi /Яn: Proc. of IJCAI-6.- Tokyo.- 1979.- p. 586-588.

94. Moldovan D.I. A Model for Parallel Processing of Production Systems /D.I. Moldovan //Syst., Man. and Cybern.- Atlanta, Ca.- 1986.- V. 1.

95. Motoda H. Second-generation expert systems /Н. Motoda //IEEE Expert.- 1994 9.- №2.- p. 66-76.

96. Newell A. Human problem solving /А. Newell, M. Simon //NJ: Prentice-Hall.- 1972.

97. Post E. Formal reduction of the general combinatorial /Е. Post //American J. Math.- 1943.

98. Preece A. Principles and practice in verifying rule-based systems /А. Preece, R. Shinghal, A. Batarekh // Knowl. Eng. Rev.- 1992 7,- №2,- p. 115-141.

99. Real-Time Fault Diagnostics /S. Padalkar, G. Karsat, C. Biegl, J. Sztipanovits /ЛЕЕЕ Expert.- vol. 6, №3.-1991.- p. 75-84.

100. SCADA система GENESIS 32 в вопросах и ответах /Приборы и системы. Управление, контроль, диагностика.- 2001.- №2.- С. 11-14.

101. Setnes М. Rule base reduction: some comments on the use of orthogonal transforms /М. Setnes R. Babuska // IEEE Trans. Syst., Man, and Gybern. C.- 2001 31.- №2.- p. 199-206.

102. Song Z. Research efforts to improve perfomarce of production systems /Z. Song, L. Li // J. Harbin Inst. Techn.- 2001 8.- №2.- p. 188-190.

103. Suwa H. An approach to veryfing Consistency and Completeness in a Rule-Based Expert System /Н. Suwa, A. Scott // Rule-Based Expert Systems.-London: Addison-Wesley, 1984.-p. 159-170.

104. Weiss S.M. A Practikal Guide to Pesigning Expert systems / S.M. Weiss, C.A. Kulikowski.- Totowa, NJ, Rowman & Allanheld.- 1984.183 p.