(Probabilistic Methods)

(a) Probabilistic methods permit the choice of weaker solutions than the current solution on each iteration. Identify the issue with first and second order methods this was designed to avoid. Explain the advantage of such an approach. (8 marks)

(b) You wish to use the Simulated Annealing approach on the Knapsack Problem. Your objective function is to minimise the weight of the knapsack while maximising the combined value of the items it contains. You may assume the knapsack is represented as a list. You have a list of items (called items), each item has an associated weight and value. The knapsack can hold a total of 10 Kg of items. Any sack heavier than 10 Kg is not a valid solution. You are required to write two functions: energy() which returns the total weight with the total value subtracted from it, and move which modifies the contents of the sack. Moves are expected to be conservative in nature. Provide python code for both methods. (12 marks)