SWEN90004
Modelling Complex Software Systems
Lecture Cx.08
Agent-Based Models II: Model development and applications
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
SLIDE 1
Recap and overview
So far:
what complex systems are
describing the behaviour of dynamic systems
ODE models (top-down, deterministic)
CA (bottom-up, can be stochastic, grid-based)
ABMs (bottom-up, stochastic, more flexible than CA)
Today:
complex systems approaches to solving computing problems
SLIDE 2
An engineering perspective on agents and complex systems
The goal of ABMs is often to provide explanatory insight into the way real world complex systems work; eg:
how do ant colonies forage in the absence of a central leader?
how will an infectious disease spread through a population?
what market dynamics arise from agents making self-interested decisions?
Naturally-occurring complex systems also suggest new and potentially valuable solutions to real world problems in computing, engineering and system design; eg:
optimisation algorithms
load balancing
traffic management
computer graphics and games supply-chains and logistics
robotics
SLIDE 3
Problem: Parcel delivery
Australia Post is main provider of postal services in Australia
Recent trends are a shift from delivery of letters to parcels: letters: fixed destinations and route
parcels: variation in destinations from day to day
Christmas 2015
1.3 million parcels delivered per day during December 2015
different addresses each day
what is the most efficient route for drivers to follow?
If a typical driver delivers 50 parcels during a daily run, how many possible routes are there?
SLIDE 4
Problem: Parcel delivery
n! (n factorial) possible routes
n! = n×(n−1)×(n−2)×···×(n−(n−1))
5 destinations 10 destinations 50 destinations
120 possible routes 3,628,800 possible routes 3 × 1064 possible routes
Some of these will be obviously suboptimal, but the optimal (shortest) route will not necessarily be clear.
SLIDE 5
The Travelling Salesman Problem
Given a list of cities, and distances between each pair of cities, what is the shortest possible route that visits all cities exactly once and returns to the original city?
SLIDE 6
The Travelling Salesman Problem
First formulated in Germany in 1832
Described and analysed mathematically in the US in the 1930s in an effort to plan
school bus routes
Shown in 1972 to be NP-complete
NP-completeness
Solutions can be verified in polynomial time
Solutions cannot be located in polynomial time (potentially exponential) Heuristic or approximate approaches often required
Often used as benchmark problems for optimisation algorithms
SLIDE 7
Note that problems in other domains may be isomorphic to the Travelling Salesman Problem.
This means, so long as the problem can be represented as identifying an efficient path on a graph, heuristic approaches developed to find solutions to the TSP may be applicable.
For example problems in bioinformatics have been represented as TSPs, where nodes in a graph are may be fragments of DNA sequence, and the distance between nodes (the edges) are a function of the similarity between those fragments.
Ant Colony Optimisation (ACO)
Ant colonies display an ability to locate efficient routes, as discussed last lecture
This ability can be used to identify efficient paths between nodes in a network
Approach developed by Marco Dorgio in 1992
Widely applied to problems in vehicle routing and scheduling, also image
processing, circuit design and others
SLIDE 8
Reminder:
Ants move from their nest (N) to the food source (F) to collect food, before returning to N. As the ants move, they deposit pheromone.
When choosing a direction to move, ants will tend to move toward high pheromone concentrations. Pheromones evaporate over time.
Ants that choose shorter routes will deposit pheromone along those routes more quickly.
Therefore pheromone will tend to accumulate on shorter routes.
More ants will take these routes, and deposit more pheromone along them (positive feedback)
Ant Colony Optimisation algorithm
1. Distribute N ants at random among the nodes (destinations)
2. Each ant randomly chooses a new node to travel to, based on:
pheromone concentration on the edge to that node (weighted by α) distance to that node (weighted by β)
it must not have visited that node previously
3. Repeat step 2 until each ant has visited all nodes
4. Calculate the total route length for each ant
5. The ant that achieved the shortest route deposits pheromone along the edges in
their route (with concentration inversely proportional to route length)
6. Pheromones evaporate at a rate ρ
SLIDE 9
NetLogo demonstration
SLIDE 10
Experimentation
How might you design a set of experiments using the ACO system? What is the question/hypothesis you would address?
What scenarios would you explore to address this question?
What outputs would you collect from the simulation runs?
How would you compare and report these outputs?
SLIDE 11
Further reading
Macal, C and North, M (2010) Tutorial on agent-based modelling and simulation, Journal of Simulation 4, 151–162
Bonabeau, E (2002) Agent-based modeling: Methods and techniques for simulating human systems, PNAS vol. 99 no. Suppl 3 7280–7287
SLIDE 12