What is Simulated Annealing?

#algorithms #javascript #programming

What Is Simulated Annealing?

Today I’ve been playing around with simulated annealing, which is just a probabilistic technique for approximating the global optimum. Don’t let that put you off, it sounds far more complicated than it really is.

The name of the algorithm is stolen from metallurgy. Annealing is a heat treatment that alters the physical and sometimes chemical properties of a material, it involves heating a metal and then slowly cooling at a specific rate.

I have put together a really simple example to help explain the purpose and application of such an algorithm.

Hill climbing

Let’s say our protagonist is a skier. Skiers – I assume – always want to get to the highest point of the mountain so they can ski as fast as possible. Let’s write a very simple algorithm that determines how the skier climbs the mountain.

findHighestPoint() {
    if (this.heightOfHillToRight() >= this.y) {
        this.x++;
    } else {
        this.x--;
    }
}

Seems simple enough. If the position to our right is the same height or higher let’s move to the right, otherwise let’s move to the left.

We’ve cracked it haven’t we? Our skier can find the top of every mountain?

Not quite:

Our skier has hit what we call the local maxima, where it thinks it’s at the highest point. In order for the skier to find the global maxima (Highest point) it’ll first need to go down before it goes up. This is where simulated annealing comes in.

The algorithm

Choose a neighbour
Calculate the cost of the neighbour
Compare the new cost with the old cost
1. if (newCost < oldCost): move to neighbour
2. if (newCost > oldCost): potentially move to neighbour
Repeat until a solution is found or we reach the maximum iterations

Let’s put this into plain English for our simple hill climbing example.

Choose a neighbour: This will simply be a position on the hill the skier can move to.

Calculate the cost of the neighbour: This is the height of the hill at that position, so for us the higher the better - meaning the cost goes up as the hill goes down.

Compare the new cost with the old cost: So if the new position is at a higher point on the mountain then we will move to that position. If the new position is not at a higher point on the mountain we will potentially move to that position (This is the important bit).

The temperature

The temperature is very important to the algorithm, it controls the probability of us choosing to go down the hill in the hope to go up at a later point.

The temperature will start at 1.0 and will be decreased each iteration by some constant, in my example I use 0.99.

The equation that we’re going to use to determine the acceptance probability, i.e the probability of us going down the hill is:

 const prob = Math.exp((this.score-newScore)/this.temp);

For a given neighbour, the probability will get smaller as the iterations tick by (Because the temperature decreases each iteration). Meaning the likelihood of us choosing to go down decreases.

simulatedAnnealing() {
    if (this.temp < this.minTemp) return;
    for (let neighbour of this.getNeighbours()) {
      if (neighbour.score > this.score) {
        this.x = neighbour.x;
      } else {
        const prob = Math.exp((this.score-neighbour.score)/this.temp);
        if (random() >= prob) {
          this.x = neighbour.x;
        }
      }
    }
    this.temp *= this.alpha;
}

Let’s put it to the test

Awesome, in this example you can see how the temperature decreased as it tried to go back down the hill towards the end but eventually decided against it!

Let’s try a more complicated example:

Conclusion

Well, I had a lot of fun implementing that, if you want to have a trawl through the code I wrote or mess with the algorithm yourself – go here and have a play!

I took a lot of inspiration for this blog from this post by Katrina Ellison
and got the hill climbing idea from this video by Erir Schirtzinger so credit to them!

I hope you've enjoyed this blog, if you do by some miracle enjoy my blabbering then head over to my blogging site at codeheir.com where I write weekly blogs about whatever in the world of programming has my attention!