Introduction to Discrete Event Simulation Using Python # 2

Introduction

Last time, I understood the mechanism of discrete event simulation and its most basic implementation method. Specifically, it keeps an event calendar (a list of events arranged in the order of occurrence timing), extracts events one by one from the beginning, and executes processing according to the type. there were. In the sample code, there is a while loop in the run () method of the model, and each time it goes around the loop, the first event is taken out from the event calendar, the type is confirmed by the if statement, and it corresponds to the type. I was performing the step of guiding to processing. This implementation method can be said to be the most naive coding style that simply encodes the mechanism of discrete event simulation as it is (hereinafter, this style is sometimes called event-oriented).

In fact, there are (at least) two problems with this event-oriented coding style. The first is that the run () method grows larger depending on the number of event types and the number of components of the target system. Second, because the processes that change the state of the target system are grouped by the signal that causes the change, that is, the event, rather than the subject that causes the change or the object that undertakes the change, each other (from the perspective of the subject or object). The point is that a series of related changes will be subdivided into smaller parts and described in multiple different parts. All of these obstruct the outlook of the entire code, and their effects become more and more serious as the scale of the target system increases.

One of the ways to solve these problems is to adopt a process-oriented coding style. With the introduction of Python's SimPy module, you can easily proceed with development in this process-oriented style. This time, let's learn the basics of coding discrete event simulation using this module.

Introduction of SimPy

SimPy overview and installation

The first thing to do is install the Simply module. In Google Colaboratoty, you can easily install it using pip as shown below (note that you do not need the! At the beginning of the line when installing in your local environment).

! pip install simpy

It seems that the three main components of SimPy are the Environment class in core.py, the Event class and its subclasses in events.py, and the resource-related classes in the resources directory. I should do it. In addition to these, process functions and methods implemented as generators play an important role. I'll cover resource-related classes next time, and this time I'll cover the basics of process-oriented coding based on the other three.

Simulation environment and events

The Environment class provides the most basic functions for discrete event simulation, such as managing simulation time and manipulating the event calendar. Therefore, when developing a simulation model using SimPy, one simulation environment (= instance of Environment class) must be created. On the other hand, the Event class is a class for expressing events, and some subclasses are also prepared as will be seen later.

Registering a certain event (= instance of Event class) in the event calendar is called trigger. In the case of a normal Event class event, it will occur at the same time it was triggered. On the other hand, we often want to use events that occur after a predetermined time delay after triggering. In that case, use the Timeout class, which is a subclass of the Event class.

In SimPy, the process executed when a certain event occurs is called the callback of that event, and by assigning a set of callbacks ʻe.callbacks to each event ʻe, the event ʻe` occurs. The processes that occur along with this are executed together. Let's look at a simple example.

import random
import simpy

class Skelton:
    def __init__(self, env):
        self.env = env  # pointer to the SimPy environment
        self.count = 0  # an example state variable

    def update(self, e):
        self.count += 1  # increment the event counter

    def print_state(self):
        print('{} th event occurs at {}'.format(self.count, round(self.env.now)))

    def run(self, horizon):
        while True:
            e = simpy.Timeout(self.env, random.expovariate(1))  # create an Timeout instance
            e.callbacks.append(self.update)  # register update() method in e's callbacks
            if self.env.now > horizon:  # if horizen is passed
                break  # stop simulation
            else:
                self.print_state()
                self.env.step()  # process the next event

env = simpy.Environment()
model = Skelton(env)
model.run(200)

In this example, almost the same function as the previous skeleton model is reproduced using SimPy's Environment class and Timeout class. The Event class and Calendar class that I made last time are unnecessary (since SimPy provides the corresponding functions). Look at the last three lines. After generating the simulation environment (= env), the model (= model) of the target system is generated by using it as an argument. Then, the run () method of that model is executed with horizon = 200.

If you check the contents of the Skelton class, the run () method has a while loop, and each lap of it generates an event (= e) of the Timeout class and sets its callbacks (= e). You can see that the ʻupdate () method is registered in .callbacks). The ʻupdate ()method is a dummy that only incrementscount`. Also, the event callback must be in the form of a function (strictly speaking, a callable object) that takes the event as its only argument.

The first argument when generating an event of the Timeout class is the corresponding simulation environment ʻenv`, and the second argument is the length of the time delay (in the above example, it is given by a random number that follows an exponential distribution). Note that Timeout events are automatically triggered when they are generated (although normal Event class events need to be explicitly triggered as described below).

The simulation time is managed by the variable now in the simulation environment ʻenv (it can be referenced by self.env.nowfrom therun ()method above). If this value is greater than or equal to thehorizonpassed as an argument, the while loop is exited and the simulation ends. Otherwise, we are calling thestep () method of the simulation environment, which takes the first event ʻe from the event calendar and causes it to occur (ie, it is included in ʻe.callbacks`). It corresponds to the process of executing the existing callbacks in order).

Process functions / methods

The Skelton class in the above example is considerably simpler than the previous one because some of the functions are left to the simulation environment. However, that alone means that SimPy will take care of the basic and common functions, so there will be less part to code by yourself. In fact, it can be said that the essential merit of introducing SimPy lies beyond that.

Process functions and methods bring about this essential merit. This makes it possible for SimPy to code in a process-oriented manner. Next, let's explain the basic mechanism using an example. See the example below.

class Skelton2:
    def __init__(self, env):
        self.env = env  # pointer to the SimPy environment
        self.count = 0  # an example state variable

    def print_state(self):
        print('{} th event occurs at {}'.format(self.count, round(self.env.now)))

    def process_method(self):  # an example process method
        while True:
            self.print_state()
            yield simpy.Timeout(self.env, random.expovariate(1))
            self.count += 1  # corresponding to Skelton's update()

def process_func(env):  # an example process function
    while True:
        env.model.print_state()
        yield simpy.Timeout(env, random.expovariate(1))
        env.model.count += 1  # corresponding to Skelton's update()

env = simpy.Environment()
env.model = Skelton2(env)
# simpy.Process(env, process_func(env))  # when using process function
simpy.Process(env, env.model.process_method())  # when using process method
env.run(until=200)

This is a rewrite of the above example using process functions and methods. You may have noticed that the run () method (and the ʻupdate ()method) in the Skelton class has disappeared, and a new method calledprocess_method ()has appeared in the Skelton2 class. This is the process method. Note that this process method may not be used, and instead a process function that performs the same function (in the above example, theprocess_func ()` function) may be used (both are prepared in this example, but in practice. Only one of them is required).

As you can see from the yield statements in process_method () and process_func (), these are Python generators. Whereas a normal function or method returns a result with return and exits, a generator only pauses there when it returns a result with yield, not exits. Then, when the signal of the restart instruction is received later, the processing is restarted from the tip of the yield statement.

In this way, process functions and methods are generators defined by yielding instances of the Event class, and SimPy uses this as a trick for process-oriented coding. Specifically, when a process function / method yields an event ʻe, a restart instruction for that process function / method is automatically added to ʻe.callbacks.

Process functions / methods are restarted when a yielded event occurs, so the state change (increment of count in this example) caused by that event should be described directly in the part after the restart. become. Therefore, in this example, it is no longer necessary to register the ʻupdate () method in the callback set. As in this example, it may be difficult to realize the benefits of a single Timeout event and a simple state change (count` increment), but the state change progresses in a complicated manner while being affected by multiple events. This makes it possible to intuitively describe any process.

In order for the created process function / method to be executed in the simulation, it must be registered in the simulation environment. This is done in the second line from the bottom (and the third line commented out). Specifically, you can see that an instance of the Process class is created. At this time, the process of generating an event (Initialize event) that emits a signal to start the corresponding process and triggering it is automatically executed behind the scenes.

Also, the run () method in the simulation environment at the bottom line is a wrapper that repeats the step () method. As run (until = time) or run (until = event), the simulation can proceed until a certain time or until a certain event occurs. In this example, the simulation proceeds until the simulation time reaches 200.

Multi-process interaction

You can define multiple process functions / methods and execute them in the same simulation while associating them with each other. Let's look at an example here. A simple example is shown below.

class Skelton3(Skelton):
    def __init__(self, env):
        super().__init__(env)

    def main_process(self):
        while True:
            self.print_state()
            yield self.env.timeout(random.expovariate(1))  # shortcut for simpy.Timeout()
            self.count += 1
            if self.count %3 == 0:
                self.env.signal4A.succeed()  # signal for resuming sub process A

    def sub_process_A(self):
        self.env.signal4A = self.env.event()  # create the first signal
        while True:
            yield self.env.signal4A
            print('> sub process A is resumed at {}'.format(round(self.env.now)))
            self.env.signal4A = self.env.event()  # create the next signal
            if self.count %5 == 0:
                self.env.process(self.sub_process_B())  # register sub process B

    def sub_process_B(self):
        print('>> sub process B is started at {}'.format(round(self.env.now)))
        yield self.env.timeout(10)  # shortcut for simpy.Timeout()
        print('>> sub process B is finished at {}'.format(round(self.env.now)))

env = simpy.Environment()
env.model = Skelton3(env)
env.process(env.model.main_process())  # shortcut for simpy.Process()
env.process(env.model.sub_process_A())  # shortcut for simpy.Process()
env.run(until=200)

Three process methods, main_process (), sub_pricess_A (), and sub_process_B (), are defined in the Skelton3 class. Of these, the main_process () method is almost the same as the process_method () method of the Skelton2 class, except for the last two lines. The timeout () method in the simulation environment is a shortcut to simpy.Timeout () and is often used because it requires only one argument.

In the last two lines added, you can see that a certain process is being executed when the value of count is divisible by 3. Here, signal4A in the simulation environment is an instance of the Event class generated in the 1st line (and 5th line) of thesub_process_A ()method, that is, an event. And the succeed () method of the event executes the process of triggering it. Therefore, this part fulfills the function of triggering signal4A every time count is divisible by 3.

Next, look at the sub_process_A () method. Since this event is yielded on the third line, this method will be paused at this point. Then, signal4A is triggered by themain_process ()method, and when the simulation environment causes this event, thesub_process_A ()method is restarted. This flow is one of the typical methods for associating multiple process functions / methods.

Looking at the second and third lines from the bottom of the entire code, you can see that both the main_process () method and the sub_process_A () method are registered in the simulation environment before the simulation starts. The process () method in the simulation environment is a shortcut to simpy.Process (), which is also often used because it requires only one argument.

Therefore, when the simulation starts, these processes will start automatically and proceed according to the interaction defined above (specifically, the main_process () method will start first and then to yield. After proceeding and pausing, the sub_process_A () method starts, proceeds to yield, and pauses. After that, when a Timeout event occurs, the main_process () method is restarted, in which the signal4A`` When occurs (then the main_process ()method is paused), thesub_process_A ()` method is restarted, and so on).

Next, let's look at the sub_process_B () method. It can be seen that this is a one-shot process that does not have a while loop. How is the execution of this process controlled? In fact, the mystery is hidden in the sub_process_A () method. Look at the last two lines. When count is divisible by 5, you can see that thesub_process_B ()method is registered in the simulation environment. In response to this, this process will be executed automatically. In this way, the registration of a new process in the simulation environment can be performed not only before the start of the simulation but also at any time after the start of the simulation. This flow is also one of the typical methods for associating multiple process functions / methods.

A slightly more advanced topic (entrance to)

Event value and ok

The event ʻe has a variable called value. The default value of ʻe.value is None, but you can set it to a value (other than None) and pass it to the process function / method. To do this, when triggering the event ʻe`,

e.succeed(The value you want to set in value)

(In the case of Timeout event, specify as " value = value you want to set to value "as a keyword argument when creating an instance). Then, on the process function / method side, in the yield part,

v = yied e

If you write, the value of ʻe.value is entered in v`.

Furthermore, the event ʻe also has a variable called ʻok. If the succeed () method is used when triggering the event ʻe, ʻe.ok = True is automatically set. This means that the event happened successfully, as you can see from the name of the succeed () method.

In fact, you can also use methods such as ʻe.fail (exception) and ʻe.trigger (event) to trigger the event ʻe. In the former, ʻe.ok = False, suggesting that the occurrence of the event failed in some way. When this method is used, the exception specified in ʻexception is entered in ʻe.value, and the exception occurs when the event ʻe is processed (so the waiting process function- Exception handling is performed by a method etc.). Also, in the latter, the values of ʻok and value of event ʻe are set to be the same as another event ʻevent passed as an argument.

This and that of event standby

A process function / method can be used to wait for a logical connection of multiple events. In that case, use & for the and combination and | for the or combination. For example, if there are three events ʻe1, ʻe2, ʻe3`

values = yield (e1 | e2) & e3

It means that it can be done like this. At this time, values becomes the OrderedDict of value of each event (of course, if the value of value of each event is unnecessary," values = `" need not be written).

Conversely, the same event may be waited for by multiple process functions / methods. In this case, those processes will be restarted in the order in which the restart instructions are (automatically) added to the set of callbacks for that event.

About Process class

When registering a process function / method, an instance of the Process class was created. this,

p = simpy.Process(env, process_func())

It may be convenient to be able to refer to it later, such as.

In fact, since the Process class inherits from the Event class, this can also be regarded as a type of event. That is, the above p can be treated as an event (it is considered to be triggered when returning, and if there is a return value, it becomes the value of value).

Also, by calling the ʻinterrupt ()method before the eventp is triggered, the corresponding process function / method can be interrupted (abnormal termination). As a result, the corresponding resume instruction is deleted from the set of callbacks for the event ʻe that the process function / method is waiting for in yield. In addition, since the exception simpy.exceptions.Interrupt (cause) is thrown into this process function / method, the behavior at the time of abnormal termination can be specified by receiving and processing it. This ʻinterrupt () method does not affect the event e itself (so it may wait for the event ʻe again after exception handling).

Simple inventory management example

Finally, to give you a more concrete image, let me give you an example of simple inventory management that I covered last time.

class Model:
    def __init__(self, env, op, oq, lt, init):
        self.env = env
        self.op = op  # ordering point
        self.oq = oq  # order quantity
        self.lt = lt  # replenishment lead time
        self.at_hand = init  # how many items you have at hand
        self.loss = 0  # opportunity loss
        self.orders = []  # list of back orders

    @property
    def total(self):
        return sum(self.orders) +self.at_hand

    def print_state(self):
        print('[{}] current level: {}, back order: {}, lost sales: {} '.format(round(self.env.now), self.at_hand, self.orders, self.loss))
        self.env.log.extend()

    def seller(self):
        while True:
            yield self.env.timeout(random.expovariate(1))
            if self.at_hand > 0:
                self.at_hand -= 1  # sell an item to the customer
                self.env.stocktake.succeed()  # activate the stocktaker
            else:
                self.loss += 1  # sorry we are out of stock
            self.print_state()  # state after dealing with each customer

    def stocktaker(self):
        self.env.stocktake = self.env.event()  # create the first signal
        while True:
            yield self.env.stocktake
            if self.total <= self.op:
                self.orders.append(self.oq)
                self.env.process(self.deliverer())  # activate deliverer
            self.env.stocktake = self.env.event()  # create the next signal

    def deliverer(self):
        self.print_state()  # state after an order is placed
        yield self.env.timeout(self.lt)
        if len(self.orders) > 0:
            self.at_hand += self.orders.pop(0)
        self.print_state()  # state after an order is fulfilled

Compared to the previous Model class, you can see that the run () method (and some other methods) has been removed and three new process methods have been defined. These process methods are for the sales person who corresponds to the randomly arriving customer, the inventory manager who checks the in-store inventory amount and places an order as needed, and the delivery person who receives the order and delivers the goods. It corresponds to each work. Compared to the previous run () method, in which these functions were described in a mixed manner, it seems that the visibility of the code has improved. This effect increases with the scale of the target system.

Let's make some changes to the Log class according to the introduction of SImPy.

import matplotlib.pyplot as plt

class Log:
    def __init__(self, env):
        self.env = env
        self.time = []
        self.at_hand = []
        self.loss = []
        self.total = []
        self.extend()

    def extend(self):
        self.time.append(self.env.now)
        self.at_hand.append(self.env.model.at_hand)
        self.loss.append(self.env.model.loss)
        self.total.append(self.env.model.total)

    def plot_log(self):
        plt.plot(self.time, self.at_hand, drawstyle = "steps-post")
        plt.xlabel("time (minute)")
        plt.ylabel("number of items")
        plt.show()

To run this simulation model, do the following:

env = simpy.Environment()
env.model = Model(env, 10, 20, 10, 20)  # op, oq, lt, init
env.log = Log(env)
env.process(env.model.seller())
env.process(env.model.stocktaker())
env.run(until=200)
env.log.plot_log()

Exercises

Let's rewrite the simulation model created in the previous exercise, which expresses the state of lunch time at a restaurant, into a process-oriented code using SImPy.

Summary

This time, we introduced SimPy and introduced the basics of how to build a process-oriented simulation model using it. Next time, let's look at resource-related classes and how to use them.

Link

Recommended Posts

Introduction to Discrete Event Simulation Using Python # 2
Introduction to Python language
Introduction to OpenCV (python)-(2)
Post to Twitter using Python
Start to Selenium using python
Introduction to serial communication [Python]
[Introduction to Python] <list> [edit: 2020/02/22]
An introduction to Python Programming
[Introduction to Python] How to stop the loop using break?
Introduction to discord.py (3) Using voice
[Introduction to Python] How to write repetitive statements using for statements
Introduction to Python For, While
[Technical book] Introduction to data analysis using Python -1 Chapter Introduction-
[Introduction to Python] How to write conditional branches using if statements
[Python] Introduction to graph creation using coronavirus data [For beginners]
[Introduction to Udemy Python 3 + Application] 58. Lambda
[Introduction to Udemy Python 3 + Application] 31. Comments
Introduction to Python Numerical Library NumPy
Practice! !! Introduction to Python (Type Hints)
[Introduction to Python3 Day 1] Programming and Python
[Introduction to Python] <numpy ndarray> [edit: 2020/02/22]
[Introduction to Udemy Python 3 + Application] 57. Decorator
Introduction to Python Hands On Part 1
[Introduction to Python3 Day 13] Chapter 7 Strings (7.1-7.1.1.1)
[Introduction to Python] How to parse JSON
[Introduction to Udemy Python 3 + Application] 56. Closure
[Introduction to Python3 Day 14] Chapter 7 Strings (7.1.1.1 to 7.1.1.4)
Introduction to Protobuf-c (C language ⇔ Python)
[Introduction to Udemy Python3 + Application] 59. Generator
Using Cloud Storage from Python3 (Introduction)
[Introduction to Python3 Day 15] Chapter 7 Strings (7.1.2-7.1.2.2)
[Introduction to Python] Let's use pandas
[Introduction to Python] Let's use pandas
[Introduction to Udemy Python 3 + Application] Summary
Introduction to image analysis opencv python
[Introduction to Python] Let's use pandas
An introduction to Python for non-engineers
Introduction to Python Django (2) Mac Edition
[AWS SAM] Introduction to Python version
[Introduction to Python3 Day 21] Chapter 10 System (10.1 to 10.5)
[Python Tutorial] An Easy Introduction to Python
[Introduction to Udemy Python3 + Application] 18. List methods
[Introduction to Udemy Python3 + Application] 63. Generator comprehension
[Python] Fluid simulation: From linear to non-linear
[Introduction to Udemy Python3 + Application] 28. Collective type
[Introduction to Python] How to use class in Python?
From Python to using MeCab (and CaboCha)
[Introduction to Udemy Python3 + Application] 25. Dictionary-type method
[Introduction to Udemy Python3 + Application] 33. if statement
[Introduction to Udemy Python3 + Application] 13. Character method
[Introduction to Udemy Python3 + Application] 48. Function definition
A super introduction to Python bit operations
[Introduction to Udemy Python 3 + Application] 10. Numerical values
Introduction to Python Image Inflating Image inflating with ImageDataGenerator
Web-WF Python Tornado Part 3 (Introduction to Openpyexcel)
[Introduction to Udemy Python3 + Application] 21. Tuple type
[PyTorch] Introduction to document classification using BERT
[Introduction to Udemy Python3 + Application] 45. enumerate function
[Introduction to Udemy Python3 + Application] 41. Input function
Log in to Slack using requests in Python
[Introduction to Python3 Day 19] Chapter 8 Data Destinations (8.4-8.5)