Простая система имитационного моделирования на Go



Введение


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

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

Уже порядка полувека при имитационном моделировании используются компьютерные модели. Для их разработки создано огромное множество различных программ и фреймворков, среди которых, на мой взгляд, наибольшее развитие получили средства для моделирования систем массового обслуживания (СМО). Одна из наиболее известных и простых программ для имитационного моделирования СМО – GPSS World (General Purpose Simulation System – система моделирования общего назначения), более подробно можно ознакомится по ссылкам [1], [2].

Концепция этой программы и была положена в основу фреймворка имитационного моделирования на Go.

Моделирование в GPSS


Модель в GPSS представляет собой последовательность блоков (команд), описывающих моделируемые объекты, между которыми перемещаются транзакты. При попадании транзакта в блок генерируются события, приводящие либо к изменению состояния моделируемого объекта, либо изменению состояния/параметров транзакта.

Основных блоков порядка десяти: GENERATE, TERMINATE, ASSIGN, SEIZE, RELEASE, QUEUE, ADVANCE, DEPART, START. Всего блоков порядка трёх десятков. Блоки имеют параметры, в качестве которых могут выступать числа, имена функций, метки в программе моделирования, имена переменных. Более подробно с блоками можно ознакомиться, например, здесь.

Объекты в GPSS имеют набор стандартных числовых атрибутов (СЧА) и стандартных логических атрибутов (СЛА). Например, для очереди, один из СЧА это текущая длина, а примером СЛА для некоего оборудования будет свободно (TRUE) или занято оно (FALSE).
В отдельных версиях GPSS присутствует визуализация процесса моделирования, но чаще всего она отсутствует. По результатам моделирования в GPSS формируется отчёт, с указанием СЧА и СЛА по всем объектам.

Реализация в Go


Реализация в Go представляет собой разработку набора объектов схожих по функциям с блоками GPSS. Первым был создан Pipeline – объект, в рамках которого выполняется симуляция.

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

После добавления всех компонентов, можно запустить моделирование с помощью метода Start. Внутри неё реализован циклический обход всех компонентов в течение заданного времени моделирования. По окончания моделирования можно напечатать отчёт, содержащий СЧА и СЛА.

Второй важный элемент это собственно компоненты для описания моделирования. Были реализованы: Generator – генерирует транзакты, Advance – создаёт задержки на пути транзакта, Queue – очереди транзактов, Facility – некое устройство, монопольно захватываемое транзактом на некоторое время, Hole – «дыра» в которую проваливаются транзакты в конце пути. Разумеется, такого набора недостаточно для создания сложных имитационных моделей, но для отработки решения и сравнения с результатами GPSS вполне хватает. Все компоненты реализуют интерфейс IBaseObj, который охватывает минимально необходимый функционал.

Каждый компонент имеет очередь транзактов. Непосредственно как очередь она используется только в Queue, для других компонентов это просто хранилище. Очередь реализована на основе map. В процесс моделирования компоненты проходят по своей очереди и проверяют готовность (выполнение некоторого условия) транзакта для передачи следующему компоненту. Передача выполняется через метод AppendTransact следующего компонента. Если передача прошла успешно, то транзакт удаляется из очереди, соответственно следующий компонент принимает его в свою очередь. Поскольку для каждого компонента определяется несколько адресатов, то если не удалось отправить транзакт одному адресату, пытаемся отправить другом.

Для генерации случайных величин при определении времени появления транзакта и создании задержек используются функции ГПСЧ в Go.

Так как при моделировании одновременно могут существовать множество транзактов, перемещающихся между различными компонентами, то возникла идея использовать внутри компонентов goroutines. Pipeline, проходя по компонентам, запускает для каждого из них обработчик HandleTransacts, внутри которого создаётся goroutine. После того как все goroutines отработают, увеличивается счётчик модельного времени и повторно вызывается HandleTransacts.

Последний ключевой объект это собственно сам транзакт. У него есть идентификатор, время рождения и смерти, владелец (в каком компоненте он сейчас), ряд параметров для вычисления СЧА и СЧЛ.

На рис. 1 приведена структурная схема взаимодействия основных объектов фреймворка при моделировании.


Рис. 1. Обобщённая структурная схема взаимодействия основных объектов при моделировании

Пример моделирования


Допустим надо смоделировать работу парикмахерской. Это известный пример из GPSS. Посетители идут хаотично, с периодичностью 18±6 минут, их количество заранее не известно. Парикмахер у нас один, на стрижку он тратит 16±4 минуты. Итак, сколько всего человек он пострижёт за рабочий день? Сколько будет людей в очереди? Сколько в среднем уйдёт времени на стрижку и сколько времени просидят люди в очереди? Много вопросов и простая симуляция. Структурная схема на рис. 2.


Рис. 2. Структурная схема моделирования парикмахерской

Код для построения модели будет следующий.

barbershop := NewPipeline("Barbershop", true) // Наша симуляция
clients := NewGenerator("Clients", 18, 6, 0, 0, nil) // Генератор клиентов
chairs := NewQueue("Chairs") // Очередь
master := NewFacility("Master", 16, 4) // Парикмахер
hole := NewHole("Out") // Выход
barbershop.Append(clients, chairs) // От генератора транзакты идут в очередь
barbershop.Append(chairs, master) // Из очереди идут в устройство
barbershop.Append(master, hole) // Из устройства в дыру
barbershop.Append(hole) // А из дыры транзакты никуда не уходят
barbershop.Start(480) // Моделируем рабочий день
<-barbershop.Done // Завершение симуляции
barbershop.PrintReport()

Результаты моделирования можно посмотреть здесь.
Pipeline name " Barbershop "
Simulation time 480
Object name " Chairs "
Max content 1
Total entries 26
Zero entries 11
Persent zero entries 42.31%
In queue 0
Average time/trans 2.58
Average time/trans without zero entries 4.47

Object name " Clients "
Generated 26

Object name " Master "
Average advance 16.46
Average utilization 89.17
Number entries 26.00
Transact 26 in facility

Object name " Out "
Killed 25
Average advance 16.56
Average life 19.44

Обслужили 25 клиентов, 26-ой на момент завершения моделирования был ещё в кресле мастера. В очереди было не более 1 человека, 11 человек не ждали (нулевой проход) и сразу проходили на стрижку. В среднем в очереди люди провели 2,58 минуты, а из тех, кто ждал (не нулевой проход) 4,47 минуты. 89,17% своего времени парикмахер усиленно стриг.

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

Другой пример. Есть офис, в нём 10 сотрудников и один туалет. Люди желают пойти в туалет каждые 90±60 минут, идти до туалета 5±3 минуты, занимают туалет 15±10 минут, поход обратно в офис 5±3 минуты. Проведём симуляцию в течении 9 часов (8 часов работы + 1 час обед), на рис. 3 приведена структурная схема.


Рис. 3. Структурная схема модели занятости туалета: слева с одним туалетом, справа с двумя

Слева модель с одним туалетом, справа с двумя. Далее приведён код модели.

waterclosetsim := NewPipeline("Water Closet Simulation", false)
office := NewGenerator("Office", 0, 0, 0, 10, nil)
wantToToilet:= NewAdvance("Wanted to use the toilet", 90, 60)
pathToWC := NewAdvance("Path to WC", 5, 3)
queue := NewQueue("Queue to the WC")
pathFromWC := NewAdvance("Path from WC", 5, 3)
wc := NewFacility("WC", 15, 10)
pathToOffice:= NewAdvance("Path from WC", 5, 3)
waterclosetsim.Append(office, wantToToilet)
waterclosetsim.Append(wantToToilet, pathToWC)
waterclosetsim.Append(pathToWC, queue)
waterclosetsim.Append(queue, wc)
waterclosetsim.Append(wc, pathFromWC)
waterclosetsim.Append(pathFromWC, wantToToilet) 
waterclosetsim.Start(540) 
<-waterclosetsim.Done
waterclosetsim.PrintReport()

Результаты моделирования следующие.
Pipeline name " Water Closet Simulation "
Simulation time 540
Object name " Office "
Generated 10

Object name " Path from WC "
Average advance 5.77

Object name " Path to WC "
Average advance 5.22

Object name " Queue to the WC "
Max content 4
Total entries 36
Zero entries 8
Persent zero entries 22.22%
Current contents 4
Average content 1.78
Average time/trans 24.11
Average time/trans without zero entries 31.00

Object name " WC "
Average advance 14.69
Average utilization 87.04
Number entries 32.00
Transact 2 in facility

Object name " Wanted to use the toilet "
Average advance 95.85

В очереди было до 4 человек, 8 раз человек сразу попал в туалет, в течении рабочего дня туалет используют на 87,04%. Самое существенное, на мой взгляд, это то, что люди ждут порядка получаса (31 минута) в очереди в туалет. Возможно, это связано с тем, туалет один, а возможно, с тем, что в среднем люди сидят в нём 14,69 минут.

Добавив ещё один туалет, я увидел, что очередь сократилась до 3 человек, 29 раз люди сразу попали в туалет. Но самое главное, почти в три раза уменьшилось ожидание.

Заключение


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

Код выложен на GitHub.
  • +23
  • 4,4k
  • 8
Поделиться публикацией

Комментарии 8

    0
    Обратите внимание, что «Имитационное моделирование» — это «масло масляное».

    Хотя термин периодически используется в научной среде, многих в той же научной среде от этого термина корежит…
      +1
      Я в научной среде не сталкивался с возмущением по поводу этого термина. Например, как разделить имитационное моделирование и аналитическое, если просто говорить «моделирование»?
        0
        А с какой ещё целью проводить имитацию (моделирование), кроме анализа?
          0
          Аналитическое моделирование это не «моделирование с целью анализа».
          Аналитическое моделирование основано на косвенном описании моделируемого объекта с помощью набора математических формул.
          Имитационное моделирование основано на прямом описании моделируемого объекта. Каждому существенному с точки зрения решаемой задачи элементу объекта ставится в соответствие элемент модели. При этом описываются законы функционирования каждого элемента объекта и связи между ними.
            0
            >… с помощью набора математических формул.
            математическое моделирование
            >… При этом описываются законы функционирования каждого элемента объекта и связи между ними
            математическими формулами (уравнениями, весами связей персептрона на GO)
              0
              Не всякую систему можно представить в виде математических формул. С системами массового обслуживания это затруднительно.
          0
          Например, как разделить имитационное моделирование и аналитическое, если просто говорить «моделирование»?

          Это странная терминология, если честно. Вы ниже привели определения, интересно знать источник, потому что в этих определениях куча спорных моментов. Начиная от косвенное/прямое и кончая тем, что наличие математических формул — это признак какого-то «особого моделирования».

          Теория графов, например, вполне себе математика, в т.ч. с формулами.

          Общее название — «математическое моделирование». То, что у вас сделано можно назвать «компьютерное моделирование».
            +1
            Здесь стоит обратиться к работе Роберта Шеннона «Имитационное моделирование систем — искусство и наука», раздел 1.6 «Достоинства и недостатки имитационного моделирования».
            Далеко не всегда можно аналитически представить модель некой системы, например, это затруднительно для систем массового обслуживания, в основном из-за наличия в них очередей.
            Хотя и в более простом примере будут сложности, попробуйте аналитически в виде системы уравнений описать модель перехода бабушки через дорогу. Построить имитационную модель будет гораздо проще, есть бабушка, есть дорога, есть машины, есть взаимосвязи между этими объектами.

            С тем, что аналитическое и имитационное моделирование относятся к математическому моделированию я и не спорил.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое