Recocido simulado: sistemas complejos e IA

Contenido

Recocido simulado

El recocido es un método metalúrgico para obtener sólidos cristalizados evitando el estado vítreo. Una vez que el metal se ha fundido, 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 etapas decrecientes de temperatura, hasta que alcanza un estado estable.

Este sistema de nivel descendente dio origen al algoritmo Metropolis de 1953 y luego al recocido simulado de 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 alcanzar 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 basa en 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.

Flujo de 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)
Reducir la temperatura T hasta un umbral de temperatura 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 degradan 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 lo tanto, la temperatura permite "saltar" áreas menos "buenas" para salir de un "valle". Las bolas y señales de la siguiente figura muestran qué tan alto 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: