Simulated Annealing

Simulated Annealing is one of the most elegant and powerful metaheuristic algorithms. The name sounds complex, but the core idea is wonderfully intuitive and based on a real-world process.

Image source: https://www.cs.us.es/~fsancho/Blog/posts/Simulated_Annealing_in_NetLogo.md

Let’s start by understanding the problem it solves.

1.0 The Problem: Getting Stuck in a “Local Optimum”

Imagine you are a hiker dropped by a helicopter into a vast, foggy mountain range at night. Your goal is to find the absolute lowest point in the entire range (the global optimum).

Your only tool is an altimeter, and you can only see the ground right at your feet.

A Simple (but flawed) Strategy: Hill Climbing The most obvious strategy is “Hill Climbing” (or in this case, “Valley Descending”):

1. Look at the ground immediately around you.
2. Take a step in the direction that goes downhill the most.
3. Repeat.

You’ll keep walking downhill until you reach the bottom of a valley. You can’t take any more downhill steps. You might think you’ve succeeded, but because of the fog, you have no idea if you are in a small, shallow valley (a local optimum) or the deepest canyon in the entire range (the global optimum).

The Hill Climbing algorithm always gets stuck in the first valley it finds. We need a smarter strategy that allows us to get out of these small valleys to search for better ones.

2.0 The Core Idea: Sometimes, You Have to Go Uphill

This is the magic of Simulated Annealing. To escape a local optimum, you must be willing to temporarily accept a worse move (i.e., take a step uphill) in the hope that it will lead you to a much better path later on.

Simulated Annealing provides a clever way to control this “uphill-walking” behavior.

3.0 The Analogy: Annealing Metal

The algorithm is named after the real-world process of annealing used by blacksmiths.

1. Heating: To make a piece of metal stronger and less brittle, a blacksmith heats it up to a very high temperature. At high heat, the atoms inside the metal gain a lot of energy and jump around almost randomly. They are free to explore many different configurations.
2. Slow Cooling: The blacksmith then cools the metal down very slowly. As it cools, the atoms lose energy and start to settle. Because the cooling is slow, they have time to arrange themselves into a highly ordered, strong crystal structure — a state of minimum energy (the global optimum).
3. Quenching (Cooling too fast): If the blacksmith cooled the metal too quickly (e.g., by dunking it in water), the atoms would get “frozen” in whatever messy, high-energy configuration they were in. This creates a brittle, flawed structure (a local optimum).

Simulated Annealing uses this process as a metaphor for searching for a solution.

• Temperature (T) = An algorithm parameter that controls how “adventurous” we are.
• High Temperature = We are willing to accept lots of “bad” (uphill) moves and explore the solution space widely.
• Low Temperature = We become more conservative and are much less likely to accept bad moves, preferring to only go downhill.
• Cooling Schedule = The process of gradually reducing the temperature.

4.0 The Simulated Annealing Algorithm in Simple Steps

Let’s apply this to our hiker.

1. Start: Drop the hiker somewhere random. Pick a very high “temperature” (T).
2. Propose a Move: The hiker considers a random step to a nearby location.
3. The Decision (The Crucial Step):

• Is the new spot DOWNHILL (a better solution)?
• ALWAYS accept the move. The hiker takes the step.
• Is the new spot UPHILL (a worse solution)?
• MAYBE accept the move. This is where temperature matters. The decision is based on a probability.
• If T is high: The probability of accepting the uphill move is high. The hiker is feeling energetic and adventurous, willing to climb out of a valley.
• If T is low: The probability of accepting the uphill move is very low. The hiker is tired and prefers to stick to downhill paths.
• The probability also depends on how far uphill the step is. A small step up is more likely to be accepted than a giant leap up a cliff.

4. Cool Down: After a few steps, slightly lower the temperature T.

1. Repeat: Go back to Step 2. Continue proposing moves, making decisions, and slowly lowering the temperature until T is near zero.

By the time the “temperature” is very low, the hiker will have explored many different valleys and will have settled into the deepest one they found.

5.0 Formalizing the “Maybe” — The Acceptance Probability

The probability of accepting a “bad” move is typically calculated with this formula:

P(accept) = exp(-ΔE / T)

Let’s break it down:

• ΔE (Delta Energy): How much worse the new solution is. For our hiker, this is the change in altitude. ΔE = (altitude_of_new_spot — altitude_of_current_spot).
• T: The current temperature.
• exp: The exponential function.

How this formula works:

• If T is very large, ΔE / T is close to 0, and exp(0) is 1. The probability of accepting is almost 100%.
• If T is very small, ΔE / T is a large negative number, and exp(-large_number) is close to 0. The probability of accepting is almost zero.
• If the move is very bad (a large ΔE), ΔE / T is a large negative number, making the probability low.

Summary

Happy learning !!!