CS计算机代考程序代写 chain Bioinformatics DNA 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

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