- 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.
Categorías: Algoritmos de búsqueda | Heurística
Wikimedia foundation. 2010.
