Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COM3524 Exam – practice
1. A delivery company with a single driver needs to optimise their route to deliver to
all cities which are shown on the following map. Distances are in km and the
company’s depot is located in city A. Dotted lines indicate the existence of roads.
Figure 1 Map showing location of depot and cities. Units are in km
Location Xi (km) Yi (km)
A (Depot) 50 15
B 80 10
C 90 50
D 40 50
E 30 30
Table 1 Co-ordinates of dept and cities (in km)
The delivery company commissions you to develop a bio-inspired algorithm to find the
best delivery route for them (meaning that every delivery site is visited only once and the
route length is minimised). In the first instance, you decide to use an Ant Colony
Optimisation Algorithm (ACO).
0 10 20 30 40 50 60 70 80 90 100
0
10
20
30
40
50
60
A
B
C D
E
a) Explain briefly in a maximum of 100 words what is meant by an ACO and the key
biological behaviour that it is inspired by. [10%]
[Answer] An Ant Colony Optimisation algorithm (ACO) is a heuristic approach that can be applied to
solving a number of real-world problems, particularly those relating to routing or networking. It is based
on the behaviour of ants which communicate stigmergically by the deposition of a pheromone trail in
order to aid the process of the location and collection of food sources. Ants returning to the next lay a
pheromone trail that decays over time. Shorter, more desirable routes will accumulate pheromone and
hence be followed by more ants, causing further deposition. This process is the inspiration behind the ACO
approach [99 words]
b) The probability of ant k located at node r, choosing to transition to an allowed node,
s, is given by the following formula:
Where τ is the pheromone strength on edge rs, and η is the inverse of distance
between nodes r and s.
a, b are weighting parameters
At the start of the simulation, assume that pheromone is equally distributed on all
model edges (=1) and a, b are both set to one.
In the first update step, what is the probability that an ant located at the depot will
transition to i) node B, ii) node D and iii) node E? [20%]
[Answer] In this simplified case τ, a, b all =1, so the problem reduces to:
= ∑ ! ∈$%%&'()
Where ηrs is the inverse of distance between nodes r and s.
Use Pythagoras to calculate magnitude of distance vectors for each ALLOWED transition :
Depot to node B= sqrt( xb - xdepot)^2 + sqrt( yb - ydepot)^2) = sqrt((80 – 50)^2 + (10 – 15)^2
= sqrt (30^2 + (-5)^2) = 30.4 so ηAB »1/30.4
So ηAB » 0.033
åÎ
=
ALLOWEDt rtrt
rsrsk
rsp ba
ba
ht
ht
COM3524 Exam – practice “takeaway” problem Jan 2021
COM3524 3
Repeating for other nodes:
ηAD » 1/36.4 » 0.0275
ηAE = 1/25 = 0.04
so i) pAB » 0.033/(0.033 + 0.0275 + 0.04) » 0.33
ii) pAD = 0.0275/(0.033 + 0.0275 + 0.04) » 0.27
iii) pAE = 0.04/(0.033 + 0.0275 + 0.04) » 0.4
Note: you can retain precision (and save time!) by not bothering to take the individual inverses and
simply using the relative ratio of relative distances between nodes, which is equivalent in this case!
c) You fully implement your ACO algorithm and find it works reasonably well.
However, you are keen to explore other bio-inspired approaches to solve the
problem and decide to supervise a student project to develop an Evolutionary
algorithm to apply to the same problem, so you can compare them.
The student reads a textbook on Evolutionary Algorithm approaches and presents
you with the following plan for the algorithm that they propose to implement
1. Generate random initial population of any route permutations of ABCDE
2. For every chromosome
3. Calculate fitness = 1/total route length
4. Select Parents for Mating Pool based on relative fitness
5. Implement probabilistic One Point Crossover to generate new offspring
6. Implement probabilistic Random Swap Mutation on offspring
Give two reasons why this proposed algorithm might give rise to some invalid
solutions to the specific delivery problem described on page 1.
[20%]