Free cookie consent management tool by TermsFeed Policy Generator
wiki:SA

Simulated Annealing

Simulated Annealing is commonly said to be the oldest among the metaheuristics. It has its origins in the Metropolis algorithm which was published in 1953 and was adopted as a general metaheuristic, termed Simulated Annealing in 1983 by Kirkpatrick, Gelatt and Vecchi (Kirkpatrick et al. 1983) who demonstrated the algorithm on various problems of computer design and the traveling salesman problem.

Cooling Schedules: Cooling schedules may alter the speed at which the temperature is reduced depending on the current iteration, so that there are schedules that offer a slower initial decrease, or even inverse signum shaped schedules that intensify rapidly in about the middle of the search. There also exist cooling schedules that swap between a growing and a deteriorating temperature, also called reheating schedules, and which allow to diversify the search to a greater degree.

  • Geometric cooling schedule
  • Linear cooling schedule

Algorithm Parameters:

Parameter Description
Analyzer The operator used to analyze each generation.
AnnealingOperator The operator used to modify the temperature.
EndTemperature The final temperature which should be reached when iterations reaches maximum iterations.
InnerIterations The amount of inner iterations (number of moves before temperature is adjusted again).
MaximumIterations The maximum number of generations which should be processed.
MoveEvaluator The operator used to evaluate a move.
MoveGenerator The operator used to generate moves to the neighborhood of the current solution.
MoveMaker The operator used to perform a move.
Seed The random seed used to initialize the new pseudo random number generator.
SetSeedRandomly True if the random seed should be set to a random value, otherwise false.
StartTemperature The initial temperature.

Is there a sample/tutorial?

Yes. HeuristicLab comes with a simulated annealing algorithm that solves the 2-dimensional Rastrigin test function. Have a look at the description here.

References:

  • Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science 220:671–680.
Last modified 12 years ago Last modified on 02/17/11 10:27:13