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

У лек

Виноградов Олег Вячеславович

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2009

003470789

Работа выполнена в ГОУ ВПО Московском энергетическом институте (техническом университете) на кафедре Прикладной математики.

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

Александр Павлович Еремеев

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

Дзегелёнок Игорь Игоревич,

кандидат физико-математических наук, доцент Аверкин Алексей Николаевич

Ведущая организация: Институт проблем управления

Российской Академии Наук (ИПУ РАН), Москва

Защита состоится "26" июня 2009 г. в час. ¿70 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: Москва, Красноказарменная ул., д. 15, ауд. МШ-

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, Москва, Красноказарменная ул., д. 14, Ученый совет МЭИ (ТУ).

Автореферат разослан "¿{" мая 2009 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, доцент М.В. Фомина

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

Актуальность темы исследований. Создание современных интеллектуальных систем (ЙС), типичным представителем которых являются интеллектуальные системы поддержки принятия решений (ИСППР), требует применения различных моделей представления знаний (МПЗ), обладающих сбалансированными характеристиками по их выразительности и приемлемой вычислительной сложности соответствующих алгоритмов. К МПЗ предъявляется достаточно широкий набор требований, включающий возможности декларативного описания знаний с использованием средств визуального конструирования, поддержки разнородных входных и выходных параметров (атрибутов), возможности верификации и оптимизации модели, способность функционировать при наличии разного рода неопределённости как в исходной информации, поступающей от внешнего объекта и среды, так и в экспертных знаниях, и наличие эффективных алгоритмов поиска решений на основе МПЗ.

Табличные модели являются удобным средством представления экспертных знаний для использования в ИСППР, включая ИСППР реального времени (ИСППР РВ). Язык таблиц решений (TP) относится к классу формальных языков, характеризующихся непроцедурной и наглядной формой описания задачи (процесса принятия решений), а также возможностью автоматизации процессов проверки корректности (полноты, непротиворечивости, неизбыточности), оптимизации и трансляции табличной модели в программы поиска решения (см работы А.П, Еремеева и др.). TP получили широкое распространение при автоматизации процессов принятия решений, проектирования, диагностики и контроля, в имитационном моделировании и других приложениях. Однако, математические и программные расширения базового языка TP, позволяющие использовать в табличных моделях нечёткую и т.н. плохоопределённую информацию, например, правдоподобные решающие правила, что крайне желательно для применение табличных МПЗ в динамических проблемных областях, - на данный момент недостаточно развиты. Поэтому возникает необходимость исследования и разработки методов и программных средств представления знаний на основе нечётких таблиц решений (НТР) для их использования в ИСППР, включая ИСППР РВ, на всех этапах обработки НТР: от первоначальной формализации до перевода в исполняемую форму. Актуальность исследования обусловлена тем, что в настоящее время существует разрыв между потенциалом табличных МПЗ, современными математическими средствами манипулирования нечёткой и плохоопределённой информацией и инструментальными средствами обработки табличных моделей для ИСППР РВ.

Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС отечественных ученых Д.А. Поспелова, А.Н. Аверкина, P.A. Алиева, A.A. Башлыкова, В.Н. Вагина, В.В. Емельянова, А.П. Еремеева, О.И. Ларичева, О.П. Кузнецова, В.М. Курейчика, A.C. Нариньяни, H.H. Непей-вода, Г.С. Осшюва, А.Б. Петровского, Г.С. Плесневича, Э.В. Попова, Г.В. Рыбиной, В .А. Смирнова, В.Л. Стефанкжа, В.Б. Тарасова, В.К. Финна. И.Б. Фоминых, В.Ф. Хорошевского, А.И. Эрлиха и др., а также зарубежных ученых В. Clayton, С, Forgy, J.C. Giarratano. R. Gupta, R. Irrgang, P. Jackson, J. Haley, J. Ко-

Y

morowski, A. Ligcjza, 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. Tsu-kamoto, J. Vanthienen, L.A. Zadeh и др.

Объектом исследования являются модели и методы табличного представления знаний на основе НТР.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Акты о внедрении и использовании результатов работы прилагаются.

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

ным участием КИИ (2004-2008 гг.) и на 2-й Всероссийской научной конференции «Нечёткие системы и мягкие вычисления» (г. Ульяновск, 2008 г.).

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

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

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

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

В первой главе приводится обзор табличных моделей представления знаний на основе ТР, применяемых в различных ИС, включая ИСППР. Впервые табличные формы как средство описания логики программ были предложены б 1957 году в ходе совместного проекта компаний General Electric, Sutherland Corporation и ВВС США по разработке системы хранения данных. Первоначально ТР использовались только как средство визуального представления логики и для автоматической генерации заготовок программного кода по табличной модели. Начиная с 1965 года, стали массово появляться прикладные системы на основе ТР, вскоре были приняты меры по стандартизации обозначений и методов обработки табличных моделей: появились стандарты Канадской ассоциации стандартов (1970 г.), европейский стандарт DIN 66241 (1979 г.) и др. Уже в 70е годы исследовалось и применение ТР для анализа, описания и документирования сложных процессов и структур, а именно: функционирования сложных прикладных программных систем, формализации баз знаний в консультирующих экспертных системах и системах поддержки принятия решений, задания логики мониторинга и управления техническими объектами и др. Со временем область применения ТР существенно расширилась, а тематика исследований сместилась в область разработки методик использования и анализа ТР для представления знаний в ИС. В конце 90-х годов наметилась новая волна интереса к табличным моделям, стали появляться новые программные системы на основе ТР. Но функциональность создаваемых систем, средства редактирования и анализа ТР во многом повторяют разработки 60-х и 70-х годов.

Рассмотрим структуру классической ТР (рис. 1) на примере базовой модели, разработанной на кафедре Прикладной математики (ПМ) МЭИ(ТУ) под руководством д.т.н., проф. Еремеева А.П.

ТР определяется набором DT = ((С,А,С',А'),В), где четвёрка (С,А,С',А') соответствует традиционному определению ТР, а компонент В является её расширением. Здесь С = {С,.}, / = 1,2,...,m, А = {л,}, .' = 1,2множества идентификаторов условий и действий соответственно, a C'=jjcJ, / = 1,2,...,m, / = 1,2,...,и, г = 1,2,...,/с, -матргты посыпок и заключений правил соответственно. Пара вектор-столбцов С', и Л',.матриц С и А', соответствующих одному значению индекса j, называется решающим правилом Rt =< С'; ,А\ >,

} -1,2,.... и; таким образом, ТР включает п решающих правил.

Правило Я]~<С']ЬАУ>, называется простым, если вектор-столбец С\ не содержит символов безразличия '*', в противном случае правило называется обобщенным. Применение обобщённых правил позволяет существенно сократить число правил в ТР (так как каждое обобщённое правило представляет собой объединение нескольких простых правил), но создаёт дополнительные трудности при обработке ТР. Для реагирования на входные векторы, к которым не применимо ни одно из правил Л,в ТР может вводиться так называемое правило "Иначе" Е=<-,А'„^> с незаданной первой компонентой, представляющее собой замыкание модели, то есть средство пополнения и адаптации, обеспечивающее универсальную реакцию на неучтённые входные векторы. Вектор данных б = (*,), ¿ = 1,2,...,т, распознаётся правилом RJ (а -> ), если *'*')=> = $,)). ТР

называется непротиворечивой относительно множества векторов данных (ситуаций) 5, если (V*, -»?,,)&иначе ТР называется противоречивой относительно 5. ТР называется полной относительно множества 5, если она содержит правило «Иначе», или выполняется условие (\/$ е 53рДя? -> иначе ТР называется неполной относительно 5. ТР называется корректной относительно множества 5, если она полна и непротиворечива относительно 5. В противном случае ТР называется некорректной относительно 5. Корректность ТР относительно множества 5 (т.е. множества всех возможных состояний) называется также синтаксической корректностью, а корректность ТР относительно множества допустимых состояний 5'с 5 называется семантической корректностью. Минимизацией ТР называется построение по ТР ОТ1 =--<(с\А\С Л'^В' > новой ТР ДГ2 =<(С2,Я2,С2 ,А'г\в2 >, эквивалентной исходной по отображению (условия -> действия), но превосходящей её по некоторому критерию, как то: минимальное количество условий в ТР, минимальное число правил в ТР, минимальное среднее число учитываемых условий в правилах 'ГР, максимальное число символов безразличия '*' в матрице С" и др.

Известны различные методы интерпретации табличных моделей для принятия (поиска) решений: прямая поочерёдная проверка всех правил на применимость; метод Вейнотта - числовое кодирование входного вектора (вычисление «ключа») и прямой переход на решение по этому ключу; метод маски -матрично-векторные операции проверки с учётом частот применимости правил; построение по ТР булевых или тернарных решающих функций; преобразование ТР в дерево решений (ДР), в том числе ДР специального вида, где все узлы одного уровня проверяют значение одного условия (т.н. последовательности решений). Разработанный аппарат ТР был положен в основу созданной на каф.

1 "' ,т? Правила (лродуккш) Правило "Ннпче" Слозсностнгто-версн \слоый

."Услтамя ! Рг 1 ... | Р. ! Е

С1 с;-1 Он Си С12 ... Си С*! ьц • • • С:« Сг1 с„г с,,, Г 1„

:: Действия. А1 А2 аи . Р12-' ... Я 1а |*2! • • -• аз,, Нк! ■ Пи ••• Я|„ 01М1 Як*! Ч: <12

. Частоты применения 1 $'| & ... 'прквкч ' ' 4

Рис. 1. Структура классической ТР

ПМ МЭИ (ТУ) Системы моделирования принятия решений СИМПР-Windows. Данная система развивается с 1980-х годов и была удостоена Серебряной медали ВДНХ СССР. Современная версия системы реализована на языке С++ для 32-хразрядных ОС семейства MS Windows. Система зарегистрирована в Роспатенте как программа для ЭВМ и рассматривается как базовое программное обеспечение табличных моделей для дальнейшего расширения.

Помимо классических TP широко исследуются различные расширенные модели: вероятностные TP, таймированные TP, расширенные табличные деревья, семантические TP и др. Масштабные исследования в направлении табличных моделей, начиная с 90-х годов, ведутся в контексте использования теории приближённых множеств (rough sets). Табличное представление используется там не для описания правил и зависимостей, а для атрибутивного представления «сырых» данных в задачах извлечения знаний. Но в силу определенного сходства соответствующих структур оказывается возможным использовать некоторые методы теории приближённых множеств для обработки ТР. В работах М. Ramme, G. Chen и др. указывается на принципиальную возможность представления нечётких знаний в табличных моделях. Но имеющиеся в литературе описания расширения аппарата TP средствами обработки нечёткой информации обладают следующими недостатками: в них не задана формальная модель НТР, нечёткие условия таблиц рассматриваются в отрыве от стандартных дискретных (в т.ч. бинарных) условий, не рассматриваются степени правдоподобия правил, не приводятся методы анализа НТР. для поиска решений по НТР используются стандартные общие схемы нечётких рассуждений, что не позволяет говорить сб эффективном обобщении аппарата TP на нечёткий случай.

В силу актуальности задачи формального описания табличных систем, интегрирующих в себе классическую, чёткую обработку дискретных входов и выходов с возможностями нечёткого вывода, принято решение о развитии методов анализа таких гибридных систем с привлечением современного математического аппарата, в частности, теории приближённых множеств. Методы представления знаний на основе НТР должны использовать особенности методов на основе классических TP для повышения эффективности вывода. В качестве базового программного инструментария предложено разработать новую, расширенную версию системы СИМПР (СИМПР-Fuzzy), дополняющую базовый аппарат средствами создания и ан&тиза мультитабличных МПЗ на основе НТР.

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

Опр. 1. Атрибутом называется четвёрка: а = {Name, Dom, Val,ср), где Name -наименование атрибута, Dom = {dp\ - множество входных значений (домен) атрибута, Val = \vq\ ~ конечное множество выходных значений атрибута, ср: DomхVal ь-> ¡0.0,1.о] - тотальная функция соответствия значений атрибута, оценивающая степень соответствия <p{dp,v ) выходного значения v(/s Val элементу домена dp е Dom.

Опишем несколько базовых классов атрибутов, с которым будем работать

в дальнейшем: бинарные, дискретные k-значные, вещественные интервальные, дискретные нечёткие, и вещественные нечёткие. Выделение данных классов достигается наложением ограничений на значения компонентов в опр. 1. Например. для дискретного нечёткого атрибута as = {Names,Dom^Vah,<^4)-. Doms = {rf,, , • ■ •, йЦ г > 2 ; Vals = {v,, v2, • • ■, vk }Д > 2, где v, = [Name4, Dom4 - нечёткая переменная с именем Namet, заданная на универсуме Domq с Dums и характеризуемая нечётким множеством Л/, ={(d,nt(d))}; а

ф (d v )= \)X^Jp^ еСЛН dp 6 d0m^q^ г ' [0, иначе

Опр. 2. Нечёткой таблицей решений (НТР) называется набор FDT = ((C,D,f),B), состоящий из ядра НТР (C,D,F) и вспомогательного компонента расширения В, где С с А - конечное множество условных атрибутов (условий), De А, Сr\D = 'Z> - конечное множество решающих атрибутов (решений, действий), F:f|Fa/(c,)x]^[(Fe/(c/()u{1-,})i->(0.0,1.0] - обобщемная реимю-

c,tC J,eD

щая функция (функция уверенности).

Введём дополнительные понятия: Domc(FDT)=Y[D°m(c,) ~ множество

с,еС

входных векторов (данных); х е Domc (FDT) - входной вектор (вектор данных); Valc (FDT) - ]~[ Val(c,) - множество возможных ситуаций (состояний, векторов

С; ei:

значений условных атрибутов); vL eValc(FDT) - вектор ситуации (состояния); ValB(FDT)= ]~[(Fa/(i/,)и{'-'}) - множество возможных векторов значений решающих атрибутов, где символ обозначает неиспользование данного решающего атрибута; DomD(FDT) = J~[Z)om(d,) - множество выходных векторов;

у б DomD(FDT) - выходной вектор (вектор решения). Процесс принятия решения на основе НТР можно интерпретировать как отображение входного вектора на выходной вектор: х П)Г > у, xeDomc{FDT\ у zDomD{Füf). Функция F кодирует знания, заложенные в НТР. Они могут быть представлены в виде набора продукционных правил специального вида. Пусть даны FDT = ((C,D,F\B),

Vе =(vf), vc eValc(FDT), v° e Valn(FDT), и известно, что F(v\vüj=t/,

где с/ будем называть коэффициентом уверенности. Последняя формула эквивалентна решающему (продукционному) правилу вида:

IF А (с, is vf) THEN А [d, isvf) с коэфф. уверенности с/.

с,еС d^Dwf^'-'

В антецеденте и консеквенте правила записываются нечёткие конъюнкции оценок значений атрибутов НТР, а само правило является правдоподобным с коэффициентом уверенности с/е(0.0,1.0]. При cf = 1.0 правило становится достоверным. Значение функции F^ ,vDj будем интерпретировать как коэффици-

-D

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

Пример НТР в табличной форме приведён в табл. 1. В примере используются 3 условных атрибута и единственный дискретный к -значный решающий атрибут: «Длина_очереди» - дискретный нечеткий атрибут; «Ур_загрузки» — вещественный партиционированный атрибут; «Исп_приоритет» - бинарный атрибут; «Стратегия» - дискретный к-значный атрибут. Таким образом, в НТР единообразно представляются лингвистические, вещественные интервальные и бинарные атрибуты. Из табличного представления НТР можно построить их альтернативное, матричное представление на основе аналогичного описания для классических ТР. НТР в матричной форме определяется как пара FDT = ((С>ДС',£)').5}, где C,DçA -конечные множества условных и решающих атрибутов соответственно, CnD = 0', С=|с'4.|, ¿„еМО^Н. Д-К|> М-}, / = 1,2,...,|С|,

7=1,2,....и. / = 1,2,...,|£>| - матрицы условий и решений (у = 1,2,...,« +1 при наличии правила "Иначе"); В - компонент расширения модели, включающий коэффициенты уверенности правил cfn у = 1.2,...,и и другие дополнительные параметры. Отдельное правило в НТР представляется набором RuleJ =<CnD'rcf >, где Сj, D'y - j -е столбцы матриц С' и D' соответственно, a cfj - коэффициент уверенности правила Rukj, 7 = 1,2,...,«. Множество всех правил в НТР будем обозначать Ru!es.

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

Опр. 3. НТР FDT = {(C,D,F\b) называется полной в слабом смысле относительно множества ситуаций S çVaIc(FDT), если (\л/ es) sî/a/0(FD7');(v<:>VD)erfcw(F)}|>oj, где don(F}çVa!c{FDT)xVala{FDT) - область определения функции F. НТР FDT = ([c,D,F\B) называется полной в сильном смысле относительно множества ситуаций Sç'/alr(FDT), если (vvc es)fj|?0 s Ka/o(FOr):/r|vC,vfi)=1.0i|>lj. НТР, не обладающая свойством

слабой полноты, называется неполной. Наличие правила «Иначе» в НТР обеспечивает её сильную полноту.

Опр. 4. НТР FDT = ((c,D,f),B) называется непротиворечивой в слабом

Табл. 1. Пример НТР

Rule, Rule, Rule, Rule, Rule, RuleJ, Rule, Else

Длина очереди Low Low Low Mid Mid Hiehl High

Ур_эагрузки * * [0.0,0.7) * [0-7,1.0] ' I [0.7,1.0]

Исл приоритет No Yes * No Yes No I Yes

Стратегия FiFO PR- RAN- FIFO PR- SPTFl PR- FIFO

FIFO DOM SPTF | SPTF

Cf 0.7 1.0 0.3 1.0 0.9 1.0 | ¡.0

смысле относительно множества ситуаций Л" с Уа1с (РОТ), если

е я)^е Уа1в(гаг): р(ус,1 ,о| 21). НТР РОТ = ((С,ДВ) называется непротиворечивой в сильном смысле относительно множества ситуаций БсУафЪТ), если ее(/ЭДГ):е4ия(Г)}|5. НТР, не обладающая свойством слабой непротиворечивости, называется противоречивой.

Опр. 5. НТР называется корректной, если она обладает свойствами полноты и непротиворечивости. Сила свойства корректности соответствует силе более слабого из двух составляющих его свойств. Например, если НТР полна в сильном смысле (а, следовательно, и в слабом), но является непротиворечивой только в слабом смысле, то такая НТР является корректной также в слабом смысле. Аналогично классическим ТР для НТР определяется синтаксическая и семантическая корректность в зависимости от выбора множества ситуаций 5 аУа1с(РОТ). Предлагается способ задания множества семантически допустимых ситуаций на основе введения отношений между условиями в виде формул некоторой формальной системы, которые интегрируются в структуру НТР з составе компонента расширения В. Описывается алгоритм построения по исходной НТР РОТ её расширенной версии F^)Гг:, в которой скрытые отношения между условиями переводятся в явную форму.

Утв. 1. Свойство семантической полноты (непротиворечивости) НТР РОТ = {(С,0,С\0'\В), й = выполняются тогда и только тогда, когда вы-

полняется свойство синтаксической полноты (непротиворечивости) построенной на её основе расширенной НТР РОТЕ = ((<С,0,С'Е ,£>'*) .

Для принятия решений по НТР предлагается алгоритм, включающий следующие этапы: вычисление значений условных атрибутов (фаззификацию); агрегирование условий с отбором активных правил; активацию заключений правил; заключительную аккумуляцию и дефаззификацию выходных значений. Агрегирование условий с получением коэффициентов активации (КА) Ас^ правил производится ка основе интерпретации нечёткой конъюнкции как вещественного произведения по формуле Аа] =с/}* ^^(г^с'Д j = \,2,...,\ЯиЩ. Ак-

с^с-.сц^ '

тивными считаются правила, КА которых превосходит заданную пороговую величину .4е/ЛЛие[0.0,1.0), они включаются в множество активных правил Для правила «Иначе» предлагается параметризованный критерий активации, зависящий от суммы КА остальных правил в НТР. Этап активации заключений требуется только для вещественных решающих атрибутов и предназначен для получения предварительных скалярных оценок решения по лингвистическим значениям в заключениях правил. Доказаны 2 утверждения, касающиеся вида скалярных оценок решения для некоторых частных случаев. Показано, что предложенная схема активации заключений является обобщением принципа активации в схеме вывода Цукамото на случай функций принадлежности, не являющихся строго монотонными. Заключительный этап приня-

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

Для ускорения отбора активных правил в НТР вводится понятие дерева активации (ДА), которое можно рассматривать как обобщение дерева решений с терминальными вершинами, помеченным списками активных правил. Ускорение достигается за счёт предварительного конструирования и последующего хранения ДА. Для построения ДА предварительно строятся разбиения п(с\ ) = |а'} доменов условных атрибутов с, с С.

Опр. 6. Множеством соответствия значений условного атрибута cl=(Name„Doml,Vall,<р() для произвольного dе Dom: называется множество Ф(<7,с,.)={уеКй7, :cp(d,v)> О.О}. Требуемое разбиение i2(c,)= {а;5} домена атрибута с, должно удовлетворять условиям:

• (vo; eofoy^.d, €О;)(Ф(4,С,)=Ф(</„С());

» (va.,c[en{cl\Vdteo',W2eolXk*l=><!)(d],cl)*<I>(d2,c,)).

Опр. 7. Классом деревьев активации, совместимых с НТР FDT - ([с, D, С", D'\ \cfj}), называется минимальное множество T(FDT), удовлетворяющее условиям:

8 Если R с Rules, R*0, то R s t(fDT), где Rules - множество правил в НТР FDT;

■Если с, е С, tj,tf,...,t' eT(FDT), a],af,...,a' efiic,) все попарно различные, то сДа;,/,1}^,2)...,(ст;,/;))б t(fdt).

Процесс нахождения множества активных правил TreeRules\k,t)c Rules для входного вектора х = (х;). х е Domc(FDT) по ДА t € T(FDT), совместимому с НТР FDT = ((С,ДС",£>'),(r/J), определяется индукцией по структуре дерева:

" TreeRules(х,R)=R, R с Rules;

• TreeRules^cp^,tfiM^^^"^ ^

10,иначе

На рис. 2. приведён пример корректного неизбыточного дерева активации для НТР в табл. 1. Его внутренние вершины помечены условными атрибутами (JIQ - «Длина_очере-ди», TL - «Ур__загрузки», HP -«Исп_приоритет»), терминальные вершины - списками активных правил, а рёбра - элементами определённого выше разбиения домена атрибута, связанного с исходящей вершиной ребра. Неизбыточность ДА требует, чтобы ни на одном пути от корня к листьям условные атрибуты не дублировались. Это гарантирует конечность любого пути от корня до листа, который не может включать более

ч-

' С. 4.!)

{[0 0, 0.ЭД0.7. t Oh

А А

(w, IHPJ

■-Г '-г

(Nov i'ei) 1NO} {Yes}

iC.sii мм w J !__J L.J U

iI0.0.0.7j;{[(l.7. 1.0]} i 1

T ' (Nrt) ¡vel}

: hp

{No} r .JL._ J. ■ TL

(No) [Yes)

т L

(»¡[riS)

{[0.7.'1.01*

{[0.7, 1 0]}

Pkc. 2, Пример дерева активации

{¡0 7.1.0]} -Т. ,

т = \С\ вершин. Для корректности ДА требуется, чтобы множество правил 7>рсйи/е.у(х,/), найденных при помощи ДА, совпадало с множеством активных явных правил. При проходе по корректному дереву активации список активных правил может быть получен за время 0(!с[), где ¡С| - количество условных атрибутов в НТР. Для этого могут быть использованы не все условные атрибуты, а только те из них, которые встречаются на пути от корневой до терминальной вершины ДА. В работе предложен алгоритм построения корректного неизбыточного ДА по заданной НТР с использованием эвристической функции для выбора очередного условного атрибута, включаемого в ДА, и алгоритм приятия решений по НТР (табл. 2).__

Тпбл. 2. Алгоритм принятия решений по НТР при наличии ДА

Входинг даянве: НТР A fir - Hf П Г" Г') {<-/ }¡ • ДА ' " rTIFDT). входной вектор у с n„,„ ¡ffir)

Выходные данные: выходной вектор у = (j>;). у <= Ппп^ПТ).

1 Сфпрмирпйять мнпжр.ГЛ ВП активных явных правил = ТУ:)•

ДЛЯ ВСЕХ правил ки}е. € АсгКи'ез^.}'- Вычислить коэффициент активации АсГу правила.

3 ЕСЛИ в НТР присутствует правило «Иначе» £ =<-/)' ->, ТО

3.1 |Вычислить степень активации Ас(ш правила «Иначе».

3.2 |нсли Лс1Еие > 0.0» ТО: Присвоить Ас1Яи1е^) = ЛаЕик^)^ {е}.

4 ДЛЯ ВСЕХ вещественных решающих атрибутов е /)

4.1 ДЛЯ ВСЕХ активных правил Ru>e, е ActRu!es{x)

4.1.11 Вычислить интервальную локальную оценку решения д^..

4.Í.2 |вычислить точечную локальную оценку решения w¡,.

5 ДЛЯ ВСЕХ решающих атрибутов d, е D '• Вычислить компонент вектора решения-y¡.

6 Вернуть вектор у = (>>,)- ВЫХОД. j

В третьей главе рассматриваются методы и алгоритмы проверки свойств и минимизации НТР, представляющие собой обобщения известных методов анализа классических ТР. Описываются подходы и приводятся алгоритмы на основе переборного метода, матричных операций, метода кардинальных чисел, логические методы. Показано, что проверка полноты и непротиворечивости НТР переборным методом применима только к небольшим НТР в силу экспоненциальной сложности алгоритма. Применение матричного подхода к проверке непротиворечивости позволяет снизить вычислительную сложность алгоритма до о(п2 (т + к)), где т = \С\, к = |Л|, п = \Rule^. Кроме того, данный метод позволяет обнаруживать аномалии задания коэффициентов уверенности правил в НТР. Другим перспективным методом анализа НТР является метод кардинальных чисел, связывающий с каждым правилом в НТР множество кодов (кардинальных чисел) всех распознаваемых им векторов ситуаций. Прямая проверка полноты и непротиворечивости НТР на основе данного метода довольно трудоемка, но метод применим для статических либо мало изменяющихся НТР. В таком случае множества кардинальных чисел правил можно вычислять заранее и сохранять, что существенно снижает сложность алгоритмов проверки НТР после внесения в неё незначительных изменений. На основе метода кардинальных чисел также возможна проверка избыточности НТР, то есть наличия в ней поглощаемых правил. Также рассматривается сводимость проверки полноты и

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

В работе подробно рассматривается применение аппарата приближённых множеств к обработке НТР. Предметом рассмотрения в теории приближенных множеств являются универсум объектов и и заданное на нем бинарное отношением неразличимости I с и2. Для формального описания признаков объектов вводится понятие информационной системы /5 = {и, Л) , включающей множество универсума и и множество атрибутов А, описывающих рассматриваемые объекты, и решающей системы 1>5 = ([/,Си1>),Сп£> = 0, в которой атрибуты разделяются на два непересекающихся множества условий и решений. На основании отношения неразличимости строятся обобщенная решающая функция, верхняя и нижняя аппроксимации подмножеств объектов универсума, определяются критерии значимости атрибутов с выделением существенных (ре-дукты, ядро информационной системы) и несущественных атрибутов. Важнейшей задачей в теории приближённых множеств является построение редуктов множеств условных атрибутов в решающих системах; для этого конструируются матрицы и функции различимости специального вида.

Нетрудно установить наличие структурного сходства между ядром НТР Л)Г = {(СГОГ,ДГОГ)С',1)'),^}) и решающей системой = в теории

приближенных множеств. Несмотря на схожую структуру НТР и решающих систем, интерпретация этих объектов различна. Содержимое НТР интерпретируется как формальное представление экспертных знаний в виде нечётких продукционных правил над множеством условий и действий. А аппарат приближенных множеств возник в задачах анализа «сырых» данных, представленных в виде таблицы (в том числе экспериментальных данных, содержимого больших баз данных, статистических наблюдений и т.п.). Результатов анализа таких данных могут являться некоторые, классификационные правила, в том числе и продукционного вида. Если представить экспертную НТР в виде решающей системы, то к ней будут применимы все ранее разработанные методы обработки информационных и решающих систем.

Применение аппарата приближённых множеств к обработке НТР требует модификации некоторых определений для корректной обработки обобщённых правил, содержащих символы безразличия '*'. Предложено перейти к нечёткому отношению неразличимости, чтобы адекватно представить степень неразличимости обобщённых правил. Будем строить отношение В -неразличимости по множеству условий йсС путём пересечения отношений неразличимости по единичным условиям на основе вещественного произведения, где полная неразличимость соответствует значению 1.0 функции принадлежности, полная различимость соответствует значению 0.0, а промежуточный случай задаётся величиной | • Предлагаемая мера неразличимости правил пропорцио-

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

ким образом нечёткое отношение В -неразличимости правил в НТР Л)7' = ((С,ДС",1),),{с/;}} при В с, С обладает свойствами рефлексивности и симметричности, свойство транзитивности отсутствует.

Следующим шагом по адаптации методов теории приближённых множеств к обработке НТР является модификация определений матриц и функций различимости. Предлагается метод построения функций различимости непосредственно по обобщённым правилам, так, чтобы получаемая функция соответствовала раскрытию обобщённых правил в набор простых. Для этого предварительно производится эквивалентное преобразование НТР, ведущее к исключению пересекающихся обобщённых правил. Особенность предлагаемого метода построения матрицы различимости для НТР с обобщёнными правилами заключается в том, что каждый вход матрицы должен содержать несколько множеств условных атрибутов, необходимых для попарного различения правил, распоЗНАЮЩИХ КС П£р£С£К2К>1ЦИ£СЯ МНОЖ2СТЕЗ. ВСКТОрОБ ЗЗХСМ ПрИ ГТСС^рОСН И1' 'иг.

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

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

Табл. 3. Алгоритм проверки непротиворечивости НТР нэ основе отношения неразличимости правил

Входные даиные: НТР FD7 ~<{C,D,C D'\ \cfj} >. Выходные дгнкыг: Признак непротиворечивости НТР ггтмтя^/тп IP«?» A.W}.

1 Построить элементарные матрицы неразличимости правил aeCuD-

2 Построитькглриии /г.. = j|,-,.Jj и rd .jr j.

3 Построить матрицу c(FDT) = ■

4 Присвоить WeakConfl = False

5 ДЛЯ/-1 ДО и ПОВТОРЯТЬ; ДЛЯ = ДО п ПОВТОРЯТЬ

5.1 ЕСЛИ !Cj*(l-ruJ#0.0.TO

5.1.i ЕСЛИ g „ 0.0= ГО: Присвоить FDTStatus = AW. ВЫХОД.

5.1.2 ИНАЧЕ: Присвоить WeakCvnjl = True ■

6 Если WeakConfl = True, 10: Присвоить FDTStaius = Weak■ ВЫХОД.

7 ИНАЧЕ: Присвоить FDTStatus = Strong ■ ВЫХОД.

Данный алгоритм проверки непротиворечивости НТР использует матричное представление отношения неразличимости правил, на его основании строится ряд вспомогательных матриц, для которых формулируется утверждение о матричной формулировке свойства непротиворечивости НТР. Сложность алгоритма составляет о(п2 *(т + к)), где т = \с\, к = Щ, и = |Лк/^. Алгоритм легко поддаётся распараллеливанию, а вспомогательные матрицы могут быть использованы и в других алгоритмах на основе аппарата приближённых множеств,

снижая их вычислительную сложность. Принцип работы алгоритма редукции условных атрибутов состоит в вычислении d -относительных редуктов множества условных атрибутов. Сложность алгоритма в случае эвристического отбора минимального редукта полиномиальна и составляет 0{(т} + /с)х и2), где n = \Rules\, m = ¡С|, к-)/)|. Также рассматривается вариант алгоритма, использующий точное вычисление минимального редукта на основе минимизации d -относительной функции различимости правил. Для поиска оптимальной формы правил предлагается искать подмножества условий, достаточные для отличия каждого правила от всех остальных правил, заключения которых отличается от заключения данного правила. Это соответствует вычислению (k,d)-относительных редуктов множества условий для каждого правила. По найденным редуктам строятся оптимальные представления правил путём применения каждого редукта как маски к множеству условий в посылке правила. В заключении главы указывается, что описанные в ней методы и алгоритмы обработки НТР могут быть использованы в ИСППР, включая ИСППР РВ.

В четвертой главе рассматривается общая методика разработки и применения НТР, выделяются классы задач и сценарии применения программных средств на основе НТР как при автономном использовании, так и при встраивании в ИСППР РВ. Описывается структура мультитабличной МПЗ для принятия решений, включающей несколько взаимосвязанных НТР над общим репозито-рием атрибутов. Для хранения таких моделей предлагается использовать специализированное XML-представление, XSD-схема которого также рассмотрена в работе. Полученные результаты использованы в программной системе представления знаний на основе НТР, разработанной на языке С++ в среде MS Visual Studio 2005. В качестве средства поддержки объектно-ориентированного анализа и проектирования выбран пакет Rational Rose Enterprise Edition 2002.

Программные компоненты системы скомпонованы в 3 взаимосвязанных пакета: Infrastructure, RoughWork и De-cisionMaking (рис. 3). Пакет Infrastructure является универсальным вспомогательным пакетом инфраструктурной поддержки разноплановых разработок, в него входят динамические библиотеки Support, xerces-c, RandGen, WinMsging, WinCatalog и TestFramework и консольное приложение SupportU-nitTests. В пакет RoughWork включены предложенные в работе средства обработки табличных данных с использованием приближённых множеств. Пакет содержит библиотеки RSMain, XMLSupport, RoughDB, Dependency, Discret, Concurrent, консольное приложение RoughUnitTests и утилиту TableBrowser для редактирования и анализа табличных данных. Пакет DecisionMaking обеспечивает непосредственно работу с аппаратом НТР; его составляющими являются библиотека Decider, содержащая программную модель, операции сохране-

Рис. 3. Диаграмма программных компонентов пакета DecisionMaking

ния/загрузки, представления, анализа и поиска решения на основе нечётких табличных моделей, консольное приложение ВешскгипкТезгБ и новая расширенная версия Системы Моделирования Принятия Решений СИМПР-Риггу. Для СИМПР-Риггу реализованы две локализации пользовательского интерфейса: англоязычная и■

fflfuainTabfc SIMPS .

Б* Kode) ХаЫв Anef/и мчр

D6B У □ ПЗВ ",!

; 1: D^alchTibie.LiU | Z DitM!ciiTaÜe_Wvi! J RWlWQ_RN;NO_TaMeji 4: DepflTchT^ate.LüU*

i " ■■-■'■ .............

_ fctttfaui» Mot AvgTanprod

Z ja NeilTE WCTtload

5:'&imJ HatSatigs"

ftiiei fart • I RuieS I flu1« 6 Rwe 7 Pi'tea i Ru)e» 1

" " J Noma! - fi zJ •1 3 .1 --------vj- •1 zl

т zi > .7.1 ... Я z. . .--J w

д, Hah ZI -f ZJ

........Д. Jj T ¿1 T Д z}

JL -1 -1 Hign Low .. . zl

„i . -1 J * нф ZJ Low ,'j

Mid z* «Oh.. 3. Lot jjj jw v I НчЬ Д Lew n«h Zj

' , tSBKSl :

Рис. 4. Основное окно среды СИМПР-Fuziy

Практическая значимость предложенных методов и программных средств представления знаний на основе НТР подтверждается на примере индустриальной задачи, связанной с автоматизацией процессов управления производством микроэлектронных компонентов. Каждый раз при завершении обработки очередного лота на одном из агрегатов производственной группы в цехе возникает задача переупорядочивания входного буфера группы для выборки следующего лота на обработку, называемая задачей диспетчеризации лотов. По умолчанию может использоваться типичная для обработки очереди стратегия FIFO (First-In-First-Out), т.е. в порядке поступления лотов в буфер, но на практике применяются и другие стратегии диспетчеризации. Установлено, что выбор стратегии (дисциплины) диспетчеризации существенно влияет на динамику функционирования производства и на его технико-экономические показатели. Предложено переупорядочивать лоты на основании присваивания им вещественных приоритетов, вычисляемых по нечётким правилам в НТР. Данные исследования выполнялись кафедрой Прикладной математики МЭИ (ТУ) совместно с факультетом Информатики Дрезденского технического университета (ДТУ) при поддержке РФФИ, Германского фонда академических обменов (DAAD) и Министерства науки и искусства федеральной земли Саксония.

Совместно с ДТУ был разработан программный комплекс, позволяющий в реальном времени управлять диспетчеризацией лотов. В силу того, что ошибки и просчёты в управлении реальным производством обходятся очень дорого, общепринятым методом оценки стратегий диспетчеризации являются вычислительные эксперименты над имитационной моделью производства. В качестве модели цеха была использована модель rnimacö из индустриального набора тестовых моделей MIMAC. Эксперименты проводились при различном уровне загруженности цеха (80%, 85%, 90%, 95% от теоретически возможного максимума) и с различными значениями коэффициента FF (1.5, 1.7, ..., 4.5) сжатости

плановых сроков готовности продукции. Эксперименты показали (рис. 5), что уже при 80%-ой загрузке оборудования предложенные нечёткие стратегии диспетчеризации, разработанные на основе МПЗ в виде НТР, показывают лучшие результаты, чем стандартные стратегии FIFO, ODD (Operation Due Date), CR (Critical Ratio). Полученные результаты позволяют говорить о большом потенциале выбранного подхода и указывают на его ценность для практического

Рис. 5. Длительность производственного цикла лотов при использовании различных стратегий диспетчеризации

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

1. Виноградов О.В., Еремеев А.П. Программные средства поддержки принятия решений па основе нечётких табличных моделей представлении знаний // Программные продукты и системы, №4 (84), 2008, с. 75-80.

2. Виноградов О.В., Еремеев А.П. Методы и программные средства на основе нечетких таблиц решений для диспетчеризации логов на полупроводниковом производстве // Вестник МЭИ, №2, 2009, с. 166-174.

3. Виноградов О.В., Чувиляев М.В. Преобразование данных, заданных н терминах различных метамоделей // Эл. журнал «ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ. Теория и практика», №1(2), 2002. URL: http://network-jouma!.mpei.ac.ru/cgi-bin/in ain.pl?Hru&n=2&pa-S'&ar=;2.

4. Виноградов О.В., ЧувиляеБ М.В. Разработка метамоделько-зазисимых языков запросов // Международный форум информатизации — 2002: Доклады международной конференции «Информационные средства и технологии», в 3-х тт. Т. 3. -М.: Янус-К, 2002., с. 25-28.

5. Еремеев А.П., Виноградов О.В., Куриленко И.Е. Программный комплекс унифицированного представления мнемосхем для имитационного моделирования процессов управления сложными техническими объектами // Докл. между.чар. кенф. «Информационные средства и технологии». М.: Янус-К, 2003, с. 123-126.

6. Виноградов О.В., Еремеев А.П. Применение теории приближенных множеств при разработке СППР // Научная сессия МИФИ-2004. Сборник научных трудов, в 15 тт. Т. 3. - М.: МИФИ, 2004, с. 122-123.

7. Виноградов О.В., Еремеев А.П. Построение правил на основе теории приближенных множеств // Радиоэлектроника, электротехника и энергетика. 10-я Международная научно-техническая конференция студентов и аспирантов: Тез. докладов в 3-х it. — М.: МЭИ. 2004, Т. !, с. 314.

8. Вкноградоа О.В., Еремеев А.П., Куриленко И.Е. Расширение языка CLIPS в плане конструирования интеллектуальных систем поддержки принятия решений реального времени //' Тр. Междунар. научно-техн. кокф. «Интеллектуальные системы» и «Интеллектуальные САПР». -М.: Физматлит, 2004, Т. 1, с. 286-294.

9. Pachoiik A., Fengler \У„ Salzwedel Н., Vinogradov О. Real Time Constraints in System Level Specifications Improving the Verification Flow of Complex Systems // Proc. of Net.ObjectDays 2005 (Erfurt, 19.-22. 9. 2005), S. 283-294.

Нахолик А,, Фенг-лер В. Зальцведедь X., Виноградов О. Задание временных ограничений для системных

спецификаций, улучшающих технологию верификации сложных систем // Труды конф- Net.ObjectDays 2005 (Эрфурт. 19.-22. 9. 2005), с. 283-294.

10. Виноградов О.В., Еремеев А.Г1. Обработка недоопределенности на основе таблиц решений Ц Радиоэлектроника, электротехника и энергетика. 12-я Международная научно-техническая конференция студентов и аспирантов: Тез. Докладов в 3-х тт. — М.: МЭИ, 2006 г. T. 1, с. 394-395.

11. Виноградов О.В., Еремеев А.П. Специфика применения аппарата приближенных множеств к табличкам моделям знаний // Научная сессия МИФИ-2006. Сборник научных трудов. Т.З - М.: МИФИ. 2006, с. 61-62.

12. Fenglcr W., Pacholik A., Vinogradov О. Development of Language of Time Constraints for the Design of Reactive Systems // Научная сессия МИФИ-2006. Сборник научных трудов. Т.З -М.: МИФИ, 2006, с. 90-91. Фенглер В., Пахолик А., Виноградов О. Разработка языка временных 01раничений для проектирования реактивных систем.

13. Виноградов О.В. Разработка и реализация методов обработки баз знаний для систем поддержки принятия решений реального времени // Тезисы докладов XIV Международной студенческой школы-семинара «Новые информационные технологии» -M.: МИЭМ, 2006. с. 213-214.

14. Виноградов О.В., Еремеев А.П. Использование таблиц решений с расширенным входом в интеллектуальных системах поддержки принятия решений .'/ 10-я национальная конференция по искусственному интеллекту с международным участием КИИ-2006: Труды конференции. Т.З-М: Физматлит, 2006 г., с. 807-815.

15. Виноградов О.В., Воробьев A.C., Тихонова Е.А. Построение отраслевой подсистемы сбора, обработки и анализа информации по потреблению и оплате энергоресурсов // Докл. междунар. научно-техн. конф. «Информационные средства и технологии», т. 3. - М.: Янус-К, 2006.

16. Виноградов О.В. Нечеткое отношение неразличимости для обработки таблиц решений на основе теории приближённых множеств // Труды международной научно-технической конференции «Информационные средства и технологии», в 3-х тт. Т. 3. - М.: Янус-К, 2006, с. 80-83.

17. Вакулко А.Г., Воробьев A.C., Виноградов О.В. Модернизация подсистемы сбора информации в отраслевой информационно-аналитической системе «Учет и контроль потребления топливно-энергетических ресурсов» // Энерго- и ресурсосбережение - XXI век: Мат. 4ÍÍ междунар. научно-практ. конф. - Орел: Орел-ГТУ, 2006, с. 19-21.

18. Виноградов О.В. Построение матриц и функций различимости правил в таблицах решений ка основе теории приближённых множеств // Научная сессия МИФИ-2007. Сборник научных трудов в 17 тт. Т.З - М.: МИФИ, 2007, с. 196-197.

19. Виноградов о.в. Расширенные табличные модели для представления временных зависимостей // Радиоэлектроника, электротехника и энергетика. 13-я Международная научно-техническая конференция студентов и аспирантов: Тез. докл.: В 3-х т. — М.: МЭИ, 2007 г. Т. 1, с. 36-4-365.

20. Виноградов О.В., Еремеев А.П Анализ зависимости условий в таблицах решений с расширенным входом // IV-я Междунар. научно-пракг. конф. «Интегрированные модели и мягкие вычисления в искусственном интеллекте», сб. тр. (Коломна, 28-30 мая 2007 г.). В 2х томах, т. 2, - M.: Физматлит, 2007,354с, с. 549-552.

2!. Виноградов О.В. Анализ таблиц решений с расширенным входом на основе теории приближённых множеств в системе «CHMni'-Windows» // Тезисы докладов XV Международной студенческой школы-семинара «Новые информационные технологии» - М.: МИЭМ, 2007, с. 166-167.

22. Виноградов О.В. Представление нечётких баз знаний на основе табличных моделей // Радиоэлектроника, электротехника и энергетика. 14-я Межд. научно-техн. конф. студ. и асл. М.: МЭИ, 2008 г., т.1, с. 293-294.

23. Vinogradov O.V., Rose О. Fuzzy Lot Dispatching in Semiconductor Wafer Fabrication Using Fuzzy Decision Tables '/ Сборник материалов научного семинара стипендиатов программы «Михаил Ломоносов» 2007/2008 года. - М.: DAAD, 2008, с. 225-227.

Виноградов О.В., Розе О. Нечёткая диспетчеризация лотов при производстве чипов с использованием нечётких таблиц решений.

24. Виноградов О.В. Формализация аппарата нечётких таблиц решений /7 Нечеткие системы и мягкие вычисления (НСМВ-2008): сб. науч. тр. Т.1. - Ульяновск: УлГТУ, 2008, с. 104-111.

25. Виноградов О.В., Еремеев А.П. Адаптация нечёткого вывода к аппарату нечётких таблиц решений // 11-я национальная конференция по искусственному интеллекту с международным участием (КИИ-2008): Труды конференции. Т. 2. - М.: ЛЕНАНД, 2008 г., с. 330-338.

26. Виноградов О.В. Свойства полноты и непротиворечивости для нечётких таблиц решений // 16-я Междунар. научно-техн. конф. «Информационные средства и технологи;:». Т. 2. - М.: МЭИ, 2008, с. 29-36.

27. Виноградов О.В. Нечёткая диспетчеризация лотов при производстве чипов на основе нечётких таблиц решений //Радиоэлектроника, электротехника и энергетика. 15-я Международная науч.-техн. конф. студентов и аспирантов: Тез. докл.: В 3-х т. Т.1. М.: Издательский дом МЭИ, 2009, с. 278-279.

28. Виноградов О.В.. Еремеев А.П, Современные программные средства поддержки принятия решений ка основе аппарата таблиц решений // Интеллектуальные системы. Колл. монография. Выпуск 3 / Под ред. В.М. Курейчика.-М.: Физматлит, 2009, с. 140-155. _

Подписано в печать ¡J_.ú¿.Q9 Зак. /ла- Тир. ILÛ П.л.

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

ОГЛАВЛЕНИЕ.

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

ВВЕДЕНИЕ.

ГЛАВА 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 для повышения интеллектуальных способностей ИСППР РВ.

ЗАКЛЮЧЕНИЕ

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