1 COMP2001/COMP2011-UNUK-E1 COMP2001/COMP2011-UNUK-E1 The University of Nottingham SCHOOL OF COMPUTER SCIENCE A LEVEL 2 MODULE, SPRING SEMESTER 2020-2021 ARTIFICIAL INTELLIGENCE METHODS Maximum Time Allowed to Submit Answers in Moodle: 24 Hours Open-book examination. Answer ALL 4 QUESTIONS Suggested time to complete the paper ~2 hours. This open-book examination will be marked out of 100. You may write/draw by hand your answers on paper and then scan them to a PDF file, or you may type/draw your answers into electronic form directly and generate a PDF file. Guidance on scanning can be found through the Faculty of Science Moodle Page Guidance for Remote Learning. Your solutions should include complete explanations and should be based on the material covered in the module. Make sure your PDF file is easily readable and does not require magnification. Make sure that each page is in the correct orientation. Text/drawing which is not in focus or is not legible for any other reason will be ignored. Submit your answers containing all the work you wish to have marked as a single PDF file. Use the standard naming convention for your document: [Student ID] [Module Code] [Academic Year]. Write your student ID number at the top of each page of your answers. Although you may use any notes or resources you wish to help you complete this open-book examination, the academic misconduct policies that apply to your coursework also apply here. You must be careful to avoid plagiarism, collusion or false authorship. Please familiarise yourself with the Guidance on Academic Integrity in Alternative Assessments, which is available on the Faculty of Science Moodle Page Guidance for Remote Learning. The penalties for academic misconduct are severe. Staff are not permitted to answer assessment or teaching queries during the period in which your examination is live. If you spot what you think may be an error on the exam paper, note this in your submission but answer the question as written. 2 COMP2001/COMP2011-UNUK-E1 COMP2001/COMP2011-UNUK-E1 Question 1. AI Methods – Basics. This question consists of three parts. [25 marks] (A) Consider 5 jobs having the processing times pj, due-dates dj and the weights wj of the jobs j=1, ..., 5, given in the table: Jobs 1 2 3 4 5 pj 10 6 5 4 2 dj 12 9 14 8 3 wj 5 10 5 1 3 Calculate the following for the schedule: <5, 2, 3, 1, 4> showing your steps: (i) the total weighted completion time [4] (ii) the maximum lateness [3] (iii) the number of tardy jobs [3] [10 Marks] (B) Based on the following box-plots of the fitness (objective) values obtained after running 8 search algorithms on a given instance for a minimisation problem for 30 trials, indicate whether each of the five given statements below is TRUE or FALSE and provide your reasoning without exceeding 100 words. [15 Marks] Statements: (i) A3 is a hill climbing algorithm (ii) The best performing algorithm is A7 on average for the instance (iii) The best solution in a single trial is achieved by the algorithm A6 for the instance (iv) The algorithm A3 performs better than A4 and this performance difference is statistically significant for the instance (v) The algorithm A6 performs slightly better than A4 on average for the instance A1 A2 A3 A4 A5 A6 A7 A8 3 COMP2001/COMP2011-UNUK-E1 COMP2001/COMP2011-UNUK-E1 <












































































>

Question 2. Heuristics/Operators. This question consists of three parts. [25 marks]

(A) Consider a traveling salesman problem (TSP) instance consisting of 5 cities C1, C2, C3, C4
and C5 and answer the following two questions. Refer to the table below for the inter-city
distances, which adopts generic units.

C1 C2 C3 C4 C5
C1 0 9 2 4 10
C2 9 0 5 6 7
C3 2 5 0 12 3
C4 4 6 12 0 9
C5 10 7 3 9 0



(i) Firstly, illustrate how the nearest neighbor heuristic works using path representation
step by step, providing the final tour and its length that will be returned by the algorithm
considering that is selected randomly as the starting city to construct a tour.
(ii) Secondly, provide 2 optimal/perfect solutions in path representation for this problem
instance.
[10 marks]

(B) Order Crossover can be applied not only permutation encoding, but also other encodings
as well, for example integer encoding. Provide the newly generated solution(s) after
applying Order Crossover to the following solutions selected as parents: 5-3-1-2-4-1-5 and
3-4-9-2-1-5-3. In this representation, repetition is allowed and you should remove the first
occurrence of an entry in the genetic material that will be inherited to an offspring, if that
entry already exists in the offspring. You can ignore any remaining entries in the genetic
material from the parent, once the offspring is complete, even if there are some left from
the parent to be inserted into the offspring. Given that the first and fourth locations (e.g.,
x|x-x-x|x-x-x) are chosen as the crossover points. Show all your steps and provide any
assumptions you make.
[5 marks]

(C) In the context of Simulated Annealing, assuming that the Geometric cooling schedule is
used and the initial temperature (T0) is fixed as 1, briefly explain how each one of the
following settings for the cooling rate (α) influences the probability of acceptance of
worsening solutions in time based on the temperature T (i.e., e-/T ). Each explanation
should not exceed 100 words.

α = 0.000001
α = 0.975
α = 1
α = 3
[10 marks]



4 COMP2001/COMP2011-UNUK-E1
COMP2001/COMP2011-UNUK-E1

Question 3. Single Point based Search. This question consists of three parts. [25 marks]
Optimal Split Problem (OSP): For a given undirected graph G = (V, E) with N vertices and
M edges, where V={v1, v2,…, vN} and E={e1, e2,…, eM}, a split in G is a subset S ⊆ V. Let S’
indicate the remaining vertices in V, that is, V\S, so S∩S’={} and S∪S’=V. Hence, a “split”
refers to the partition (S, S’) of the vertices in V. The optimal split problem is to find a split S;
such that the number of edges between the vertices in S and S’ is maximised. An example
optimal solution to the OSP instance of G1 with 6 vertices (V={v1, v2, v3, v4, v5, v6}) and 8
edges (i.e., N=6, M=8) is provided below. The vertices in black and white colours indicate the
partitions S={v1, v2, v4, v5} and S’={v3, v6}, respectively and the maximum number of edges
between S and S’ is 6.

G1:


Answer the following questions.

(A) Assume that you decided to design a great deluge algorithm for solving the optimal split
problem as described above, hence binary encoding will be used to represent a candidate
solution r=[b1, b2, b3,…, bk,… bN], where bk is a binary variable indicating which set the k-
th vertex in V is partitioned into, that is, if bk =1, then the k-th number is partitioned into
S, otherwise (which means bk =0) the k-th vertex is partitioned into S’. The objective
function f(r) counts the number of edges between the vertices in S and S’. For example,
the optimal solution to the instance G1 as illustrated above can be represented as
[1,1,0,1,1,0] and the objective value would be 6.
(i) How many different candidate solutions can be encoded with this representation
scheme? Provide your answer in terms of N and/or M.
(ii) Is there any redundancy in this representation (that is for any given solution, is it
possible to create an equivalent solution)? If yes, explain without exceeding 100
words.
[6 marks]

(B) Provide a general case for the solution r to an optimal split problem instance based on the
formulation as in (A), for which the objective function, f(r) evaluates to the minimum
possible objective value.
[5 marks]

(C) Given the optimal split problem instance G2 as illustrated on the
right-hand side with V={v1, v2, v3, v4, v5} and 8 edges (i.e., N=5,
M=8) and a current solution of [1,1,1,0,0] with the objective
value of 4 using the formulation as explained in part (A), what
would be the resultant solutions returned by the first-descent
(next-descent) and best-descent (steepest-descent) hill
climbing methods, respectively? Assume that the bit-flip
neighbourhood move is used, first-descent starts scanning a
solution from the first bit returning as soon as a strictly better
solution than the input solution is found, while best-descent
makes a single complete pass over the current solution. Show
the details of your computation for each step including the current solution, best solution
and their objective values computed as described.
[14 marks]
v1
v2
v3 v4
v5
G2
v1
v2 v3 v4
v5
v6
5 COMP2001/COMP2011-UNUK-E1
COMP2001/COMP2011-UNUK-E1 <>

Question 4. Population-based Search, Metaheuristics and Hyper-heuristics. This question
consists of two parts. [25 marks]
Storage Packing Problem (SPP). This is the problem of orthogonally packing a given set of M
rectangular-shaped boxes, each with different dimensions into the minimum number of
rectangular storage units (containers) of predefined dimension as illustrated below. SPP is proven
to be an NP-hard optimisation problem.







(A) Assume that there are three constructive packing heuristics, c#0, c#1 and c#2. Each heuristic
uses a different strategy to choose from the remaining boxes and then to pack the chosen
box into an available storage unit (if necessary opening a new storage unit). The details of
those three heuristics are irrelevant.

Design a genetic algorithm hyper-heuristic for solving the Storage Packing Problem (SPP)
using c#0, c#1 and c#2 as the low level heuristics in your hyper-heuristic algorithm design.
Explain all your algorithmic choices, in particular chromosome length, (candidate solution)
representation showing how a complete solution can be obtained with respect to the
chromosome length, initialisation, genetic operators, replacement, termination and any other
relevant parameter settings.
[15 marks]

(B) Which algorithm would perform better for this problem, a genetic algorithm hyper-heuristic
or a simulated annealing metaheuristic? Provide your reasoning without exceeding 100
words.
[10 marks]









Boxes of different
dimensions
Storage unit
(container) of fixed
dimension
Minimise the number
of storage units
(containers) to pack
all boxes
storage
unit#1
storage
unit#2

<>

学霸联盟