дискретно событийный подход означает что

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

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

Содержание

Компоненты системы дискретно-событийного моделирования

Кроме переменных, определяющих состояние системы, и логики, определяющей, что произойдет в ответ на какое-то событие, система дискретно-событийного моделирования содержит следующие компоненты:

Основной компонент системы, синхронизирующий изменения системы, т.е. возникновение событий.

Список событий

Система моделирования поддерживает по крайней мере один список событий моделирования.

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

Генераторы случайных чисел

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

Статистика

Основные данные, которые собираются в системах дискретно-событийного моделирования:

Условие завершения

Условием завершения могут выступать:

Реализация

Источник

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

Дискретно-событийное моделирование (англ. discrete-event simulation, DES) — это вид имитационного моделирования. В дискретно-событийном моделировании функционирование системы представляется как хронологическая последовательность событий. Событие происходит в определенный момент времени и знаменует собой изменение состояния системы.

Компоненты системы дискретно-событийного моделирования

Кроме переменных, определяющих состояние системы, и логики, определяющей, что произойдет в ответ на какое-то событие, система дискретно-событийного моделирования содержит следующие компоненты:

Основной компонент системы, синхронизирующий изменения системы, т.е. возникновение событий.

Список событий

Система моделирования поддерживает по крайней мере один список событий моделирования.

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

Генераторы случайных чисел

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

Статистика

Основные данные, которые собираются в системах дискретно-событийного моделирования:

Условие завершения

Условием завершения могут выступать:

Реализация

Системы дискретно-событийного моделирования—это, чаще всего, проблемно-ориентированные языки программирования или библиотеки для высокоуровневых языков. Наиболее известные: Arena, AnyLogic, SIMSCRIPT, SLAM, SIMAN, AweSim, GPSS.

Источник

Дискретно-событийный подход в имитационном моделировании

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

имитационно модели Рис. 1.1. Связь между понятиями «действие» и «событие».

Понятие события, происходящего мгновенно в определенный момент времени, в который начинается или заканчивается некоторое действие, является основополагающим. На рис. 1.1 показана связь между понятиями «действие» и «событие». Внутри события время не изменяется, а изменения состояния системы происходят только в моменты наступления событий. Поведение системы имитируется последовательностью изменений ее состояния, происходящих по мере наступления событий. Когда происходит событие, состояние системы может быть изменено четырьмя способами: 1) изменением значений одной или нескольких переменных модели; 2) изменением количества компонентов в системе; 3) изменением значении одного иди нескольких атрибутов одного компонента; 4) изменением взаимосвязей между компонентами с помощью средств оперирования с файлами. Отметим, что возможны и такие события, при которых состояние системы не меняется.

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

Разработка модели

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

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

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

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

Так же различают аналитическое и имитационное моделирование.

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

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

Источник

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

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

При дискретно-событийном моделировании движение поезда из точки А в точку Б представляется как два события: отправление и прибытие. Непосредственно движение поезда – лишь временная задержка между событиями. Эти события и движение между ними можно анимировать.

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

Дискретно-событийное и многоподходное моделирование

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

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

Библиотека процессного моделирования AnyLogic

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

Библиотека процессного моделирования AnyLogic интегрирована с анимационными средствами AnyLogic и позволяет анимировать процессы любой сложности.

Вы знаете, как правильно строить имитационные модели?

Об этом мы рассказываем в аналитической статье на английском «Multimethod Simulation Modeling»

Источник

Продукты и технологии:
C#, объектно-ориентированное программирование
В статье рассматриваются:

На протяжении всей истории возможность моделирования помогала развитию множества наук. Модели в медицине, симулирующие человеческое тело, улучшают изучение анатомии. Компьютерные игры-симуляторы, такие как «World of Warcraft», создают полностью выдуманный мир, а «Flight Simulator» помогает тренировать пилотов на земле. Различные программы-тренажеры также позволяют исследовать реакцию на террористические атаки, пандемии и другие возможные кризисные явления. Даже динозавры в фильме «Парк Юрского периода» намекают на широкое применение моделирования и его потенциал.

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

Моделирование обычно включает либо непрерывный процесс, либо дискретные события. Для моделирования метеорологической системы, например, наблюдение ведется непрерывно, так как все элементы постоянно изменяются. Следовательно, график зависимости переменной температуры от переменной времени был бы представлен непрерывной кривой. И напротив, взлеты и посадки самолетов являются некими точками во времени, а значит, при моделировании можно учитывать только эти моменты или события, а все остальное — отбрасывать. Этот тип симуляции известен как дискретно-событийное моделирование (discrete event simulation, DES), и именно о нем я расскажу в этой статье.

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

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

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

Поскольку программирование симуляции может быть весьма сложным, неоднократно предпринимались попытки создать языки, которые охватывают все требования парадигмы симуляции, чтобы облегчить разработку. Один из таких языков — SIMULA, изобретенный в 1960-х Оле-Йоханом Далем (Ole Johan) и Кристеном Нюгордом (Kristen Nygaard) и ставший первым языком, в который была введена концепция объектно-ориентированного программирования (ООП) — ведущая в наши дни парадигма программирования. В настоящее время фокус внимания больше смещен в сторону создания пакетов, инфраструктур или библиотек, включающих то, что понадобится программистам при создании симуляции. Подразумевается, что эти библиотеки должны вызываться из обычных языков вроде C#, C++, Java или Python.

В статье «A History of Discrete Event Simulation Programming Languages» Нэнс (Nance) предложил минимум шесть требований, которым должен удовлетворять любой язык программирования для DES (bit.ly/1ZnvkVn):

Все эти требования могут быть удовлетворены в C#, так что в этой статье я представлю дискретно-событийное моделирование для увеличения популяции на C#.

DES для увеличения популяции

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

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

В этой статье я представлю DES для увеличения популяции. Цель — наблюдение за тем, как популяция развивается со временем, и получение некоторой статистики с помощью анализа конечных результатов (размера популяции, количества стариков и молодых людей и т. п.). Популяция начинается с наличия m мужчин и n женщин, при этом с каждым индивидуумом сопоставляется некий возраст. Очевидно, что m и n должны быть больше нуля, а иначе симуляция бессмысленна. Объектами в этой модели являются индивидуумы.

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

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

Табл. 1. Вероятность прекращения взаимоотношений

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

Женщина можете забеременеть, если ее возраст соответствует функции нормального (колоколообразного) распределения с параметрами µ=28 и σ 2 =8 годам. У каждой женщины появляется количество детей, распределяемое гауссовой функцией с параметрами µ=2 и σ 2 =6 годам. (Параметр µ представляет средний возраст, а σ 2 — мера вариативности возраста.)

У каждого индивидуума продолжительность жизни (life expectancy) распределяется функцией Пуассона с параметром λ=70 лет, где λ представляет среднюю продолжительность жизни.

В предыдущем описании можно идентифицировать несколько событий:

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

Вероятностные распределения

Дискретной случайной переменной является та, у которой набор значений конечный или счетно бесконечный (countably infinite). То есть значения могут быть перечислены как конечная или бесконечная последовательность значений 1, 2, 3… В случае дискретной случайной переменной ее распределение вероятностей является любым графиком, таблицей или формулой, которая присваивает вероятность каждому возможному значению. Сумма всех вероятностей должна быть равна 1, а каждая индивидуальная вероятность должна укладываться в диапазон 0–1. Скажем, при броске правильной кости (все стороны равно вероятны) дискретная случайная переменная X, представляющая возможные результаты, будет иметь вероятностное распределение X(1) = 1/6, X(2) = 1/6, …, X(6) = 1/6. Все стороны равно вероятны, поэтому каждой назначается вероятность 1/6.

Параметры l и µ указывают среднее (ожидаемое значение) в соответствующих распределениях. Среднее представляет значение, принимаемое случайной переменной в среднем. Иначе говоря, это сумма E=[(каждый возможный результат) × (вероятность этого результата)], где E обозначает среднее. В случае кости среднее было бы таким: E = 1/6 + 2/6 + 3/6 + 4/6 + 5/6 + 6/6 = 3.5. Заметьте, что результат 3.5 на самом деле находится посередине между всеми возможными значениями, которые может показывать кость; это ожидаемое значение, когда кость бросается большое число раз.

Параметр σ 2 определяет разброс (variance) распределения. Разброс представляет дисперсию возможных значений случайной переменной, и он всегда положительный. Малая дисперсия (близкая к 0) указывает, что значения близки друг к другу и к среднему, а высокая дисперсия (близкая к 1) — на большой разброс между значениями и большое отклонение от среднего.

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

Рис. 1. Пуассоново распределение, параметр λ = 18

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

Рис. 2. Экспоненциальное распределение, параметр λ = 8

Нормальное распределение описывает вероятности, которые выпадают вокруг центрального значения, без смещения влево или вправо, как показано на рис. 3. Нормальные распределения симметричны и имеют колоколообразные пограничные кривые (density curves) с единственным пиком в середине. При этом 50% распределения располагается слева от середины и 50% справа. Среднеквадратичное отклонение (standard deviation) указывает протяженность колоколообразной кривой; чем меньше среднеквадратичное отклонение, тем более сконцентрированы данные. И среднее значение, и среднеквадратичное отклонение следует передавать как параметры в функцию нормального распределения. Многие природные явления весьма близко следуют нормальному распределению: кровяное давление, рост людей, ошибки измерений и многое другое.

Рис. 3. Нормальное распределение, параметры µ = 28 и σ 2 = 8 лет

Теперь я покажу, как реализовать предложенное DES в популярном и элегантном языке вроде C#.

Реализация

Для разработки этой симуляции я задействую все преимущества парадигмы ООП. Идея в том, чтобы получить максимально читаемый код. Научные приложения имеют тенденцию к сложности и трудности в понимании, поэтому важно пытаться делать их предельно ясными, чтобы и другие могли воспринимать код. Я создам консольное приложение на C# со структурой, показанной на рис. 4.

Рис. 4. Структура приложения симуляции

Логический путь существен; заметьте, что структура пространства имен сохраняет здравый смысл: Simulation.DES.PopulationGrowth

Папка Events содержит файл Event.cs, который определяет перечислимый тип, представляющие все возможные события в симуляции:

Папка Objects содержит все классы, относящиеся к индивидуумам; это те части кода, которые в наибольшей мере выигрывают от ООП. К индивидуумам относятся три класса: Individual, Male и Female. Первый — это абстрактный класс, а остальные наследуют от него, т. е. мужчины и женщины являются индивидуумами. Основной объем кодирования приходится на класс Individual. На рис. 5 приведены его свойства и методы.

Ниже дано описание всех свойств.

А это описание его методов.

Класс начинается с определения всех свойств, а затем конструктора, который просто задает возраст:

Методы SuitableRelation и SuitablePartner, также свойство Engaged являются довольно простыми логическими проверками:

Метод Disengage разрывает взаимоотношения, записывая null в поле Couple, а потом устанавливая null и для самого индивидуума. Кроме того, он задает время появления детей у пары равным 0, поскольку они больше не имеют взаимоотношений:

Метод EndRelation в основном занимается трансляцией таблицы вероятностей для определения шанса на прекращение взаимоотношений. Он использует единую случайную переменную, которая создает случайное значение в диапазоне [0, 1], что эквивалентно созданию процентной доли принятия (acceptance percentage). Словарь распределений создается в классе симуляции (вскоре я его опишу) и хранит пары (событие, распределение вероятностей), тем самым связывая каждое событие с его распределением:

Метод FindPartner (рис. 6) находит доступного партнера для экземпляра Individual. Он принимает список популяции, текущее время симуляции и словарь распределений.

Рис. 6. Метод FindPartner

Наконец, метод ToString определяет строковое представление индивидуума:

Класс Male очень прост:

Класс Female немного посложнее, так как включает обработку беременности, рождения ребенка и т. д. Определение этого класса начинается с объявления всех свойств и конструктора:

Ниже перечислены свойства класса Female.

А это список методов класса.

SuitablePregnancy — это метод проверки, который выводит true, если экземпляр объекта женщины удовлетворяет всем условиям для возможности забеременеть:

Метод GiveBirth (рис. 7) — это код, который добавляет и инициализирует новых индивидуумов в популяции.

Рис. 7. Метод GiveBirth

Однородная выборка (uniform sample) генерируется, чтобы первым делом определить, будет новый индивидуум женщиной или мужчиной при равной вероятности 50% (0.5). Значение ChildrenCount уменьшается на 1, указывая, что эта женщина должна родить на одного ребенка меньше. Остальной код относится к инициализации индивидуума и сбросу некоторых переменных.

Метод ToString изменяет манеру, в которой объекты Female представляются строками:

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

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

Рис. 8. Конструктор класса Simulation

Наконец, метод Execute (рис. 9) содержит всю логику симуляции.

Рис. 9. Метод Execute

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

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

Рис. 10. Наблюдение за популяцией во времени

На рис. 11 показана популяция через 1000 лет.

Рис. 11. Популяция через 1000 лет

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

Выражаю благодарность за рецензирование статьи эксперту Microsoft Джеймсу Маккафри (James McCaffrey).

Источник