The name comes from annealing in metallurgy -- that is, heating and then controlled cooling of a material in order to reduce the defects. The heat causes the atoms to become unstuck from the initial local minima and wander randomly through states of higher energy. The slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.

The principles of simulated annealing are similar. Each point in the search space has an energy associated with it (for example, the value of the function to be minimized) and the goal is to find the point with the minimum energy.

The probability of transition from one point to another is a function of the energy difference δE between the two points and a global time-dependent parameter T called the temperature.

If δE is negative (i.e., the new point has a smaller energy) then the algorithm moves to the new point with probability 1. If not, it does so with probability e^-δE/T. This rule is deliberately similar to the Maxwell-Boltzmann distribution governing the distribution of molecular energies. This algorithm is named after Metropolis.

The temperature is gradually reduced according to the schedule function which is often taken in the form T=c^k T₀, where c is some constant that satisfies 00 is the initial temperature.

start at some Point with some Energy
while not yet in the global minimum
	make a trial move from Point to New_Point
	if New_Energy < Energy then accept New_Point with probability P=1
	if New_Energy >= Energy then accept New_point with probability P=exp(-(New_Energy-Energy)/T)
	adjust the temperature according to the schedule function

Problems

1. (non-obligatory) Implement simulated annealing in your simplex subroutine.