Simulated Annealing

Simulated Annealing (SA) draws inspiration from the physical process of annealing in metallurgy—where metals are heated and then slowly cooled to reduce defects and increase strength through controlled crystallization. This optimization technique mimics this thermodynamic process to escape local optima and find near-global optimal solutions.

The algorithm begins with an initial solution and a high 'temperature' parameter. At each iteration, it randomly proposes a neighboring solution and decides whether to accept it based on both its quality and the current temperature. Better solutions are always accepted, but importantly, worse solutions may also be accepted with a probability that depends on how much worse they are and the current temperature.

This probabilistic acceptance of suboptimal moves allows the algorithm to escape local optima by occasionally moving 'uphill' in the early stages when the temperature is high. As the temperature gradually decreases according to a cooling schedule, the algorithm becomes increasingly selective, eventually converging toward a local optimum—but ideally after having explored enough of the solution space to find a high-quality region.

Simulated annealing has proven remarkably effective for combinatorial optimization problems like circuit design, job shop scheduling, and graph partitioning. Its simplicity of implementation combined with theoretical guarantees of convergence to global optima (given sufficiently slow cooling) makes it a popular choice for problems with complex, multimodal optimization landscapes.