Wednesday, March 25, 2009

Simulated Annealing

Simulated Annealing (SA) is a smart (meta)-heuristic for Optimization. Given a cost function in a large search space, SA replaces the current solution by a random "nearby" solution. The nearby solution is chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T (a.k.a the temperature). T is gradually decreased during the process. The current solution changes almost randomly when T is large, but increasingly "downhill" as T goes to zero. The allowance for "uphill" moves saves the method from becoming stuck at local minima.

This approach has some similitude with Physic, where the heat causes the atoms to become unstuck from their initial positions 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.

Simulated Annealing is also used for many different data mining tasks such as Classification, Clustering, and Web search Ranking.

Here you have the code for Simulated Annealing in C++

8 comments:

  1. Hi,

    I changed abs to fabs in your cost function. The minimization seemed to work a bit better. Thanks for your code snippet.

    ReplyDelete
  2. Also... I made the random update step proportional to the size of the current entry:

    Essentially, changed:

    vecb[i] += step;

    to:

    vecb[i] = (1.+step)*vecb[i];

    The code now gets to a cost around 1.e-16 before the iterations finish.

    ReplyDelete
  3. wanted to know how to use this algorithm in optimisation

    ReplyDelete
  4. thanks. That's one well written piece of code.

    ReplyDelete
  5. I 've done a comparison between simulated annealing and tabu search for the nurse rostering competition problem:
    http://blog.athico.com/2010/07/simulated-annealing-new-algorithm-for.html

    ReplyDelete
  6. Thanks for the introduction to simulated annealing. I've linked through from a recent post of mine about the importance of finding the global minimum (over the local minimum) when analysing problems in Business Analysis:
    http://www.darrensmith.com.au/discovering-the-optimal-solution/

    ReplyDelete
  7. I've written a post on my blog where I show a method to improve the accuracy of SA through a transformation of the matrix cost
    http://textanddatamining.blogspot.it/2012/07/simulated-annealing-how-to-boost.html
    I hope it could be helpful to your followers.
    cheers
    cristian mesiano

    ReplyDelete