ASSESSMENT TASK
This assignment consists of 4 questions.
This is an individual assignment.
Please note that this is an anonymous assessment, so you should refrain from using your name or other identifiers.
This assignment addresses all Intended Learning Outcomes (ILOs) for this unit (see below).
Question 1. Reinforcement learning (20 marks)
Dora is usually faced with the choice of going alone to the sport centre (S1) or going with her friends (S2). She likes playing golf (a1) and swimming (a2). After experiencing few times both choices with different activities, she wants now to capture a policy that maximises her enjoyment playing sport.
1- Let the discount factor be 0.5. Starting from a Q-table with zero values, please apply the Q-learning algorithm by computing the Q-table given the following sample of training examples in the format (start_state, action, reward, end_state): (14 marks)
(S1, a1, 10, S2)
(S2, a2, -10, S1)
(S1, a2, 10, S1)
(S1, a1, 10, S1)
Please show the intermediate configuration of the Q-table after the presentation of each example.
2- Identify the learned policy – please explain how you obtain it. (6 marks)
Question 2. Genetic algorithms (30 marks)
A small company has 13 employees (E1 … E13) available for assignment to 10 tasks (see table below). Any person can be assigned to any task and each task requires processing by only one person. The table below shows how well each person performs in each task. For instance, Employee 1 (E1) performs better
on Task 1 (T1) then on Task 2 (T2).
The questions to be answered are:
1- Explain how this assignment problem can be solved using genetic algorithms. In other terms, explain why it can be considered as an optimisation problem. (3 marks)
2- Provide the technical details of your solution by describing the: (12 marks)
a. Fitness function (3 marks)
b. Encoding of the chromosomes (3 marks)
c. Crossover (3 marks)
d. Mutation (3 marks)
3- Implement Java code (with comments) and run your simulation to find the employee-task assignment that produces the best score that should be indicated too. Please make sure to submit your code as well. (15 marks)
Question 3. Genetic algorithms (25 marks)
For the production of a number of laptops, a computer company needs a quantity of each component such as screens (S), hard drives (HD), optical drives (OD), RAM, video cards (VC), CPU, Ports, etc. The company received a number of priced offers. Note that offers do not contain all components. As examples:
- Offer 1: 1000 RAMs, 800 HDs, 2000 ODs - £75K
- Offer 2: 1850 S, 1570 OD - £40K
- Offer 3: 3000 HD, 2000 RAM – £70K
- Offer 4: 1500 RAM, 2000 VC, 1700 S – £55K
etc.
The company would be interested to accept cheaper offers in the first place.
Answer the following:
1. Formulate the problem as a search problem. (7 marks)
2. Give the expression of the fitness function. (6 marks)
3. Provide the encoding of the chromosomes. (6 marks)
4. Explain how crossover and mutation can be performed. (6 marks)
Question 4. Ant Colony Optimisation (25 marks)
In Internetworking, routing is the process of transmitting a packet of data from a source computer to destination computer using a router. Each intermediary computer performs routing by passing along the packet to the next computer. In routing, we usually rely on a routing table to determine the best path.
1- Explain how ACO can be applied to solve the routing problem; that is how we can find the best
path between the source computer and the destination computer (20 marks).
2- Do we need to change the structure of the ACO algorithm as presented during the lecture to solve
this routing problem? (5 marks)
contact us for this solution