2 AE2AIM.AMI -E1 AE2AIM.AMI -E1 Turn Over The University of Nottingham Ningbo China SCHOOL OF COMPUTER SCIENCE A LEVEL 2 MODULE, Spring SEMESTER 2017-2018 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 -E1 AE2AIM.AMI -E1 Next Page 1. [25 marks] AI Methods Basics. (A) What are the main differences between strong AI and weak AI. (4 marks) (B) List three major categories of artificial intelligence research and two popular topics in each category. (6 marks) (C) Describe what a linear program model is and give its general form? (5 marks) (D) 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) 3 AE2AIM/AMI-E1 AE2AIM/AMI-E1 Turn Over 2. [25 marks] Local search. (A) List 5 stages of a local search implementation. (5 marks) (B) Bin packing is a classic combinatorial optimization problem that has practical applications in many fields. The one-dimensional bin packing problem aims to pack a set of n items with minimum number of homogeneous bins. Answer the following questions regarding the implementation details of a simple local search algorithm for bin packing. (i). Describe and compare the first fit and the best fit heuristics for bin packing. Which is better? (6 marks) (ii). Give two possible neighbourhood operators for this problem. (4 marks) (iii). Using this problem as an example to explain the drawbacks of simple local search methods. Explain how these drawbacks can be addressed, at least partially? (6 marks) (iv). Explain what partial objective evaluation is and why it is useful in local search. (4 marks) 4 AE2AIM.AMI -E1 AE2AIM.AMI -E1 Next Page 3. [25 marks] Metaheuristics. 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 metaheuristic approaches like simulated annealing and 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) Given a knapsack problem with S=[i1, i2, i3, i4, i5], w=[3,4,2,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) (D) Assume a different solution encoding/representation is now adopted for a genetic algorithm. The new representation x’=[y1, y2, y3, …] stores the indexes of the set of items being selected in the knapsack and a set Z is used to record the remaining unpacked item set. For example, assume the problem has 7 items (i.e. N=7), a solution with x’=[2, 4, 3] and Z = {1, 7, 5, 6} means items 2, 3, 4 are selected in the knapsack while the remaining items 1, 5, 6, 7 are not in the knapsack. Please give one crossover operator and one mutation operator with illustrative examples. Compared with the solution representation in (A), what 5 AE2AIM/AMI-E1 AE2AIM/AMI-E1 Turn Over are the pros and cons of this solution representation if it is used to encode solutions in a genetic algorithm? (12 marks) 6 AE2AIM.AMI -E1 AE2AIM.AMI -E1 End 4. [25 marks] Metaheuristics and Hyper-heuristics. Wind-farm layout optimisation problem (WLOP). A variant of WLOP involves determining the best locations for M wind turbines in a given region subject to various topographical constraints. The objective is to minimise the overall cost of energy production. WLOP is proven to be NP-hard. (A) Assume that there are three constructive turbine placement heuristics, c#0, c#1 and c#2. Each heuristic uses a different strategy to determine the best location for a given turbine on the remaining available region excluding the used land by the already placed turbines and respecting the topographical constraints. Design a genetic algorithm hyper-heuristic for solving the wind-farm layout optimisation problem 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) Assume that you have tested the performances of c#0, c#1 and c#2 heuristics separately by running each heuristic on ten WLOP instances. The results show that c#1 performs the best on all instances, while c#0 performs the worst. The performance of c#2 is slightly worse than c#1 but this performance variation is not significant. Having this knowledge, which component(s) would you change in your genetic algorithm hyper-heuristic design for WLOP, if any? (5 marks) (C) Which algorithm would perform better for this problem, a genetic algorithm hyper-heuristic or a tabu search metaheuristic? (5 marks)
欢迎咨询51作业君
