Data Science

Simulated Annealing

Global and Local Maximum

Simulated Annealing came from the concept of annealing in physics. This technique is used to increase the size of crystals and to reduce the defects in crystals. This was done by heating and then suddenly cooling of crystals.

Fig: Random soft hand graph

Simulated Annealing is an optimization technique which helps us to find the global optimum value (global maximum or global minimum) from the graph of given function. This technique is used to choose most probable global optimum value when there is multiple number of local optimum values in a graph.

Basically Simulation annealing is the combination of high climbing and pure random walk technique, first one helps us to find the global maximum value and second one helps to increase the efficiency to find the global optimum value.

For e.g if we are moving upwards using hill climbing algorithm our solution can stuck at some point because hill climbing do not allow down hill so in this situation, we have to use one more algorithm which is pure random walk, this algorithm helps to find the efficient solution that must be global optimum.Whole algorithm is known as Simulated Annealing.

Likewise, in above graph we can see how this algorithm works to find most probable global maximum value. In above figure, there is lot of local maximum values i.e. A,B,D but our algorithm helps us to find the global optimum value, in this case global maximum value.

Let’s see algorithm for this technique after that we’ll see how this apply in given figure.

Algorithm

• First generate a random solution
• Calculate it’s cost using some cost function
• Generate a random neighbor solution and calculate it’s cost
• Compare the cost of old and new random solution
• If C old > C new then go for old solution otherwise go for new solution
• Repeat steps 3 to 5 until you reach an acceptable optimized solution of given problem

Let’s try to understand how this algorithm helps us to find the global maximum value i.e. A in this given figure.

First let’s suppose we generate a random solution and we get B point then we again generate a random neighbor solution and we get F point then we compare the cost for both random solution, and in this case cost of former is high so our temporary solution will be F point then we again repeat above 3 steps and finally we got point A be the global maximum value for the given function.

Example Code:

from random import random
def anneal(sol):
    old_cost = cost(sol)
    T = 1.0
    T_min = 0.00001
    alpha = 0.9
    while T > T_min:
        i = 1
        while i <= 100:
            new_sol = neighbor(sol)
            new_cost = cost(new_sol)
            ap = acceptance_probability(old_cost, new_cost, T)
            if ap > random():
                sol = new_sol
                old_cost = new_cos
            i += 1
        T = T*alpha
    return sol, cost

In above skeleton code, you may have to fill some gaps like cost() which is used to find the cost of solution generated, neighbor() which returns random neighbor solution and acceptance_probability() which helps us to compare the new cost with old cost , if value returned by this function is more than randomly generated value between 0 and 1 then we will upgrade our cost from old to new otherwise not.

Calculation of acceptance probability

Equation for acceptance probability is given as:

a=e(c_new-c_old)/T

Here c_new is new cost , c_old is old cost and T is temperature , temperature T is increasing by alpha(=0.9) times in each iteration.

Some points related to acceptance probability:

• is >1 is new solution is better than old one.
• gets smaller value as temperature decreases(if new solution is worse than old one.
• gets smaller as new solution gets more worse than old one.

Applications:

Deployment of mobile wireless base (transceiver) stations (MBTS, vehicles) is expensive, with the wireless provider often offering a basic coverage of BTS in a normal communication data flow. However, during a special festival celebration or a popular outdoor concert in a big city, the quality of the wireless connection would be insufficient. In this situation, wireless provider increase the number of MBTS to improve data communication among public.

Simulated Annealing is used to find the optimal value of MBTS which should be suitable for proper data communication.

We have come to the end of this blog. In this blog, the main agenda was to understand the Simulating Annealing technique which is most powerful technique in finding global optimum value of any graph . In the next set of articles, I will continue to explain you about more powerful algorithms like this one . Thanks for reading this article.

Thank You

AI Technology & Systems