Tema

Recocido simulado

IA clásica
Nivel intermedio
Con simulador interactivo

El recocido simulado es una búsqueda local que acepta siempre un vecino mejor y acepta uno peor con probabilidad exp(-delta / T), donde delta es el empeoramiento y T es una temperatura que baja con el tiempo.

Nombre en inglés

Simulated annealing

Intuición

Conviene imaginar una canica en un paisaje de valles y montañas dentro de una caja que se agita. Al principio la caja se agita con fuerza y la canica salta de un valle a otro, incluso hacia arriba. A medida que la agitación baja, la canica queda atrapada, y si el enfriamiento fue lento esa trampa suele ser el valle más profundo. La temperatura controla el canje entre explorar y afinar, y toda la destreza está en el ritmo de enfriamiento.

Fórmula

P(aceptar) = exp( -( f(vecino) - f(actual) ) / T )  para minimizar,  T_{k+1} = alfa T_k con alfa cercano a 1

Ejemplo resuelto

Se minimiza una función y el estado actual vale 10 mientras el vecino propuesto vale 12, de modo que delta = 2. Con T = 10 la probabilidad de aceptar el empeoramiento es exp(-0.2) = 0.819, o sea que casi siempre se acepta y la búsqueda vaga por el espacio. Con T = 1 la probabilidad baja a exp(-2) = 0.135. Con T = 0.1 queda en exp(-20), del orden de 2 por diez elevado a menos nueve, y el método ya se comporta como un ascenso de colinas puro.

Errores frecuentes

Enfriar deprisa para acabar antes, con lo que el método se queda en el primer óptimo local y rinde peor que un ascenso de colinas con reinicios aleatorios.
Calcular la probabilidad de aceptación también para los vecinos mejores, cuando esos se aceptan siempre y aplicarles la fórmula rechaza mejoras sin motivo.
Comparar el recocido con otros optimizadores contando iteraciones en lugar de evaluaciones de la función objetivo, que es el recurso caro y el único justo para comparar.

Ejercicio

Se minimiza una función, el estado actual vale 5, el vecino vale 8 y la temperatura es T = 3. Calcula la probabilidad de aceptar el vecino.

Ver la solución

El empeoramiento es delta = 8 - 5 = 3. La probabilidad de aceptación vale exp(-delta / T) = exp(-3 / 3) = exp(-1) = 0.368. Dicho de otro modo, cerca de 37 de cada 100 propuestas de ese tamaño se aceptarían a esa temperatura. Si la temperatura bajase a T = 0.5, la misma propuesta se aceptaría con probabilidad exp(-6) = 0.0025.