Методы и программные средства представления знаний на основе нечетких таблиц решений и их применение в интеллектуальных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Виноградов, Олег Вячеславович

• Виноградов, Олег Вячеславович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Виноградов, Олег Вячеславович

ОГЛАВЛЕНИЕ.

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. Табличные модели представления знаний в интеллектуальных системах поддержки принятия решений.

1.1. История и области применения табличных моделей.

1.2. Структура табличных моделей.

1.3. Задачи анализа табличных моделей.

1.3.1. Корректность TP.

1.3.2. Минимизация TP.

1.4. Принятие решений по табличным моделям.

1.5. Расширенные табличные модели.

1.6. Программные средства обработки табличных моделей.

1.7. Табличные модели в контексте СППР.

1.8. Выводы по главе 1.

ГЛАВА 2. Нечёткие таблицы решений.

2.1. Структура нечётких таблиц решений.

2.2. Корректность нечётких таблиц решений.

2.2.1. Свойства полноты и непротиворечивости.

2.2.2. Выделение области семантически допустимых ситуаций.

2.3. Принятие решений на основе нечётких таблиц решений.

2.3.1. Базовая схема вывода.

2.3.2. Вычисление значений условных атрибутов.

2.3.3. Агрегирование условий.

2.3.4. Активация заключений правил.

2.3.5. Аккумуляция и дефаззификация.

2.3.6. Активация правила «Иначе».

2.3.7. Деревья активации.

2.3.8. Обобщённый алгоритм принятия решений по НТР.

2.4. Выводы по главе 2.

ГЛАВА 3. Методы и алгоритмы обработки НТР.

3.1. Переборный метод проверки корректности НТР.

3.2. Матричный метод проверки корректности НТР.

3.2.1. Матричная формулировка непротиворечивости НТР.

3.2.2. Проверка аномалий коэффициентов уверенности правил.

3.3. Метод кардинальных чисел.

3.3.1. Базовый метод.

3.3.2. Модифицированная проверка полноты НТР.

3.3.3. Проверка избыточности НТР.

3.4. Логические методы.

3.4.1. Оптимизация НТР на основе ФАЛ.

3.4.2. Проверка полноты НТР как задача логического вывода.

3.5. Аппарат приближённых множеств.

3.5.1. Основные понятия приближённых множеств.

3.5.2. Построение НТР по неполным и противоречивым данным.

3.5.3. НТР как решающая система.

3.5.4. Отношение неразличимости для НТР.

3.5.5. Матрицы и функции различимости для НТР.

3.5.6. Проверка непротиворечивости НТР.

3.5.7. Редукция условий в НТР.

3.5.8. Оптимизация правил в НТР.

3.6. Выводы по главе 3.

ГЛАВА 4. Практическое применение НТР.

4.1. Методика н сценарий применения НТР.

4.2. Структура мультитабличной модели НТР.

4.3. Программная реализации модулей работы с НТР.

4.3.1. Общая архитектура системы.

4.3.2. Среда редактирования НТР СИМПР-Fuzzy.

4.4. Диспетчеризация лотов на производстве чипов.

4.4.1. Организация полупроводникового производства.

4.4.2. Методы решения задачи диспетчеризации лотов.

4.5. Контроллер диспетчеризации лотов на основе НТР.

4.5.1. Структура программного комплекса.

4.5.2. Описание НТР диспетчеризации.

4.5.3. Результаты экспериментов.

4.6. Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Методы и программные средства представления знаний на основе нечетких таблиц решений и их применение в интеллектуальных системах»

В диссертационной работе исследованы, разработаны и реализованы модели, методы и программные средства принятия решений на основе табличных моделей представления знаний (МПЗ) для интеллектуальных систем (ИС) типа ИС поддержки принятия решений (ИСППР) [1-3]. Полученные результатов использованы для разработки архитектуры и программной реализации системы представления знаний и поиска решений на основе аппарата нечётких таблиц решений (НТР), ориентированной на использование в составе современных ИС, в том числе и ИСППР реального времени (РВ). Реализованная подсистема применена в рамках прототипа ИСППР для управления микроэлектронным производством [4].

Актуальность темы исследования.

ИСППР представляют собой программные комплексы, предназначенные для помощи лицам, принимающим решения (ЛПР), в оперативном управлении сложными системами. Необходимость внедрения ИСППР РВ обуславливается возрастающей сложностью управляемых объектов и процессов с одновременным сокращением времени, отводимого ЛПР на анализ проблемной ситуации и принятие решений. Характерной особенностью ИСППР РВ является возможность работы в динамических проблемных областях, где требуется наличие возможности быстрой подстройки модели знаний под меняющиеся условия предметной области [5, 6]. Создание современных ИСППР требует применения различных МПЗ, обладающих сбалансированными характеристиками по выразительности их языка с одной стороны и приемлемой вычислительной сложностью использования с другой стороны [7, 8]. К МПЗ предъявляется широкий спектр требований, включающий возможности декларативного задания с использованием средств визуального конструирования, поддержку разнородных входных и выходных параметров (атрибутов), возможности верификации и оптимизации модели, способность функционировать при наличии разного рода неопределённости как в исходной информации, поступающей от внешнего объекта и среды, так и в экспертных знаниях и наличие эффективных алгоритмов принятия решений по модели.

Существует достаточно большое количество различных классов моделей представления знаний и подходов к их формализации [9]: методы классической математической логики (высказываний и первого порядка), методы на основе нетрадиционных логик (темпоральных, абдуктивных, индуктивных, нечетких, аргументации), на основе аналогий, приближенных множеств и др. [10-17]. В плане ускорения процессов обработки знаний и поиска решений на их основе широко исследуются и применяются методы параллельной обработки информации [18-20]. Табличные модели являются удобной моделью представления экспертных знаний для использования в ИСППР РВ. Язык таблиц решений (TP) относится к классу формальных языков, характеризующихся непроцедурной и наглядной формой описания задачи (процесса принятия решений), а также возможностью автоматизации процессов проверки корректности (полноты, непротиворечивости, неизбыточности), оптимизации и трансляции табличной модели в программы поиска решения [21-24]. TP получили широкое распространение при автоматизации процессов принятия решений, проектирования, диагностики и контроля, в имитационном моделировании. Однако расширения базового языка TP, позволяющие использовать в табличных моделях нечёткую и т.н. плохоопределённую информацию (например, правдоподобные решающие правила), что крайне желательно для применение табличных МПЗ в динамических проблемных областях, на данный момент недостаточно развиты [25, 26]. Практическое использование табличных моделей сопряжено с различными задачами их обработки, в том числе с проверкой определённых свойств TP и с оптимизацией по различным критериям. Такого рода обработка требуется не только при первичной разработке ИСППР, но и при её последующей динамической модификации [27, 28]. В связи с этим возникает необходимость исследования и разработки методов принятия решений на основе табличных МПЗ, охватывающих все этапы обработки табличной модели: от первоначальной формализации до перевода в исполняемую форму в рамках ИСППР на основе современных программных средств.

Потребность в мощных ИСППР, равно как и в системах прямого интеллектуального управления технологическими объектами крайне высока [29]. Она обусловлена растущим уровнем автоматизации и скоростью протекания контролируемых и управляемых процессов, их увеличивающейся сложностью и высоким уровнем ответственности за принимаемые решения. Ошибки в управлении производственным цехом обходятся в миллионы рублей, простои оборудования и срывы заказов. Ошибки в системах управления транспортом способны привести к человеческим жертвам. В ситуациях же управления жизненно-критическими системами (например, объектами энергетики) количество жертв может быть значительно выше, не говоря уже о потенциальном ущербе для окружающей среды. Эти факторы обуславливают такие приведённые выше требования к интеллектуальным системам, основанным на знаниях (СОЗ), как их верифицируемость и быстродействие [2, 3, 30]. Необходимо учитывать также, что развитые мировые коммерческие средства проектирования экспертных систем и ИСППР РВ (например, G2 компании Gensym, RTWorlcs компании Talarian и др.) имеют очень высокую стоимость, что практически исключает их использование на отечественном рынке [5].

Актуальность исследования обусловлена тем, что в настоящее время существует разрыв между потенциалом табличных МПЗ, современными математическими средствами манипулирования нечёткой и плохоопределённой информацией и инструментальными средствами обработки табличных моделей для ИСППР РВ. Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС (ИСППР) отечественных ученых Д.А. Поспелова, А.Н. Аверкина, Р.А. Алиева, А.А. Башлыкова, В.Н. Вагина, В.В. Емельянова, А.П. Еремеева, О.И. Ларичева, О.П. Кузнецова, В.М. Курейчика, А.С. Нариньяни, Н.Н. Непейвода, Г.С. Осипова, А.Б. Петровского, Г.С. Плесне-вича, В.Э. Попова, Г.В. Рыбиной, В.А. Смирнова, В.Л. Стефанюка, В.Б. Тарасова, В.К. Финна, И.Б. Фоминых, В.Ф. Хорошевского, А.И. Эрлиха и др., а также зарубежных ученых В. Clayton, С. Forgy, J.С. Giarratano, R. Gupta, R. Irrgang, P. Jackson, J. Haley, J. Komorowski, A. Lig^za, M. Minsky, N.J. Nilsson, P. Norvig, Z. Pawlak, L. Polkowski, J.R. Quinlan, J.A. Robinson, G. Riley, S. Russell, A. Skowron, M. Sugeno, Y. Tsukamoto, J. Vanthienen, L.A. Zadeh и др.

Объектом исследования являются модели и методы табличного представления знаний на основе нечётких таблиц решений (НТР). Предмет исследования составляют методы обработки НТР в плане их использования в ИС типа ИСППР РВ.

Целью работы является разработка методов и программных средств представления знаний на основе НТР, расширяющих возможности современных ИС типа ИСППР РВ средствами оперирования нечёткой и плохоопреде-лённой информацией.

Для достижения указанной цели необходимо решить следующие задачи:

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

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

- разработка архитектуры и сценариев применения программных средств на основе НТР для использования в ИСППР РВ, включающих средства редактирования, контроля корректности, минимизации и отладки табличных моделей;

- использование разработанных методов и программных средств в прототипе ИСППР РВ для решения задачи диспетчеризации лотов на производстве микроэлектронных компонентов.

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

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

Научная новизна исследования состоит в следующем:

- предложен аппарат представления знаний на основе НТР, расширяющий классические TP средствами оперирования с нечёткой и плохоопределённой информацией;

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

- предложены алгоритмы и методы анализа свойств и минимизации НТР;

- разработана архитектура и программные средства представления знаний на основе НТР для ИСППР РВ.

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

Практическая значимость работы подтверждается использованием разработанных программных средств в прототипе ИСППР РВ для управления производством микроэлектронных компонент, реализованным на кафедре Прикладной математики МЭИ (ТУ) в сотрудничестве с Дрезденским техническим университетом (ДТУ), а также в других задачах, о чем имеются акты о внедрении (см. приложение 12).

Реализация результатов. Разработанная система поиска решений на основе НТР использована в совместном исследовательском проекте МЭИ (ТУ) с ДТУ по снижению длительности производственного цикла полупроводниковых устройств, а также в учебно-научном процессе МЭИ (ТУ), что подтверждается соответствующими актами о внедрении. В результате применения результатов исследований удалось добиться существенного уменьшения длительности производственного цикла лотов (до 10% по показателю 95%-го квантиля эмпирического распределения) и до 30% сокращения доли опаздывающих лотов по сравнению с базовыми стратегиями диспетчеризации.

Результаты работы использованы в НИР, выполняемых в рамках грантов РФФИ: проект №02-07-90042 «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» (науч. рук.: д.т.н., проф. Вагин В.Н., д.т.н., проф. Еремеев А.П.); проект №05-07-90232 «Исследование и разработка инструментальных средств создания экспертных систем поддержки принятия решений» (науч. рук.: д.т.н., проф. Вагин В.Н., д.т.н., проф. Еремеев А.П.), № 08-01-00437 «Модели и методы поиска решения на основе экспертных знаний в интеллектуальных системах поддержки принятия решений» (науч. рук. Еремеев А.П.), в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. (гос. контракт от 1.02.2002 г. №37.011.11.0021 и дополнительное соглашение от 18 августа 2004 г. №5; раздел «Информационно-телекоммуникационные технологии и электроника», подраздел «Информационные технологии») по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик» (науч. рук. д.т.н., проф. Еремеев А.П.), а также в рамках Аналитической ведомственной целевой программы Рособразования «Развитие научного потенциала высшей школы (2006-2008 годы)» (направление №2.2.2.3 «Развитие научной и академической мобильности в рамках международного сотрудничества», проект № 10074) по теме «Исследование и разработка методов принятия решений на основе табличных моделей представления знаний для интеллектуальных систем поддержки принятия решений реального времени» (рук., отв. исп. асп. Виноградов О.В.).

Программная реализация подсистемы принятия решений на основе НТР для ИСППР РВ зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (свидетельство №2009612313 от 07.05.2009 г.).

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях студентов и аспирантов «Радиотехника, электроника и энергетика» (г. Москва, 2002-2009 гг.), на «Научных сессиях МИФИ» (г. Москва, 2004-2007 гг.), Международных научно-технических конференциях «Информационные средства и технологии» (г. Москва, 2002-2008 гг.), на Международных студенческих школах-семинарах «Новые информационные технологии» (г. Судак, 2006-2009 гг.), на 4-й международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007 г.), на Национальных конференциях по искусственному интеллекту с международным участием КИИ (2004-2008 гг.) и на 2-й Всероссийской научной конференции «Нечёткие системы и мягкие вычисления» (г. Ульяновск, 2008 г.).

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 28 печатных работах, включая 2 работы в изданиях, рекомендуемых ВАК.

Структура и объем работы. Диссертация содержит 174 листа машинописного текста, состоит из введения, четырех глав, заключения, списка использованной литературы (173 наименования) и 12 приложений.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Виноградов, Олег Вячеславович

Основные результаты диссертационной работы:

1. Проведено исследование существующих табличных моделей представления знаний и методов принятия решений на их основе. Описана базовая структура табличной модели в виде расширяемой TP и показано, что для применения в контексте ИСППР РВ целесообразно дополнить её средствами обработки нечётких и плохоформализованных знаний.

2. Разработан аппарат НТР, введены две эквивалентные формы представления НТР: на 'основе обобщённой решающей функции и на основе матриц. Показано, что НТР являются обобщением классических TP на случай вещественных и нечётких входов и выходов и правдоподобных решающих правил.

3. Исследовано свойство корректности (полноты, непротиворечивости) НТР с выделением сильного и слабого вариантов свойства. На основе выделения множества допустимых векторов значений условных атрибутов введены понятия синтаксической и семантической корректности НТР.

4. Предложена схема принятия решений на основе НТР, являющаяся обобщением схемы нечёткого вывода Цукамото на случай немонотонных функций принадлежности. Введены ДА для отбора активных правил в НТР. Приведены обобщённые алгоритмы построения ДА и принятия решений по НТР как при наличии, так и при отсутствии ДА.

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

6. Предложена модификация метода на основе приближённых множеств для обработки НТР, в том числе введены нечёткое отношение неразличимости правил и модифицированные матрицы и функции различимости правил.

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

8. Предложена методика построения и сценарии использования НТР в ИСППР, включая ИСППР РВ.

9. Выполнена программная реализация модульной системы представления знаний и поиска решений на основе НТР и приближённых множеств. В системе выделены универсальные встраиваемые модули и развитые средства визуального редактирования и анализа моделей.

10.Рассмотрено применение разработанных программных средств в составе прототипа ИСППР РВ для решения задачи диспетчеризации лотов на производстве микроэлектронных компонентов. Разработанный нечёткий контроллер диспетчеризации успешно использован в рамках проекта Дрезденского ТУ и МЭИ (ТУ) по снижению времени производственного цикла лотов, о чём получен акт о внедрении. Результаты работы также использованы в научно-учебном процессе кафедры Прикладной математики МЭИ (ТУ).

Основные направления дальнейших исследований:

- Исследование алгоритмов построения субоптимальных деревьев активации по заданным НТР.

- Разработка алгоритмов анализа и оптимизации не отдельных НТР, а мультитабличных моделей в целом.

- Исследование перспектив применения расширенных TP, семантических TP и темпоральных TP для повышения интеллектуальных способностей ИСППР РВ.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Виноградов, Олег Вячеславович, 2009 год

1. Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Известия РАН. Теория и системы управления, №6, 2001, с. 114-123.

2. Еремеев А.П. Экспертные модели и методы принятия решений. М.: Изд. МЭИ, 1995.

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

4. Осипов Г.С. Приобретение знаний интеллектуальными системами: Основы техники и технологии. -М.: Наука. Физматлит, 1997.

5. Вагин В.Н. Знание в интеллектуальных системах // Новости искусственного интеллекта, 2002, №6, с. 8-18.

6. Еремеев А.П. Об интеграции моделей в интеллектуальных системах поддержки принятия решений // Девятая национальная конференция по искусственному интеллекту с международным участием КИИ-2004: Тр. конф. В 3-х т. Т.2. М.: Физматлит, 2004, с. 815-823.

7. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. -СПб.: Питер, 2000.

8. Вагин В.Н., Куликов А.В., Фомина М.В. Методы теории приближённых множеств в решении задачи обобщения понятий // Известия РАН. Теория и системы управления, №6, 2004, с. 52-66.

9. Вагин В.Н., Загорянская А.А. Организация абдуктивного вывода средствами теории аргументации / Коллективная монография «Интеллектуальные системы». Под ред. В.М. Курейчика. М.: Физматлит, 2005, стр. 129143.

10. Вагин В.Н., Головина Е.Ю., Загорянская АА., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах / Под ред. Вагина В.Н., Поспелова Д.А. М.: Физматлит, 2008.

11. Варшавский П.Р., Еремеев А.П. Поиск решения на основе структурной аналогии для интеллектуальных систем поддержки принятия решений // Известия РАН. Теория и системы управления, 2005, № 1, с. 97-109.

12. Еремеев А.П., Троицкий В.В\ Темпоральные рассуждения в интеллектуальных системах поддержки принятия решений / Коллективная монография «Интеллектуальные системы». Под ред. В.М. Курейчика. Москва: Физматлит, 2005, стр. 169-180.

13. Поспелов Д.А. Логико-лингвистические модели в системах управления и искусственного интеллекта. М.: Наука. Гл. ред. физ.-мат. лит., 1981.

14. Трахтенгерц Э.А. Компьютерная поддержка принятия решений // Научно-практическое издание. М.: Синтег, 1998.

15. Плесневич Г.С. Силлогистики для семантических сетей // 10-я национальная конференция по искусственному интеллекту с международным участием КИИ-2006: Труды конференции. В. 3-х т., Т. 1. -М: Физматлит, 2006, с. 321-330.

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

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

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

19. Еремеев А.П. О корректности модели представления знаний для экспертных систем поддержки принятия решений // Известия РАН. Техническая кибернетика, №5, 1993, с. 45-53.

20. Еремеев А.П. О корректности продукционной модели принятия решений на основе таблиц решений // Автоматика и Телемеханика, №10, 2001, с. 78-90.25