Genetic Algorithm

UNIVERSITY OF KENT
DIVISION OF COMPUTING, ENGINEERING
AND MATHEMATICAL SCIENCES
LEVEL 6 EXAMINATION
Computational Intelligence in Business, Economics & Finance

Paper Instructions
The paper contains TWO questions. Answer ALL the questions.
Notes to Candidates

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]