Optimization with Simulated Annealing

Simulated Annealing (SA) is a powerful algorithm inspired by a real-world process called annealing in metallurgy. In annealing, metals are heated to high temperatures and then slowly cooled to change their physical properties, such as strength and durability. The Simulated Annealing algorithm mimics this process to find the optimal solution for complex problems, rather than altering metal properties.

How Simulated Annealing Works

The algorithm begins by operating at a high temperature, similar to heating metal. This high temperature allows the algorithm to explore a wide range of solutions, even those that are not as good as the current one. This is crucial because it prevents the algorithm from getting trapped in local optimal points where a solution may seem good, but could be better overall (global optimum).

As the algorithm progresses, the temperature gradually decreases. At lower temperatures, the algorithm becomes more selective and only accepts better solutions or, in rare cases, worse ones based on a predefined probability. This cooling process mimics the slow cooling of metal, allowing the solution to "settle" near the global optimal solution.

The Simulated Annealing Pseudocode

Here’s a simplified look at how the algorithm works step by step:

1. Initialize:
   - Cooling schedule, maximum and minimum temperatures (Tmax, Tmin)
   - Generate an initial solution s0
   - Set the current solution s = s0
   - Set the starting temperature T = Tmax

2. Repeat until T <= Tmin:
   a. Repeat until a condition is met at each temperature:
      - Generate a neighboring solution s'
      - Calculate the change in cost (∆E) between s' and s
      - If ∆E ≤ 0, accept the new solution s' as the current solution s
      - Otherwise, accept s' with a probability proportional to e^(-∆E/T)
   b. Decrease the temperature T = α * T (cooling step)

3. Output the best solution found

Key Considerations for Simulated Annealing

• Cooling Schedule: The temperature needs to decrease gradually, allowing the solution to converge slowly towards the global optimum. A common choice for the cooling rate (α) is between 0.5 and 0.99.
• Starting Temperature: It’s important to start with a high temperature to explore a wide range of possible solutions. The higher the initial temperature, the more flexibility the algorithm has to accept worse solutions early on, which helps avoid local optima.
• Move Acceptance: Even if a new solution is worse than the current one, it might still be accepted, especially when the temperature is high. This probability decreases as the temperature drops.
• Equilibrium Condition: At each temperature, the algorithm explores a set number of neighboring solutions before cooling down. This can be a fixed number or dynamically adjusted based on the problem.
• Termination Condition: The algorithm can stop either after a set number of iterations or when the temperature reaches a very low value (effectively zero), ensuring that the search process is complete.

Real-World Applications

Simulated Annealing is utilized in various fields such as operations research, machine learning, and artificial intelligence. It is particularly valuable for solving problems in which the solution space is extensive and traditional methods struggle to find the global optimum.

If you want to dive deeper into the technical details of Simulated Annealing and see a practical example, I recommend checking out this tutorial on The Project Spot.