Stochastic Optimization Algorithm: Simulated Annealing
Problem description:
Assume that you are a salesman and you have to travel through a number of cities to meet some clients. In order to minimize the cost of travelling you are motivated to find the best routine, make it simple: you should choose the shortest distance to travel through all of those cities. As the number of cities gets large, it is a real headache to check every possible itinerary.
Another example is that you are asked to optimize (find global maximum) a problem which is calculated by a function as following:
z = f(x, y) = x * y^2 * sin(y/(0.01 + x^2)) + x^3 * y^2 * sin(y^3/(0.001 + x^4))
The function is visualized in the picture below:
These 2 examples are particular problems which can be solved by simulated annealing algorithm.
So what is simulated annealing?
The name of this algorithm reflects its origin as this algorithm is originally inspired from the process of annealing in metal work. Annealing involves heating and cooling a material to alter its physical properties due to the changes in its internal structure. As the metal cools its new structure becomes fixed, consequently causing the metal to retain its newly obtained properties.
The simulated annealing algorithm starts with a random solution. Each iteration forms a random nearby solution. If this solution is a better solution, it will replace the current solution. If it is a worse solution, it may be chosen to replace the current solution with a probability that depends on the temperature parameter. As the algorithm progresses, the temperature parameter decreases, giving worse solutions a lesser chance of replacing the current solution. Allowing worse solutions at the beginning helps to avoid converging to a local minimum rather than the global minimum.
There are many optimization algorithms including hill climbing, genetic algorithms, batch gradient descent and stochastic gradient descent (which i will discuss in later articles). An advantage of SA is that, unlike simple hill climbing algorithm which sometimes gets stuck at a local maxima, it injects an amount of randomness (that’s why it is called stochastic) in finding path to global maximum.
Hill-climbing may get to green star but never moves downhill after that because all neighboring points are worse solutions.
Basic algorithm:
SA is an effective optimization algorithm yet its implementation is quite simple. Lets have a look through this pseudo-code:
The algorithm can be described as following:
Initialize random value for s0 as well as the temperature T
Iterate temperature T until it approximates 0. In each iteration:
Update T
Neighbor values s_new within distance d from the current solution s will be carried out many times.
New solution s_new is calculated from the given function
Compare new solution with current one:
If s_new > s: move to the better solution
If s_new < s: consider moving if the acceptance probability is greater than a random number between 0 and 1.
Put it in practice:
I have implemented a program so solve the second problem. In addition, you can find an example of solution to the first problem in this link.
Note: variable x and y are replaced by u and v in my code.
This is the result after running the program. Both x and y approach 1 and temperature is reduced to nearly zero.
All of these code is uploaded in my Kaggle profile including some other functions that have similar form. So if you find it interesting, please follow this link.
References:
1. http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
2. http://optlab-server.sce.carleton.ca/POAnimations2007/SimAnnealing.aspx
3. https://en.wikipedia.org/wiki/Simulated_annealing