Simulated Annealing

La característica principal del algoritmo es que al buscar una nueva aproximación X_n+1 dado X_n, acepta de vez en cuando una solución inferior a X_n por medio de un mecanismo probabilístico.

El esquema base es:

WHILE not-good-enough(x) DO
genera(x)
IF f(y) > f(x)

ELSE con probabilidad e^{(f(y)-f(x))/T}

dónde

genera():

tal que se pueda calcular fácilmente f(y)-f(x) ; esta función determina el número de óptimas locales; las restricciones teóricas son que se debería poder generar cualquier estado a partir de cualquier otro estado, usando eventualmente un número de estados intermediarios y que la probabilidad de generar x a partir de y es igual a la probabilidad de generar y a partir de x.

lower-temp:

Típicamente con entre 0.9 y 0.99; un demasiado grande implica una perdida de calculos; si es demasiado pequeno, ya no se puede escapar de optimas locales.

T₀:

tal que se acepte la mayoría de los cambios.

Se ve que entre más baja la temperatura, menor la probabilidad de aceptar una solución peor; i.e. al inicio el énfasis está en la exploración del espacio y al final a la explotación.

Para la descripción teorica de este algoritmo (usando cadenas de Markov), referimos a un curso más especializado.