Разработка формальных моделей рассуждающих сетей для анализа параллельных событийных процессов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Анисимов, Михаил Михайлович

• Анисимов, Михаил Михайлович
• кандидат физико-математических наук
• 2009

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

Введение.

Глава 1 Событийные сетевые модели

1.1 Понятие сущности.

1.2 Понятие семантической сети.

1.3 Понятие рассуждающей сети (RN).

1.4 Понятие процесса.

1.5 Понятие процессорной сети (PN).

1.6 История развития сетевых моделей

1.6.1 Сети Петри.

1.6.2 Алгебраические сети (AN).

Вычислительные модели Э. Тыугу.

1.6.3 Joiner-сети.

1.6.4 Дискретные нейронные сети

Мак Каллока-Питтса (VN).

1.6.5 Вычислительные сети (CN).

1.6.6 Сети Ван-Хао (WN).

Выводы.

Глава 2 Формализация сетей Ван-Хао

2.1 Когнитивная карта.

2.2 Построение когнитивной карты по данным опроса экспертов.

2.3 Логика исследования сети Ван-Хао.

2.4 Задачи формализации.

2.5 Процессорное представление для WN.

2.6 Формы представления сценариев возбуждения для WN.

2.7 Система логических уравнений для WN.

Выводы.

Глава 3 Автоматное представление событийных сетей

3.1 Формальная интерпретация JN сетью автоматов.

3.2 Внутренняя структура элементарного автомата и правила его работы в сети.

3.3 Асинхронный автомат Малера.

3.4. Пространство состояний автомата.

3.5. Алгебраические решетки для представления и анализа данных

3.6. Поведение ААМ в ситуационном пространстве.

3.7. Композиции сетей WN.

Выводы.

Глава 4 Асинхронное управление в сетях Ван-Хао

4.1 Асинхронное управление в живых и неживых системах.

4.2 Задача разметки сети управляющими функциями

4.3 Задача построения тормозящих процессов.

Выводы.

Глава 5 Примеры построения формализации для реальных событийных сетевых моделей

5.1 Пропозиционная сеть для экспертных систем

5.1.1 Описание экспертных правил.

5.1.2 Построение формализованной модели.

5.1.3 Построение системы уравнений.

5.2. Событийная рассуждающая модель для исследования динамики цен в Российской экономике.

5.2.1 Выбор сущностей.

5.2.2 Описание причинно-следственных связей.

5.2.3 Построение формализованной модели WN.

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

5.4 Событийная рассуждающая модель для анализа энергетических катастроф.

Выводы.

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

Рассуждающие сети представляют собой конечную совокупность элементарных рассуждений вида: «если (р , то (р>>, объединенных в сети. В диссертации рассматриваются событийные сети с причинно-следственными утверждениями вида: если произошло событие ср., то оно вызывает событие (р .

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

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

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

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

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

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

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

Научная новизна. В результате проведенных исследований, анализа и обобщения опыта по формализации сетей Ван-Хао получены следующие научные результаты:

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

• доказаны теоремы о представлении сети Ван-Хао в виде Joiner-сетей и процессорных сетей, обосновывающие корректность проведенной формализации;

• впервые осуществлено представление поведения сети в виде асинхронного автомата Малера, которое дало возможность рассматривать развитие возбуждения из произвольного состояния и ввести условия для реализации асинхронного управления;

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

• построен Joiner-элемент для введения тормозящего процесса с целью парирования неблагоприятных ситуаций.

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

История исследование началась с практической задачи, поставленной экспертами Института система энергетики им. JI.A. Мелентьева СО РАН. Оказалось, что разработанный инструментарий также востребован в аналитических департаментах компаний ЗАО «ВТБ Капитал», Москва и VTB Capital pic., London, так как в процессе исследований аналитики столкнулись с проблемой анализа сетей, содержащих значительное количество сущностей, и отсутствием возможности формализовано записать такие сети.

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

Результаты, полученные в диссертационной работе, входят в состав исследований при поддержке грантов РФФИ 08-07-00198 «Интеллектуальная система обработки данных для моделей с рассуждающими сетями» и 08-0700200 «Модель противодействия рейдерству (захвату собственности), использующая интеллектуальную, самосинхронизирующуюся Joiner-сеть».

Логика построения работы и ее содержание

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

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

Рассмотрение формальных объектов событийных сетей сопровождается примерами.

Во второй главе рассмотрен формальный аппарат сетей Ван-Хао. Даны основные определения и теоремы. Глава содержит логику исследования, которую удобно представить в виде последовательности преобразования одних формальных объектов в другие: KK-WN-(PN-JN)~AAM, где КК- когнитивная карта, WN-сеть Ван-Хао, PN-процессорная сеть, JN-Joiner-сеть, а ААМ— асинхронный автомат Малера. Подобный подход раскрывает ряд новых возможностей анализа, недоступных при использовании интуитивной интерпретации сетей Ван-Хао. В заключение главы приводится постановка основной задачи диссертации: построение формализованной обобщенной модели сети Ван-Хао, механизмов ее описания, анализа, логики управления прохождением возбуждения в сети WN, а также создание собственно способов построения управляющих воздействий для расширения возможностей анализа и выработки практических рекомендаций по управлению.

В третьей главе содержится построение модели распространения возбуждения в произвольной Joiner-сети в виде сети некоторых элементарных автоматов. Для булевских функций в сети Ван-Хао детально рассматривается асинхронный автомат Малера, который дает возможность анализа параллельно протекающих процессов возбуждения событий и их взаимного влияния.

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

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

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

1. Доказаны теоремы о преобразовании исходной сети в последовательность формальных объектов: WN-(PN-JN), где WN-сеть Ван-Хао, PN-процессорная сеть, JN-Joiner-сеть, обеспечивающих корректность формализации.

2. Введено понятие «исторической памяти» и доказана теорема о представления работы произвольной Joiner-сети в виде набора элементарных автоматов. Построен вид автоматного представления формализованной сети Ван-Хао с помощью асинхронного автомата Малера.

3. Исследована задача достижимости и выводимости конечных цепочек событий.

4. Предложен метод построения траекторий в ситуационном пространстве с помощью алгебраических решеток: диаграммы Вейча и гиперкуба;

5. Разработан инструментарий для асинхронного управления сетями Ван-Хао посредством Joiner-сетей специального вида.

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

Заключение диссертации по теме «Теоретические основы информатики», Анисимов, Михаил Михайлович

Выводы.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

1. Доказаны теоремы о преобразование исходной сети: WN-(PN-JN), где WN-сеть Ван-Хао, PN-процессорная сеть, JN-Joiner-сеть, обеспечивающие корректность формализации.

2. Введено понятие «исторической памяти» в сети и доказана теорема об автоматном представлении работы сети как набора элементарных автоматов с целью подготовки сети к аппаратной реализации.

3. Разработан вид асинхронного автомата Малера для описания работы сети Ван-Хао, что позволило изучать развитие возбуждения в сети из произвольного начального состояния.

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

5. Разработан инструментарий для управления сетями Ван-Хао посредством разработки Joiner-сетей специального вида.

6. Представлен ряд примеров реальных систем и в них проведен анализ развития процессов возбуждения.

Эффективность разработанных в диссертации теоретических положений, моделей и методов подтверждена их использованием в разработках по моделированию катастроф в электроэнергетике (ИСЭМ СО РАН), аналитических системах по построению социальных и макроэкономических моделей (ЗАО «ВТБ Капитал» и VTB Capital pic., London), а также системах по организации защиты информации.

Список литературы диссертационного исследования кандидат физико-математических наук Анисимов, Михаил Михайлович, 2009 год

1. Пирс, Ч. С. Принципы философии. — СПб., 2001.

2. Richens, R.H. and Booth A. D. "Some methods of mechanized translation". — Cambridge, Mass.: Technology Press of MIT, 1955.

3. Варшавский В.И. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах М.: Наука, 1986. — 308 с.

4. Bernstain P. Description problems in the modeling of asynchronous computer systems // Tech. Report / Univ. of Toronto. 1973. - N 48.

5. Petri C.A. Kommunication mit Automaten. Schriften fur des Rheinich-Westfalischen Inst. Fiir Instrumentalle Mathematik. Univ. Bonn. — Bonn, 1962.

6. Котов B.E. Сети Петри. M.: Наука, 1984. - 160 с.

7. Dijkstra Е. W. Cooperating sequential processes // Programming Languages / NATO Advanced Study Institute. Academic Press, 1968. - P. 43-112.

8. Мальцев A.M. Алгебраические системы. — M.: Наука, 1970. — 392 с.

9. Xudong Не, John А. N. Lee A methodology for Contructing Predicate Transition Net Specifications // Software Practice and Experience. - 1991. - V. 21, N8.-P. 845-875.

10. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971. — 320 с.п. Клини С.К. Введение в математику. М.: ИЛ, 1957. — 526 с.

11. Минский М. Структура для представления знания // Психология машинного зрения. М.: Мир, 1978. - С. 249-338.

12. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984. — 256 с.

13. Столяров Л.Н., Новик К.В. Joiner-сеть для моделирования взаимодействующих параллельных процессов // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. М., 2004. - С. 81-97.

14. Столяров Л.Н., Новик К.В. Реализация параллельных процессов с помощью сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2004. - С. 11-14.

15. Мак-Каллок У.С., Питтс У. Логическое исчисление идей, относящихся к нервной активности // Автоматы, под ред. Шеннона К.Э. и Маккарти Дж. -М.:ИЛ, 1956.-С. 362-384.

16. Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 392 с.

17. Столяров JJ.H. Структурный анализ численных алгоритмов для параллельных и конвейерных вычислений: Дисс. докт. физ.-мат. наук. — М.: МФТИ, 1987.

18. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. -М.: Син-тег, 1998, — 376 с.

19. Ed. R. Axelrod. Structure of Decision. The cognitive Maps of Political Elites /N.Y.: Princeton, 1976.

20. M.M. Анисгшов Асинхронный автомат Малера как способ интерпретации обобщенных сетей Ван-Хао// Моделирование и обработка информации. Сб. научных трудов. / Моск. физ-тех. ин-т. -М., 2009. — С. 116-117

21. М.М. Анисгшов, JI.H. Столяров Анализ экономических процессов с применением событийных, ситуационных и тормозящих сетей// Вестник компьютерных и информационных технологий, М.-2009.- №11(65). С. 2229.

22. Новик К.В. Сеть автоматов для моделирования асинхронных процессов // Вестник ИрГТУ / ИрГТУ Иркутск, 2005. - №4 - С. 51 -56.

23. М.М. Анисимов Расширение сетей Ван-Хао для анализа «сложных» процессов/ Современные технологии. Системный анализ. Моделирование, ИрГУПС.-2009.- №3(23). С. 239-245.

24. Трахтенгерц Э.А. Компьютерная поддержка сложных организационно-технических систем, 2002— 160 с.

25. Зайцев Д. А. Инвариантность модели Петри протокола TCP // Научные труды Одесской национальной академии связи им. А.С. Попова. 2004. — №2.-С. 19-27.

26. Айзерман М.А., Гусев Л.А., Розоноэр Л.И. и др. Логика. Автоматы.

27. Алгоритмы. 1963., 556стр.,

28. Muller D.E. Lecture Notes on asynchronous circuits theory. Urbana: Univ. of Illinois, 1961.

29. Xoap Ч. Взаимодействующие последовательные процессы. M.: Мир, 1988.- М.: Мир. -264 с.

30. Richard W. Hamming Error-detecting and error-correcting codes, Bell System Technical Journal 29(2): 147-160, 1950.

31. К.Г. Самофалов, A.M. Романкевич, B.H. Валуйский, Ю.С. Каневский, М.М. Пиневич "Прикладная теория цифровых автоматов", Киев, "Вища Школа", 1987

32. И.С.Потёмкин "Функциональные узлы цифровой автоматики", М.: Энер-гоатомиздат, 1988

33. У. Росс Эшби Конструкция мозга- М.: Мир, 1964. 410 с

34. Сакс Дж., Ларрен Ф. Макроэкономика. Глобальный подход,—М.: Дело, 1996,-848 с.

35. М.М. Анисимов Интерпретации рассуждающих сетей Ван-Хао // Информационные технологии в науке, социологии, экономике и бизнесе. Приложение к журналу «Открытое образование». XXXVI международная конференция. IT+SE'09. / МГАПИ.-М., 2009. -С. 147-150.

36. М.М. Анисимов. Аномалия в сетевой модели Ван-Хао финансового сектора США.// Моделирование и обработка информации. Сб. научных трудов. /Моск. физ-тех. ин-т. -М., 2008. — С.160-161.

37. М.М. Анисимов Применение сетевых моделей для мониторинга кризисов валютных рынков развивающихся стран.// Моделирование процессов обработки информации. Сб. научных трудов. / Моск. физ-тех. ин-т. -М., 2007. —С.92-93.

38. М.М. Анисимов Рассуждающие сети Ван-Хао. Анализ и практическое применение.// Вестник компьютерных и информационных технологий, М.-2009.- №7(61). С. 22-27.

39. Steven Levitt and Stephen J. Dubner Freakonomics: A Rogue Economist Explores the Hidden Side of Everything. William Morrow/HarperCollins. (2005).

40. Пухалъский Г.И., Новосельцева Т.Я. Цифровые устройства—СПб.: Политехника, 1996. 885 с.

41. Новик К.В. Исследование Joiner-net для управления синхронизацией данных // Процессы и методы обработки информации: Сб. научных тру-дов/Моск. физ.-тех. ин-т. -М., 2005. С. 31-39.

42. М.М. Анисимов, JJ.H. Столяров. Как организовать искусственную аномалию в рассуждающей сети // Моделирование и обработка информации. Сб. научных трудов. / Моск. физ-тех. ин-т. -М., 2008. — С.160-161.

43. М.М. Анисимов Управление событийными сетями//Труды XIV Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении». / ИСЭМ СО РАН. Иркутск, 2009. -Часть 3-С. 238-240.

44. М.М. Анисимов Искусственная аномалия-рейдер (Black Swan) в рассуждающей сети Ван-Хао // Современные достижения в науке и образовании: Сб. трудов II международная научная конференция. / г. Нетания (Израиль).-Хмельницкий: ХНУ, 2008-233с., С. 103