(Probabilistic Methods)

(a) Probabilistic methods are considered to be non deterministic in nature, when compared to first and second order methods. Explain why this is the case (8 marks)

(b) Predict the effect the temperature will have on the acceptance of weaker solutions in Simulated Annealing when the temperature is high and when the temperature is low. (4 marks)

(c) You wish to use the Simulated Annealing approach on the Traveling Salesman Problem. Your objective function is to minimise the total distance traveled on an itinerary represented as a list of cities. You are required to write two functions: energy() which returns the total distance of an itinerary, and move() which randomly modifies the itinerary. Moves are expected to be conservative in nature. Provide python code for both methods. You may assume you have a matrix called distance that provides the distance in kilometers between every pair of cities. (8 marks)