Agent-Based
Modelling and Simulations
Simulation
Agostino Poggi
System, Model & Simulation
♦ System
An actual or theoretical system in which distinct entities interact
♦ Model
A reproduction of the system at an appropriate level of granularity
♦ Simulation
Designing a model of a system, executing the model on a computer, and analyzing the execution output
Simulation Activities
Simulation Goals
♦ Imitate the operation of a real-world process or system over time
♦ Prediction
Model should produce quantitatively correct predictions depending on its input values
♦ Explanation
Qualitatively significant results are sufficient for
understanding the reaction of the system to input values
When Is Appropriate (1/3)
♦ Enables the study of an experimentation with the internal interactions of a complex system, or of a subsystem within a complex system
♦ Informational, organizational and environmental changes can be simulated and the effect of those alterations on the model’s behavior can be
observer
♦ Knowledge gained in designing a simulation model can be of great value toward suggesting
improvement in the system under investigation
When Is Appropriate (2/3)
♦ By changing simulation inputs and observing the resulting outputs, valuable insight may be obtained into which variables are most important and how variables interact
♦ Can be used as a pedagogical devices to reinforce analytic (exact) solution methodologies
♦ Can be used to experiment with new designs or policies prior to implementation, so as to prepare for what may happen
♦ Can be used to verify analytic solutions
When Is Appropriate (3/3)
♦ Requirements for a machine can be determined by simulating its different capabilities
♦ Simulation models designed for training, allow
learning without the cost and disruption of on-the- job learning
♦ Animation shows a system in simulated operation so that the plan can be visualized
♦ Modern systems (factories, service organizations, computing systems, …) are so complex that the
interactions can be treated only through simulation
When Is Not Appropriate (1/2)
♦ Simulation should not be used when the problem can be solved using common sense
♦ Simulation should not be used if the problem can be solved analytically
♦ Simulation should not be used, if it is easier to perform direct experiments
♦ Simulation should not be used, if the costs exceeds savings
♦ Simulation should not be performed, if the resources or time are not available
When Is Not Appropriate (2/2)
♦ If no data are available, not even estimate simulation is not advised
♦ If there is not enough time or persons are not available, simulation is not appropriate
♦ If managers have unreasonable expectation or the power of simulation is over estimated, simulation may not be appropriate
♦ If system behavior is too complex or cannot be defined, simulation is not appropriate
Advantages (1/2)
♦ Studies about systems can be done in the design stage
♦ Models are run rather than solver
♦ New policies, operating procedures, decision rules, information flow can be explored without disrupting the ongoing operations of the real system
♦ New hardware designs, physical layouts,
transportation systems can be tested without committing resources for their acquisition
♦ Hypotheses about how or why certain phenomena occur can be tested for feasibility
♦ Time can be compressed or expanded allowing for a speedup or slowdown of the studied phenomena
Advantages (2/2)
♦ Insight can be obtained about the interaction of variables
♦ Insight can be obtained about the importance of variables to the performance of the system
♦ Bottleneck analysis can be performed finding indication where work-in-process, information
materials and so on are being excessively delayed
♦ A simulation study can help in understanding how the system operates rather than how individuals think the system operates
♦ What-if questions can be answered (useful in the design of new systems)
Disadvantages
♦ Model building requires special training
♦ Simulation results may be difficult to interpret
♦ Simulation modeling and analysis can be time consuming and expensive
♦ Simulation is used in some cases when an analytical solution is possible or even preferable
Simulation Model
♦ Allows to study the behavior of a system as it evolves over time
♦ Takes the form of a set of assumptions concerning the operation of the system
♦ Assumptions are expressed in relationships between the entities of the system
Mathematical relationships
Logical relationships
Symbolic relationships
System Components
♦ Entity
Is an object of interest in a system
♦ Attribute
Denotes the property of an entity
♦ Activity
Is a process causing changes in a system
♦ State
Is a collection of variables necessary to describe a system at any time
♦ Event
Is an instantaneous occurrence that may change the state of the system
Modelling Dilemma
Simplicity
Generality
Lack of error (accuracy of results) Realism
(design reflects observations)
System Environment
♦ External components which interact with the
system and produce necessary changes are said to constitute the system environment
♦ In modeling systems, it is necessary to decide on the boundary between the system and its
environment
♦ This decision may depend on the purpose of the study
System Adjectives (1/2)
♦ Endogenous
Is used to describe activities and events occurring within a system
♦ Exogenous
Is used to describe activities and events in the environment that affect the system
♦ Closed
Is used for defining a system for which there is no exogenous activity and event
System Adjectives (2/2)
♦ Open system
Is used for defining a system for which there are exogenous activities and events
♦ Continuous
Is used for defining a system in which the changes are predominantly smooth
♦ Discrete
Is used for defining a system in which the changes are predominantly discontinuous
Model Types
♦ Mathematical model
Represents a system through a symbolic notation and mathematical equations
♦ Static model
Represents a system at a particular point of time
♦ Dynamic model
Represents a system as it changes over time
♦ Deterministic model
Represents a system for which a specific set of outputs always corresponds to the same set of inputs (it does not contain random variables)
♦ Stochastic model
Represents a system having one or more random variables as inputs that lead to random outputs
Simulation Types Classification
♦ Discrete versus continuous time
♦ Stochastic versus deterministic
♦ Macro versus micro
Discrete Event Simulation
♦ Model
Finite state machines, queues, Petri nets, …
♦ Execution
Read the “queue” of events and trigger new events as each event is processed
♦ Applications
Diagnosing, business decisions, networks analysis, …
Continuous Dynamic Simulation
♦ Model
Partial or ordinary differential equations
♦ Execution
Periodic numerical resolution of equations
♦ Applications
Flight simulators, electrical circuits, …
Monte Carlo Simulation
♦ Model
Can be almost anything
♦ Execution
Generate inputs randomly from the domain and perform a deterministic computation on them
♦ Applications
Physics, engineering, applied statistics, …
Cellular Automata
♦ Model
Regular n-dimensional grid of cells whose state is function of the state of their neighborhood
♦ Execution
Periodic application of rules which determine state of a cell as a function of neighboring cells
♦ Applications
Theoretical computer science, mathematics, biology, physics, engineering, cryptography, …
Macro Simulation
♦ Model
Complete system is modeled as one monolithic entity
• Populations are averaged together
• Model attempts to simulate changes in these averaged characteristics for the whole population
♦ Execution
Periodically update the state variables describing the system
♦ Applications
Naturally applies to systems that can be modeled
centrally and in which the dynamics are dominated by physical laws
Micro Simulation
♦ Model
Explicitly attempts to model specific behaviors of specific individuals
♦ Execution
Periodic communication between individuals
♦ Applications
Most appropriate for domains characterized by a high degree of localization and distribution and dominated by discrete decisions
Simulation Techniques
♦ By hand
♦ Spreadsheets
♦ Computational mathematics systems
♦ Programming in general purpose languages
♦ Simulation languages
♦ Simulation environments
Simulation Paradigms
Lotka-Volterra Prey Predator Model
Size of the prey population at time t
Size of the predator population at time t
Evolution of prey population Evolution of predator population
Simulation Time
♦ Simulation execution consists in stepping through time while updating the variables in the model
♦ In continuous-time models (e.g., differential
equations) time steps can be reduced indefinitely
♦ In discrete-time models time is quantized somehow
Leap through time using event scheduling
Employ small time increments using time slicing
Simulation Steps
♦ Problem formulation
♦ Setting of objectives and overall project plan
♦ Model conceptualization
♦ Model translation
♦ Model validation and verification
♦ Documentation and reporting
Problem Formulation
♦ Every study begins with a statement of the problem, provided by policy makers
♦ Analyst ensures its clearly understood
♦ If it is developed by analyst, policy makers should understand and agree with it
Objectives
♦ Objectives indicate the questions to be answered by simulation
♦ At this point a determination should be made
concerning whether simulation is the appropriate methodology
♦ Objectives must be made explicit through the definition of a project plan
Project Plan Definition
♦ A statement of the alternative systems
♦ A method for evaluating the effectiveness of these alternatives
♦ Number of days required to accomplish each phase of the work with the anticipated results
♦ Number of people involved
♦ Cost
Model Conceptualization
♦ Construction of a model of a system is probably as much art as science
♦ Art of modeling is enhanced by an ability
To abstract the essential features of a problem
To select and modify basic assumptions that characterize the system
To enrich and elaborate the model until a useful approximation of results
♦ Thus, it is best to start with a simple model and build toward greater complexity
♦ Model conceptualization enhance the quality of the resulting model and increase the confidence of the model user in the application of the model
Model Translation
♦ Real-world systems result in models that require a great deal of information storage and computation
♦ It can be programmed by using simulation languages or special purpose simulation environments
♦ Simulation languages are powerful and flexible
♦ Simulation environments can reduce development time
Validation
♦ It is the determination that a model is an accurate representation of the real system
♦ Crucial for guaranteeing that output of simulation will say something meaningful
♦ Achieved through calibration of the model, that is an iterative process of comparing the model to actual system behavior and their discrepancies
Verification
♦ Is the process of confirming that the model is correctly implemented
♦ Model is tested to find and fix errors in the implementation of the model
♦ There are many techniques that can be utilized to verify a model
♦ In particular, many software engineering
techniques used for software verification are applicable to simulation
Validation & Verification Process
Validation & Verification Procedures
Instruments for Output Analysis
Program Documentation
♦ Can be used again by the same or different analysts to understand how the program operates
♦ Further modification of the model will be easier
♦ Model users can change the input parameters for better performance
Process Documentation
♦ Gives the history of a simulation project
♦ Result of all the analysis should be reported clearly and concisely in a final report
♦ Enable to review the final formulation and
alternatives, results of the experiments and the recommended solution to the problem
♦ Final report provides a vehicle of certification
Some Main Simulation Tools