Simulated annealing


Simulated annealing

Simulated annealing

Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta-heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande.

El nombre e inspiración viene del proceso de recocido del acero, una técnica que consiste en calentar y luego enfriar controladamente un material para aumentar el tamaño de sus cristales y reducir sus defectos. El calor causa que los átomos se salgan de sus posiciones iniciales (un mínimo local de energía) y se muevan aleatoriamente; el enfriamiento lento les da mayores probabilidades de encontrar configuraciones con menor energía que la inicial.

Contenido

Iteración básica

En cada iteración, el simulated annealing considera algunos vecinos del estado actual s, y probabilísticamente decide entre cambiar el sistema al estado s' o quedarse en el estado s. Las probabilidades se escogen para que el sistema tienda finalmente a estados de menor energía. Típicamente este paso se repite hasta que se alcanza un estado suficientemente bueno para la aplicación o hasta que se cumpla cierto tiempo computacional dado.

Vecindario de un estado

Los vecinos de cada estado se eligen dependiendo del problema específico. Usualmente es una pequeña variación en la representación escogida.

Probabilidad de transición

La probabilidad de hacer la transición al nuevo estado s' es una función P(δ E, T) de la diferencia de energía δE=E(s')-E(s) entre los dos estados, y de la variable T, llamada temperatura.

Una cualidad importante del método SA es que la probabilidad de transición P es siempre distinta de cero, aún cuando δE sea positivo, es decir, el sistema puede pasar a un estado de mayor energía(peor solución) que el estado actual. Esta cualidad impide que el sistema se quede atrapado en un óptimo local.

Cuando la temperatura tiende al mínimo, la probabilidad tiende a cero asintóticamente. Así, cada vez el algoritmo acepta menos movimientos que aumenten la energía.

Si δE es negativo, es decir, la transición disminuye la energía, el movimiento es aceptado con probabilidad P=1.

La velocidad de enfriamiento

Otra cualidad del simulated annealing es que la temperatura va disminuyendo gradualmente conforme avanza la simulación. Hay muchas maneras de disminuir la temperatura, siendo la más usual la exponencial, dónde T disminuye por un factor α<1 en cada paso.

Obtenido de "Simulated annealing"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Simulated annealing — (SA) is a generic probabilistic meta algorithm for the global optimization problem, namely 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 (e.g.,… …   Wikipedia

  • Simulated annealing — (SA) es una meta heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande. El nombre e inspiración viene del proceso de templado (annealing en… …   Enciclopedia Universal

  • Simulated Annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… …   Deutsch Wikipedia

  • Simulated annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… …   Deutsch Wikipedia

  • simulated annealing — noun A randomized improvement algorithm, analagous to the metalworking process annealing. For this problem, the simulated annealing based heuristic provides a near optimal solution …   Wiktionary

  • 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… …   Wikipedia

  • [ECG]; simian adenovirus; simulated annealing [algorithm]; sinoatrial; sinus arrest; sinus arrhythmia; skeletal age; skin-adipose [unit]; sleep apnea; slightly active; slowly adapting [receptor]; soluble in alkaline medium; Spanish American; specific activity; spectrum analysis; sperm abnormality; s — sinoatrial; sinoauricular …   Medical dictionary

  • Annealing — may refer to: *Annealing (metallurgy), a heat treatment that alters the microstructure of a material causing changes in properties such as strength and hardness *Annealing (glass), heating a piece of glass to remove stress *Annealing (biology),… …   Wikipedia

  • Quantum annealing — In mathematics and applications, quantum annealing (QA) is a general method for finding the global minimum of a given objective function over a given set of candidate solutions (the search space ), by a process analogous to quantum fluctuations.… …   Wikipedia

  • Algoritmo de recocido simulado — Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta heurística para problemas de optimización global; el objetivo geneneral de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en …   Wikipedia Español