Simulated Annealing

Suppose we have a optimisation problem where has some sense of neighbourhood for each point .

Then we want to emulate Hill climbing but probabilistically allow for random walking. We do this by randomly deciding to take moves from to based on the temperature of the algorithm at that time this is given by Then we just modify what is done in Hill climbing with this and gradually decrease the temperature and we have simulated annealing.

Pseudocode

simulated_annealing(optimise, neighourhood, max_itterations, update_temperature, starting_temperature):
	Input:
		optimise: The function you are looking to optimise
		neighbourhood: A function that returns the neighbourhood of a point A -> P(A).
		max_itterations: An integer that tells us when to stop.
		update_temperature: A method to update the temperature.
		starting_temperature: The starting value of the temperature.
	Output: Some a in A that hopefully is a local optimum.
1. Pick a random start point current in A.
2. Set temperature = starting_temperature
3. For iteration in 1, ..., max_itterations
	1. Pick a random point to_switch in N(current).
	2. Set current = to_switch with probability P(current, to_switch, temperature)
	3. Set temperature = update_temperature(T, iteration)
4. Return current

Run time

Correctness