COM3524 Exam – practice “takeaway” problem Jan 2021
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.
0 10 20 30 40 50 60 70 80 90 100
Figure 1 Map showing location of depot and cities. Units are in km
Copyright By PowCoder代写 加微信 powcoder
15 10 50 50 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).
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:
pk =å tahb rs rs
rs tahb tÎALLOWED rt rt
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
COM3524 Exam – practice “takeaway” problem Jan 2021
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. Foreverychromosome
3. Calculatefitness=1/totalroutelength
4. SelectParentsforMatingPoolbasedonrelativefitness
5. ImplementprobabilisticOnePointCrossovertogeneratenewoffspring 6. ImplementprobabilisticRandomSwapMutationonoffspring
Give two reasons why this proposed algorithm might give rise to some invalid solutions to the specific delivery problem described on page 1.
[Answer] – in this case, only a subset of transitions are permitted due to the presence of roads connecting only some cities/nodes. Step 1 will therefore create a population of solutions where some transitions are invalid as roads do not exist between neighbouring points in the chromosomes e.g. ACBED contains the invalid transition A – C.
Step 5 combines the two parent genomes randomly and this may result in either repeated nodes (e.g., missing nodes (e.g ABCCD), or invalid node transitions.
Step 6 randomly swaps individual entries of a chromosome and may also result in invalid node transitions.
{Any two of the above are correct answers}
d) Your student takes note of your suggestions and implements a revised version of the Evolutionary Algorithm, that appears to work.
The delivery company asks you to implement your preferred algorithm for them, with their primary requirement that delivery routes for up to 10 possible delivery cities are identified as quickly and efficiently as possible. They want the software to be delivered to them, fully functional and optimised as much as possible, by the end of the week.
i) From your knowledge of the characteristics of the two approaches, explain which algorithm you would choose to package for the client, and why. [20%]
ii) A month later, they phone to let you know that they have been taken over by a larger company, and will now be delivering to up to 100 cities nationwide. They ask you whether you think your previously delivered algorithm will still work efficiently in this scenario. What is your response? [10%]
[ANSWER] i) In terms of efficiency requirement: The ACO works on a smaller population of solutions each iteration (no. ants/solutions == no. nodes =5), whereas an EA typically works on populations of O(100) chromosomes that need to be evaluated and operated on at multiple steps within any given iteration. Therefore for a small problem size of <10 it is likely that the ACO is more efficient (note that this was an outcome discussed in a lab session follow up).
You can also comment on the quick turnaround requested by the client – EAs are usually more complex to program and test due to the multiple steps with probabilistic calculations involved, so ACO would probably be the best option here too!
ii) For a larger problem size, the EA would probably scale better as the chromosome size tends to stay fixed. Again, this was an outcome of a lab session.
You will obtain marks for any justified argument here. You would be expected to cite sources to support your arguments where possible.
e) The new parent delivery company imposes a new business model. Under this new model, its staff receive commission for every parcel that they deliver. The expanded fleet of vehicles at other depots means that not every driver needs to visit every city on every trip, but they must still start and finish at their depot and visit at least 3 other locations. The aim of your original client is to keep their inter-city travel distance as low as possible, whilst maximising their commission.
The number of parcels to be delivered in city i, can be denoted as Ni
Your student is still working on their Evolutionary Algorithm (irrespective of whether it is actually being used by the client!). How would the student need to modify steps 1 and 2 of their algorithm (from part c) in order to take this into account? [20%]
[Answer] Step 1 needs to be modified to permit chromosomes of differing length >=3 (as well as removing any that are invalid e.g. containing repeated entries or transitions between locations not connected directly by roads.
COM3524 Exam – practice “takeaway” problem Jan 2021
The fitness function would need to be adapted to take into account the gain/profit of visiting each location rather than just the cost (distance travelled to get to/from there).
An example could be fitness = total profit – total cost (i.e. distance travelled) (or some other valid form that maximises profit and penalises distance)
So for each location the consideration is something like:
cNi – distance to reach and return to that node from the rest of the route
(where c is the commission rate)
So fitness of chromosome = cN – sum of segment lengths,
Or cN/sum of segment lengths
Where N =total number of cities visited.
Note: there is no exact mathematical formalism that is “correct” here, but your answer will be expected to be logical, justified and consistent.
END OF QUESTION PAPER