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

Термин “дискретно-событийно моделирование” исторически закрепился за моделированием систем обслуживания потоков объектов некоторой природы: клиентов банка, автомобилей на заправочной станции, телефонных вызовов, пациентов в поликлиниках и т.п. Именно такие системы называются системами массового обслуживания.

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

В основе данного вида моделирования лежит концепция заявок (транзактов, entities), ресурсов и потоковых диаграмм (flowcharts), определяющих потоки заявок и использование ресурсов. Этот подход восходит к Джеффри Гордону, который в 1960х придумал и развил GPSS и реализовал её, работая в IBM. Заявки (транзакты в GPSS) – это пассивные объекты, представляющие людей, детали, документы, задачи, сообщения и т.п. Они путешествуют через flowchart, стоя в очередях, обрабатываясь, захватывая и освобождая ресурсы, разделяясь, соединяясь и т.д. Типичная потоковая диаграмма показана на рис. 1 в терминах продукта Arena. Вообще, существует около сотни коммерческих инструментов, так или иначе поддерживающих подобный стиль моделирования; некоторые общего назначения, большинство нацелено на определённые ниши: обслуживание, бизнес-процессы, производство, логистика и т.д. Их пользовательские интерфейсы могут существенно различаться из-за специализации, но за ними непременно стоит более или менее одинаковый дискретно-событийный “движок” (engine), который “гоняет” заявки через блоки.

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

В настоящее время делается большое количество исследований и разработок в различных областях под лозунгом многоагентные системы, например, в искусственном интеллекте, теории сложных систем, теории игр и т.д. Общепризнанного определения “что такое агент” не существует; люди до сих пор спорят о том, какими же качествами должен обладать объект, чтобы “заслужить” называться агентом: инициативность и реактивность, ориентация в пространстве, способность обучаться, общаться, “интеллект” и т.д. Таким обзором, существует множество определений понятия агента. Общим во всех этих определениях является то, что агент – это некоторая сущность, которая обладает активностью, автономным поведением, может принимать решения в соответствии с некоторым набором правил, может взаимодействовать с окружением и другими агентами, а также может изменяться (эволюционировать). Многоагентные модели используются для исследования децентрализованных систем, динамика функционирования которых определяется не глобальными правилами и законами, а наоборот, эти глобальные правила и законы являются результатом индивидуальной активности членов группы. Цель агентных моделей – получить представление об этих глобальных правилах, общем поведении системы, исходя из предположений об индивидуальном, частном поведении ее отдельных активных объектов и взаимодействии этих объектов в системе. Таким образом, агентное моделирование называют также моделированием снизу вверх. Пример агентной системы изображен на рис. 2.

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

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

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

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

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

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

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

Событийный подход

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

Для иллюстрации событийного подхода вновь рассмотрим пример банка с одним кассиром, приведенный ранее. Клиен­ты заходят в банк, после возможного ожидания обслужива­ются кассиром и затем уходят. Состояние системы в этом при­мере определяется состоянием кассира и числом ожидающих обслуживания клиентов. Оно остается неизменным, за исключением моментов, когда клиент прибывает в систему или покида­ет ее. Поэтому событийная модель в данном случае состоит из описания действий, происходящих в момент прибытия и окон­чания обслуживания очередного клиента. Так как изменения состояния системы могут происходить только в эти моменты времени, использование событий «прибытие» и «конец обслу­живания» полностью обеспечивает воспроизведение динамики функционирования системы.

Обсудим сначала логику события «прибытие». Оператор­ная схема этого события имеет следующий вид:

ПЛАНИРОВАНИЕ СЛЕДУЮЩЕГО ПРИБЫТИЯ.

ЕСЛИ КАССИР ЗАНЯТ: ЧИСЛО ОЖИДАЮЩИХ=ЧИСЛО ОЖИДАЮ-

ЩИХ+1; ВОЗВРАТ.

ЕСЛИ КАССИР СВОБОДЕН: ПЕРЕВОД КАССИРА В СОСТОЯНИЕ «ЗА­НЯТ»; ПЛАНИРОВАНИЕ СОБЫТИЯ «ОКОНЧАНИЕ» ОБСЛУЖИВА­НИЯ В МОМЕНТ ВРЕМЕНИ=ТЕКУЩЕЕ ВРЕМЯ+ВРЕМЯ ОБСЛУ­ЖИВАНИЯ; ВОЗВРАТ.

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

Рассмотрим теперь логику обработки события «конец обслу­живания». Операторная схема этого события имеет следующий вид:

ЕСЛИ ЧИСЛО ОЖИДАЮЩИХ БОЛЬШЕ НУЛЯ: ЧИСЛО ОЖИДАЮ­ЩИХ=ЧИСЛО ОЖИДАЮЩИХ-1; ПЛАНИРОВАНИЕ ОКОНЧАНИЯ ОБСЛУЖИВАНИЯ В МОМЕНТ ВРЕМЕНИ, РАВНЫЙ ТЕКУЩЕМУ ВРЕМЕНИ + ВРЕМЯ ОБСЛУЖИВАНИЯ; ВОЗВРАТ.

ЕСЛИ ЧИСЛО ОЖИДАЮЩИХ РАВНО НУЛЮ: ПЕРЕВОД КАССИРА В

СОСТОЯНИЕ «СВОБОДЕН»; ВОЗВРАТ.

Когда кассир заканчивает обслуживание очередного кли­ента, сначала проверяем, есть ли клиенты, ожидающие обслу­живания. Если такие клиенты есть, их число уменьшается на единицу и планируется событие «конец обслуживания» первого из ожидающих клиентов. В противном случае кассир перехо­дит в состояние «свободен».

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

Подход сканирования активностей

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

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

Процессно-ориентированный подход

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

СОЗДАВАТЬ ПРИБЫВАЮЩИХ КЛИЕНТОВ ЧЕРЕЗ КАЖДЫЕ Т ЕДИНИЦ ВРЕМЕНИ;

ОЖИДАТЬ КАССИРА;

ПРОДВИНУТЬ ВРЕМЯ НА ПРОДОЛЖИТЕЛЬНОСТЬ ОБСЛУЖИВАНИЯ;

ОСВОБОДИТЬ КАССИРА;

УДАЛИТЬ КЛИЕНТА;

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

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

Определим основные понятия и термины, используемые в моде­лировании.

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

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

Состояние системы - множество переменных, которые содер­жат всю информацию, необходимую для описания свойств системы в любое время.

Объект - любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслу­живающее устройство, клиент, машина).

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

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

Событие - мгновенно возникающее изменение состояние сис­темы (например, прибытие нового требования).

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

Список событий - список намеченных будущих событий, упо­рядоченных по времени возникновения, известный также как список будущих событий (СБС).

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

Задержка - продолжительность времени неопределенного про­межутка, для которого неизвестно заранее, когда он заканчивается (например, задержка клиента в очереди по правилу «последний при­шел - первый обслужился», так как начало обслуживания зависит от будущих поступлений).

Модельное время - неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.

Часы - переменная, отражающая протекание времени модели­рования, называется в примерах ЧАСЫ (CLOCK).

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

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

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

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

В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин и требуемыми временами их обслуживания продавцом, а на рис. 1.3 проведено графическим методом «ручное» моделирование СМО с одним устройством.

С точки зрения объектного подхода имеются динамические объ­екты - требования (ПОКУПАТЕЛИ) и некоторый ресурс - устройст­во обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, а он занят, то оно становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связанным с ресурсом. Примем за пра­вило обслуживания - FIFO.

Википедия дает следующее определение:

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

Под дискретной имитационной моделью понимают такую модель, состояние которой изменяется в определенные моменты времени t 1 , t 2 ,…, t i ,…, t N . На интервале времени [ t i , t i +1 ) переменные не изменяются, и их значения равны значениям в момент времени t i .

Например, моделирование началось в момент времени t0. На интервале времени }