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
1 / 12
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
2 / 12
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
3 / 12
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?
4 / 12
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.
5 / 12
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?
6 / 12
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
7 / 12
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
8 / 12
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 ρ
9 / 12
Outline
NetLogo demonstration
10 / 12
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?
11 / 12
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
12 / 12