# Simulated Annealing

Simulated Annealing (SA) is a probabilistic technique used for finding the global optimum of a given function. It is particularly useful for optimization problems with a large search space. The method is inspired by the annealing process in metallurgy, a technique involving heating and controlled cooling of material to increase the size of its crystals and reduce their defects.

## Overview

Simulated Annealing is a metaheuristic approach to solve global optimization problems that may have many local optima. It’s often used when the search space is discrete (e.g., all tours that visit a given set of cities). The main idea is to simulate the physical process of heating a material and then slowly lowering the temperature to decrease defects, thus minimizing the system energy.

At each step, the SA algorithm randomly selects a solution close to the current one, measures its quality, and then decides to move to it or to stay with the current solution based on a probability that decreases as the temperature goes down. In this way, this method avoids being trapped in local optima and is able to explore globally for more possible solutions.

## Algorithm

The algorithm starts with an initial solution at a high initial temperature and then the temperature ‘cools’ over time. At each iteration, a neighbor solution is randomly generated. If the neighbor solution is better, it is accepted. However, if it is not, it can still be accepted with a certain probability, which is determined by the current temperature and the difference in quality between the current solution and the neighbor solution. This allows for a better exploration of the solution space.

The cooling schedule, which determines how the temperature decreases over time, is a critical component of the simulated annealing algorithm. It should be slow enough to allow a good exploration of the solution space, but not so slow that the algorithm takes too long to converge.

## Applications

Simulated Annealing has been successfully applied to a wide range of optimization problems, including: