Questions: Simulated Annealing

Question 1

When simulated annealing evaluates a neighboring solution that is worse than the current one, what does it do?

• A. It always rejects worse solutions to ensure the objective function never decreases
• B. It accepts the worse solution with probability exp(−ΔE/T), which is close to 1 at high temperature and near 0 at low temperature
• C. It restarts from a random position in the search space to escape the local region
• D. It pauses and waits for temperature to decrease before deciding whether to accept

Answer: (B)

This probabilistic acceptance of worse solutions is the defining mechanism of simulated annealing and the key difference from hill climbing. At high temperature, exp(−ΔE/T) ≈ 1, so almost any move is accepted — the algorithm wanders freely. As temperature decreases, the probability drops, and worse moves are accepted less often. This schedule of gradually restricting exploration is what allows the algorithm to first escape local optima (high T) and then converge to a good solution (low T).

Question 2

A practitioner runs simulated annealing with a very aggressive cooling schedule, halving the temperature every 10 iterations. What is the most likely outcome compared to using a slow cooling schedule?

• A. The algorithm explores more of the search space and reliably finds a better final solution
• B. The algorithm effectively behaves like hill climbing and is likely to get stuck in a local optimum
• C. The algorithm converges to the global optimum faster because it wastes less time on bad solutions
• D. The theoretical guarantee still ensures convergence to the global optimum in fewer total steps

Answer: (B)

Fast cooling means the temperature drops quickly to near zero, so the acceptance probability for worse solutions falls to near zero almost immediately. The algorithm then only accepts improvements — exactly like hill climbing — and gets stuck at whatever local optimum is nearby. The whole point of simulated annealing is to avoid this by cooling slowly enough that the algorithm has time to explore beyond local optima. The theoretical guarantee of finding the global optimum requires a specific logarithmically slow cooling schedule, which fast cooling violates entirely.

Question 3

Simulated annealing is theoretically guaranteed to find the global optimum if the cooling schedule is slow enough.

• T. True
• F. False

Answer: True

This is a proven theoretical result: if the temperature decreases no faster than T(t) ≥ C/log(t), where C is a constant related to the energy barriers in the problem, then simulated annealing converges to the global optimum with probability 1. The catch is that this logarithmic cooling schedule is extraordinarily slow — impractically slow for real problems. In practice, faster cooling schedules (geometric decay) are used, sacrificing the theoretical guarantee for a good-enough solution in reasonable computation time.

Question 4

In practice, simulated annealing is widely used because any reasonable cooling schedule is expected to find the global optimum in polynomial time.

• T. True
• F. False

Answer: False

The theoretical guarantee of convergence to the global optimum requires a logarithmically slow cooling schedule — one so slow it is computationally impractical. No faster cooling schedule carries this guarantee. In practice, geometric cooling schedules (T_new = α·T_old with α close to 1) are used because they work well empirically, but they only guarantee a good solution, not the global optimum. Simulated annealing is a heuristic that trades guaranteed optimality for practical efficiency.

Question 5

Explain how simulated annealing differs from simple hill climbing, and why accepting worse solutions early in the search actually improves the quality of the final solution.

Model answer: Hill climbing always moves to a better neighbor and never accepts worse solutions, so it converges to the nearest local optimum and gets stuck there — unable to explore the broader search space. Simulated annealing adds probabilistic acceptance of worse solutions, controlled by a temperature parameter. Early in the search (high temperature), the algorithm accepts almost any move, allowing it to explore widely across the search space and escape the basin of attraction around any single local optimum. As temperature decreases, acceptance becomes increasingly selective, and the algorithm settles into the best region it has found. The insight is that getting stuck in a local optimum is a failure of short-sighted greedy search; by temporarily allowing moves that look bad locally, the algorithm gains the ability to discover globally better solutions that would be inaccessible to hill climbing.

The physics analogy is instructive: a molten metal cooled rapidly (quenching) freezes into a disordered crystal with many local energy minima (defects). Cooled slowly (annealing), atoms have time to explore configurations and settle into the lowest-energy crystalline state. The algorithm mimics this process, using the Boltzmann probability distribution from statistical mechanics to control exploration vs exploitation.