Computer Science
Simulations

A simulation is a computer model of a real system. The events that are simulated may be real or imaginary. The aim is to create a model that allows the performance of the system to be explored. A simulation may be used to model traffic flow on an actual road with a view to improving things with additional roads or altering the phasing of traffic lights. A similar approach may be taken to asses the feasibility of a new road system.

Simulations are an abstraction of the real system they aim to simulate. Only the key details are included in the model - unnecessary details are removed.

Example - Simulating The Tuck Shop Queue

Suppose that we wanted to simulate a tuck shop queue over the course of a lunch break. The aim of such a simulation is to explore whether or not the current setup functions as expected (ie queue times are short and throughput is high). In our simulation we have 3 entities - the components of our simulation. The server is one of the entities in our simulation - the customer is another. The queue itself is also one of the entities in our simulation.

The entities have attributes, properties or characteristics that our simulation must take into account. For example, a customer can be waiting in the queue or being served.

Our simulation is of a system that changes discretely over time. By this we mean that changes of state are abrupt - when a customer joins the queue they are waiting, when they get to the front and the server is free, the state of this entity changes to being served. This is an abrupt rather than a gradual change.

A methodological approach to constructing a simulation is required - the following are stages that we might expect to be undertaken in setting up this simulation.

Formulate The Problem

At this stage of the process, we consider the objectives of our simulation. In this case it might be to ascertain the number of customers that can be served over a given period of time.

We also need to consider the way we are going to measure our findings in the simulation. We should be able to state what we intend to measure (average wait time, average number of customers, maximum queue length etc.) and to what degree of accuracy.

Observation

Since this is a simulation of an existing system, we would need to observe and inspect the current system to be able to abstract the key details for our simulation.

State transition diagrams are a useful tool in modelling this system. We would look at the entire life cycle of the system - in this case, we would look at the journey each new customer makes through the system until they have been served.

There would be a need to consider the real-life system as an information system. What data enter the system, what are the outputs? What are the variables? What are the relationships between different parts of the system? What are the key processes.

In our example, we should look at the probability of a customer arriving. Is it a fairly consistent rate throughout the period of opening or is it more haphazard? We would need to measure this by collecting data. We need to think about the time it takes for a person to be served. This might vary over the course of lunch time with larger items bought earlier or it may be fairly constant. It may relate to the number of items being purchased which may in turn be connected to the amount of money being spent. We would be interested in the extent to which this varies from customer to customer.

Formulate The Model

In this stage of the process, we aim to describe the model as completely as possible. Some aspects of the model are best explained using diagrams. The life cycles of the entities need to be mapped out. We also need to state any assumptions that we are making (eg assume that it takes 1 minute to serve each customer.

In formulating the model, we consider how we are going to represent the passing of time. In a time-driven simulation we increment a master clock in time units appropriate to the model. After each tick, the program must work out which events (if any) should occur.

An activity-driven simulation is another method that is used. The program checks against a schedule for the next event to occur and advances the clock by an appropriate amount of time for the activity that has taken place. To get a sense of how this approach differs, consider the arrival of a person in a queue. If our program ticks away a second at a time, it might model the arrival of a customer by generating a random number on each tick and, if the number generated falls within a specific range, may add another customer to the queue. In an activity-driven simulation, when the next event to occur is the arrival of a customer, the program advances the master clock by the amount of time that this event takes to occur - again this could be a random number.

Validate The Model

Before spending time and money on development, the model needs to be validated. This means checking its logic as well as hand-tracing. You would need to look at the effect of extreme inputs on the system and make sure that you are not missing any theoretical limits. For example, there is a physical limit to the size of a queue.

Write The Program

With a valid model, the simulation needs to be programmed. There are languages developed for this purpose but high-level languages tend to be fairly well suited.

The fact that we base our model on entities with their own attributes makes simulation particularly suited to object oriented techniques.

Validate The Program

The program, once written, needs to be validated. This can be tricky if the system being modelled doesn't really exist. If it does, we can compare our model with historical data and verify that the data produced by our model matches what we observe in the real world. If there is no system, we can only check that the logic and assumptions behind the model are valid.

Design Experiment

Once the program is designed and validated, the next step is to design experiments to use the model. The simulation needs to run long enough to make a meaningful test. Our tuck shop queue would need to run repeatedly to ensure that possible problems are not missed.

Randomness

Remember that we use the term pseudo-random to describe the random numbers that a computer generates. It is vital to make sure that the seed of the random number generator is not kept the same for each run of the simulation. In such cases, the results may a little too predictable.

When you generate a random double in C#, the value is between 0.0 and 1.0 (but does not include 1). Probabilities are measured in the same range. Conveniently then, when we want to make an event happen with a certain probabiliy, say 0.5, we need only check if our random double is less than the probability value to determine whether or not the event occurred.