COMP6560/2022 UNIVERSITY OF KENT DIVISION OF COMPUTING, ENGINEERING AND MATHEMATICAL SCIENCES LEVEL 6 EXAMINATION Computational Intelligence in Business, Economics & Finance MAY/JUNE 2022 Paper Instructions The paper contains TWO questions. Answer ALL the questions. Notes to Candidates This is an open book examination to be completed and submitted within 24 hours. This examination is designed to take two hours but you can take longer if you wish. Please ensure that you submit your answer booklet within 24 hours of the exam release time. As you will have access to resources to complete your assessment, any content you use from external source materials should be cited. Full academic referencing is not required. You are reminded of your responsibility to act with honesty, integrity and fairness in completing assessment requirements for your course, and to demonstrate good academic practice when undertaking this assessment. This is an individual piece of work and collusion with others is strictly prohibited. Plagiarism detection software will be in use. Breaches of academic integrity will be considered to be academic misconduct. Where the University believes that academic misconduct has taken place the University will investigate the case and apply academic penalties as published in Annex 10 of the Credit Framework. - 2 - 1. (a) For each of the statements below, say whether it is true or false, and briefly justify your answer. (i) The selection method in a Genetic Algorithm can be used to control the exploration and exploitation properties of the search. [3 marks] (ii) Performing a crossover between 2 identical individuals will result in different offspring. [3 marks] (iii) The best individual fitness value of a generation can be lower than the previous generation. [3 marks] (iv) The individual selected as a winner in a tournament selection is chosen at random. [3 marks] (v) Genetic Algorithms guarantee finding the optimal solution for a given problem. [3 marks] (b) Given the following 2 individuals of a Genetic Programming population: Individual 1 Individual 2 where the data types of each function and terminal nodes are: input data type output data type AND, OR (boolean, boolean) boolean >, < (real, real) boolean +, -, ?, ? (real, real) real a, b, 5, 7, 10 - real (i) Perform a subtree crossover between Individuals 1 and 2, showing the resulting offspring (2 individuals). [8 marks] - 3 - (ii) Perform a subtree mutation on Individual 1 using the node < as the mutation point, showing the resulting offspring (1 individual). [4 marks] (iii) Create a new individual using a full initialisation method and a maximum tree depth of 3. [3 marks] - 4 - 2. (a) Consider the problem of finding the shortest path in a city map starting from a point A and terminating at a point B. Is this a travelling salesman problem (TSP)? Justify your answer, also referring to the computational complexity of the problem. [6 marks] (b) (i) Consider the following 5-city TSP problem illustrated in Figure A. The edges of the graph correspond to the distance between the cities. What is the cost of the dashed tour (i.e. the tour 1-2-3-4-5-1)? [2 marks] Figure A (ii) Is there any better solution (tour) to improve the cost calculated in (i)? Indicate the tour, the cost and justify why this is a better solution with respect to the previous tour. [4 marks] (c) (i) Consider the following 5-city TSP problem illustrated in Figure B. The edges of the graph correspond to the distance between the cities. Explain what are the main differences compared to the TSP problem presented in Figure A? [2 marks] Figure B 3 2 4 5 2 2 1 1 1 1 1 1 2 6 3 2 4 5 2 6 1 1 1 1 1 1 2 - 5 - (ii) Write a viable tour and its related cost for the TSP problem in Figure B. [4 marks] (d) (i) Consider a Genetic Algorithm implementation to solve a TSP problem. Is the binary representation a good choice for the individual representation? Justify your answer. [3 marks] (ii) Provide an example of an individual representation for the tour illustrated in Figure A (tour 1-2-3-4-5-1). Justify your choice of representation. [4 marks] (iii) Describe a suitable mutation operator and apply mutation to the individual from (ii). [5 marks]

Attachments:

1652102331-26....pdf