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

00505^

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

Карпухин Илья Николаевич

Исследование и реализация систем дискретно-событийного имитационного моделирования на основе графовых моделей

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

4 АПР 2013

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

Москва, 2013

005051273

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

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

Официальные оппоненты:

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

Кораблин Юрий Прокофьевич

доктор технических наук, профессор, профессор кафедры моделирования систем и сетей федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Российский государственный социальный университет» Фальк Вадим Николаевич

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

Аникеев Александр Викторович

кандидат технических наук, доцент, главный специалист ООО «КВАРЦ — Новые Технологии»

Федеральное государственное бюджетное учреждение науки Институт системного анализа Российской академии наук (ИСА РАН)

Защита состоится «17» апреля 2013 г. в 15-30 на заседании диссертационного совета Д 212.131.05 при МГТУ МИРЭА по адресу:

Москва, 119454, пр-т Вернадского, д. 78, Д412

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан «16» марта 2013 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу 119454, г.Москва, пр-т Вернадского,78, диссертационный совет Д 212.131.05

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

Е.Г. Андрианова

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

Актуальность темы исследования. Имитационное моделирование является мощным инструментом исследования поведения реальных систем. Методы имитационного моделирования позволяют собрать необходимую информацию о поведении системы путем имитационного эксперимента над её математической моделью. Полученная информация используется затем для изменения или проектирования новой системы.

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

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

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

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

Объект работы — модели дискретно-событийного имитационного моделирования, базы знаний на их основе.

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

Цель работы - повышение эффективности процессов создания моделей поведения систем и программ, разработка программного комплекса, используемого для повышения эффективности компьютерного

др.

моделирования на основе баз знаний, хранящих информацию о поведении систем.

Решаемые задачи. Для достижения поставленной цели в работе решаются следующие задачи.

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

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

3. Реализация модели и алгоритмов в виде программных библиотек общего назначения.

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

5. Создание на основе библиотек прикладного программного комплекса G-IPS Ultimate для интерактивного манипулирования моделями представления знаний и проведения имитационных экспериментов.

6. Применение программного комплекса G-IPS Ultimate для получения теоретических и прикладных результатов, использование в учебном процессе.

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

Достоверность результатов обосновывается доказательством свойств предложенных моделей и подтверждается объёмными вычислительными экспериментами.

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

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

широкий спектр прикладных и учебных задач при сохранении простоты интерпретации, присущей продукционным моделям.

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

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

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

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

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

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

Разработан и апробирован программный комплекс G-IPS Ultimate. Данный комплекс можно использовать как при решении прикладных задач, так и в учебном процессе: при проведении лабораторного практикума по таким дисциплинам как исследование операций и принятие решений, теория игр, экспертные системы, имитационное моделирование, интеллектуальные системы, при выполнении курсовых и дипломных проектов.

Внедрение. К настоящему моменту разработанный программный комплекс внедрён ФГБУ «Федеральный Научно-Клинический Центр Детской Гематологии Онкологии и Иммунологии имени Дмитрия Рогачева» министерства здравоохранения РФ для моделировании бизнес-процессов, а

также в учебный процесс Российского государственного социального университета.

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13 международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2007 г.), научно-практической конференции студентов, аспирантов, молодых ученых и специалистов: «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (г. Коломна, 2009 г.), на научных семинарах РГСУ и НИУ ВШЭ.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы (117 наименований) и 3 приложений. Общий объём диссертационной работы составляет 142 страницы в основной части и 179 страниц приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации, формулируются цели и задачи исследования, научная новизна, теоретическая и практическая значимость работы.

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

При изучении задач ИМ очень важно понимать то, как учитывается время в конкретной задаче. Оно может быть дискретным (например, при моделировании систем, основанных на системах массового обслуживания (СМО)), непрерывным (например, для задач физического моделирования) или не учитываться (например, для задач статистического моделирования). Чтобы определить круг наиболее актуальный задач, были исследованы модели времени в ИМ: дискретно-событийное моделирование, непрерывное моделирование, моделирование Монте-Карло. Обоснован выбор дискретного представления времени, так как данная модель позволяет охватить наиболее широкий (по сравнению с непрерывным моделированием) круг актуальных задач ИМ (моделирование систем, основанных на СМО, моделирование

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

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

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

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

Было рассмотрено и систематизировано более 20 наиболее известных и широко используемых программных средств имитационного моделирования, таких как:

• средства визуального моделирования широкого назначения (например, AnyLogic by XJ Technologies, SIMUL8);

• системы визуального моделирования узкого назначения (COMNET III by CACI Products - моделирование информационных сетей, MedModel by PROMODEL Corporation - моделирование больничных комплексов);

• специализированные языки программирования (GPSS by Minuteman Software, SIMNETII by Hamdy A. Taha);

• библиотеки, используемые для ИМ на основе языков программирования общего назначения (Ascape by The Brookings Institution (Java), SimPy by SimPy Developer Team (Python).

Особый акцент сделан на рассмотрение программных средств ИМ, используемых в учебном процессе в российских ВУЗах: РДО (разработанное в МГТУ им. Баумана) и SIMPR-Windows (разработанное в НИУ МЭИ).

Проведённое исследование показало, что наиболее ранние средства преимущественно представляют собой низкоуровневые средства моделирования и особые языки программирования, которые хоть и отличаются полезными инструментами для моделирования, малопригодны для решения современных задач в виду сложности синтаксиса. Большинство современных средств являются высокоуровневыми средствами визуального проектирования или интегрированными средами разработки с поддержкой современных языков программирования, как универсальных (например, Java, С++, Python) так и предметно-ориентированных (GPSS, Omola). В российской высшей школе при изучении дисциплин связанных с интеллектуальными системами в большинстве случаев используются малоизвестные программные средства, разработанные на кафедрах, и ориентированные на узкий круг задач.

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

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

Предлагаемая модель представления знаний расширяет область определения продукционных правил, с помощью алгебры L = <Q, +, ~>, где О = {Т, F, Е) — множество из трёх элементов (Т — «истина», F— «ложь» и Е — «ошибка»), «+» - коммутативная операция суммирования (+: ÍÍ2 —> О.) и «~» — некоммутативная операция квазисравнения Q2 —> Q). Эти операции не полны, но удобны для реализации процесса интерпретации модели, описываемой далее. Определение этих операций задаётся аналитически.

Операция суммирования:

• X¡+x2=T О Xl=x2=T,

• xj+x2=F О (х/ £ {Т, F} и Х2 € {Т, F} и Х1ФХ2) или x¡=x¿=F,

• xi+x2=E О х]=Е ИЛИ х2=Е.

Операция квазисравнения:

• х1~х2 = Т О х1=х2,

• х1~х2 = ^ О х[фх2 И Х/^Д

• Х/~Х2 = £ О X[~фХ2 И Х/^.

Таблицы истинности для данных <

Таблица 1. Таблица истинности операции суммирования

Т F Е

т т F Е

F F F Е

Е Е Е Е

й приведены в таблицах 1 и 2.

Таблица 2. Таблица истинности операции квазисравнения

Xi\X2 Т F Е

Т т F F

F F Т F

Е Е Е Т

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

Предлагается описывать систему правил в виде набора решающих графов RGS = {RG*}.

RGt = < D,M,A,S > - ¿-дольный конечный решающий граф (t > 3), где:

• D = (Х1м ...,Хк) - вектор (к = t — 2), в котором XL = Í4í,i» 4i,2> —>4i,n) — непустой вектор датчиков г-го порядка, i > 1, п > 1 — конечные, Х\ — вектор простых датчиков (или датчиков первого порядка), значение которых задаёт функция интерпретации, присваивая вектор исходных значений, (Х2, Хз, ... Xt¡) - векторы (слои) датчиков более высокого порядка (второго, третьего и т.д.), их значения определяет функция интерпретации по значениям датчиков предыдущего порядка. Датчик q¡j задается парой <val, Соп>; где val ей- значение датчика; Con = {<id, vv>} - непустое множество пар <id, w>, где id е [1.. \Xi+11] для слоев от 1 до (t-2) и id G [1.. |Л/|] для датчиков (М)-го слоя — индекс датчика более высокого порядка, т.е. дуга, связывающая датчик q¡j с датчиком более высокого порядка, w £ Í1 — вес дуги.

Таким образом, датчик определяется своим значением val, и взвешенными связями с датчиками более высокого порядка Con — множество пар «связь-вес», где вес ребра означает ожидаемое значение; на рис. 1 эти веса обозначены цветом дуг;

• М = (<7с-1,1><7£-1,2> ■■■> 4t-i,z) ~ непустой вектор датчиков высшего порядка, z > 1. Датчик qt-¡j отличается от датчиков более низкого порядка отсутствием логических связей, он определяется лишь

значением qt.\j = val e Q. Так как первый индекс датчиков доли М всегда равен (í-1), в дальнейшем будем его опускать;

• А = (аь «2,..., ар) — непустой вектор действий, р > 1; a¡ -идентификатор действия (реально выполняемое действие определяется интерпретацией);

• S — матрица размером \М\ х \А\, устанавливающая связь между датчиками высшего порядка и действиями. Элементом данной матрицы является либо пустой элемент (отсутствие связи) либо тройка s¡j = <ord, lv, rv>, где

o ord - целое число, такое, что нуль означает отсутствие действия для данного правила, а любое другое число означает приоритет действия в наборе действий подлежащих выполнению, о lv — левая допустимая граница вероятности (из отрезка [1, 100]); о rv — правая допустимая граница вероятности (из отрезка [1, 100]).

Рассмотрим обозначения весов дуг на решающем графе (рис. 1).

Рис. 1. Обозначения весов дуг в решающем графе

Вес дуги (ожидаемое значение датчика) обозначается графически так: Т (истина) — зелёным или белым цветом в зависимости от режима отображения (цветной/монохромный), .Р (ложь) - красным или чёрным, Е (ошибка) -серым или штрихованным.

На рис. 2 представлен пример решающего графа.

Рнс. 2. Пример решающего графа

Множество И (рис. 2) содержит 2 множества Х\ и Хг, где вектор Хг содержит датчики (1.1, 1.2, 1.3, 1.4), а Хг содержат датчики 2.1-2.3, множество М содержит датчики 3.1-3.5, и вектор действий А = (1, 2, 3), а матрица 5 =

1 2 3

3.1 1/1/100 2/1/100 0

3.2 1/1/100 0 2/1/100

3.3 0 2/1/100 1/1/100

3.4 0 1/1/100 0

3.5 0 0 1/1/100

Рассмотрим процесс интерпретации решающего графа. Неформально, интерпретация — это некоторая функция, которая ставит в соответствие вектору входных значений упорядоченное мультимножество действий. Формально определим функцию интерпретации FIFp^RGt —> В, где

• RGt — решающий граф;

• § £ [1, 100] — случайная величина (для каждой итерации генерируется заново) - зерно (random seed)',

• В = {B¡ 6 RGZ.A], — частично упорядоченное по приоритетам мультимножество элементов из А, где / > 0. То есть, на мультимножестве В определено отношение частичного порядка р такое, что:

V a¡, a.j+1 £ В ctj р aJ+1, где о,, aj+1 получены из датчика qk<S>S(M.qk,a¡).ord < S(M.qk,a]+1).ord, где; £[1..|В|];

• FP(RG', Q есть тройка <FS, FQ, FA>, где

о FS((vh)): {Xi.qu.val} Д i £ [1..[RG^X^], h = \RG'X^\ - функция, задающая значения датчиков первой доли; будем говорить, что функция FS применяет вектор (v¿) к датчикам первой доли, присваивая соответствующие значения; о FQ = OS,i, ... , ft-i.n) - система функций, где f{i+\)j: {#¡+u}—► A i £

[1.. (t - 2)],; £ [1.. |*¡+11], к £ [1.. n = \M[, о FA = (гi, ..., r„) — вектор процедур, заполняющих мультимножество В элементами из А, согласно матрице S; где п = \М\. (уь) - вектор входных значений, h £ [1.. |пС.Хг|], переменные со значениями из Q, определяемые вне интерпретации;

Функция FI ставит в соответствие любому вектору (va) мультимножество В, содержащее элементы из А.

Значение val датчиков, принадлежащих долям от 2 до (/-1), вычисляется следующим образом:

(1) qi+1J.val = fi+1J : Xi -> П, где i £ [1.. (t - 2)], j £ 1.. |*i+1|]

(2) ft+ij = T + Zt(4i,k-val ~ 4i,k■ wk); VqUk-.j £ Con-, где i £ [1.. (t - 2)],

j e[i..|x(+1|],fc 6[i..|*i+ill;

То есть, до того, как мы начинаем вычислять значения датчиков, принадлежащих долям от 2 до (М), их значение равно Т, а пришедшие с датчиков значения суммируются так: к текущему значению датчика q(¡+iy прибавляем результат квазисравнения ожидаемого значения со значением датчика, принадлежащего предыдущей доле, связанного через Con с датчиком qu+\)j.

Вектор FA сопоставляет /-му датчику высшего порядка процедуру г„ которая добавляет в мультимножество В подмножество действий B¡ £ А, которые связаны с í-m датчиком высшего порядка элементом матрицы S, удовлетворяющим зерну то есть:

(3) В; = {ак \S(qt, ак) Ф 0; 5(q¡, ak). lv < ? < 5(q¡, ak). rv},

V qi : val = Г имеем r¡ SFA-B UB¡, где г e [1.. \RGt.M\], к € [1..|Л|].

Следует отметить, что разные действия могут иметь один и тот же

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

V a¡, az ё В •■ S(q}-, a¡). ord = S[fl¡, az). ord имеем a¡ <p az, для i < z, i £ [1..И1 ],z e [1.. |i4|],y e [l..|M|] или

V at, az £B: S{c¡j,a¡).ord = S(qk,az~).ord имеем a¡ <p а2,для j < k, i £ [i..\A\],z e [i..\A\U e [i-.|M|],fc e [i..|M|],

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

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

Рассмотрим пример использования решающего графа (рис. 3) для задачи диагностики.

Рис. 3. Пример решающего графа

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

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

В третьей главе также определены такие свойства решающего графа как полнота/неполнота, однозначность/неоднозначность, эквивалентность.

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

RG — полный О V(n) функция интерпретации сопоставляет Вфф.

Будем говорить, что решающий граф RG является неоднозначным, если существует такой вектор (v/¡), которому функция интерпретации сопоставляет не менее двух датчиков из Мсо значением «истина».

RG - неоднозначный О 3 (vh): М'бМ, где М' = {qL\val = Т}, \М'\ > 2.

Решающий граф может быть:

• неполным и однозначным (рис. 4);

• неполным и неоднозначным (рис. 5);

• полным и однозначным (рис. 6);

• полным и неоднозначным (рис. 7).

l:q-l l:m-l

Рис. 4. Неполный и однозначный RG3

Рис. 5. Неполный и не однозначный RG3

Рис. 6. Полный и однозначный RG3

Рис. 7. Полный и неоднозначный RG3

Будем говорить, что решающий граф RG' эквивалентен решающему графу RC, если:

• RG'JC\ = RGPХ\ — то есть у них идентичный набор датчиков первого порядка;

• RG'.A = RC.A - то есть у них идентичный набор идентификаторов действий;

• любому вектору входных значений (уи) функция интерпретации решающего графа RGXRC) ставит в соответствие тот же набор действий, что и для решающего графа RGp(RG'y,

Доказано утверждение: для любого t-дольного решающего графа RG' (t > 4) существует эквивалентный трёхдольный решающий граф RG3. Приводится алгоритм построения эквивалентного трёхдольного решающего графа. Используя утверждение и алгоритм, можно находить решение за наименьшее время вне зависимости от начальной топологии модели.

Использование решающих графов для визуализации и формализации продукционных правил знаний даёт следующие преимущества:

• удобство визуализации и наглядность процесса принятия решений;

• возможность описывать различные компоненты системы на разном уровне абстракции;

• возможность легко строить и модифицировать уже существующие модели;

• возможность распараллеливать различные этапы принятия решений;

• возможность автоматически преобразовывать модель в более эффективную (по скорости принятия решений) без изменения системы правил (на основе утверждения о сведении моделей) и др.

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

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

На основе математических алгоритмов описанных в главе 3 разработаны библиотеки, содержащие функции верификации, интерпретации, сводимости и обработки моделей. Данные библиотеки легли в основу следующего программного комплекса G-IPS Ultimate, поддерживающего такие режимы работы как:

• создание и редактирование моделей, представленных решающими графами;

• тестирование и прояснение внутренней логики модели (режим кларификации);

• режим тестовой имитации с остановкой после каждого шага имитации;

• режим рабочей имитации с демонстрацией динамики процесса;

• режим демонстрации ранее проведённой имитации.

Комплекс G-IPS Ultimate реализован как И^'и^оую-приложение (рис. 8) и содержит ряд инструментов, позволяющих строить модели для самых разных задач, например:

• средства для обучения оперативно-диспетчерского персонала сложных систем (тренажёры);

• экономические модели, основанные на методе Монте-Карло;

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

• игровые модели;

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

Приложение G-IPS Ultimate имеет следующие объёмные характеристики.

Среда разработки Число строк исходного кода Объём исходного кода Объём машинного кода

CodeGear RAD STUDIO 2007 >10200 > 230 Кб -2.3 Мб

Ultimate <càr_test.gips>

0le Project Щей Help Щ5 С ri; » j«|

Oj Ей Ы :: © (§ (TTcar's Tactics

Project Structure

e 58SKS3EH

B Coordinator 6 Us Car's Tactics B fn 5imple Que: ; 4. OSL

;.....->j Green? >

i- UhM

i.....WGreer

■■■ <ij Danger B Complex Ql m-0

__; t m-l _ I

i.^rjgtorjca^s Tactics ]_=__

» a ± Ï T

A UN

Object Inspector

ID* (l

Caption ÎGreen? Description ! Горит зеленыг In parallel with i Name isjight_is_gree

[internal step] I.*} m-4: NotDef + False[True] — False [internal step] 1.5 m-5: False + False[True] = False [internal step] 1.4 m-4: False + True[True] = False

■/ Ц »

Передать ход светофору

Рис. 8. Окно редактора G-IPS Ultimate

Для обеспечения взаимодействия комплекса G-IPS Ultimate с внешними модулями были разработаны специальные низкоуровневые интерфейсы:

a) интерфейс для подключения внешних ¿///-модулей, реализующих взаимодействие конкретной модели с внешней средой;

b) интерфейс для подключения ¿///-модулей, расширяющих функциональное наполнение комплекса G-IPS Ultimate, например, генераторов, валидаторов моделей и т.п.

G-IPS Ultimate обеспечивает взаимодействие построенной модели с внешним модулем (DLL), имитирующим внешнюю среду для системы. Шаг прогона модели можно условно разделить на два этапа. На первом этапе (рис. 9) G-IPS Ultimate запрашивает значения элементарных датчиков из подключаемого внешнего модуля (DLL), используя низкоуровневый интерфейс API Gipslnclnde. Помимо самого значения функции, из dll-модуля может поступить команда редактору G-IPS Ultimate через функцию обратного вызова, с помощью которой реализован ряд команд, таких как «добавить запись в текстовый журнал событий», «приостановить выполнение», «сохранить какую-либо величину в памяти» и др.

После того как показатели простых датчиков получены, редактор вычисляет значения остальных датчиков и составляет список действий, подлежащих выполнению. Затем наступает второй этап прогона модели -выполнение предписанных действий (рис. 10).

Рис. 9. Схема опроса условий G-IPS Ultimate через Рис. 10. Схема выполнения действий через API Gipslnclude API Gipslnclude

Аналогичным образом реализован API GipsHostPlugins, используемый для подключения таких плагинов, расширяющих функциональное наполнение комплекса G-IPS Ultimate. Данные плагины могут поддерживать различные этапы моделирования - это могут быть генераторы моделей, валидаторы, проверяющие как корректность модели, так и различные её свойства (например, полнота или неоднозначность), различные сборщики статистики и многое другое.

В отличие от многих рассмотренных в главе 2 программных средств данный комплекс содержит ряд функциональных возможностей помогающих построить корректную (с точки зрения логики) модель: это журнал, в который заносятся все промежуточные шаги имитации, это режим кларификации, позволяющий визуально наблюдать логику принятия решения и режим пошаговой имитации. G-IPS Ultimate имеет возможность расширения функционального наполнения за счёт подключения плагинов (валидаторов, генераторов, анализаторов прогона и др.), представленных динамическими библиотеками (dll). Данный комплекс поддерживает возможность подключения программных модулей, задающих внешнюю среду для конкретной модели, что позволяет не только узнать результат имитации, но и визуализировать протекание имитационного эксперимента. Он может быть использован в учебном процессе при выполнении лабораторного практикума в таких дисциплинах как: экспертные системы, теория игр, теория принятия решений, интеллектуальные системы, а так же при выполнении курсовых и дипломных проектов.

Для демонстрации работы разработанного программного средства в данной главе подробно описаны следующие модели.

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

2. Модель (6 графов) решения игровой ситуации на примере игры «РасМап».

3. Модель (5 графов), имитирующая бизнес-процесс функционирования приёмного отделения медицинского центра.

С помощью специальных плагинов, таких как: генератор конструктивного перечисления семейства решающих графов, пакетный преобразователь произвольных моделей к трёхдольному виду и пакетный обработчик моделей была подтверждена полнота и корректность работы комплекса G-IPS Ultimate, получены оценки эффективности преобразования моделей к трёхдольному виду. Тестирование проводилось на семействе четырёхдольных решающих графов, содержащих по 2-3 вершины в каждой доле (299943 пары решающих графов, проверка более сложных случаев продолжается).

В приложениях приведены автоматически сгенерированные шаблоны исходного кода для демонстрационных примеров, список сокращений и исходный код комплекса G-IPS Ultimate.

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

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

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

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

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

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

5. Создан оригинальный программный комплекс G-IPS Ultimate, поддерживающий визуальное проектирование имитационных моделей в виде решающих графов. Ядро комплекса G-IPS Ultimate реализовано в среде CodeGear Rad Studio 2007, объём авторского исходного кода составляет более 10200 строк авторского кода объёмом более 230 Кб, размер скомпилированного модуля — 2,3 Мб.

6. В работе приведены примеры разработок с использованием комплекса G-IPS Ultimate. Тестирование комплекса проводилось как с помощью объёмных вычислительных экспериментов на конструктивно перечисленных классах решающих графов (299943 пары решающих графов), так и на синтетических и реальных примерах: реализации алгоритма решения ./VP-трудной задачи поиска топологических индексов графов в базисах цепей, реализации игры «РасМап», имитации принятия решений в работе приёмного отделения медицинского центра и др.

7. К настоящему моменту разработанный программный комплекс внедрён ФГБУ «ФНКЦ ДГОИ им. Дмитрия Рогачева» Министерства здравоохранения РФ для моделирования бизнес-процессов, а также в учебный процесс РГСУ.

Список работ, опубликованных по теме диссертации: Работы, опубликованные в перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК:

1. Карпухин И. Н., Кораблин Ю. П., Незнанов А. А. Модели времени в имитационном моделировании / Научно-Техническая Информация. Серия 2. Информационные процессы и системы, № 5, 2012.-С. 16-21.

2. Карпухин И. Н., Кораблин Ю. П., Незнанов А. А. Программное средство для имитационного моделирования с помощью графовых моделей / Программные продукты и системы, № 2 (98), 2012. -С. 156-158.

В других изданиях:

3. Карпухин И. Н., Незнанов А. А. Системы имитационного моделирования учебного назначения в российской высшей школе / Современные проблемы информационной безопасности и программной инженерии, 2011. — С. 132-142.

4. Карпухин И. Н. Программное средство учебного назначения для имитационного моделирования с помощью графовых моделей / Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий, T. III, 2012. - С. 218-222.

5. Karpukhin I. N., Korablin Yu. P., Neznanov A. A. The Models of Time in Simulation / Automatic Documentation and Mathematical Linguistics, № 3, 2012.

6. Карпухин И.Н., Незнанов A.A. Программные средства имитационного моделирования процессов принятия решений реального времени // Научные доклады НПК «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Т.2. - М.: Физматлит, 2009. - С. 132-140.

7. Карпухин И. Н., Яркин С. В., Кохов В. А. Генераторы средних по сложности структур для исследования базовых алгоритмов структурной информатики // Тринадцатая ежегодная международная научно-техническая конференция студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА», Т.1. -М.: МЭИ (ТУ), 2007. - С. 367-368.

Российский государственный социальный университет

04201355021

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

Карпухин Илья Николаевич

Исследование и реализация систем дискретно-событийного имитационного моделирования на основе

графовых моделей

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

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

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

Москва, 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..................................................................................................................................................4

Актуальность темы работы.......................................................................................................................................4

Цель работы...............................................................................................................................................................5

Решаемые задачи.......................................................................................................................................................5

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

Практическая полезность..........................................................................................................................................6

Методы исследований и достоверность результатов.............................................................................................7

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

Личный вклад диссертанта.......................................................................................................................................7

Публикации................................................................................................................................................................8

Содержание работы по главам.................................................................................................................................8

1. ИССЛЕДОВАНИЕ МОДЕЛЕЙ И МЕТОДОВ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.......................................................................................................................9

1.1. Глоссарий.........................................................................................................................................9

1.2. Значимость.....................................................................................................................................10

1.3. Определение имитационного моделирования..............................................................................12

1.4. Этапы имитационного моделирования.........................................................................................14

1.5. Модели времени в имитационном моделировании......................................................................15

1.5.1. Дискретно-событийное моделирование.....................................................................................................17

1.5.2. Моделирование Монте-Карло.....................................................................................................................21

1.5.3. Непрерывное моделирование......................................................................................................................23

1.6. Методы имитационного моделирования.......................................................................................24

1.7. Модели представления знаний......................................................................................................25

1.7.1. Формальные грамматики.............................................................................................................................27

1.7.2. Логические модели.......................................................................................................................................29

1.7.3. Комбинаторные модели...............................................................................................................................30

1.7.4. Алгебраические модели...............................................................................................................................30

1.7.5. Продукционные модели...............................................................................................................................31

1.7.6. Семантические сети.....................................................................................................................................34

1.7.7. Байесовские сети..........................................................................................................................................35

1.7.8. Фреймы..........................................................................................................................................................37

1.7.9. Ленемы..........................................................................................................................................................40

1.7.10. Нечёткие логики...........................................................................................................................................41

1.7.11. Нейронные сети............................................................................................................................................43

1.7.12.Генетические алгоритмы.............................................................................................................................45

1.8. Основные подходы к имитационному моделированию...............................................................47

1.8.1. Агентное моделирование.............................................................................................................................48

1.8.2. Дискретно-событийный подход..................................................................................................................50

1.8.3. Системная динамика....................................................................................................................................51

Выводы и результаты по главе................................................................................................................52

2. АНАЛИЗ СУЩЕСТВУЮЩИХ ПРОГРАММНЫХ СРЕДСТВ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ..........................................................................54

2.1. Программные средства имитационного моделирования..............................................................54

2.1.1. AnyLogic by XJ Technologies.......................................................................................................................58

2.1.2. GPSS by Minuteman Software.......................................................................................................................58

2.1.3. Arena Simulation Software by Rockwell Automation...................................................................................59

2.1.4. SCADA-системы...........................................................................................................................................61

2.1.5. VisSim by Visual Solutions............................................................................................................................62

2.1.6. 20-sim by Controlab Products В. V................................................................................................................63

2.1.7. Dymola by Dassault Systèmes AB.................................................................................................................63

2.1.8. Omola by M. Andersson................................................................................................................................64

2.1.9. COMNET III by CACI Products....................................................................................................................65

2.1.10. SIMNET II by Hamdy A. Taha......................................................................................................................65

2.1.11. AutoMod by Brooks-PRI Automation...........................................................................................................66

2.1.12. MedModel by PROMODEL Corporation......................................................................................................66

2.1.13. Vensim by Ventana Systems..........................................................................................................................67

2.1.14.Powersimby Powersim Software AS.............................................................................................................67

2.1.15.Ascape by The Brookings Institution.............................................................................................................68

2.1.16.The RePast Suite............................................................................................................................................68

2.1.17.CSIM by Mesquite Software..........................................................................................................................69

2.1.18.Extend by Imagine That.................................................................................................................................69

2.1.19.SIMUL8.........................................................................................................................................................70

2.1.20.SimPy by SimPy Developer Team.................................................................................................................70

2.2. Программные средства имитационного моделирования в российской высшей школе...............71

2.2.1. Инструментальный комплекс СИМПР-WINDOWS..................................................................................72

2.2.2. Среда имитационного моделирования РДО..............................................................................................74

Выводы и результаты по главе................................................................................................................75

3. МОДЕЛЬ ДИСКРЕТНО-СОБЫТИЙНОГО ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ НА ОСНОВЕ РЕШАЮЩИХ ГРАФОВ..........................................77

3.1. Понятие решающего графа и его использование в имитационном моделировании...................77

3.2. Формальное представление...........................................................................................................78

3.3. Полнота, неоднозначность и эквивалентность решающих графов..............................................85

3.4. Утверждение (о сводимости многодольных моделей).................................................................87

Выводы и результаты по главе................................................................................................................89

4. ПРОГРАММНОЕ СРЕДСТВО «G-IPS ULTIMATE»...........................................................91

4.1. Общие сведения о программных разработках..............................................................................91

4.2. История развития комплекса G-IPS Ultímate................................................................................92

4.3. Программное средство G-IPS Ultímate..........................................................................................95

4.3.1. Требование к программе..............................................................................................................................96

4.4. Реализация......................................................................................................................................97

4.4.1. Структура проекта........................................................................................................................................97

4.4.2. Графический интерфейс G-IPS Ultimate.....................................................................................................99

4.4.3. Структуры данных в G-IPS Ultimate.........................................................................................................102

4.4.4. API Gipsinclude...........................................................................................................................................Ill

4.4.5. API GipsHostPlugins...................................................................................................................................113

4.4.6. Функциональное наполнение....................................................................................................................117

4.4.7. Объемные характеристики G-IPS Ultimate..............................................................................................118

4.5. Примеры использования G-IPS Ultimate.....................................................................................118

4.5.1. Пример реализации в G-IPS Ultimate алгоритма поиска цепей заданной длины в графе....................118

4.5.2. Пример реализации логики игры в G-IPS Ultimate.................................................................................123

4.5.3. Пример моделирования бизнес-процесса работы приёмного отделения медицинского центра........127

4.6. Тестирование комплекса G-IPS Ultimate.....................................................................................128

4.6.1. Постановка эксперимента..........................................................................................................................128

Результаты по главе...............................................................................................................................130

ЗАКЛЮЧЕНИЕ......................................................................................................................................131

СПИСОК ЛИТЕРАТУРЫ...................................................................................................................133

ПРИЛОЖЕНИЕ 1. ПРИМЕРЫ ШАБЛОНОВ КОДА...............................................................143

П 1.1 .Автоматически сгенерированный шаблон кода для модуля поиска ISSC.................................143

П 1.2. Автоматически сгенерированный шаблон кода «РасМап»........................................................149

ПРИЛОЖЕНИЕ 2. СПИСОК СОКРАЩЕНИЙ..........................................................................160

ПРИЛОЖЕНИЕ 3. ИСХОДНЫЙ КОД ПРОГРАММНОГО СРЕДСТВА G-IPS

ULTIMATE....................................................................................................................................161

ВВЕДЕНИЕ

Тема работы

Исследование и реализация систем дискретно-событийного имитационного моделирования на основе графовых моделей. Объект работы

Модели дискретно-событийного имитационного моделирования, базы знаний на их основе. Предмет работы

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

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

Имитационное моделирование является мощным инструментом исследования поведения реальных систем. Методы имитационного моделирования позволяют собрать необходимую информацию о поведении системы путем создания её математической модели и последующего имитационного эксперимента. Эта информация используется затем для проектирования системы.

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

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

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

Цель работы

Цель диссертационной работы - исследование современных средств имитационного моделирования и моделей представления экспертных знаний, разработка программного комплекса для дискретно-событийного имитационного моделирования на основе графовых моделей.

Решаемые задачи

Для достижения поставленной цели в работе решаются следующие задачи.

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

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

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

4. Создание на основе библиотек прикладного программного комплекса G-IPS Ultimate.

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

6. Применение программного комплекса G-IPS Ultimate для получения теоретических и прикладных результатов, использование в учебном процессе.

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

Новыми научными результатами работы являются следующие.

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

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

3. Создан программный комплекс имитационного моделирования G-IPS Ultimate, прошедший апробацию, подтверждена корректность и функциональная полнота разработанного программного обеспечения.

Практическая полезность

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

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

Комплекс G-IPS Ultimate внедрён в учебный процесс для студентов в качестве лабораторного практикума по таким дисциплинам как: • исследование операций и принятие решений,

• экспертные системы,

• интеллектуальные системы и др.

А так же планируется внедрение в учебный процесс по курсам:

• теории игр,

• имитационного моделирования.

Методы исследований и достоверность результатов

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

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

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

Основные положения и результаты диссертации докладывались и обсуждались на 13 международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2007г.), научно-практической конференции студентов, аспирантов, молодых ученых и специалистов: «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (г. Коломна, 2009г), на научных семинарах РГСУ и НИУ ВШЭ.

Личный вклад диссертанта

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

Публикации

Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в статьях [2, 3, 4, 5, 6], трудах [7] и тезисах конференций [8].

Содержание работы по главам

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

В первой главе рассматриваются общие воп