SWEN90004
Modelling Complex Software Systems
Lecture Cx.01 Introduction to Complex Systems
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
SLIDE 1
What are complex systems?
SLIDE 2
What is a system?
A set of things working together as parts of a mechanism or an interconnecting network; a complex whole
Physiology: A set of organs in the body with a common structure or function Biology: The human or animal body as a whole
Computing: A group of related hardware units or programs or both, especially
when dedicated to a single application
Astronomy: A group of celestial objects connected by their mutual attractive
forces, especially moving in orbits about a centre Oxford Dictionary
SLIDE 3
But what makes a system complex?
SLIDE 4
Few parts, simple rules, simple behaviour
the two-body problem:
can be solved analytically
produces regular trajectories
FigureA single planet orbiting a star
SLIDE 5
The two-body problem is to determine the motion of two interacting bodies; for example, a moon orbiting a planet, a planet orbiting a star (gravitational force) or, at a microscopic scale, an electron orbiting an atomic nucleus (electromagnetic force).
The two-body problem can be solved by resolving into two one-body problems, eac of which can be solved independently.
Few parts, simple rules, complex behaviour
the three-body problem:
no exact mathematical solution produces chaotic trajectories
FigureThe path of a single planet orbiting two stars http://sprott.physics.wisc.edu/chaos/3body.htm
SLIDE 6
The addition of a third body with it’s own position, mass and motion renders the system’s dynamics much more complex. Examples include the motion of a moon around a planet, that simulatenously orbits a star, or a planet within a binary star system.
Formalised in the 17th Century by Newton, it’s technical importance was in sea navigation, enabling determination of lonitude.
More recent application is in the area of space flight, for example considering the trajectory of spacecraft in conjunction with the movement of the Earth and Moon.
NB: this and the following few slides are based on lectures developed by René Doursat, whose (excellent) slides are available here: http://doursat.free.fr/teaching.html
Few parts, simple rules, complex behaviour
low-dimensional chaos:
the logistic equation: xn+1 = rxn(1 − xn) more on this next lecture
FigureA bifurcation diagram based on the logistic map https://www.flickr.com/photos/davidmxg
SLIDE 7
The logistic map is an example of a relatively simple dynamical equation that can give rise to broad range of complex emergent behaviours, including chaos. We are going to explore this model in some detail on Wednesday.
Many parts, simple rules, simple behaviour
crystals and gases
highly ordered and regular (crystal)
highly disordered but statistically homogeneous (gas)
FigureDiamond crystal structure http://www.crystalmaker.com
http://ccl.northwestern.edu/netlogo/models/GasLabMovingPiston
FigureGas in a piston
SLIDE 8
In contrast to the preceding systems, these examples consist of many interacting parts (molecules). The rules for their interaction are relatively simple, defined by the strength of interaction forces between particles, and their kinetic energy.
For crystals, the emergent structure of the lattice will depend upon the arrangement of atoms for that material. For gases, the emergent behaviour is governed by Newtonian dynamics or complex dynamics, and can analysed and described at a macro-level using statistical mechanics.
Many parts, simple rules, complex behaviour
flocking behaviour
also cellular automata, pattern formation, complex networks archetypal complex systems
http://www.alaindelorme.com/ https://www.youtube.com/watch?v=eakKfY5aHmY
FigureA murmuration of starlings
SLIDE 9
Again, we have systems composed of many relatively simple parts, interacting according to relatively simple rules, but now the behaviour that emerges is much more complex. A key feature of these systems is that the interesting global behaviour is very difficult, if not impossible, to predict by examining a single part of the system.
For example, examining a single starling won’t provide us with the key to understanding the flight
patterns produced by the whole flock.
Yet, we can use three simple rules to generate this flocking behaviour:
1. separation: each bird wants to maintain a certain distance from its neighbours
2. alignment: each bird wants to be heading in the same direction as its neighbours
3. cohesion: each bird wants to remain within the flock
Human crowds can also spontaneously exhibit such flocking behaviour.
We will focus on this class of systems throughout the course, particularly in Weeks 3 (Cellular Automata models) and 5 (Complex networks).
Many parts, complicated rules, complex behaviour
biological development, evolution, societies, markets
heterogeneous rules, specialisation, hierarchies
behaviour is complex, but can be reproducible and robust
FigureDevelopment of C. elegans
Esnard, J. 2001. The Plant Health Instructor http://animal-kid.com/termite-mound.html
FigureTermite mound structure
SLIDE 10
Again, we have many parts, but now these parts are more specialised, and the rules that govern their interaction are more detailed.
Consider biological development: a single fertilised egg cell divides, again and again, with each new generation of cells becoming more specialised in their functional role, until the full organism is formed. While the genome within each cell can be considered a ‘blueprint’ for this process, the end result is a product of a complex interplay among the cells, and between the cells and their environment.
At a different scale, a termite colony contains individuals with multiple different roles (defense, construction, foraging, reproduction), but while there is a queen, who has reproductive responsibilities, there is no centralised leader who directs the actions of each termite. Their interactions are local, with one another, and mediated by the environment, via chemical signals that they deposit. Nonetheless the mounds they construct are complex and multi-functional structures.
Other systems in this category include the brain and immune system, in which various specialised classes of cell interact to produce cognition and defense against disease, and human societies, in which people play a wide variety of specialised roles.
We will focus on this class of system in Weeks 4 (Agent-based models) and 5 (Complex networks).
Many parts, complicated rules, deterministic behaviour
classical engineering
many specialised parts
globally designed to ensure predictable behaviour
http://en.wikipedia.org/wiki/Systems_engineering
SLIDE 11
Now we move onto systems that also consist of many intricate parts that interact via complicated rules.
These systems are not typically considered ‘complex systems’ because their behaviour is designed rather than emergent. These globally complicated systems can be decomposed into subsystems that interact with one another in a linear fashion.
Some people have described emergence as ‘surprising’ behaviour. A goal of the design of these systems is explicitly to avoid such surprise.
Many parts, complicated rules, centralised behaviour
orchestra, military, administration
behaviour governed by a central cause, leader or plan
FigureDublin orchestra FigureUS Fife & Drum Corps
http://en.wikipedia.org/wiki/Orchestra http://www.acclaimimages.com/_gallery/_pages/0420-0908-1715-3754.html
SLIDE 12
Again, we have many parts in these systems, and potentially complicated rules determining how they all interact with one another. There is also a sense in which the global behaviour is emergent: the symphony produced by an orchestra is greater than the individaal parts played by each musician. However, these systems are not considered complex, because this global behaviour is the result of a centralised controller: the conductor, score, general, etc.
What is a complex system?
A working definition:
Complex systems. . .
are made up of a number of components. . .
that interact with each other. . .
typically in a non-linear fashion. Complex systems. . .
may arise from and evolve through self-organization. . .
are neither completely regular nor completely random. . .
permit the development of emergent behaviour at macroscopic scales.
from Hiroki Sayama, Introduction to the Modelling and Analysis of Complex Systems
SLIDE 13
Properties of complex systems
SLIDE 14
Properties of complex systems
Emergence
The system has properties that the individual parts do not
These properties cannot be easily inferred or predicted
Different properties can emerge from the same parts, depending upon context or
arrangement
Self-organisation
Order increases without external intervention
Typically as a result of interactions between parts
SLIDE 15
Emergence:
In the bird flock, we can see global patterns of movement (the shape of the flock) that are not apparent from observing any individual bird, and indeed, we could not predict the shape of the flock on the basis of observing an individual bird.
In biological development, cells differentiate into more specialised types (eg, skin cells, blood cells, nerve cells) depending upon signals they receive from their surrounding environment (including from other cells)
Self-organisation:
In the bird flock, the global pattern is neither completely regular nor completely random, but it does display some order or organisation. This order is not imposed externally, but results from a simple set of rules describing how each bird moves in response to the other birds around it.
In biological development, a single egg cell transforms into a complex organism without an explicit ‘blueprint’ or instruction set.
Properties of complex systems
Decentralisation
There is not a single controller or ‘leader’
distribution: each part carries a subset of global information bounded knowledge: no part has a full view of the whole
parallelism: parts can act simultaneously
Feedback
Positive feedback amplifies fluctuations in system state Negative feedback dampens fluctuations in system state
SLIDE 16
Decentralisation:
In the bird flock, the bird at the front is not the ‘leader’, they all act independently (guided by *local* cues. No bird could be aware of the whole flock of which they are apart, and all birds are continuously updating the position.
Feedback:
Positive feedback in the stockmarket: – people buy shares with the expectation that prices will go up
– as more people buy shares, demand increases and drives the price up – therefore *more* people want to buy shares, further increasing the price
Negative feedback in an air-conditioner thermostat: – As temperature *increases*, a switch is triggered and the air-conditioner turns *on* – The air-conditioner reduces the temperature – As temperature *decreases*, the reverse switch is triggered and the air-conditioner turns *off*
Note: *negative* feedback acts to make system behaviour more *stable*, while *positive* feedback makes system behaviour more *unstable*.
Exercise
What are some of the complex systems found in cities? What are the parts? What are the interactions? What are the effects of complexity?
http://www.fastcoexist.com/1680269
SLIDE 17
Modelling complex systems
SLIDE 18
What is a model?
A simplified description, especially a mathematical one, of a system or process, to assist calculations and predictions.
Oxford Dictionary
SLIDE 19
Why build models?
Models allow us to examine system behaviour in ways that are not feasible in the real world:
too expensive
too time-consuming not ethical
simply not possible
Models help us to understand a system by building it
SLIDE 20
Types of models
Mathematical models
For some systems, we can describe the global state and behaviour in terms of
macro-equations
For example, in a predator-prey system:
state:
[W,S] whereW =#wolves,S=#sheep
behaviour:
dS/dt = αS − βSW dW/dt = δSW − γW
where α, β, δ and γ are interaction parameters
SLIDE 21
Types of model
Mathematical models – analytic solutions
For some systems, these macro-equations exist and have an analytical solution (found using calculus):
eg, geometric GDP growth → exponential function dG(t)/dt = ρG(t) → G(t) = G(0)eρt
Unfortunately, many systems have no such analytic solution
Mathematical models – numerical analysis
Here, numerical analysis can be used
discretization of space into cells and time into steps
solve algorithmically (step-by-step) to discover future trajectory
SLIDE 22
Types of model
What if there are no macro-equations?
no macroscopic description of system such as pressure or GDP
systems contain heterogeneity
parts are irregularly located in space
parts are connected in a complex network
parts are differentiated/specialised into various types
systems are dynamically adaptive
interaction topology changes over time in response to environment
SLIDE 23
Types of model
Computational models
In particular agent-based models (ABMs), which arose (in the 1960s) to model systems that were too complex for analytical descriptions
system parts :
agents with local state and rules
system structure :
patterns of local interaction between agents
system behaviour :
dynamic rules for updating agent state on the basis of interactions
The rapid growth of computational power has made ABMs a practical tool
SLIDE 24
Steps in modelling a complex system
1. define the key questions
2. identify the structure (parts and interactions) of the system
3. define the possible states for each part
4. define how the state of each part changes over time through interactions with
other parts
5. verify, validate and evaluate the model in terms of simplicity, correctness and
robustness
6. define and run experiments with the model to address key questions
SLIDE 25
Questions in complex system modelling
how can we explain current and past events? evolution of multicellular life, disease outbreaks
global climate change, mass extinctions
political and social extremism, the collapse of civilisations stock market crashes, economic bubbles
how can we predict future behaviour?
this is often why we want to understand systems
how can we design and build better engineered systems? nature-inspired optimisation (ant colony, particle swarm)
decentralised computing (the Internet)
autonomous sensor networks, ambient computing
SLIDE 26
Assignment
Replication of an existing NetLogo model in Java
“replication is a critical component of the scientific method and a core practice of
scientists”
Wilensky & Rand (2007), Making Models Match: Replicating an Agent-Based Model, JASSS 10(4):2
work in groups of three
choose a NetLogo model (I will provide a shortlist) explore the behaviour of the NetLogo model
design and implement the model in Java
analyse your Java model and compare to the original extend the model to address a new question
write a report on what you find
submit report and code Full details available on LMS.
SLIDE 27
References and further information
Boccara, M (2010) Modeling Complex Systems. Springer. (ebook online via library)
Flake, GW (1998) Thye Computational Beauty of Nature. MIT Press. (ebook online via library)
Bar-Yam, Y (1997). Dynamics of Complex Systems http://necsi.edu/publications/dcs/index.html#fulltext
Wolfram, SA new kind of science. http://www.wolframscience.com/
New England Complex Systems Institute http://necsi.edu/
Santa Fe Institute for Complex System http://www.santafe.edu/
The Journal of Artificial Societies and Social Simulation http://jasss.soc.surrey.ac.uk/
Netlogo http://ccl.northwestern.edu/netlogo/
Axelrod, R and Tesfatsion, L On-Line Guide for Newcomers to Agent-Based Modeling in the Social Sciences http://www2.econ.iastate.edu/tesfatsi/abmread.htm
SLIDE 28