# 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]

## Leave a Reply

Want to join the discussion?Feel free to contribute!