Simulated Annealing
Basic information
Simulated Annealing (SA) is a probabilistic metaheuristic inspired by the annealing process in metallurgy. It is used for finding an approximate global optimum of a given function in a large search space. The algorithm explores the solution space by probabilistically accepting not only improvements but also, with a certain probability, worse solutions. This allows it to escape local optima and increases the chance of finding a global optimum.
The probability of accepting worse solutions decreases over time, controlled by a “temperature” parameter that is gradually reduced according to a cooling schedule.
Structure of the algorithm
The main steps in Simulated Annealing are:
Initialization: Start with an initial solution and set the initial temperature.
Main Loop: - Generate a neighbor solution using a neighborhood structure. - Evaluate the neighbor solution. - If the neighbor is better than the current solution, accept it. - If the neighbor is worse, accept it with a probability that depends on the temperature and the difference in solution quality. - Update the temperature according to the cooling schedule.
Termination: The algorithm stops when a stopping criterion is met (e.g., maximum number of iterations, time limit, or temperature threshold).
Implementation notes
Implementation of this optimization method is given within the class SaOptimizer.
Neighborhoods: The neighborhood structure is defined by subclasses of
SaNeighbourhood
, such asSaNeighbourhoodInt
for integer-encoded solutions andSaNeighbourhoodBitArray
for bit array-encoded solutions.Temperature Schedules: Several temperature schedules are available, including constant, linear, and exponential decay, implemented in classes such as
SaTemperatureConst
,SaTemperatureLinear
, andSaTemperatureExponential
.Extensibility: You can implement custom neighborhoods or temperature schedules by subclassing the appropriate base classes.
Usage: To use the SA optimizer, construct an instance of
SaOptimizer
with the desired neighborhood, temperature schedule, problem, and other parameters.
References
Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983). “Optimization by Simulated Annealing”. Science. 220 (4598): 671–680. doi:10.1126/science.220.4598.671.
Aarts, E.; Korst, J. (1988). “Simulated Annealing and Boltzmann Machines”. Wiley.
Burke, EK.; Kendall, G. (2005). Burke, Edmund K; Kendall, Graham (eds.). Search methodologies. Introductory tutorials in optimization and decision support techniques. Springer. doi:10.1007/978-1-4614-6940-7. ISBN 978-1-4614-6939-1.