SWEN90004
Modelling Complex Software Systems
Lecture Cx.06
Cellular Automata II: Implementing a Model
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
SLIDE 1
Recap
Cellular Automata (CA) as a formalism for modelling complex systems.
Compared to the ODE models, they are bottom up rather than top down.
Complex system characteristics: many interacting parts
parallel distributed processing
state updates are determined by local rules and interactions complex global behaviour emerges
Can be suited for modelling systems where “macro-rules” are hard to identify.
But, not straight forward to analyse behaviour.
Good for testing questions such as: Can local mechanism X generate phenomenon Y?
SLIDE 2
Objectives
recognise some of the key decisions that need to be made when implementing a CA model
understand the steps involved in specifying a CA model based on an ODE model appreciate the ‘creative’ aspects of model design
SLIDE 3
Model implementation
SLIDE 4
Key questions: Space
How is space represented?
How are agents located in space?
Consider:
discrete vs continuous space
single vs multiple occupancy of cells proximate vs long-range interactions
SLIDE 5
Key questions: Time
How is time represented?
How does the order of events affect behaviour?
Consider:
the order in which the state of each cell is updated
will every component of the system be updated simultaneously? (synchronous updating) or will they be updated one-at-a-time? (asynchronous updating)
if so, in what order will the components be updated?
discrete vs continuous time
discrete: check what happens at each time step
continuous: what event happens next and when does it happen?
SLIDE 6
Key questions: Information
What information do components (cells/agents) use? How do they obtain it?
Consider:
the scope of variables: global, cell (patch), agent (turtle)
how these variables are accessed and modified
the (spatial) range of sensing: what happens as this is increased? (ie, what is the
neighbourhood)
SLIDE 7
Key questions: State updating
Will updating be deterministic or stochastic? How does this decision affect behaviour?
will the future state of a component be uniquely specified by its current inputs, environment, etc? (deterministic updating)?
or will their be some randomness involved? (stochastic updating)
SLIDE 8
Application: Lotka-Volterra
SLIDE 9
The Lotka-Volterra model (from lecture Cx.03)
Prey (rabbits):
Predators (red foxes):
α = growth rate of the rabbit population
β = rate at which foxes predate upon (eat) rabbits
δ = growth rate of the fox population
γ = decay rate of the fox population due to death and migration
How could you build a CA model of the fox-rabbit population dynamics?
Parameters:
dR dt
dF dt
= αR − βRF
= δRF − γF
SLIDE 10
A CA version of the Lotka-Volterra model
Rather than modelling the size of each population (the macro-variable) directly, we will represent each individual explicitly, and then observe (measure) the size of the population.
Space: Rather than assuming our populations are “well mixed”, we will represent the location of each individual on a 2D regular lattice (grid).
Space: We will make a new assumption that only one animal can occupy a grid space at any point in time.
Time: Rather than treating time continuously, we will use discrete time steps.
Information: We will assume that each individual animal is only aware of its
immediate neighbours.
State updating: . . . (next slides)
SLIDE 11
A CA version of the Lotka-Volterra model Representing our system
Each cell in our 2D lattice will take one of three values:
0
xi,j = 1 2
if site (i, j) is empty
if site (i,j) contains a rabbit (prey) if site (i,j) contains a fox (predator)
SLIDE 12 In NetLogo:
;; create environment ask patches [ set pcolor green ]
;; create rabbits ask n-of initial-rabbits patches [ set pcolor white ] ;; create foxes ask n-of initial-foxes patches [ set pcolor red ]
A CA version of the Lotka-Volterra model
Update rules
1. Pick a cell (A) from our lattice at random
2. Choose one of A’s neighbours (B) at random
3. Update as follows:
if A contains a rabbit and B is empty, then, with probability α, the rabbit reproduces, B
now contains a new rabbit—prey reproduction
if A contains a fox and B contains a rabbit, or if A contains a rabbit and B contains a
fox, then with probability β the rabbit is eaten; and, if this happens, with probability δ, the cell formerly containing a rabbit now contains a new fox—prey death and predator reproduction
if A contains a fox and B is empty, then, with probability γ, the fox dies—predator death
if A is empty and B contains a fox or a rabbit, then the adjacent animal moves from B
to A—animal movement
SLIDE 13
A CA version of the Lotka-Volterra model
Update rules—prey reproduction
If A contains a rabbit and B is empty, then, with probability α, the rabbit reproduces, B now contains a new rabbit.
SLIDE 14 In NetLogo:
if A = white and B = green [ if random-float 1 < alpha [
ask nbor [ set pcolor white ] ]
]
A CA version of the Lotka-Volterra model
Update rules—predation (prey death & predator reproduction)
If A contains a fox and B contains a rabbit, or if A contains a rabbit and B contains a fox, then, with probability β, the rabbit is eaten; and, if this happens, then with probability δ, the cell formerly containing a rabbit now contains a new fox.
SLIDE 15 In NetLogo:
if A = red and B = white [ if random-float 1 < beta [
ask nbor [ set pcolor green ] if random-float 1 < delta [
ask nbor [ set pcolor red ] ]
] ]
Note that this code only handles ONE of the two possible predation cases!
A CA version of the Lotka-Volterra model
Update rules—predator death
If A contains a fox and B is empty, then, with probability γ, the fox dies.
SLIDE 16 In NetLogo:
if A = red and B = green [
if random-float 1 < gamma [ ask self [ set pcolor green ]
] ]
A CA version of the Lotka-Volterra model
Update rules—movement
If A is empty and B contains a fox or a rabbit, then the adjacent animal moves from B to A.
SLIDE 17 In NetLogo:
if A = green and B != green [ ask self [ set pcolor B ]
ask nbor [ set pcolor green ]
]
Application: Epidemics
SLIDE 18
The SIR disease model (from lecture Cx.04)
dS dt
dI dt
dR
= γI dt
S = the fraction of the population who are currently susceptible I = the fraction of the population who are currently infectious R = the fraction of the population who are currently recovered Note: thereforeS+I+R=1
β = the rate of effective contact between susceptible and infectious people γ = the rate of recovery of infectious people
State variables:
Parameters:
= −βSI
= βSI − γI
SLIDE 19
A CA version of the SIR disease model
Rather than measuring the fractions of the population in each disease compartment (the macro-variable) directly, we will represent each individual explicitly, tagged with their current disease status, and then observe (measure) population fractions in each state.
Again, rather than assuming our populations are “well mixed”, we will represent the location of each individual on a 2D regular lattice (grid).
Again, rather than treating time continuously, we will use discrete time steps.
We will make the new assumption that only one person occupies a grid cell at
once, and that people’s location is fixed over time (ie, they don’t move!)
Initially, a fraction p of the population is infectious, and the remainder of the population is susceptible.
SLIDE 20
A CA version of the SIR disease model Representing our system—Version 1
Each cell in our 2D lattice will take one of three values:
0
xi,j = 1 2
if the person at site (i,j) is susceptible if the person at site (i,j) is infectious if the person at site (i,j) is recovered
SLIDE 21
A CA version of the SIR model
Update rules—Version 1
1. A susceptible person can be infected by an infectious neighbour with probability β 2. An infectious person recovers with probability γ
SLIDE 22
A different CA version of the SIR model
Note that for any real world system, we may have a choice of multiple possible models
As before, each site can be susceptible (S), infectious (I) or recovered (R) to a disease.
Now, immunity is temporary, and people become susceptible again at a rate ω.
Thus, on average, people are:
infectious for q = γ1 days
recovered (immune) for r = ω1 days
A variation—Version 2
SLIDE 23
A different CA version of the SIR model Representing our system—Version 2
Each cell can now take a value in the range [0, q + r] as follows:
0
xi,j = 1,...,q
q + 1,...,q + r
if the person at site (i,j) is susceptible if the person at site (i,j) is infectious if the person at site (i,j) is recovered
SLIDE 24
A different CA version of the SIR model
Update rules—Version 2
1. A susceptible person becomes infected if at least one of their neighbours is infectious
2. An infectious person recovers after q days
3. A recovered person loses their immunity and becomes susceptible after r days
(waning immunity)
SLIDE 25
Exploring our model behaviour
Parameter sweeps
A common approach to characterising the behaviour of a model is to conduct a parameter sweep: systematically varying the value of each parameter to understand its effect on system behaviour.
For example (Version 2), run the model for each combination of: p = 0.01, 0.05, 0.1 (initial proportion of infectious people)
q = 2, 4, 8 (number of days a person is infectious)
r = 2, 4, 8 (number of days a person is recovered/immune) ie, 3 × 3 × 3 = 27 possible parameter combinations
SLIDE 26
Exploring our model behaviour
Parameter sweeps
Because our model behaviour is stochastic, we may want to run each parameter combination several times and consider the “average” behaviour of the system.
For trajectories (ie, sequences of state changes over time), this may be difficult. Typically, we identify some global measurement, record the value for each simulation run, and report the mean and standard deviation.
SLIDE 27
Looking further. . .
SLIDE 28
Extensions to the basic CA model
Asynchronous CA
The basic CA updates all cells synchronously (at the same time) at every time step. We could also update cells at different times.
Probabilistic CA
The basic CA update rules are deterministic (Cx.05 examples). We could also use update rules that are probabilistic/stochastic (Cx.06 examples).
Non-homogeneous CA
The basic CA applies the same update rule to every cell. We could also use context-sensitive rules.
Network-structured CA
The basic CA defines neighbourhood in terms of grid adjacency. We could also use a more complex network topology of neighbours (we’ll look at this later)
SLIDE 29
Why use CA?
Advantages
they are (relatively) simple and easy to implement
they can represent interactions and behaviours that are difficult to model using
ODEs
they reflect the intrinsic individuality of system components
Disadvantages
they are relatively constrained (topology, interactions, individual behaviour) the global behaviour may be difficult to interpret
Next week, we will relax some of these constraints further, and explore agent based models where the actors in a system are the primary focus.
SLIDE 30
CA can be used to demonstrate important characteristics of complex systems - self organisation
- non-linearity
- chaotic behaviour
- self-organisation
Try to identfiy about examples from this week’s lectures illustrating each of these characteristics.
Reading
Daniel Shiffman, The Nature of Code, chapter 7 (available at http://natureofcode.com/book/chapter-7-cellular-automata/)
Gary W Flake, The Computational Beauty of Nature, chapter 15
Stephen A Wolfram, A New Kind of Science, Wolfram Media, 2002
Langton, C. Studying artificial life with cellular automata. Physica D 22:120-149, 1986
Hoekstra, Alfons G.; Kroc, Jiri; Sloot, Peter M.A. (Eds.) Simulating Complex Systems by Cellular Automata. Springer. 2010
Joel L Schiff. Cellular automata : a discrete view of the world. Wiley-Interscience. 2008
SLIDE 31