CS计算机代考程序代写 chain flex ant algorithm SWEN90004

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