Содержание к диссертации
ОГЛАВЛЕНИЕ 2
СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ. 4
ВВЕДЕНИЕ 5
ГЛАВА 1. Табличные модели представления знаний в интеллектуальных системах
поддержки принятия решений 13
История и области применения табличных моделей 13
Структура табличных моделей 19
Задачи анализа табличных моделей 25
Корректность ТР 25
Минимизация ТР 27
Принятие решений по табличным моделям 28
Расширенные табличные модели 31
Программные средства обработки табличных моделей 37
Табличные модели в контексте СППР 40
Выводы по главе 1 43
ГЛАВА 2. Нечёткие таблицы решений 44
Структура нечётких таблиц решений .44
Корректность нечётких таблиц решений 55
Свойства полноты и непротиворечивости 55
Выделение области семантически допустимых ситуаций 57
2.3. Принятие решений на основе нечётких таблиц решений 62
Базовая схема вывода 62
Вычисление значений условных атрибутов 65
Агрегирование условий 65
Активация заключений правил 67
Аккумуляция и дефаззификация 70
Активация правила «Иначе» 72
Деревья активации 76
Обобщённый алгоритм принятия решений по НТР 84
2.4. Выводы по главе 2 86
ГЛАВА 3. Методы и алгоритмы обработки НТР 87
Переборный метод проверки корректности НТР 87
Матричный метод проверки корректности НТР 89
Матричная формулировка непротиворечивости НТР 89
Проверка аномалий коэффициентов уверенности правил 92
3.3. Метод кардинальных чисел 93
Базовый метод 93
Модифицированная проверка полноты НТР 97
Проверка избыточности НТР 98
3.4. Логические методы 98
Оптимизация НТР на основе ФАЛ 98
Проверка полноты НТР как задача логического вывода 100
3.5. Аппарат приближённых множеств 100
Основные понятия приближённых множеств 100
Построение НТР по неполным и противоречивым данным 105
НТР как решающая система 111
Отношение неразличимости для НТР 113
Матрицы и функции различимости для НТР 1 ] 5
Проверка непротиворечивости НТР 120
Редукция условий в НТР 123
Оптимизация правил в НТР 127
3.6. Выводы по главе 3 130
ГЛАВА 4. Практическое применение НТР 131
Методика и сценарий применения НТР 131
Структура мультитабличной модели НТР 133
Программная реализации модулей работы с НТР 135
Общая архитектура системы 135
Среда редактирования НТР СИМПР-Fuzzy 140
4.4. Диспетчеризация лотов на производстве чипов 143
Организация полупроводникового производства 143
Методы решения задачи диспетчеризации лотов 149
4.5. Контроллер диспетчеризации лотов на основе НТР 151
Структура программного комплекса 152
Описание НТР диспетчеризации 154
Результаты экспериментов 156
4.6. Выводы по главе 4 159
ЗАКЛЮЧЕНИЕ. 160
СПИСОК ЛИТЕРАТУРЫ. 162
ПРИЛОЖЕНИЯ 175
Приложение 1. Обзор эволюции программных средств поддержки табличных МПЗ 175
Приложение 2. Иерархия отношений на множестве правил Rules в НТР 186
Приложение 3. Доказательства утверждений из главы 2 187
Приложение 4. Описание XSD-схемы представлении мультитабличной .модели 190
Приложение 5. Организация модульного тестирования кода 202
Приложение 6. Программная модель компонента Decider 204
Приложение 7. Описание среды СИМПР-Fuzzy 209
Приложение 8. Обзор комбинированных методов диспетчеризации лотов 212
Приложение 9. Описание программной среды контроллера диспетчеризации 215
Приложение 10. XML-представление модели диспетчеризации 222
Приложение 11. Результаты имитационного моделирования 229
Приложение 12. Акты о результатах внедрения диссертационной работы 243
СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ
Введение к работе
В диссертационной работе исследованы, разработаны и реализованы модели, методы и программные средства принятия решений на основе табличных моделей представления знаний (МПЗ) для интеллектуальных систем (ИС) типа ИС поддержки принятия решений (ИСППР) [1-3]. Полученные результатов использованы для разработки архитектуры и программной реализации системы представления знаний и поиска решений на основе аппарата нечётких таблиц решений (НТР), ориентированной на использование в составе современных ИС, в том числе и ИСППР реального времени (РВ). Реализованная подсистема применена в рамках прототипа ИСППР для управления микроэлектронным производством [4].
Актуальность темы исследования.
ИСППР представляют собой программные комплексы, предназначенные для помощи лицам, принимающим решения (ЛПР), в оперативном управлении сложными системами. Необходимость внедрения ИСППР РВ обуславливается возрастающей сложностью управляемых объектов и процессов с одновременным сокращением времени, отводимого ЛПР на анализ проблемной ситуации и принятие решений. Характерной особенностью ИСППР РВ является возможность работы в динамических проблемных областях, где требуется наличие возможности быстрой подстройки модели знаний под меняющиеся условия предметной области [5, 6]. Создание современных ИСППР требует применения различных МПЗ, обладающих сбалансированными характеристиками по выразительности их языка с одной стороны и приемлемой вычислительной сложностью использования с другой стороны [7, 8]. К МПЗ предъявляется широкий спектр требований, включающий возможности декларативного задания с использованием средств визуального конструирования, поддержку разнородных входных и выходных параметров (атрибутов), возможности верификации и оптимизации модели, способность функционировать при наличии разного рода неопределённости как в исходной информации, поступающей от внешнего объ-
екта и среды, так и в экспертных знаниях и наличие эффективных алгоритмов принятия решений по модели.
Существует достаточно большое количество различных классов моделей представления знаний и подходов к их формализации [9]: методы классической математической логики (высказываний и первого порядка), методы на основе нетрадиционных логик (темпоральных, абдуктивных, индуктивных, нечетких, аргументации), на основе аналогий, приближенных множеств и др. [10-17]. В плане ускорения процессов обработки знаний и поиска решений на их основе широко исследуются и применяются методы параллельной обработки информации [18-20]. Табличные модели являются удобной моделью представления экспертных знаний для использования в ИСППР РВ. Язык таблиц решений (ТР) относится к классу формальных языков, характеризующихся непроцедурной и наглядной формой описания задачи (процесса принятия решений), а также возможностью автоматизации процессов проверки корректности (полноты, непротиворечивости, неизбыточности), оптимизации и трансляции табличной модели в программы поиска решения [21-24]. ТР получили широкое распространение при автоматизации процессов принятия решений, проектирования, диагностики и контроля, в имитационном моделировании. Однако расширения базового языка ТР, позволяющие использовать в табличных моделях нечёткую и т.н. плохоопределённую информацию (например, правдоподобные решающие правила), что крайне желательно для применение табличных МПЗ в динамических проблемных областях, на данный момент недостаточно развиты [25, 26]. Практическое использование табличных моделей сопряжено с различными задачами их обработки, в том числе с проверкой определённых свойств ТР и с оптимизацией по различным критериям. Такого рода обработка требуется не только при первичной разработке ИСППР, но и при её последующей динамической модификации [27, 28]. В связи с этим возникает необходимость исследования и разработки методов принятия решений на основе табличных МПЗ, охватывающих все этапы обработки табличной модели: от первоначальной формализации до
7 перевода в исполняемую форму в рамках ИСППР на основе современных программных средств.
Потребность в мощных ИСППР, равно как и в системах прямого интеллектуального управления технологическими объектами крайне высока [29]. Она обусловлена растущим уровнем автоматизации и скоростью протекания контролируемых и управляемых процессов, их увеличивающейся сложностью и высоким уровнем ответственности за принимаемые решения. Ошибки в управлении производственным цехом обходятся в миллионы рублей, простои оборудования и срывы заказов. Ошибки в системах управления транспортом способны привести к человеческим жертвам. В ситуациях же управления жизненно-критическими системами (например, объектами энергетики) количество жертв может быть значительно выше, не говоря уже о потенциальном ущербе для окружающей среды. Эти факторы обуславливают такие приведённые выше требования к интеллектуальным системам, основанным на знаниях (СОЗ), как их верифицируемость и быстродействие [2, 3, 30]. Необходимо учитывать также, что развитые мировые коммерческие средства проектирования экспертных систем и ИСППР РВ (например, G2 компании Gensym, RTWorks компании Talarian и др.) имеют очень высокую стоимость, что практически исключает их использование на отечественном рынке [5].
Актуальность исследования обусловлена тем, что в настоящее время существует разрыв между потенциалом табличных МПЗ, современными математическими средствами манипулирования нечёткой и плохоопределённой информацией и инструментальными средствами обработки табличных моделей для ИСППР РВ. Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС (ИСППР) отечественных ученых Д.А. Поспелова, А.Н. Аверкина, Р.А. Алиева, А.А. Башлыкова, В.Н. Вагина, В.В. Емельянова, А.П. Еремеева, О.И. Ларичева, О.П. Кузнецова, В.М. Курейчика, А.С. Нариньяни, Н.Н. Непейвода, Г.С. Осипова, А.Б. Петровского, Г.С. Плесне-вича, В.Э. Попова, Г.В. Рыбиной, В.А. Смирнова, В.Л. Стефанюка, В.Б. Тарасова, В.К. Финна, И.Б. Фоминых, В.Ф. Хорошевского, А.И. Эрлиха и др., а также
8 зарубежных ученых В. Clayton, С. Forgy, J.С. GiaiTatano, R. Gupta, R. Irrgang, P. Jackson, J. Haley, J. Komorowski, A. Ligejza, 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 и др.
Объектом исследования являются модели и методы табличного представления знаний на основе нечётких таблиц решений (НТР). Предмет исследования составляют методы обработки НТР в плане их использования в ИС типаИСППРРВ.
Целью работы является разработка методов и программных средств представления знаний на основе НТР, расширяющих возможности современных ИС типа ИОД IP РВ средствами оперирования нечёткой и плохоопреде-лённой информацией.
Для достижения указанной цели необходимо решить следующие задачи:
исследование моделей и методов принятия решений на основе табличных МПЗ, выявление недостатков существующих моделей, выбор базовой модели для последующего расширения;
формальное описание аппарата НТР и схемы поиска решений на его основе, разработка методов и алгоритмов контроля корректности и минимизации табличных моделей;
разработка архитектуры и сценариев применения программных средств на основе НТР для использования в ИСППР РВ, включающих средства редактирования, контроля корректности, минимизации и отладки табличных моделей;
использование разработанных методов и программных средств в прототипе ИСППР РВ для решения задачи диспетчеризации лотов на производстве микроэлектронных компонентов.
Методы исследования. Поставленные задачи решаются с использованием методов дискретной математики, математической логики, искусственного интеллекта, теории графов, нечёткой логики, теории приближённых множеств и методов анализа вычислительной сложности алгоритмов.
9 Достоверность научных положений. Достоверность научных положений подтверждена теоретическими выкладками, результатами тестирования, данными имитационного моделирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе. Научная новизна исследования состоит в следующем:
предложен аппарат представления знаний на основе НТР, расширяющий классические ТР средствами оперирования с нечёткой и плохоопределённой информацией;
предложены алгоритмы поиска решений на основе НТР, использующие для ускорения отбора активных правил деревья активации, являющиеся обобщением деревьев решений на случай НТР;
предложены алгоритмы и методы анализа свойств и минимизации НТР;
разработана архитектура и программные средства представления знаний на основе НТР для ИСПТТР РВ.
Практическая значимость работы заключается в создании базового программного обеспечения для ИСГПТР РВ на основе аппарата НТР, повышающего эффективность и расширяющего интеллектуальные возможности современных компьютеров и компьютерных систем.
Практическая значимость работы подтверждается использованием разработанных программных средств в прототипе ИСППР РВ для управления производством микроэлектронных компонент, реализованным на кафедре Прикладной математики МЭИ (ТУ) в сотрудничестве с Дрезденским техническим университетом (ДТУ), а также в других задачах, о чем имеются акты о внедрении (см. приложение 12).
Реализация результатов. Разработанная система поиска решений на основе НТР использована в совместном исследовательском проекте МЭИ (ТУ) с ДТУ по снижению длительности производственного цикла полупроводниковых устройств, а также в учебно-научном процессе МЭИ (ТУ), что подтверждается соответствующими актами о внедрении. В результате применения результатов
10 исследований удалось добиться существенного уменьшения длительности производственного цикла лотов (до 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) по теме «Исследование и разработка методов принятия решений на основе табличных моделей представления знаний для интеллектуальных систем поддержки принятия решений реального времени» (рук., отв. исп. асп. Виноградов О.В.).
Программная реализация подсистемы принятия решений на основе НТР для ИСППР РВ зарегистрирована в Федеральной службе по интеллектуальной
11 собственности, патентам и товарным знакам (свидетельство №2009612313 от 07.05.2009 г.).
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях студентов и аспирантов «Радиотехника, электроника и энергетика» (г. Москва, 2002-2009 гг.), на «Научных сессиях МИФИ» (г. Москва, 2004-2007 гг.), Международных научно-технических конференциях «Информационные средства и технологии» (г. Москва, 2002-2008 гг.), на Международных студенческих школах-семинарах «Новые информационные технологии» (г. Судак, 2006-2009 гг.), на 4-й международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007 г.), на Национальных конференциях по искусственному интеллекту с международным участием КИИ (2004-2008 гг.) и на 2-й Всероссийской научной конференции «Нечёткие системы и мягкие вычисления» (г. Ульяновск, 2008 г.).
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 28 печатных работах, включая 2 работы в изданиях, рекомендуемых ВАК.
Структура и объем работы. Диссертация содержит 174 листа машинописного текста, состоит из введения, четырех глав, заключения, списка использованной литературы (173 наименования) и 12 приложений.
Краткий обзор содержания работы.
В первой главе дается обзор табличных моделей представления знаний, применяемых в различных ИС, включая ИСППР РВ. Выделяется базовая структура ТР, рассматриваются её свойства и методы поиска решений по ней. Описываются возможные дополнения базовой модели, указываются их недостатки в плане использования в ИСППР РВ. Рассматриваются существующие программные реализации табличных моделей. Делается вывод о важности расширения табличных моделей средствами обработки нечёткой и плохоопределён-ной информации и их программной реализации для применения в ИСППР РВ.
12 Во второй главе вводится формальное описание табличных МПЗ, базирующихся на классических ТР и способных работать как с дискретными, так и с непрерывными и нечёткими входами и выходами (нечёткие таблицы решений, НТР). Для НТР вводятся свойства полноты, непротиворечивости и корректности относительно заданного множества входных векторов. Описывается схема принятия решений по НТР, являющаяся обобщением схемы нечёткого вывода Цукамото, для правила «Иначе» рассматриваются различные критерии активации. В заключение главы вводится аппарат деревьев активации для ускорения отбора активных правил в НТР, и приводятся описания алгоритмов.
В третьей главе рассматриваются методы и алгоритмы проверки свойств и минимизации НТР. Описываются подходы на основе матричных операций, метода кардинальных чисел, логические методы. Особо рассматривается применение аппарата приближённых множеств к обработке НТР. Для этого вводится нечёткое отношение неразличимости правил и переопределяются понятия матриц и функций различимости по сравнению с базовой теорией приближённых множеств. На основании введённых понятий предлагаются новые алгоритмы минимизации и верификации НТР.
Четвертая глава посвящена прикладным вопросам применения аппарата НТР. В ней вводится архитектура подсистемы принятия решений на основе НТР, описывается сценарий её применения и функциональные возможности. Описываются особенности программной реализации подсистемы. Рассматривается практическое применение разработанных методов и программных средств в ИСППР РВ для управления производством микроэлектронных компонентов на примере задачи диспетчеризации лотов в рамках проекта по снижению длительности производственного цикла полупроводниковых устройств, реализованного на базе ДТУ.
