Simulated Annealing

Simulated Annealing (SA) is a probabilistic technique used for finding an approximate solution to an optimization problem. To find the optimal solution when the search space is large and we search through an enormous number of possible solutions the task can be incredibly difficult, often impossible. Even with today’s modern computing power, there are still often too many possible solutions to consider. Therefore, we often settle for something that’s close enough to optimal solution when we may be not able to find the optimal solution within a certain time.

Good example study case would be “the traveling salesman problem (TSP). TSP is an NP-hard problem. Finding the optimal solution in a reasonable amount of time is challenge and we are going to solve this challenge with the Simulated Annealing (SA) algorithm. SA is a good finding solutions to the TSP in particular. Before we start solving the challenge, I would like to ask a question to readers of this article. Could we solve the TSP problem with Genetic Algorithm? I leave the answer blank for you until I write another article for solving the TSP with Genetic Algorithm.

Terms (don’t get lost):

  • “SA” means the Simulated Annealing.
  • “TSP” means the The traveling salesman problem.

What is Simulated Annealing (SA)?

The SA algorithm was originally inspired from the process of annealing in metal work. Then, what is Annealing? Annealing is 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. In the SA, we keep a temperature variable to simulate this heating process and then allow it to slowly ‘cool’ as the algorithm runs. Here is good simulation from wikipedia:

Simulated Annealing – By Kingpin13 (Own work) [CC0], via Wikimedia Commons

The SA algorithm try to combine hill climbing with a random walk in some way that yields both efficiency and completeness.

  • “A hill-climbing” algorithm that never makes “downhill” moves toward states with higher cost or lower value is guaranteed to be incomplete, because it can get stuck on a local maximum.
  • “Random-restart hill climbing” conducts a series of hill-climbing searches from randomly generated initial states until a goal state is found. What it does is “if at first you don’t succeed, try, try again until you reach the goal”.

The SA algorithm picks a random move compared to hill-climbing search which picks best move. If the move improves solution, it is always accepted as a next move. Otherwise, the algorithm accepts the move with some probability less than 1. The probability decreases exponentially with the badness of the move. Therefore, the evaluation is worsened. The probability also decrease as the “temperature” goes down. Therefore, bad moves are more likely allowed in early on in its execution when T is high, and they become unlikely as T decreases.

Let’s clarify what we meant above. While the temperature (T) variable is high, the SA algorithm will accept solutions that are worse solutions than our current solution. This allow the algorithm to move around quickly (jump out of any local optimums such as shoulder (plateaux), local maximum, flat local maximum) in early on in its execution. As the temperature goes down, the chance of accepting worse solutions will be unlikely allowed. This will lead the algorithm to global optimum solution.

To sum up, the temperature (T) decreases slowly enough, the SA algorithm will find the a global optimum with probability of approaching to 1.

Simulated Annealing (SA)
Simulated Annealing pseudocode from AIMA

New terms:

  • “ΔE” means the delta variable, acceptance variable or probability.
  •  “random.random_sample()” will return random floats in the half-open interval [0.0, 1.0) in python (Math.random() in java)

Let’s talk about the delta variable (ΔE) in the pseudocode. After randomly selected successor of current state, we check if the neighbor solution is better than our current solution by calculation the delta variable (ΔE next.VALUE – current.VALUE). If the move improves solution (when ΔE > 0), we then move to that neighbor solution. Otherwise, neighbor solution is not improving (when ΔE <= 0), consider a couple factors mentioned above:

  1. How bad move the neighbor solution is.
  2. How high the current temperature (T) variable of our system is.

Remember that the system accepts the move regardless how bad it is with some probability less than 1. At high temperatures, the system is more likely accept solutions that are worse (when random.random_sample() < eΔE/T”).

Temperature variable allow the SA algorithm the ability to widely explore the whole search state before cooling and settling in a more focused area. So choosing right temperature schedule is a key at the start. T

The most common temperature schedule is simple exponential decay. However, there are different schedule functions like linear, quadratic, etc… In most cases, the valid range for temperature T0 can be very high (e.g., 1e8 or higher), and the decay parameter alpha should be close to, but less than 1.0 (e.g., 0.95 or 0.99). Think about the ways that changing the form of the temperature schedule changes the behavior and results of the simulated annealing function.

alpha = 0.95
temperature=1e4

#Simple exponential decay
def schedule(time):
return alpha**time * temperature

Now we are ready to solve TSP problem with the Simulated Annealing (SA). I encourage you to give a try to solve this problem before looking at my solution or searching a solution on online. However, the solution is available in the references below. It will take you to my GitHub.

References:

  1. Solving TSP with the Simulated Annealing (SA)
  2. Simulated Annealing pseudocode from AIMA
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s