turn over
1. Genetic algorithms
Imagine you want to travel somewhere and you need to pack your suitcase. You have a list of 20 items that you would like to bring with you, but you are only allowed to fill your suitcase with at most 15kg. Each item i has a weight wi and a “utility” value ui, which measures the usefulness of the item. The utility of the bag is the sum of the utilities of the individual items. The proposed items, their weights and utility are given in this table:
-2-
Item number
weight
utility
1
7
9
2
4
5
3
1
5
4
8
1
5
9
4
6
6
4
7
1
5
8
7
3
9
9
7
10
4
9
11
9
4
12
7
4
13
6
2
14
5
6
15
6
1
16
2
2
17
3
8
18
5
2
19
1
5
20
1
2
Knowing that this is a difficult optimisation problem to solve, you decide to use genetic algorithms to find a good combination of items to take with you.
(a) You choose to encode a candidate solution as a binary string and choose a population size of 3. Write down a possible initial population.
(b) Write down a reasonable fitness function for this problem. If possible use a mathematical notation for the fitness function.
(c) Subject the first candidate solution from the initial population to a point mutation and write down the result.
[6 marks] [4 marks] [2 marks]
2. (a)
Contrast the properties of best-first search and uniform-cost search. Present your answer in a table of two columns.
[4 marks]
[2 marks]
[6 marks]
(d) Assume you have a candidate solution consisting of items 5, 11 and 12. What is the fitness of this solution?
(e) We now turn our attention to a different genetic algorithm that solves an unrelated problem (and we do not need to worry about what this unrelated problem is). Assume that you are given a population of the following strings of integers that encode candidate solutions for this new genetic algorithm:
1,12,15,0,8,0 1,4,0,2,1,1
What are the possible candidate solutions you can obtain by subjecting these candidate solutions to single point crossover with the crossover point being at position 3?
(f) One of the purposes of mutations is to introduce genetic diversity to the genetic algorithm. But what about crossover? Does it increase or decrease diversity, or leave it unaffected? Justify your answer in at most 2 sentences.
[2 marks]
(b) Consider the following maze where the problem is to plan a journey from the entry square, 0, to the exit square, 49, both of which are highlighted in grey. All intermediate squares are white, and are numbered 1 to 48, giving 50 squares in total. One can move from one square to another by moving up or down or left or right.
-3-
turn over
3. (a)
You need to graphically represent how a layered tree is constructed to describe all moves in any game. Then show how the nodes of the tree can be annotated with 0 or 1, explaining the meaning of this annotation.
Draw a schematic diagram of a perceptron with two inputs, x and y, labelling each of the components.
[6 marks]
[6 marks]
(i) Suppose the objective is to find a journey which takes the minimum number of right-angle turns. What squares should be used to make up the states of the search space so that iterative deepening can solve this problem? Hint: the search space should not contain unnecessary states.
(ii) Suppose now that the objective is to find a journey which travels through the minimum number of squares. Which squares should be used to make up the states of the search space so that iterative deepening can solve this problem? Explain your answer.
(c) Consider a two-player game in which 7 stones are placed on a table and the two players alternate in making a move. At each move, a player must divide a pile of stones into two non-empty piles of different sizes. The first person who cannot make a move loses the game.
[5 marks]
[3 marks]
(b) Suppose that you have to train a perceptron on the following training data comprising of three points labelled as follows:
-4-
point
label
p1 = (1,1)
t1 = 1
p2 = (-1,1)
t2 = 0
p3 = (0,-1)
t3 = 0
Suppose that initial weights are assigned to w0 = (-3, 0) and that the initial bias is set to b0 = 0. Compute w1 and b1 and then w2 and b2 using Rosenblatt’s learning rule using a learning rate of 0.1. Give the working in your calculation.
(c) Consider the following graph of birds from the crow and swallow families. The x-axis of the graph is the percentage of plumage that is blue and the y-axis is the length of the bird in centimetres. Birds from the crow family face left whereas birds from the swallow family face right.
[6 marks]
Explain why a perceptron could never decide whether a bird is from the crow family or the swallow family if its two inputs are percentage of blue plumage and bird length?
(d) Give a two-dimensional solid shape which can be modelled with a two-layer neural network but not a one-layer network.
[4 marks] [4 marks]
-5-
turn over