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

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

004ЬИ61^

Лебедев Анатолий Анатольевич

МЕТОДЫ СИНТЕЗА ЭЛЕМЕНТОВ И АНАЛИЗА ДИСКРЕТНЫХ И НЕЧЕТКИХ ИЕРАРХИЧЕСКИХ СИСТЕМ

Специальность 05.13.01 -Системный анализ, управление и обработка информации

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

2 /, ИЮН 2010

Тверь —2010

004606134

Работа выполнена в Институте точной механики и вычислительной техники им. С.А. Лебедева

Научный руководитель

доктор технических наук, доцент Рыжов Александр Павлович

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

Дудаков Сергей Михайлович

кандидат физико-математических наук, доцент Петровский Михаил Игоревич

Ведущая организация

Вычислительный центр им. А.А. Дородницына Российской академии наук

Защита диссертации состоится 2 июля 2010 г. в 16:00 на заседании диссертационного совета Д 212.263.04 при Тверском государственном университете по адресу: 170002, г. Тверь, Садовый пер., д.35, ауд. 246а.

С диссертацией можно ознакомиться в научной библиотеке Тверского государственного университета по адресу: 170000, г. Тверь, ул. Володарского, 44а.

Объявление о защите диссертации и автореферат опубликованы 1 июня 2010 г. на официальном сайте Тверского государственного университета по адресу: http://universitv.tversu.ru/aspirants/abstracts/.

Автореферат разослан « ?> / » ¿УЛ-З 2010 г.

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

Д 212.263.04 при ТвГУ

доктор технических наук, профессор

Михно В.Н.

Общая характеристика работы

Актуальность темы

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

• моделирование поведения клиента (маркетинг);

• продвижение кандидата на выборах (политология);

• диагностика (медицина);

• повышение эффективности работы предприятия (менеджмент);

• развитие технологий/научных исследований (наукометрия).

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

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

Системы информационного мониторинга можно отнести к классу иерархических нечетких дискретных динамических систем. Теоретическую основу такого класса систем составляет теория нечетких множеств, дискретная

математика, методы анализа иерархий, которые были разработаны в работах Т. Саати, М.Д. Месаровича, JI. Заде, C.B. Яблонского и других ученых. Системы, разработанные на базе этой технологии, позволяют иметь развивающуюся во времени модель проблемы на основе оценок аналитиков с общими и частными оценками состояния проблемы и/или ее аспектов. Использование времени как параметра системы позволяет проводить как ретроспективный анализ, так и строить прогнозы развития проблемы (отвечать на вопросы типа «Что будет, если ...?»). В последнем случае также возникает возможность выделения «критических путей» - таких наборов элементов модели, небольшое изменение которых может вызвать заметные изменения в состоянии всей проблемы. Знание таких элементов позволяет выявить «слабые места» в проблеме на текущий момент времени, разработать мероприятия по блокированию нежелательных ситуаций или провоцированию желательных, т.е. в некоторой степени управлять развитием проблемы в интересах организации, ее отслеживающей.

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

Цель работы

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

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

- Теоретические оценки качества работы нечеткого оператора агрегирования информации как элемента схемы функциональных элементов (СФЭ) и СФЭ в целом;

- Обратная задача (задача оптимального распределения ресурсов) для дискретных СФЭ.

• В прикладной части:

- Разработка прикладной системы оценки и мониторинга (в качестве предметной области была выбрана микроэлектроника).

Основные методы исследования

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

Научная новизна

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

• Для решения этой задачи введена и изучена новая управляющая система -граф нечеткого условия.

• Сформулированы и решены две задачи для иерархических систем - задача проверки устойчивости в дискретном и нечетком случаях и задача оптимального распределения ресурсов в различных метриках:

- Доказана ЫР-полнота задач в общем случае;

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

- Получены эффективные алгоритмы выделения этих частных случаев;

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

Теоретическая и практическая ценность работы

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

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

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

Созданная прикладная система оценки и мониторинга проектов разработки изделий микроэлектроники была принята в тестовую эксплуатацию компанией Cadence Design Systems. Она позволяет оценивать способность коллектива разработчиков выполнить проект в заданные сроки, выявлять слабые места и находить оптимальные способы вложения средств с целью повышения возможностей коллектива.

Разработанные методы позволяют строить системы мониторинга для обширного класса областей: маркетинг, менеджмент, медицина, экономика, административное управление и т.д.

Структура и объем диссертации

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

Апробация работы

Материалы диссертации, ее основные положения и результаты неоднократно докладывались на научных семинарах механико-математического факультета и факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, в Институте точной механики и вычислительной техники им. С.А. Лебедева, а также на следующих международных и всероссийских конференциях:

• «Нечеткие системы и мягкие вычисления». Всероссийская научная конференция НСМВ-2006. Тверь, 20-22 сентября 2006 г;

• Девятая Международная конференция «Интеллектуальные системы и компьютерные науки», 23-27 октября 2006;

• Конференции молодых ученых «Ломоносов», Москва, 2007, 2008, 2009;

• Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию академика В.А. Садовничего. Москва, 30.03-1.04 2009 г.

• 5th International Conference on Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control. 2-4 September, 2009, Famagusta, North Cyprus.

• II международная конференция «Технологии искусственного интеллекта-2009». 10-11 декабря 2009г., г. Дубна.

• X международный семинар «Дискретная математика и ее приложения». Москва, 1-6 февраля 2010.

Публикации по теме диссертации

Основные результаты диссертации опубликованы в трех работах (из них две - в журналах, рекомендованных ВАК), список которых приводится в конце автореферата.

Краткое содержание работы

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

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

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

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

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

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

• Исследование операций;

• Имитационное моделирование;

• Экспертные системы;

• Системы поддержки принятия решений;

• Анализ иерархий.

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

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

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

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

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

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

3. Инициализация - сбор информации о состоянии параметров системы и введение данных в модель.

Технология допускает следующие сценарии использования:

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

• Прогнозирование дальнейшего развития проблемы. Пользователь системы, задавшись вопросом «а что будет, если этот фактор изменится некоторым образом?», может достаточно легко получить на него ответ.

• Моделирование последствий действий. Под действием понимается некоторое мероприятие, приводящее к одновременному изменению сразу нескольких факторов.

• Поиск оптимальных воздействий.

Здесь же кратко описываются две ранее созданных системы мониторинга: 1. Система мониторинга ядерных технологий проекта DISNA (Development of an Intelligent System for Monitoring and Evaluation of Peaceful Nuclear

Activities), разработанной по заказу Международного Агентства по Атомной Энергии (МАГАТЭ) с целью обеспечить сотрудникам управления гарантий Агентства удобное средство для выявления недекларированной ядерной активности стран-участниц. 2. Система мониторинга для прогнозирования риска развития сердечнососудистых заболеваний, созданную совместно с институтом профилактической медицины МЗ РФ с целью отслеживания на новом технологическом уровне факторов риска атеросклеротических заболеваний у населения России, прогнозирования дальнейшей динамики заболеваний этого класса в различных его возрастных группах и выработки наиболее экономически эффективных способов уменьшения риска. Также в этом разделе приводится формализация технологии информационного мониторинга и вводятся основные обозначения.

Во второй главе формулируется и решается задача выбора оператора агрегирования по экспертным описаниям. Эта задача - определение функции, характеризующей зависимость некоторой величины от наблюдаемых параметров — в том или ином виде возникает при разработке большинства систем сбора и обработки информации. В работе рассматриваются дискретные функции - функции ¿-значной логики (рассматривается неоднородный случай, в котором множеством значений аргументов является множество Ек = {0,1,...,АГ — 1}, а множеством значений функции является множество Ек ={0,1,...Д-1}; такие функции мы называем функциями АГД-значной логики, а множество всех таких функций обозначаем РК к).

Подход к решению задачи заключается в следующем: на универсальном множестве функций К,к-значной логики от и переменных РКк(п) на основе экспертных описаний вводится функция принадлежности ¡л :РКк(п) —> [0;1], определяющая для каждой функции степень выполнения условия. После этого находится функция из РК, (п), максимизирующая /у.

Мы вводим новую управляющую систему - граф нечеткого условия. Он определяется как тройка <G,p,T >, где:

G=<V,E> - неориентированный граф без кратных ребер с множеством вершин V = {(а,а),ае Е"к,а е Ек} и некоторым множеством ребер Е; р\Е-> [0;1] - веса ребер;

Т :[0;1]г [0;1] - Т-норма - бинарная операция, удовлетворяющая свойствам коммутативности, ассоциативности, монотонного неубывания и ограниченности: Т(0,х) = 0, Т(1,х) = х.

Граф нечеткого условия С реализует нечеткое условие fi:PKk{ri)-*[0;1],

степень выполнения которого для произвольной функции /(х.....,хп)е Ркк{п)

вычисляется следующим образом:

1. из множества вершин V графа G выделяется подмножество Vf={(a,f(a)),aeE"K}\

2. в графе G выделяется подграф G/=<V/,Ef>, индуцированный подмножеством Vf;

3. значением fic (/) является значение Т-нормы от весов всех ребер подграфа Gf, т.е. /.ic (/) = Т р(е). Если Ef пусто, полагаем //(/) = 1.

Класс всех графов нечеткого условия для фиксированных п, К, к и Т обозначим Ф(К,к,п,Т).

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

• Условия на значение функции в точке (задаваемые такими фразами как, например, «при максимальных значениях всех аргументов значение функции максимально» или «значение функции не превосходит значения третьего аргумента»);

• Локальное условие по одной переменной («функция не убывает по первой переменной», «функция слабо изменяется при изменении второго аргумента» и т.п.);

• Локальное условие по нескольким переменным («при совместном возрастании второй и четвертой переменных функция слабо возрастает»);

• Устойчивость (описана в разделе 3.1);

• Логические операции (конъюнкцию и дизъюнкцию нескольких условий). Далее формулируется задача выбора адекватного оператора агрегирования. Степенью выполнимости нечеткого условия ц назовем величину

/Г" = max //(/).

AVaC)

Задача определения степени выполнимости заключается в том, чтобы для данного нечеткого условия Мс> заданного графом нечеткого условия С, и данного рационального 0 < а< 1 проверить, верно ли, что > а.

Задача нахождения оптимальной функции заключается в нахождении для данного нечеткого условия //с, заданного графом нечеткого условия Се Ф(К,к,п,Т), хотя бы одной функции / е РК,(п), такой, что //с(/) = //"".

Доказательство труднорешаемости задачи формулируется в виде следующих теорем:

Теорема 2.1. При С еФ(К,к,п,Т) задача определения степени выполнимости нечеткого условия цс является ЫР-трудной для любого фиксированного 0<а<1, любого фиксированного К> 2 любого фиксированного к> 3 и любой фиксированной Т-нормы Т.

Теорема 2.2. При справедливости гипотезы Р * АГР не существует приближенного полиномиального алгоритма, решающего задачу определения степени выполнимости с результатом, отклоняющимся от истинного значения не более чем в фиксированное число раз.

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

Теорема 2.3. Если С е Ф(А',2,п,шт), то задача нахождения оптимальной функции разрешима за время 0(К2") при п —> со.

Замечание. Так как входом алгоритма является граф нечеткого условия, имеющий 2К" вершин, то такая оценка сложности является полиномиальной.

Граф нечеткого условия назовем параллельным, если все ребра в нем проводятся через пары вершин вида (а,а),(а + 6,Ь), где Зе Е"к-фиксированный вектор. Класс всех параллельных графов нечеткого условия обозначим П(К,к,п,Т). Из вышеприведенных, параллельными являются графы нечеткого условия для условия на значение в точке и локальных условий по одной и нескольким переменным.

Теорема 2.4. Если С е ЩК,к,п,Т), то задача нахождения оптимальной функции разрешима за время 0(К"*к*') при п -> со,К -»со.

Граф нечеткого условия назовем локальным, если в нем ребро между вершинами {а,а) и (Д6) может быть проведено, только если тах|£г | = 1.

Класс всех локальных графов нечеткого условия обозначим К{К,к,п,Т). Из вышеприведенных, локальными являются графы нечеткого условия для условия Л-устойчивости при А=1, условия на значение в точке и локальных условий по одной и нескольким переменным.

Теорема 2.5. Если С е А(К,к,п,Т), то при п = 1 задача нахождения оптимальной функции разрешима за время 0{кг ■ К) К со,к -» со, а для любого фиксированного п> 2 задача определения степени выполнимости условия является NP-трудной.

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

В разделе 3.1 формулируется и решаются задача проверки устойчивости для дискретного случая.

Формальная постановка задачи имеет следующий вид: F(x,,...,xK) - функция к-значной логики, заданная схемой функциональных элементов над базисом, состоящим из всех функций от и и менее переменных. Для заданного 1 < А < к-2 необходимо проверить, удовлетворяет ли F следующему условию (назовем его ^-устойчивостью):

V а, р £ ENt max|ar, - Д | < А => |F(a„....а„) - F(Д.....)| < А

В связи с этой задачей рассматриваются следующие замкнутые классы функций ¿-значной логики (классы ^-устойчивых функций):

R* = {/ е Рк: V«, Д £ E"t max|ar( - Д | < А => \/(а,,...,а.) -/(Д,.... Д )| < А }

Роль этих классов заключается в том, что они проводят грань между полиномиально-разрешимыми и NP-полными случаями задачи. Этот факт демонстрируют следующие утверждения:

Теорема 3.1.1. Если все функции, вычисляемые элементами схемы, А-устойчивы (принадлежат классу Л/), то реализуемая схемой функция также А-устойчива.

Теорема 3.1.3. Существует &(*)6 ((^ + 1)-устойчивая функция от одной

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

СФЭ над множеством (функция g и все 1-устойчивые функции от

двух переменных), со-ЫР-полна.

Теорема 3.1.4. Для любой <£ задача проверки ^-устойчивости

для функций, заданных СФЭ над множеством {/}и/?/(2)1^/(1), со-ЫР-полна.

Их содержательный смысл таков: пока все функции в базисе СФЭ принадлежат Я*, проверка свойства для реализуемой схемой функции тривиальна, но как только базис содержит функцию, не принадлежащую Я*, задача проверки становится труднорешаемой.

В разделе 3.2 формулируется и решается задача оптимального распределения ресурсов для дискретного случая.

Формальная постановка задачи выглядит следующим образом:

функция Л-значной логики, заданная схемой функциональных

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

а{,...,аК - начальные значения переменных, С^х) - стоимость замены значения

/'-ой переменной нах (вместо текущего значения). Для заданного С необходимо

максимизировать при ограничении _]_С((х.)<С, где 1. -бинарная

/

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

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

Теорема 3.2.1. Если 1 (х,у) = тах(д:,у) а базис СФЭ содержит только монотонные функции, то задача разрешима за линейное (от сложности схемы) время.

Теорема 3.2.2. Если J.{х,у) = х + у, то задача оптимального распределения ресурсов NP-полна в следующей постановке:

f(xi.....xn) - функция алгебры логики (к= 2), заданная схемой функциональных

элементов над множеством {&,v} (соответственно, F(0,...,0)=0). Для заданного натурального С необходимо проверить, существует ли такой набор

N

ссеЕ",\а\<С, такой что F(a) = l (по определению, \a\ = Y,ai)-

Следствие 3.2.2.1. Задача NP-полна в следующей постановке:

F(x.....,xN) - функция А>значной логики (к> 2), заданная схемой

функциональных элементов над множеством, содержащим функции от двух переменных min и max. Для заданного натурального С необходимо проверить, существует ли такой набор а е S С, такой что F {а) > 0. Следствие 3.2.2.2. В формулировке следствия 3.2.2.1 задача NP-трудна и для функционала стоимости А.(х,у) = ху.

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

Пусть дан ациклический ориентированный граф G с единственной корневой вершиной s.

Вершина d называется доминатором вершины v, если d лежит на каждом пути от вершины v к корневой вершине s.

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

Пусть d - сверхдоминатор, Dd ={d„...,dMt} - все сверхдоминаторы верхнего

уровня подграфа Gj (подграфа графа G, состоящего из вершины d и всех подчиненных ей вершин, а также соединяющих их ребер). Обозначим Gj = (Vj,Ed) следующий подграф: его корневой вершиной является вершина d, а листьями - вершины dv...,dMj (все вершины-потомки d.....,dM удаляются).

Нами построен алгоритм поиска всех сверхдоминаторов в графе СФЭ, который работает за время 0(р2) (р - число вершин) в общем случае и за время 0(р) в некоторых важных для приложений частных случаях (теорема 3.3.1). Имеет место

Теорема 3.3.2. Пусть 5 - схема функциональных элементов, й - ее граф, р -число вершин графа, й - множество всех сверхдоминаторов, М - максимальное число листьев в подграфах С1Пс1 е О. Тогда существуют алгоритмы решения задач проверки устойчивости и распределения ресурсов со временем работы не более С(п)-р-к" для некоторой величины С{п), зависящей только от и — максимальной полустепени захода вершин графа.

Следствие 3.3.2.1. Если М <С^р для некоторой константы С, то алгоритмы работают за полиномиальное (от числа вершин графа) время.

В разделе 3.4 результаты дискретного случая для задачи проверки устойчивости перенесены на нечеткий случай.

Пусть ср: [0;1]" -> [0;1] - оператор агрегирования, заданный па основе нечеткого вывода Мамдани1. Доопределим его на нечетких числах следующим образом. Пусть аргументы ¿¡. представляют собой нечеткие числа с треугольной функцией принадлежности Тогда значением оператора будет нечеткое число, функцию принадлежности которого мы определим как {п) = , где г = «1.....£), КЬ = гат д (£).

Обозначим длины отрезков, на которых //,(£)> 0 и р -, {?]) > 0, через ё. и д соответственно. Тогда нашей задачей будет оценить зависимость 3 от .

Теорема 3.4.1. Пусть функция £>(£,...,£,) строится на основе нечеткого вывода Мамдани. Пусть наборы функций принадлежности для входов и выхода треугольные, то есть имеют вид х — х, + а

/Ф) =

-,-а<х-х <0,

а

а-(х~х,) 1 . .

-— ,0<х-х,<а, где а =-,х, = i-a.

а к-\

0, иначе

1 Mamdam E.A. Application of fuzzy logic to approximate reasoning using linguistic synthesis. // IEEE Trans. Computers, 1977, Vol. C26, N12, pp. 1182-1191.

Пусть функция /(хр..определяющая набор правил, является 1-устойчивой. Тогда в приведенных выше обозначениях выполняется:

А

я,

о < —Ъ ■ шах 5

+ о(шах|<5||), при 6, 0, где а= ^ * ^ ,Ъ = ,

Обозначим через Рл '" «-мерный параллелепипед

.....£): < < = где - центр у-о го лингвистического

значения /'-го аргумента.

Теорема 3.4.2. Пусть функция ,...,£) строится на основе нечеткого вывода Мамдани. Пусть центры лингвистических значений выходной

переменной расположены равномерно, т.е. у, = —— Пусть функция

А 1

/(*,,.•■>■*„), определяющая набор правил, является Л-устойчивой. Тогда в приведенных выше обозначениях выполняется:

' -А}

еРГ- ^ <Р(П-<Р(П , , v 1 k-\j

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

Раздел 4.1 описывает систему оценки и мониторинга проектов разработки электронных устройств, созданную по заказу и при поддержке компании Cadence Design Systems - лидера рынка САПР (систем автоматизированного проектирования) микроэлектроники. Основными задачами, которые призвана решать система, являются:

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

• Выделить наиболее трудные (для коллектива) части проекта;

• Оценить, каким образом различные вложения средств (например, обучение, закупка оборудования) повлияют на возможности коллектива;

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

Традиционно такие задачи решают эксперты, менеджеры проекта, основываясь на своем личном опыте и интуиции. Цена ошибки на этом этапе -увеличение стоимости проекта, увеличение времени разработки изделия -вплоть до провала проекта. Поэтому любое повышение надежности оценок и

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

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

• Модель предметной области;

Функциональный прототип системы успешно прошел первичное тестирование и передан в опытную эксплуатацию в компанию Cadence Design Systems (акт о внедрении приведен в приложении 1 диссертации).

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

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

• Предложена формализация технологии информационного мониторинга в терминах теории схем функциональных элементов.

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

• Сформулирована и решена проблема проверки устойчивости для схем функциональных элементов в дискретном и нечетком случаях.

• Сформулирована и решена задача оптимального распределения ресурсов для схем функциональных элементов в различных метриках.

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

Работы автора по теме диссертации

Издания из списка ВАК:

1. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологических изделий микроэлектроники. //Известия ТРТУ, Тематический выпуск "Интеллектуальные САПР", 2006, № 8 с.93-99.

2. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологичных изделий на примере микроэлектроники //"Интеллектуальные системы" Том 11, выпуск 1-4, 2008 г., с.55-82.

Прочие издания:

3. Лебедев A.A., Рыжов А.П. Интеллектуальные вычисления в системах информационного мониторинга. // Нечеткие системы и мягкие вычисления, Том 3 №4, Тверь, РАНСМВ, 2008г. с.23-48.

Работы по материалам конференций:

4. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологических изделий. // Нечеткие системы и мягкие вычисления. Всероссийская научная конференция НСМВ-2006. Сборник трудов. Тверь, 2022 сентября 2006 г. Москва, Физматлит, 2006 с. 269-279.

5. Лебедев А. А. NP-полнота и полиномиально разрешимые случаи задач управления и проверки устойчивости для схем функциональных элементов в k-значной логике // Материалы докладов XV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», Москва, МГУ им. М.В.Ломоносова, 8-11 апреля 2008г., секция «Математика и механика», с.28-29.

6. Лебедев A.A. Синтез операторов агрегирования информации в нечетких иерархических системах по экспертным описаниям // Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А.Садовничего. Москва, 30.03-1.04 2009г. Сборник трудов, с. 364-365.

7. Лебедев A.A. О задачах распределения ресурсов и проверки устойчивости для систем информационного мониторинга // Материалы докладов XVI Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», Москва, МГУ имени М.В.Ломоносова, 14-17 апреля 2009 г., секция «Математика и механика», с. 41.

8. A.A. Lebedev, А.P. Ryjov. Design team capability and project progress evaluation based on information monitoring technology // 5lh International Conference on Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control. 2-4 September 2009, Famagusta, North Cyprus. Conference proceedings.

9. Лебедев A.A. О свойстве устойчивости для схем функциональных элементов в Ахзначной логике // Материалы X международного семинара «Дискретная математика и ее приложения». Москва, 1-6 февраля, с. 375-376.

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

Подписано в печать: 29.05.10

Объем: 1,5 усл.печ.л. Тираж: 100 экз. Заказ № 256 Отпечатано в типографии «Реглет» 119526, г.Москва, пр-т Вернадского, 39 (495) 363-78-90; www.reglet.ru

5

ГЛАВА 1. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ И АНАЛИЗ

ОСНОВНЫХ ПОДХОДОВ К ЕЕ РЕШЕНИЮ

1.1. Содержательная постановка задачи

1.2. Обзор основных подходов

1.2.1. Исследование операций

1.2.2. Имитационное моделирование

1.2.3. Экспертные системы

1.2.4. Системы поддержки принятия решений

1.2.5. Анализ иерархий

1.3. Технология информационного мониторинга

1.3.1. Основные этапы разработки и использования систем информационного мониторинга

1.3.2. Пример использования системы информационного мониторинга-Система мониторинга ядерных технологий

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

1.3.4. Формализация и обозначения

1.4. Выводы

ГЛАВА 2. СИНТЕЗ ЭЛЕМЕНТОВ СИСТЕМ МОНИТОРИНГА

2.1. Синтез операторов агрегирования информации по экспертным описаниям

2.1.1. Постановка задачи и формулировка результатов

2.1.2. Труднорешаемость задачи выбора оптимальной функции

2.1.3. Примеры условий

2.1.4. Полиномиально разрешимые случаи

2.1.5. Пример

2.2. Выводы

ГЛАВА 3. АНАЛИЗ СИСТЕМ МОНИТОРИНГА

3.1. Задача проверки устойчивости

3.1.1. Формализация и труднорешаемость

3.1.2. Полиномиально разрешимый случай

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. Выводы

ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ СИСТЕМЫ ИНФОРМАЦИОННОГО МОНИТОРИНГА

4.1. Оценка и мониторинг проектов разработки высокотехнологичных изделий

4.1.1. Cadence VCAD

4.1.2. Создание структурной модели

4.1.3. Создание поведенческой модели

4.1.4. Инициализация

4.1.5. Графический интерфейс

4.1.6. Результаты

4.2. Возможные области применения технологии информационного мониторинга

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

В 30-40 годы XX века А. Тьюрингом был предложен подход к моделированию поведения вычислительных систем, а также созданы предпосылки для возникновения соответствующей теории. Подобные системы быстро нашли применение, и интенсивная работа в этом направлении в итоге привела к возникновению новой науки - кибернетики. Основной вклад в ее создание внесли К. Шеннон и А. Тьюринг. В развитии кибернетики важную роль также сыграли Дж. фон Нейман, Н. Винер, A.A. Ляпунов, А.Н. Колмогоров, C.B. Яблонский, О.Б. Лупанов, Ю.И. Журавлев, В.Б. Кудрявцев и другие ученые. С развитием техники и математического аппарата задачи, решаемые машинами, усложнялись. Помимо чисто вычислительных задач, перед ними ставились все более интеллектуальные проблемы, такие как распознавание образов, управление сложными процессами и т.п. В результате в кибернетике возникло и со временем заняло одну из ведущих ролей понятие интеллектуальной системы [6].

В 70-е годы в этом направлении, помимо прочих, обозначились такие разделы, как системы поддержки принятия решений [51], экспертные системы [34]. Они накапливали знания о некоторой конкретной предметной области и могли принимать решения о поведении в различных ситуациях в рамках этой области, заменяя собой человека-эксперта.

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

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

Системы информационного мониторинга можно отнести к классу иерархических нечетких дискретных динамических систем. Теоретическую основу такого класса систем составляет теория автоматов, теория нечетких множеств, дискретная математика, методы анализа иерархий, которые были разработаны в работах Саати (T.L. Saaty, США) [19], Месаровича (M.D. Messarovich, США) [43], Заде (L.A. Zadeh, США) [52], Яблонского C.B. [23], Кудрявцева В.Б. [7] и других ученых. Системы, разработанные на базе этой технологии, позволяют иметь развивающуюся во времени модель проблемы на основе оценок аналитиков, подкрепленную ссылками на все информационные материалы, выбранные ими, с общими и частными оценками состояния проблемы и/или ее аспектов. Использование времени как параметра системы позволяет проводить как ретроспективный анализ, так и строить прогнозы развития проблемы (отвечать на вопросы типа «Что будет, если . ?»). В последнем случае также возникает возможность выделения «критических путей» - таких элементов (или наборов элементов) модели, небольшое изменение которых может вызвать заметные изменения в состоянии всей проблемы. Знание таких элементов имеет большое практическое значение и позволяет выявить «слабые места» вп роблеме на текущий момент времени, разработать мероприятия по блокированию нежелательных ситуаций или провоцированию желательных, т.е. в некоторой степени управлять развитием проблемы в интересах организации, ее отслеживающей.

Актуальность

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

Цели и задачи работы

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

• В теоретической части:

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

- Теоретические оценки качества работы нечеткого оператора агрегирования информации как элемента Схемы Функциональных Элементов (СФЭ) и СФЭ в целом;

- Обратная задача (задача оптимального распределения ресурсов) для дискретных СФЭ.

• В прикладной части:

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

Структура и краткое содержание работы

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

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

• Предложена формализация технологии информационного мониторинга в терминах теории схем функциональных элементов.

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

• Сформулирована и решена проблема проверки устойчивости для схем функциональных элементов в дискретном и нечетком случаях.

• Сформулирована и решена задача оптимального распределения ресурсов для схем функциональных элементов в различных метриках.

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

ЗАКЛЮЧЕНИЕ

1. Вачнадзе Р.Г., Гибрадзе Т.А., Карчаеа М.О., Маркозашвили С.Г. Методика оценки эффективности лекарственных средств на основе экспериментальных морфологических данных. // Вестник JI.MH СССР. 1988. №7, сс. 80-83.

2. Вентцелъ Е.С. Исследование операций. — М.: Советское радио, 1972, 552 с.

3. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приблизительных решений. — М.:Мир, 1976. 165с.

4. Козлов М.А., Тарасов С.П., Хачиян Л.Г. Полиномиальная разрешимость выпуклого квадратичного программирования // Журнал вычислительной математики и математической физики, 1980, Том 20, № 5, сс. 1319-1323.

5. Кудрявцев В.Б. Функциональные Системы. — М., Издательство Московского Университета, 1982. 158с.

6. Лебедев A.A. О задачах оптимального распределения ресурсов и проверки устойчивости для схем функциональных элементов в k-значной логике (готовится к печати).

7. Лебедев A.A. Синтез операторов агрегирования информации по экспертным описаниям (готовится к печати).

8. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологических изделий микроэлектроники. //Известия ТРТУ, Тематический выпуск "Интеллектуальные САПР", ISBN 5-8327-0249-2, 2006, № 8 с.93-99.

9. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологичных изделий на примере микроэлектроники // Интеллектуальные системы, Том 11, выпуск 1-4, 2008 г., с. 55-82.

10. Подколзин A.C. Компьютерное моделирование логических процессов (монография). — М., Физматлит. 2008г. 1024 с.

11. Рогожин C.B., Рыжов А.П. О нечетко заданных классах функций k-значной логики. // V Всероссийская конференция «Нейрокомпьютеры и их применение». Москва, 17-19 февраля 1999 года. Сборник докладов, с.460-463

12. Рыжов А.П. Об агрегировании информации в нечетких иерархических системах. //Интеллектуальные системы, Том 6, выпуск 1-4, 2001, с. 341-364.

13. Рыжов А.П. О степени нечеткости размытых характеристик. // Математическая кибернетика и ее приложения в биологии. Под редакцией Л.В.Крушинского, С.В.Яблонского, О.Б.Лупанова. — М., Издательство МГУ, 1987, с. 60-77.

14. Рыжов А.П. Оценка степени нечеткости ие е применение в системах искусственного интеллекта. //Интеллектуальные системы. Т.1, Вып. 1-4, Москва, МНЦ КИТ, 1996, с. 95-102.

15. Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. — М., Диалог-МГУ, 1998, 116с.

16. Саати Т. Анализ иерархических процессов. — М.: Радио и связь, 1993. 315с.

17. ТахаХ.А. Введение в исследование операций — М.: «Вильяме», 2007. ISBN 0-13-032374-8. 912 с.

18. Форрестпер Д. Мировая динамика. — М., ACT, 2003

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

20. Яблонский С.В. Основные понятия кибернетики // Проблемы кибернетики. 1959. Вып. 2. с.7-38.

21. Aspvall В., Plass M.F, Tarjan R.E. A linear-time algorithm for testing the truth of certain quantified boolean formulas. // Information Processing Letters 8 (3), 1979, pp. 121-123

22. Banks J., Carson J., Nelson В., Nicol D. Discrete-event system simulation. — Pearson, 2005.

23. Berner, E.S., ed. Clinical Decision Support Systems. — NY: Springer, 2007, ISBN 0387339140. 281 p.

24. O'Brien, J.A., Marakas, G.M. Management information systems (9th ed.). Boston, MA: McGraw-Hill/Irwin. 2009

25. Buchanan B.G., Shortliffe E.H. (eds.). Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project. — The Addison-Wesley series in artificial intelligence, 1984.

26. Cocke J. Global common subexpression elimination. // ACM SIGPLAN Notices 5:7. 1970, pp 20-24

27. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. // 1976, SIAM J: Comput. 5, pp 691-703

28. Fayyad U.M. (Ed.). Advances in Knowledge Discovery and Data Mining.— MIT Press, 1996. 560p.

29. Garey, M.R.; Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York: W.H. Freeman. 1979. ISBN 0-7167-1045-5

30. Gholam-Nezhad H., Kathawala Yu. Risk Assessment for International Investment.//Management Research News, 1990, Vol. 13, Iss. l,pp 1-8.

31. Jackson P. Introduction to expert systems — Addison-Wesley, 1999, ISBN 0-201-87686-8, 542pp.

32. Jintrawet A. A Decision Support System for Rapid Assessment of Lowland Rice-based Cropping Alternatives in Thailand. // Agricultural Systems, 1995, Vol. 47, pp 245-258.

33. Kaplan R.S., Norton D.P. The balanced scorecard: measures that drive performance. // Harvard Business Review Jan — Feb 1992 pp. 71-80.

34. Karp R.M. Reducibility among combinatorial problems // Complexity of computer computations, 1974, Plenum Press, NY, pp 85-103

35. Libecap G.D. University entrepreneurship and technology transfer: process, design, and intellectual property. — ELSEVIER, 2005. 31 lp.

36. Mamdani E.A. Application of fuzzy logic to approximate reasoning using linguistic synthesis. // IEEE Trans. Computers, 1977, Vol. C26, N12, pp. 1182-1191.

37. Martin Michael J.C. Managing innovation and entrepreneurship in technology based firms. — NY: John Wiley & Sins, Inc., 1994. 402p.

38. Matsatsinis N.F., Siskos Y. Intelligent support systems for marketing decisions. — Kluwer Academic Publishers, 2002.

39. Matzke W.E., Strube G„ Schmidt-Habich H., Drenan L. VCAD a virtual enterprise collaboration model impacting the semiconductor industry. // IASTED International Conference on Knowledge Sharing & Collaborative Engineering (KSCE 2004).

40. Messarovich M.D., Macko D., Takahara Y. Theory of hierarchical multilevel systems. — Academic Press, N.Y. London, 1970. 344p.

41. Pardalos P.M., Vavasis S.A. Quadratic programming with one negative eigenvalue is NP-hard. //Journal of Global Optimization, Vol. 1, Number 1, 1991, pp.15-22.

42. Ryjov A. Basic principles and foundations of information monitoring systems. // Monitoring, Security, and Rescue Techniques in Multi-agent Systems. Springer, 2005. pp. 147-160.

43. Ryjov A., Belenki A., Hooper R., Pouchkarev V., Fattah A., Zadeh, L.A. Development of an Intelligent System for Monitoring and Evaluation of Peaceful Nuclear Activities (DISNA) //IAEA, STR-310. Vienna, 1998. 122p.

44. Saaty T. Theory and Applications of the Analytical Network Process: Decision Making with Benefits, Opportunities, Costs and Risks. — RWS Publications, 2005, ISBN 1-888603-06-2. 352 pp.

45. Shoham Y., Ley ton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.

46. Tarjan R. Finding dominators in directed graphs. // SIAM J Computing, 1974, 3, №1, pp. 62-89

47. Turban E., Aronson J.E., Liang T.-P., Sharda R. Decision Support Systems and Intelligent Systems. — Prentice-Hall, Inc. Upper Saddle River, NJ, USA, 2006, ISBN 0131986600, 850 p.

48. Zadeh L.A. Fuzzy sets. // Information and Control, 1965, v.8, pp. 338-353.

49. Zeigler B.P., Praehofer H., Kim T.G. Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems 2nd edition. — Academic Press, 2000.