Adaptive simulated annealing
Encyclopedia
Adaptive simulated annealing (ASA) is a variant of simulated annealing
(SA) algorithm in which the algorithm parameters that control temperature schedule and random step selection are automatically adjusted according to algorithm progress. This makes the algorithm more efficient and less sensitive to user defined parameters than canonical SA. These are in the standard variant often selected on the basis of experience and experimentation (since optimal values are problem dependent), which represents a significant deficiency in practice.
The algorithm works by representing the parameters of the function to be optimized as continuous numbers, and as dimensions of a hypercube (N dimensional space). Some SA algorithms apply Gaussian
moves to the state, while others have distributions permitting faster temperature schedules. Imagine the state as a point in a box and the moves as a rugby-ball shaped cloud around it. The temperature and the step size are adjusted so that all of the search space is sampled to a coarse resolution in the early stages, whilst the state is directed to favorable areas in the late stages.
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
(SA) algorithm in which the algorithm parameters that control temperature schedule and random step selection are automatically adjusted according to algorithm progress. This makes the algorithm more efficient and less sensitive to user defined parameters than canonical SA. These are in the standard variant often selected on the basis of experience and experimentation (since optimal values are problem dependent), which represents a significant deficiency in practice.
The algorithm works by representing the parameters of the function to be optimized as continuous numbers, and as dimensions of a hypercube (N dimensional space). Some SA algorithms apply Gaussian
GAUSSIAN
Gaussian is a computational chemistry software program initially released in 1970 by John Pople and his research group at Carnegie-Mellon University as Gaussian 70. It has been continuously updated since then...
moves to the state, while others have distributions permitting faster temperature schedules. Imagine the state as a point in a box and the moves as a rugby-ball shaped cloud around it. The temperature and the step size are adjusted so that all of the search space is sampled to a coarse resolution in the early stages, whilst the state is directed to favorable areas in the late stages.
See also
- Simulated annealingSimulated annealingSimulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
- Combinatorial optimizationCombinatorial optimizationIn applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
- OptimizationOptimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
External links
- Global optimization Explains some ideas behind ASA.
- Adaptive Simulated Annealing (ASA) Explains history and use of the ASA code, first published as Very Fast Simulated Reannealing (VFSR) in 1989, and made available to the public at no charge since 1993 under the name ASA. This ASA algorithm is not the same as the algorithm described at the top of http://en.wikipedia.org/wiki/Adaptive_simulated_annealing or in http://www.sinopt.com/learning1/desnotes/globopt.htm.