В диссертационной работе исследованы, разработаны и реализованы модели, методы и программные средства принятия решений на основе табличных моделей представления знаний (МПЗ) для интеллектуальных систем (ИС) типа ИС поддержки принятия решений (ИСППР) [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−90 042 «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» (науч. рук.: д.т.н., проф. Вагин В. Н., д.т.н., проф. Еремеев А.П.) — проект № 05−07−90 232 «Исследование и разработка инструментальных средств создания экспертных систем поддержки принятия решений» (науч. рук.: д.т.н., проф. Вагин В. Н., д.т.н., проф. Еремеев А.П.), № 08−01−437 «Модели и методы поиска решения на основе экспертных знаний в интеллектуальных системах поддержки принятия решений» (науч. рук. Еремеев А.П.), в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002;2006 гг. (гос. контракт от 1.02.2002 г. № 37.011.11.0021 и дополнительное соглашение от 18 августа 2004 г. № 5- раздел «Информационно-телекоммуникационные технологии и электроника», подраздел «Информационные технологии») по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик» (науч. рук. д.т.н., проф. Еремеев А.П.), а также в рамках Аналитической ведомственной целевой программы Рособразования «Развитие научного потенциала высшей школы (2006;2008 годы)» (направление № 2.2.2.3 «Развитие научной и академической мобильности в рамках международного сотрудничества», проект № 10 074) по теме «Исследование и разработка методов принятия решений на основе табличных моделей представления знаний для интеллектуальных систем поддержки принятия решений реального времени» (рук., отв. исп. асп. Виноградов О.В.).
Программная реализация подсистемы принятия решений на основе НТР для ИСППР РВ зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (свидетельство № 2 009 612 313 от 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 для повышения интеллектуальных способностей ИСППР РВ.
ЗАКЛЮЧЕНИЕ
.