Comparison of Search Algorithms, A* algorithm Heuristics and Integrating Local Search and Genetic Al

Comparison of results between different search algorithms

(a) Student 1 applied different search algorithms on a problem instance and got the following results:

(b) Student 2 attempted the same problem with his own implementation and got some different results:

Compare each corresponding result with Student 2’s result is reasonable. Explain

Student 1 and discuss if any source of discrepancy.

(c) The A* algorithm uses the evaluation function f(n)=g(n)+h(n) to order candidate nodes in the fringe.

Discuss ideas on resolving conflict when 2 nodes are having the same f(n) value. Explain whether your suggestion(s) will give the A* algorithm a better performance in reducing the number of nodes explored.

(d) A student represents the state in the “Missionaries and Cannibals” problem by a simple String like: “3300S”, meaning: “There are 3 missionaries and 3 cannibals in the south, 0 missionaries and 0 cannibals in the north, and the raft is on the south.” The goal state is: “0033N”.

(i) The following heuristic functions are proposed for the “Missionaries and Cannibals” problem:

Heuristic 1:

If current state equals to goal state, return 0 else return 1

Heuristic 2:

Return the no. of mismatched characters between the 2 strings.

For each of the proposed heuristics, discuss its suitability for the A* algorithm, and its expected performance

(ii) Suggest a heuristic function for the Missionaries and Cannibals problem, which can be used in an A* search. You can change the state representation if needed. Justify its suitability.
(i) Discuss if alpha-beta pruning can occur at node C.
(ii) Discuss if alpha-beta pruning can occur at node D.
(iii) “Command and Conquer” is a classic war game where 2 opposing players control their respective armies in a 2D world in real-time without the need to wait for their turns. Discuss ideas on how you would implement a computer player for this game. Your answer can include discussion on why some ideas fail to apply to this domain.

(b) In local search, the objective function guides the exploration of the state space by telling whether 1 state is preferred (i.e. better) than another state.

(i) For each of the following domains, discuss ideas of an objective function. Your answer should include multiple factors that you will take into consideration.

• Packing boxes into a cargo plane

• Scheduling classes in a university

• Assigning deliveries to a fleet of couriers

(ii) Discuss the statement: “Local search is a genetic algorithm where the population size is 1.” Your answer should highlight the similarities and differences between the two approaches.

3 Case-Based Reasoning (CBR), is a paradigm of AI and cognitive science that models the reasoning process as primarily memory based.

Suppose you are building a digital health monitoring system to analyse a patient’s activities (walking, running etc.) together with their daily mood tracker to help manage their health and well-being and to provide digital interventions. For instance, consider the following:

Sue, a 45-year-old woman with a 9-5 desk job is coping with a recent knee replacement surgery. Her GP has asked her to fill-in a questionnaire which helps to find out about the type of knee pain she is experiencing, the types of activities she finds difficult to carry out due to the pain, the amount of sleep she manages a day and the level of physical activity that she manages on a daily basis. Based on her responses the GP consults a CBR system and uses its recommendation to tailor a self-management plan, which require that she: performs 5 leg muscle strengthening exercises 3 times a week and maintain a minimum of 3000 steps worth of normal walking each day.
Sue follows the proposed self-management plan (i.e. exercises and physical activity). After a month of adherence, she is pleased to see her pain has reduced.

Assume that activities are tracked by a smart phone/watch, exercises are recognised by a camera, and that the self-management plan is generated by a CBR system.

(a) Describe features that would be relevant to represent the problem description (e.g. patient context), and the solution description (e.g. the self-management plan of recommended amounts of physical activity and exercise sessions) and any other features that would be useful maintain as part of a case.

(b) Identify 5 features from the case structure in part (a) and explain the type of similarity knowledge you might use to compute local similarity scores when comparing cases for these features. Note: you should try to select 5 features that would help you to discuss knowledge in the form of numeric weights and similarity matrices.

(c) Provide an example of a case and a query and describe how global similarity can be calculated for the case pair.

(d) Having a good spread of cases in the casebase is important so as to cover as many of the real-world situations. Propose strategies for acquiring this knowledge initially and for adding new knowledge as new patients are encountered.

(e) A right to obtain an explanation of the decision reached by an Intelligent System, is now an EU regulation. Discuss how

recommendations made by the CBR system above might be explained to a GP who may be interested to understand “Why” the system has proposed a specific self-management plan. You may want to use illustrations to convey your ideas here.

(a) How would you combine a Local Search Algorithm and a Genetic Algorithm (GA) to solve an arbitrary combinatorial optimization problem with an expensive fitness evaluation function? Your answer should describe:

(i) The main steps of the resulting combined search strategy

(ii) The pros and cons of the combined search strategy when comparing to a standard GA-based approach for solving the same problem.

(b) A GA is currently operating on the following population of character array solutions:

Solutions and Fitnesses in a GA Population

(i) What is the probability that solution S is selected under Roulette Wheel selection?

(ii) Assuming solutions R and T have been selected as parents, show, with an example, how children would be produced under one-point crossover.

(iii) Without attempting to calculate precise probabilities, comment how the GA operators will favour / disfavour combinations of the highlighted genes HTO, DVD and XYZ being present in children of this population.

(c) What considerations should be made when in deciding whether to apply a GA in practice? Illustrate your answer with an example of a real world problem where a GA was successfully used.

(d) You are advising a large garden supplies company on how they can use AI to help purchase and arrange stock to maximise profitability. The company has tens of thousands of items they could stock, divided into several departments. Each item has a profit and a shelf-space per unit. The company has several stores around the country and has a large database of which items sold in different regions at different