Recocido simulado: sistemas complejos e IA

Contenido

Recocido simulado

El recocido es un método metalúrgico que permite obtener sólidos cristalizados evitando el estado vítreo. Una vez que el metal se ha derretido, la temperatura se baja gradualmente hasta que alcanza un estado sólido. Para eliminar todos los defectos, el metal se calienta y luego se enfría, en pasos de temperatura decrecientes, hasta que se alcanza un estado estable.

Este sistema de pasos decrecientes dio origen al algoritmo Metropolis de 1953 y luego al recocido simulado por IBM en 1983.

Presentación del algoritmo

El algoritmo de recocido simulado, o recocido simulado para hablantes de inglés, es por lo tanto la adaptación algorítmico del proceso de recocido.

El objetivo es lograr un estado estable de la función objetivo, un óptimo local o global, a partir de una solución aleatoria. Este estado se alcanza por etapas, donde la aceptación de una mutación se realiza según la "temperatura" de la etapa.

El algoritmo de recocido simulado genera sucesivamente configuraciones a partir de una solución inicial R₀ y una temperatura inicial T₀ disminuyendo con cada iteración, hasta obtener una configuración estable. La probabilidad de aceptar una nueva configuración es (regla de Metropolis):

1 si la configuración mejora la función objetivo;
exp (diff (E) / T) con diff (E) la diferencia de energía y T la temperatura; la diferencia de energía es una función interna, dependiendo de la función objetivo.

Secuencia del algoritmo

El algoritmo de recocido es el siguiente:

Tome una solución inicial R = R₀ y una temperatura inicial T = T₀. El estado inicial es en cuanto a los métodos exactos, obtenidos por un heurístico (cuesta abajo o glotón).
Genera una solución aleatoria R_{(yo + 1)} en las cercanías de la solución actual:
1. comparar R_{(yo + 1)} con R_I según la regla de Metropolis
2. repetir hasta que se encuentre una solución estable (o después de un cierto número de iteraciones)
Disminuir la temperatura T a una temperatura umbral T_min, o tener una solución estable.

 R₀
T₀
tanto que T> T_min y E> e_max
   R_{(yo + 1)} = vecino (R_I)
   si E (R_{(yo + 1)}) <E (R_I) Dónde aleatorio () <P (diff (E) / T) entonces
      aceptar R_{(yo + 1)}
   actualizar T
regreso R_no

Dado que T es grande al principio, se pueden elegir muchas soluciones que degraden la solución actual. Esto permite escapar de un óptimo local. La siguiente figura muestra el valor de la función objetivo en función del vector de parámetros X. Por tanto, la temperatura permite "saltar" zonas menos "buenas" para dejar un "valle". Las bolas y señales de la siguiente figura muestran hasta qué altura pueden "saltar" las bolas, es decir, la tolerancia de variación negativa de la función objetivo en la obtención de una nueva solución.

Si la temperatura es baja, es más difícil escapar de un óptimo local: