程序代写 Modelling Complex Software Systems

Modelling Complex Software Systems
Lecture Cx.08
Agent-Based Models II: Model development and applications

Copyright By PowCoder代写 加微信 powcoder

Semester 1, 2022

Recap and overview
􏰁 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)
􏰁 complex systems approaches to solving computing problems

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

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?

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.

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?

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

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 in 1992
􏰁 Widely applied to problems in vehicle routing and scheduling, also image
processing, circuit design and others

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 ρ

NetLogo demonstration

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?

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

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com