Informed (Heuristic) Search
Simulated Annealing Search
Simulated Annealing (SA) is an optimization algorithm inspired by the annealing process in metallurgy, where materials are heated and slowly cooled to reach a stable state with minimal energy. It is used to find approximate solutions to optimization problems by iteratively exploring potential solutions and occasionally accepting worse solutions to escape local optima.
How Simulated Annealing Works
1. High Temperature Phase: The algorithm explores widely,
accepting many worse solutions to escape local minima.
2. Cooling Process: As temperature decreases, the algorithm becomes
more selective about which solutions to accept.
3. Convergence: At low temperatures, the algorithm converges to
a near-optimal solution, making only small adjustments.
Key Insight: The acceptance probability ($P = e$-ΔE/T) allows the algorithm to escape local minima while eventually settling in a good solution.