Recocido simulado

En cada paso, la heurística de recocido simulado considera un estado vecino s* del estado actual s y decide probabilísticamente entre mover el sistema al estado s* o permanecer en el estado s . Estas probabilidades, en última instancia, llevan al sistema a estados de menor energía. Normalmente, este paso se repite hasta que el sistema alcanza un estado suficientemente bueno para la aplicación o hasta que se agota el presupuesto computacional asignado.

La optimización de una solución implica evaluar los estados vecinos, que son nuevos estados generados mediante la modificación conservadora del estado actual. Por ejemplo, en el problema del viajante , cada estado se define típicamente como una permutación de las ciudades a visitar, y los vecinos de cualquier estado son el conjunto de permutaciones que se obtienen al intercambiar dos de estas ciudades. La forma bien definida en que se modifican los estados para generar estados vecinos se denomina movimiento , y diferentes movimientos dan lugar a diferentes conjuntos de estados vecinos. Estos movimientos suelen producir modificaciones mínimas del estado actual, con el objetivo de mejorar progresivamente la solución mediante la mejora iterativa de sus componentes (como las conexiones entre ciudades en el problema del viajante).

Las heurísticas simples , como el algoritmo de ascenso de colinas , que avanza buscando vecinos mejores uno tras otro y se detiene cuando alcanza una solución sin vecinos mejores, no garantizan encontrar ninguna de las soluciones mejores existentes ; su resultado puede ser fácilmente un óptimo local , mientras que la mejor solución real sería un óptimo global que podría ser diferente. Las metaheurísticas utilizan los vecinos de una solución para explorar el espacio de soluciones y, aunque prefieren los vecinos mejores, también aceptan probabilísticamente vecinos peores para evitar quedarse atascadas en óptimos locales; pueden encontrar el óptimo global si se les da suficiente tiempo. 

La probabilidad de realizar la transición desde el estado actual${\displaystyle s}$a un candidato nuevo estado${\displaystyle s_{\mathrm {new} }}$se especifica mediante una función de probabilidad de aceptación${\displaystyle P(e,e_{\mathrm {nuevo} },T)}$, eso depende de las energías${\displaystyle e=E(s)}$y${\displaystyle e_{\mathrm {nuevo} }=E(s_{\mathrm {nuevo} })}$de los dos estados, y en un parámetro global que varía con el tiempo.${\displaystyle T}$llamada temperatura . Los estados con menor energía son mejores que aquellos con mayor energía. La función de probabilidad${\displaystyle P}$debe ser positivo incluso cuando${\displaystyle e_{\mathrm {new} }}$es mayor que${\displaystyle e}$Esta característica evita que el método se quede atascado en un mínimo local que sea peor que el mínimo global.

Cuando${\displaystyle T}$tiende a cero, la probabilidad${\displaystyle P(e,e_{\mathrm {nuevo} },T)}$debe tender a cero si${\displaystyle e_{\mathrm {nuevo} }>e}$y a un valor positivo en caso contrario. Para valores suficientemente pequeños de${\displaystyle T}$, el sistema favorecerá cada vez más los movimientos que van cuesta abajo (es decir, hacia valores de energía más bajos) y evitará aquellos que van cuesta arriba . Con${\displaystyle T=0}$El procedimiento se reduce al algoritmo voraz , que realiza únicamente las transiciones cuesta abajo.

En la descripción original del recocido simulado, la probabilidad${\displaystyle P(e,e_{\mathrm {nuevo} },T)}$era igual a 1 cuando${\displaystyle e_{\mathrm {nuevo} }<e}$—Es decir, el procedimiento siempre avanzaba cuesta abajo cuando encontraba la manera de hacerlo, independientemente de la temperatura. Muchas descripciones e implementaciones del recocido simulado aún consideran esta condición como parte de la definición del método. Sin embargo, esta condición no es esencial para que el método funcione.

El${\displaystyle P}$La función se suele elegir de modo que la probabilidad de aceptar un movimiento disminuya cuando la diferencia${\displaystyle e_{\mathrm {nuevo} }-e}$Los incrementos —es decir, los pequeños ascensos son más probables que los grandes—. Sin embargo, este requisito no es estrictamente necesario, siempre que se cumplan los requisitos anteriores.

Dadas estas propiedades, la temperatura${\displaystyle T}$desempeña un papel crucial en el control de la evolución del estado${\displaystyle s}$del sistema con respecto a su sensibilidad a las variaciones de las energías del sistema. Para ser precisos, para un gran${\displaystyle T}$, la evolución de${\displaystyle s}$es sensible a variaciones de energía más gruesas, mientras que es sensible a variaciones de energía más finas cuando${\displaystyle T}$es pequeño.

Rápido

Lento

Ejemplo que ilustra el efecto del programa de enfriamiento en el rendimiento del recocido simulado. El problema consiste en reorganizar los píxeles de una imagen para minimizar una determinada función de energía potencial , que provoca que los colores similares se atraigan a corta distancia y se repelan a una distancia ligeramente mayor. Los movimientos elementales intercambian dos píxeles adyacentes. Estas imágenes se obtuvieron con un programa de enfriamiento rápido (izquierda) y un programa de enfriamiento lento (derecha), produciendo resultados similares a los de sólidos amorfos y cristalinos , respectivamente.

El nombre y la inspiración del algoritmo exigen una variación de temperatura controlada. Esto requiere una reducción gradual de la temperatura a medida que avanza la simulación. El algoritmo comienza inicialmente con${\displaystyle T}$establecido a un valor alto, y luego se disminuye en cada paso siguiendo algún programa de recocido , que puede ser especificado por el usuario pero debe terminar con${\displaystyle T=0}$hacia el final del tiempo asignado. De esta manera, se espera que el sistema se dirija inicialmente hacia una amplia región del espacio de búsqueda que contenga buenas soluciones, ignorando las pequeñas características de la función de energía; luego se desplace hacia regiones de baja energía que se vuelven más estrechas, y finalmente descienda siguiendo la heurística del descenso más pronunciado .

Para cualquier problema finito dado, la probabilidad de que el algoritmo de recocido simulado termine con una solución óptima global se aproxima a 1 a medida que se extiende el programa de recocido. ^{[ 12 ]} Sin embargo, este resultado teórico no es particularmente útil, ya que el tiempo requerido para asegurar una probabilidad significativa de éxito generalmente excederá el tiempo requerido para una búsqueda completa del espacio de soluciones . ^{[ 13 ]}

El recocido simulado puede modelarse como un paseo aleatorio en un grafo de búsqueda, cuyos vértices son todos los estados posibles y las aristas que conectan los vértices son los movimientos candidatos. Un requisito esencial para la función neighbor() es que debe proporcionar un camino suficientemente corto en este grafo desde el estado inicial a cualquier estado que pueda ser el óptimo global ; el diámetro del grafo de búsqueda debe ser pequeño. En el ejemplo del viajante de comercio anterior, por ejemplo, el espacio de búsqueda para n = 20 ciudades tiene n! = 2.432.902.008.176.640.000 (2,4 quintillones) de estados; sin embargo, el número de vecinos de cada vértice es   ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$bordes (que vienen de${\displaystyle n \choose 2}$), y el diámetro del gráfico es${\displaystyle n-1}$.

Para investigar el comportamiento del recocido simulado en un problema particular, puede ser útil considerar las probabilidades de transición que resultan de las diversas decisiones de diseño tomadas en la implementación del algoritmo. Para cada arista${\displaystyle (s,s')}$del grafo de búsqueda, la probabilidad de transición se define como la probabilidad de que el algoritmo de recocido simulado se mueva al estado ${\displaystyle s'}$cuando su estado actual es${\displaystyle s}$Esta probabilidad depende de la temperatura actual especificada por temperature() , del orden en que se generan los movimientos candidatos mediante la función neighbor() y de la función de probabilidad de aceptación P() . Tenga en cuenta que la probabilidad de transición no es simplemente${\displaystyle P(e,e',T)}$, porque los candidatos son evaluados de forma secuencial.

La especificación de neighbor() , P() y temperature() es parcialmente redundante. En la práctica, es común usar la misma función de aceptación P() para muchos problemas y ajustar las otras dos funciones según el problema específico.

En la formulación del método de Kirkpatrick et al., la función de probabilidad de aceptación P(e, e', T) se definió como 1 si e' < e y \exp(-(e'-e)/T) en caso contrario. Esta fórmula se justificó superficialmente por analogía con las transiciones de un sistema físico; corresponde al algoritmo de Metropolis-Hastings , en el caso de que T=1 y la distribución de propuestas de Metropolis-Hastings sea simétrica. Sin embargo, esta probabilidad de aceptación se usa a menudo para el recocido simulado incluso cuando la función neighbor() , que es análoga a la distribución de propuestas en Metropolis-Hastings, no es simétrica o no es probabilística en absoluto. Como resultado, las probabilidades de transición del algoritmo de recocido simulado no corresponden a las transiciones del sistema físico análogo, y la distribución a largo plazo de estados a una temperatura constante T no tiene por qué tener ninguna semejanza con la distribución de equilibrio termodinámico sobre los estados de ese sistema físico, a ninguna temperatura. Sin embargo, la mayoría de las descripciones del recocido simulado asumen la función de aceptación original, que probablemente está codificada de forma fija en muchas implementaciones.

En 1990, Moscato y Fontanari ^{[ 14 ]} , e independientemente Dueck y Scheuer ^{[ 15 ],} propusieron que una actualización determinista (es decir, una que no se basa en la regla de aceptación probabilística) podría acelerar el proceso de optimización sin afectar la calidad final. Moscato y Fontanari concluyeron, al observar la curva análoga de "calor específico" del recocido de "actualización de umbral" originada en su estudio, que "la estocasticidad de la actualización de Metropolis en el algoritmo de recocido simulado no juega un papel importante en la búsqueda de mínimos casi óptimos". En cambio, propusieron que "el suavizado del paisaje de la función de costo a alta temperatura y la definición gradual de los mínimos durante el proceso de enfriamiento son los ingredientes fundamentales para el éxito del recocido simulado". El método se popularizó posteriormente bajo la denominación de "aceptación de umbral" debido a la denominación de Dueck y Scheuer. En 2001, Franz, Hoffmann y Salamon demostraron que la estrategia de actualización determinista es, de hecho, la óptima dentro de la amplia clase de algoritmos que simulan un paseo aleatorio en el paisaje de costos/energía. ^{[ 16 ]}

Al elegir el generador candidato neighbour(), se debe considerar que después de algunas iteraciones del algoritmo de recocido simulado, se espera que el estado actual tenga una energía mucho menor que un estado aleatorio. Por lo tanto, como regla general, se debe sesgar el generador hacia movimientos candidatos donde la energía del estado de destino${\displaystyle s'}$Es probable que sea similar al estado actual. Esta heurística (que es el principio fundamental del algoritmo de Metropolis-Hastings ) tiende a excluir tanto los movimientos candidatos muy buenos como los muy malos ; sin embargo, los primeros suelen ser mucho menos frecuentes que los segundos, por lo que la heurística suele ser bastante eficaz.

En el problema del viajante de comercio anterior, por ejemplo, se espera que intercambiar dos ciudades consecutivas en un recorrido de baja energía tenga un efecto modesto en su energía (longitud); mientras que intercambiar dos ciudades arbitrarias tiene muchas más probabilidades de aumentar su longitud que de disminuirla. Por lo tanto, se espera que el generador de vecinos de intercambio consecutivo funcione mejor que el de intercambio arbitrario, aunque este último podría proporcionar un camino algo más corto hacia el óptimo (con${\displaystyle n-1}$intercambios, en lugar de${\displaystyle n(n-1)/2}$).

Una formulación más precisa de la heurística es que se deben probar los primeros estados candidatos.${\displaystyle s'}$para qué${\displaystyle P(E(s),E(s'),T)}$es grande. Para la función de aceptación "estándar"${\displaystyle P}$arriba, significa que${\displaystyle E(s')-E(s)}$es del orden de${\displaystyle T}$o menos. Por lo tanto, en el ejemplo del viajante de comercio anterior, se podría usar una neighbour()función que intercambie dos ciudades aleatorias, donde la probabilidad de elegir un par de ciudades se desvanece a medida que su distancia aumenta más allá de${\displaystyle T}$.

Al elegir el generador candidato, neighbour()también se debe intentar reducir el número de mínimos locales profundos: estados (o conjuntos de estados conectados) con una energía mucho menor que la de todos sus estados vecinos. Estas "cuencas cerradas " de la función de energía pueden atrapar el algoritmo de recocido simulado con alta probabilidad (aproximadamente proporcional al número de estados en la cuenca) y durante un tiempo muy prolongado (aproximadamente exponencial con respecto a la diferencia de energía entre los estados circundantes y el fondo de la cuenca).

Por regla general, es imposible diseñar un generador de candidatos que satisfaga este objetivo y también priorice candidatos con energía similar. Por otro lado, a menudo se puede mejorar enormemente la eficiencia del recocido simulado mediante cambios relativamente simples en el generador. En el problema del viajante, por ejemplo, no es difícil mostrar dos recorridos${\displaystyle A}$,${\displaystyle B}$, con longitudes casi iguales, de tal manera que (1)${\displaystyle A}$es óptimo, (2) cada secuencia de intercambios de pares de ciudades que convierte${\displaystyle A}$a${\displaystyle B}$pasa por recorridos que son mucho más largos que ambos, y (3)${\displaystyle A}$puede transformarse en${\displaystyle B}$al invertir (cambiar el orden de) un conjunto de ciudades consecutivas. En este ejemplo,${\displaystyle A}$y${\displaystyle B}$Estos elementos se encuentran en diferentes "cuencas profundas" si el generador realiza solo intercambios de pares aleatorios; pero estarán en la misma cuenca si el generador realiza volteos de segmentos aleatorios.

La analogía física que se utiliza para justificar el recocido simulado supone que la velocidad de enfriamiento es lo suficientemente baja como para que la distribución de probabilidad del estado actual se encuentre cerca del equilibrio termodinámico en todo momento. Desafortunadamente, el tiempo de relajación —el tiempo que hay que esperar para que se restablezca el equilibrio tras un cambio de temperatura— depende en gran medida de la "topografía" de la función de energía y de la temperatura actual. En el algoritmo de recocido simulado, el tiempo de relajación también depende del generador de candidatos, de una manera muy compleja. Cabe señalar que todos estos parámetros suelen proporcionarse como funciones de caja negra al algoritmo de recocido simulado. Por lo tanto, la velocidad de enfriamiento ideal no se puede determinar de antemano y debe ajustarse empíricamente para cada problema. Los algoritmos de recocido simulado adaptativos abordan este problema conectando el programa de enfriamiento con el progreso de la búsqueda. Otros enfoques adaptativos, como el Recocido Simulado Termodinámico ^{[ 17 ]} , ajustan automáticamente la temperatura en cada paso en función de la diferencia de energía entre los dos estados, de acuerdo con las leyes de la termodinámica.