AE2AIM.AMI/G52AIM.AMI-E1 The University of Nottingham, UK & The University of Nottingham, Ningbo China SCHOOL OF COMPUTER SCIENCE A LEVEL 2 MODULE, Spring SEMESTER 2016-2017 ARTIFICIAL INTELLIGENCE METHODS Time allowed TWO Hours Candidates may complete the front cover of their answer book and sign their desk card but must NOT write anything else until the start of the examination period is announced Answer ALL questions Each question carries 25 marks Only silent, self contained calculators with a Single-Line Display are permitted in this examination. Dictionaries are not allowed with one exception. Those whose first language is not English may use a standard translation dictionary to translate between that language and English provided that neither language is the subject of this examination. Subject specific translation dictionaries are not permitted. No electronic devices capable of storing and retrieving text, including electronic dictionaries, may be used. DO NOT turn your examination paper over until instructed to do so ADDITIONAL MATERIAL: None. INFORMATION FOR INVIGILATORS: Please collect the exam papers at the end of the exam. 2 AE2AIM.AMI/G52AIM.AMI-E1 AE2AIM.AMI/G52AIM.AMI-E1 1. [25 marks] AI Methods Basics. This question consists of four parts. (A) Consider 5 jobs having the processing times pj, the 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 What is the total weighted completion time for the schedule: 5, 2, 3, 1, 4? (5 marks) (B) What is the main difference between a metaheuristic and hyper-heuristic? (5 marks) (C) Explain in detail what a fuzzy set is, by means of a fully-labelled illustrative example. Use a commonly used linguistic variable having at least three associated terms (fuzzy sets). In doing so, give a specific example of the following two concepts: (i) an element may have partial membership of a set, and (ii) an element may be a member of more than one set at the same time. (10 marks) (D) What is the main difference between search and planning? (5 marks) 2. [25 marks] Graph Colouring and Timetabling. This question consists of two parts. (A) Name a graph colouring heuristics that are related to timetabling and give a brief description. (5 marks) (B) Andrew, Jason, Rong and Ferda are university lecturers attending a workshop. The workshop consists of seven, each one hour long meetings. The table below contains the meetings that each lecturer has to attend. Where a cell in the table contains 1, this indicates that the lecturer has to attend the meeting. By using an appropriate graph colouring heuristic, schedule all seven meetings in a single afternoon between 2pm and 6pm so that the four lecturers can be present at all their meetings given that there are only two meeting rooms available at all times. (20 marks) Meetings 1 2 3 4 5 6 7 Andrew 1 0 0 1 1 0 1 Jason 1 1 1 0 0 0 0 Rong 0 0 1 0 1 1 0 Ferda 1 0 1 1 1 0 0 3 AE2AIM.AMI/G52AIM.AMI-E1 AE2AIM.AMI/G52AIM.AMI-E1 Turn Over 3. [25 marks] Single Point based Search. This question consists of three parts. 0-1 Knapsack Problem: Given N items [i1,.., iN], each item ij with a weight wj and a value vj, solving this problem involves determining a subset of items to be included in a collection/knapsack so that their total weight is less than or equal to a given limit (C) and their total value is maximised. For example, given three items S=[i1, i2, i3], w=[5,10,15], v=[100,250,300] and C=15, the optimal solution would be [1,1,0] which indicates that 1st and 2nd items are included in the knapsack with a total value of 350 (which is the objective value to be maximised), since the value of the 1st and 2nd items are 100 and 250, respectively. Additionally, the weights of those items being 5 and 10 sum up to a total weight of 15, which do not exceed the limit C. Answer the following questions. (A) Given a knapsack problem with N items and a solution representation x=[x1, x2, x3, … xN], where xk is a binary variable to indicate whether the k-th item is chosen in the solution or not, please give two neighbourhood operators that can be used in local search methods such as simulated annealing or Tabu search. (6 marks) (B) Given a knapsack problem with N items and the solution representation scheme as described in (A), how many different candidate solutions can be encoded with the representation scheme? Write your answer in terms of N. (3 marks) (C) Describe the delta-objective evaluation. Select one neighbourhood that you answered in (A), explain how the delta-objective evaluation could help speed up the search process for this problem. (4 marks) (D) Given a knapsack problem with S=[i1, i2, i3, i4, i5], w=[3,4,5,3,10], v=[4,5,8,2,14], C=20, construct a feasible solution with a heuristic that repeatedly selects an item with the highest possible ratio of vk/wk as long as the capacity is not exceeded. (4 marks) (E) Given a knapsack problem with S=[i1, i2, i3, i4, i5], w=[3,4,5,3,10], v=[4,5,8,2,14], C=20, a current solution of [1,0,0,0,1], and bit-flip move (neighbourhood move), what are the solutions returned by the first-ascent (next-ascent) and best-ascent (steepest-ascent) hill climbing methods, respectively? Assume that first-ascent returns as soon as a better solution than the input solution is found, while best ascent makes one pass over the current solution. Show the details of your computation for each iteration including the total weight, indicating whether the limit is exceeded or not and, the total value. (8 marks) 4 AE2AIM.AMI/G52AIM.AMI-E1 AE2AIM.AMI/G52AIM.AMI-E1 End 4. [25 marks] Metaheuristics and Hyper-heuristics. This question consists of two parts. Surgery Scheduling Problem (SSP). SSP involves in assigning operating rooms for M surgeries associated with a surgeon, a surgical team and possibly other resources given the time periods when the surgeries are required to take place while satisfying a set of hard and soft constraints. The objective is to use the minimum number of operating rooms while reducing the number of constraint violations. SSP is NP-hard. (A) Assume that there are two constructive heuristics, h#1 and h#2 which are capable of scheduling a given single surgery provided a partial surgery timetable which contains some of the already scheduled surgeries. Design a genetic algorithm hyper-heuristic for solving the Surgery Scheduling Problem using h#1 and h#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) Discuss why a metaheuristic may be needed as a solution method in this case rather than a deterministic local search (hill climbing) algorithm. (5 marks) (C) Which algorithm would perform better for this problem, a genetic algorithm hyper-heuristic or an iterated local search metaheuristic? (5 marks)
欢迎咨询51作业君
