Data Provided: None
DEPARTMENT OF COMPUTER SCIENCE Autumn Semester 2020-2021 COM3524 30 minutes
This exam has one question, consisting of six parts. Answer ALL parts of the question.
Figures in square brackets indicate the percentage of available marks allocated to each part of a question.
Copyright By PowCoder代写 加微信 powcoder
1. A company of scrap metal merchants have a single van. They receive calls from members of the public in 8 different locations offering metal, each with a potential value, Pi.
Customer Xi (km) Yi (km) Profit, Pi (¡ê)
1 70 90 90 2 80 10 120 3 20 20 100 4 10 50 90 5 80 50 80 6 40 60 60 7 20 90 100 8 90 20 80
The van depot is located at co-ordinates [60,60], as shown in the figure below.
Figure 1 Location of customers (red crosses) and depot (blue circle). All units are in km.
The running costs of the vehicle, including the overhead of paying the driver, is equivalent to ¡ê10 per km. The company asks you to apply an Evolutionary-Algorithm- based approach in order to find the most profitable route starting and ending at the depot, for them to use on any day, given that the know the likely value of goods to be collected at each pick-up point.
a) What is the general form (in words, or a mathematical expression) of a suitable fitness function for a solution? Note that there are a number of valid possibilities here, so please explain your choice. [10%]
b) One possible genotype that may or may not result in a profit is: 1-6-5-8-2
Calculate the fitness of the above genotype according to your fitness function above. Would this route allow the merchants to make a profit for that trip? [20%]
c) Write down, in the form of readable English, pseudocode or a flow diagram, the steps that you would use in an Evolutionary algorithm to find an optimum solution to this problem (note that you are not expected to describe the specifics of the selection, mutation or crossover operators). [20%]
d) An initial population generated for your algorithm consists of these genotypes. Why might this be a problem? (note that you should not have to carry out any
calculations to answer this question). 158263
16582 58263 16528 63528 164358 658234
e) Which type of genetic operator might be the most effective in ensuring that your population of solutions achieved good coverage of the potential solution space? Explain your answer. Give an example of what one chromosome from the initial
population above might look like after your operator has been applied.
f) The van develops a fault which means that it must return to the depot for refuelling after each 150km traversed. Explain how you would modify your algorithm from part c) to take this into account, whilst keeping the number of calculations performed as small as possible, in the interests of computational
efficiency.
END OF QUESTION PAPER