Recocido simulado

En algorítmica , el recocido simulado es un método de optimización empírico ( metaheurístico ) , inspirado en un proceso utilizado en metalurgia . En este último se alternan ciclos lentos de enfriamiento y recalentamiento ( recocido ) , que tienen el efecto de minimizar la energía del material. Este método se transpone a la optimización para encontrar los extremos de una función.

Fue desarrollado por tres investigadores de la empresa IBM , S. Kirkpatrick, CD Gelatt y MP Vecchi en 1983, e independientemente por V. Černy en 1985.

El método proviene de la observación de que el enfriamiento natural de ciertos metales no permite que los átomos se coloquen en la configuración más sólida. La configuración más estable se logra controlando el enfriamiento y ralentizándolo agregando calor externo, o bien mediante aislamiento.

Recocido real

La descripción de los fenómenos físicos y cuánticos relacionados con el proceso de recocido se basa en las estadísticas de Maxwell-Boltzmann .

Escalada de colinas con recocido simulado.gif

Arriba, damos un ejemplo de recocido simulado con el objetivo de buscar un máximo. No es suficiente usar un algoritmo de escalada simple porque hay muchos máximos locales. Al enfriar el material lentamente, se puede encontrar el máximo general, con una probabilidad bastante alta.

Flujo del proceso

El recocido simulado se basa en el algoritmo Metropolis-Hastings , que describe la evolución de un sistema termodinámico . Por analogía con el proceso físico, la función a minimizar se convertirá en la energía del sistema. También introducimos un parámetro ficticio, la temperatura del sistema. $mi$ $T$

Partiendo de un estado dado del sistema, modificándolo, obtenemos otro estado. O mejora el criterio que se busca optimizar - luego se dice que se ha bajado la energía del sistema - o éste lo degrada. Si se acepta un estado que mejora el criterio, se tiende a buscar el óptimo en las proximidades del estado inicial. La aceptación de un estado "malo" permite explorar una parte más grande del espacio estatal y tiende a evitar quedar atrapado demasiado rápido en la búsqueda de un óptimo local.

Estado inicial del algoritmo

El estado inicial se puede tomar al azar en el espacio de estados posibles. A este estado corresponde una energía inicial . Esta energía se calcula según el criterio que se busca optimizar. También se elige una temperatura inicial alta de forma totalmente arbitraria en función de la ley de disminución utilizada. $E = E_ {0}$ $T = T_ {0}$

Iteraciones de algoritmos

En cada iteración del algoritmo se lleva a cabo una modificación elemental del estado. Esta modificación implica una variación de la energía del sistema (siempre calculada a partir del criterio que se busca optimizar). Si esta variación es negativa (es decir, baja la energía del sistema), se aplica en el estado actual. De lo contrario, se acepta con probabilidad . Esta elección de la exponencial para la probabilidad se llama regla de Metropolis. $\ Delta _ {E}$ $e ^ {{- {\ frac {\ Delta _ {E}} {T}}}}$

Luego se itera de acuerdo con este proceso mientras se mantiene constante la temperatura.

Programa de recocido

Son posibles dos enfoques con respecto a la variación de temperatura:

iterar manteniendo la temperatura constante. Cuando el sistema ha alcanzado el equilibrio termodinámico (después de un cierto número de cambios), la temperatura del sistema se reduce. Luego hablamos de niveles de temperatura;
bajar la temperatura continuamente. Podemos imaginar todo tipo de leyes de desintegración, siendo la más común con (elegimos con bastante frecuencia ). $T _ {{i + 1}} = \ lambda T_ {i}$ $\ lambda <1$ $\ lambda = 0,99$

En ambos casos, si la temperatura ha alcanzado un umbral lo suficientemente bajo establecido de antemano o si el sistema se congela, el algoritmo se detiene.

La temperatura juega un papel importante. A alta temperatura, el sistema es libre de moverse en el espacio de estados ( cercano a 1) eligiendo estados que no necesariamente minimizan la energía del sistema. A bajas temperaturas se eligen modificaciones que bajan la energía del sistema, pero se pueden aceptar otras, evitando así que el algoritmo caiga en un mínimo local. $e ^ {{- {\ frac {\ Delta _ {E}} {T}}}}$

Pseudocódigo

El siguiente pseudocódigo implementa el recocido simulado como se describió anteriormente, comenzando en el estado s0 y continuando hasta un máximo de pasos kmax o hasta que se encuentre un estado con energía emax o menos. E es una función que calcula la energía del estado s . La llamada vecina ( s ) genera un estado vecino al azar de un estado s . Llamar a random () devuelve un valor aleatorio en el rango [0, 1]. La llamada temp (r) devuelve la temperatura que se utilizará como una fracción r del tiempo total ya empleado, y P es una función de probabilidad que depende del cambio de energía y temperatura.

s := s0 e := E(s) k := 0 tant que k < kmax et e > emax sn := voisin(s) en := E(sn) si en < e ou aléatoire() < P(en - e, temp(k/kmax)) alors s := sn; e := en k := k + 1 retourne s

En la práctica, en el caso de que el número de iteraciones esté limitado con la kmax, también podemos considerar que s es un estado óptimo local e introducir una variable g para mantener el estado óptimo global, m para la mejor energía con inicialmente g: = s0 . Por lo tanto, al final del algoritmo, encontramos el estado de energía más bajo en lugar de un estado intermedio obtenido después de una ráfaga.

s := s0 g := s0 e := E(s) m := E(g) k := 0 tant que k < kmax et e > emax sn := voisin(s) en := E(sn) si en < e ou aléatoire() < P(en - e, temp(k/kmax)) alors s := sn; e := en si e > m alors g := s; m := e; k := k + 1 retourne g

En la imagen de abajo, la línea vertical azul representa los valores sucesivos de g , la línea roja representa los valores de sy la línea negra representa los valores de sn .

Desventajas

Los principales inconvenientes del recocido simulado radican en la elección de numerosos parámetros, como la temperatura inicial, la ley de disminución de la temperatura, los criterios de parada o la duración de las etapas de temperatura. Estos parámetros a menudo se eligen empíricamente.

Estudio teórico

Los estudios teóricos de recocido simulado han podido demostrar que, en determinadas condiciones, el algoritmo de recocido converge hacia un óptimo global. Este resultado es importante porque nos asegura, a diferencia de otras metaheurísticas , que el recocido simulado puede encontrar un estado correspondiente a la mejor solución, si lo dejamos buscar indefinidamente.

Las pruebas de convergencia se basan en el principio de construcción del algoritmo de recocido simulado:

siempre que respete la condición de Doeblin, una cadena de Markov admite una distribución estacionaria única ;
el algoritmo Metropolis-Hastings permite, dada una distribución de probabilidad , construir una cadena de Markov cuya distribución estacionaria es esta distribución de probabilidad.

Además, las medidas de Gibbs , muy utilizadas en física estadística , son una familia de medidas que dependen de un parámetro de temperatura de tal manera que cuando la temperatura tiende a 0, la medida converge hacia un Dirac en un punto dado (estado de mínima energía).

Al componer los dos, obtenemos una cadena de Markov que converge hacia una medida invariante que evoluciona al mismo tiempo hacia una medida que designa el óptimo deseado (en el sentido de la función energética asociada a la medida de Gibbs).

Un análisis fino de las velocidades de convergencia y de las desviaciones asintóticas permite entonces conducir a varias condiciones de convergencia, incluida la de Hajek: si el diagrama de temperatura utilizado satisface , entonces el algoritmo converge en probabilidad hacia el óptimo global. $T_ {n} \ geq {\ frac {K} {\ ln {n}}}$

En la práctica, este diagrama converge demasiado lentamente y se prefieren temperaturas con disminución lineal o cuadrática, incluso si eso significa obtener solo un mínimo local (que se espera que esté cerca del mínimo global).

Aplicaciones

Como ocurre con cualquier metaheurística , el método encuentra su aplicación en muchos campos en los que hay que resolver problemas de optimización difíciles . Estos incluyen el diseño de circuitos electrónicos ( ubicación-enrutamiento ) o la organización de redes informáticas. Este algoritmo se ha utilizado desde finales de la década de 1980 para determinar la arquitectura óptima de grandes redes telemáticas .

Ejemplo en Mathematica

F[X_] := Abs[X[[1]]] + Abs[X[[2]]]; g[T_] := N[T^0.99]; Recuit[F_, g_,Xi_,Ti_,Tf_,Ampli_,MaxTconst_,itermax_] := Module[{T,Xopt,iter=1,DF,p,L,X,compteur}, X = Xi; T = Ti; L = {Xi}; Xopt = X; While [T > Tf && iter < itermax, compteur = 1; While[compteur < MaxTconst, Y = X + Table[Ampli*Random[Real, {-1, 1}], {i, 1, Length[X]}]; DF = F[Y] - F[X]; If[DF < 0, X = Y; AppendTo[L, X]; If[F[X] < F[Xopt], Xopt = X], p = Random[]; If [p ≤ Exp[-DF/T], X = Y; AppendTo[L, X]]; ]; compteur = compteur + 1; ]; T = g[T]; iter = iter + 1; ]; Return[L] ]; resR = Recuit[F, g, {2, 3}, 10, 1, 0.5, 1.5, 1000]; ListPlot[resR, Joined -> True];

Notas y referencias

Virginie MATHIVET, Inteligencia artificial para desarrolladores: conceptos e implementaciones en C # , Saint-Herblain, edición eni,diciembre de 2017, 521 p. ( ISBN 978-2-409-01140-5 , leer en línea ) , pág. 10.3.5 Metaheurísticas de optimización. Implementación de recocido simulado
Aarts, EHL y v. Laarhoven (1985), Enfriamiento estadístico: un enfoque general de los problemas de optimización combinatoria, Philips J. Res., 40 (4), 193-226.
Cf. J. Lacroix, “ Markov Chains and Poisson Processes ” , en Pierre et Marie Curie University DEA Probabilities and Applications , 2001-2002) (consultado el 6 de marzo de 2017 ) .
Cf. Jean-Luc Lutton y Ernesto Bonomi , “ Le annuit simulé ”, Pour la science , n o 129,Julio de 1988, p. 68-77.

Ver también

Volver sobre la pista

enlaces externos

recocido simulado (subprograma Java)
recocido simulado para el viajante, aplicación en línea