Simulated annealing explained with examples

First of all, we will look at what is simulated annealing ( SA). Simulated annealing is a method for solving unconstrained and bound-constrained optimisation problems. Inspired from the annealing process in metal works, which involves heating and controlled cooling of metals to reduce the defects.

To mimic this behaviour in our application, we keep a temperature variable to simulate this heating process. Initially we set the temperature to high level and gradually decrease the temperature as our algorithm runs. Higher the temperature, more it allows to accept solutions that are worse than our current solution. This gives the algorithm the ability to jump out of any local optimums it finds itself in early execution. Once our temperature is reached to bare minimum time or zero, cooling process is complete and our algorithm should stop.

Why should i use simulated annealing ? Any advantages?

Simulated annealing solves the problem of getting stuck at local minima and maxima by allowing worse moves (lesser quality) to be taken some of the time. That is, it allows some worse values ( steps ) so that it can escape from local minima.

Advantages:

• Can deal with arbitrary systems and values.
• Statistically guarantees finding an optimal solution.
• Easy to code and understand, even for complex problems.

Simulated Annealing and Hill Climbing

Unlike hill climbing, simulated annealing chooses a random move from the neighbourhood where as hill climbing algorithm will simply accept neighbour solutions that are better than the current. When it can't find any better neighbours ( quality values ), it stops. But in simulated annealing if the move is better than its current position then it will always take it. If the move is worse ( lesser quality ) then it will be accepted based on some probability.

Acceptance Criteria

Let's understand how algorithm decides which solutions to accept. First we check if the neighbour solution is better than our current solution. If it is, we accept it ( No problem there ). If however, the neighbour solution isn't better we need to consider a couple of factors. Firstly, how much worse the neighbour solution is; and secondly, how high the current 'temperature' of our system is. At high temperatures the system is more likely accept solutions that are worse. The probability of accepting a worse state is given by the equation :

P = exp(-c/t) > r 

Where

• c = the change in the evaluation function 
• t = the current temperature 
• r = a random number between 0 and 1

Algorithm in simple language

• Set the initial temperature (high enough) and create a random initial solution and start looping temperature.
• Obtain a next neighbour or solution by making a change to our current solution.
• Decide whether to accept that neighbour solution based on the acceptance criteria.
• Decrease the temperature and continue looping until stop condition is met.

Enough talking, let's see some examples:

• Simulated annealing and knapsack problem