Sample Iteration

To help illustrate the algorithm, let's run through a couple of iterations to see how it works. Note that when the working solution has a lower energy (representing a better solution) than the current solution, it's always used. Only when the working solution is worse than the current solution does the acceptance probability equation come into play.

Let's say in our current environment that the temperature is 50 C and the current solution has an energy of 10. We copy the current solution to the working solution and tweak it. After assessing the energy, the new working solution has an energy of 20. In this case, the energy for the working solution is worse (higher) than the original solution and therefore we use the acceptance criteria.

current solution energy	10
working solution energy	20

The delta energy for this sample is (working solution energy - current solution energy), or 10. Plugging this delta, and our temperature of 50, into Equation 2.1, we get a probability:

Therefore, for this sample we see that it's very likely that the worse solution will be propagated forward.

Let's now look at an example near the end of the temperature schedule. Our temperature is now 2 and the energies for the current and working solutions are:

current solution energy	3
working solution energy	7

The delta energy for this sample is four. Using this delta and the temperature, we again use Equation 2.1 to find the probability of acceptance:

Given the low probability result of this sample, it's very unlikely that the working solution will be propagated on to the subsequent iterations.

That's the basic flow of the algorithm. Let's now apply simulated annealing to a problem and see how well it actually works.