Este artículo necesita citas adicionales para su verificación . ( diciembre de 2009 ) |
El recocido simulado ( SA ) es una técnica probabilística para aproximar el óptimo global de una función dada . Específicamente, es una metaheurística para aproximar la optimización global en un gran espacio de búsqueda para un problema de optimización . Para un gran número de óptimos locales, SA puede encontrar el óptimo global. [1] A menudo se utiliza cuando el espacio de búsqueda es discreto (por ejemplo, el problema del viajante , el problema de satisfacibilidad booleana , la predicción de la estructura de proteínas y la programación de talleres ). Para problemas en los que encontrar un óptimo global aproximado es más importante que encontrar un óptimo local preciso en una cantidad fija de tiempo, el recocido simulado puede ser preferible a algoritmos exactos como el descenso de gradiente o la ramificación y acotación .
El nombre del algoritmo proviene del recocido en metalurgia , una técnica que implica calentar y enfriar de forma controlada un material para alterar sus propiedades físicas . Ambos son atributos del material que dependen de su energía libre termodinámica . Calentar y enfriar el material afecta tanto a la temperatura como a la energía libre termodinámica o energía de Gibbs . El recocido simulado se puede utilizar para problemas de optimización computacional muy difíciles en los que los algoritmos exactos fallan; aunque generalmente logra una solución aproximada al mínimo global, podría ser suficiente para muchos problemas prácticos.
Los problemas que resuelve SA se formulan actualmente mediante una función objetivo de muchas variables, sujeta a varias restricciones matemáticas . En la práctica, la restricción puede penalizarse como parte de la función objetivo.
Técnicas similares se han introducido de forma independiente en varias ocasiones, incluyendo Pincus (1970), [2] Khachaturyan et al (1979, [3] 1981 [4] ), Kirkpatrick, Gelatt y Vecchi (1983), y Cerny (1985). [5] En 1983, este enfoque fue utilizado por Kirkpatrick, Gelatt Jr., Vecchi, [6] para una solución del problema del viajante de comercio . También propusieron su nombre actual, recocido simulado.
Esta noción de enfriamiento lento implementada en el algoritmo de recocido simulado se interpreta como una disminución lenta en la probabilidad de aceptar peores soluciones a medida que se explora el espacio de soluciones. Aceptar peores soluciones permite una búsqueda más extensa de la solución óptima global. En general, los algoritmos de recocido simulado funcionan de la siguiente manera. La temperatura disminuye progresivamente desde un valor positivo inicial hasta cero. En cada paso de tiempo, el algoritmo selecciona aleatoriamente una solución cercana a la actual, mide su calidad y se mueve hacia ella de acuerdo con las probabilidades dependientes de la temperatura de seleccionar mejores o peores soluciones, que durante la búsqueda permanecen respectivamente en 1 (o positivo) y disminuyen hacia cero.
La simulación se puede realizar ya sea mediante una solución de ecuaciones cinéticas para funciones de densidad de probabilidad , [7] [8] o utilizando un método de muestreo estocástico . [6] [9] El método es una adaptación del algoritmo Metropolis-Hastings , un método de Monte Carlo para generar estados de muestra de un sistema termodinámico, publicado por N. Metropolis et al. en 1953. [10]
El estado s de algunos sistemas físicos y la función E ( s ) que se desea minimizar es análoga a la energía interna del sistema en ese estado. El objetivo es llevar el sistema, desde un estado inicial arbitrario , a un estado con la mínima energía posible.
En cada paso, la heurística de recocido simulado considera algún estado vecino s* del estado actual s y decide de manera probabilística entre mover el sistema al estado s* o permanecer en el estado s . Estas probabilidades finalmente llevan al sistema a moverse a estados de menor energía. Normalmente, este paso se repite hasta que el sistema alcanza un estado que es lo suficientemente bueno para la aplicación o hasta que se agota un presupuesto computacional determinado.
La optimización de una solución implica evaluar los vecinos de un estado del problema, que son nuevos estados producidos mediante la alteración conservadora de un estado dado. Por ejemplo, en el problema del viajante, cada estado se define típicamente como una permutación de las ciudades que se visitarán, y los vecinos de cualquier estado son el conjunto de permutaciones producidas al intercambiar dos de estas ciudades. La forma bien definida en que se alteran los estados para producir estados vecinos se denomina "movimiento", y diferentes movimientos dan lugar a diferentes conjuntos de estados vecinos. Estos movimientos suelen dar lugar a alteraciones mínimas del último estado, en un intento de mejorar progresivamente la solución mediante la mejora iterativa de sus partes (como las conexiones de las ciudades en el problema del viajante). Es incluso mejor invertir el orden de un intervalo de ciudades. Este es un movimiento más pequeño, ya que el intercambio de dos ciudades se puede lograr invirtiendo dos veces un intervalo.
Las heurísticas simples como la escalada de colinas , que se mueven encontrando un vecino mejor tras otro y se detienen cuando han llegado a una solución que no tiene vecinos que sean mejores soluciones, no pueden garantizar que conduzcan a ninguna de las mejores soluciones existentes: su resultado puede ser fácilmente solo 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 como una forma de explorar el espacio de soluciones y, aunque prefieren mejores vecinos, también aceptan peores vecinos para evitar quedarse estancadas en óptimos locales; pueden encontrar el óptimo global si se ejecutan durante un tiempo lo suficientemente largo.
La probabilidad de realizar la transición del estado actual a un nuevo estado candidato se especifica mediante una función de probabilidad de aceptación , que depende de las energías y de los dos estados, y de un parámetro global variable en el tiempo llamado temperatura . Los estados con una energía menor son mejores que aquellos con una energía mayor. La función de probabilidad debe ser positiva incluso cuando es mayor que . Esta característica evita que el método se quede estancado en un mínimo local que sea peor que el global.
Cuando tiende a cero, la probabilidad debe tender a cero si y a un valor positivo en caso contrario. Para valores suficientemente pequeños de , el sistema favorecerá cada vez más los movimientos que vayan "cuesta abajo" (es decir, hacia valores de energía más bajos) y evitará los que vayan "cuesta arriba". Con el procedimiento se reduce al algoritmo voraz , que solo realiza las transiciones cuesta abajo.
En la descripción original del recocido simulado, la probabilidad era igual a 1 cuando —es decir, el procedimiento siempre se movía cuesta abajo cuando encontraba una manera de hacerlo, independientemente de la temperatura. Muchas descripciones e implementaciones del recocido simulado aún toman 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.
La función suele elegirse de modo que la probabilidad de aceptar un movimiento disminuya cuando la diferencia aumenta, es decir, es más probable que se produzcan pequeños movimientos ascendentes que grandes. Sin embargo, este requisito no es estrictamente necesario, siempre que se cumplan los requisitos anteriores.
Dadas estas propiedades, la temperatura juega un papel crucial en el control de la evolución del estado del sistema con respecto a su sensibilidad a las variaciones de las energías del sistema. Para ser precisos, para un gran , la evolución de es sensible a variaciones de energía más gruesas, mientras que es sensible a variaciones de energía más finas cuando es pequeño.
El nombre y la inspiración del algoritmo exigen que se incorpore en las características operativas del algoritmo una característica interesante relacionada con la variación de la temperatura. Esto requiere una reducción gradual de la temperatura a medida que avanza la simulación. El algoritmo comienza inicialmente con un valor alto (o infinito) y luego se reduce en cada paso siguiendo un programa de recocido , que puede ser especificado por el usuario, pero debe finalizar hacia el final del presupuesto de tiempo asignado. De esta manera, se espera que el sistema se desplace inicialmente hacia una amplia región del espacio de búsqueda que contenga buenas soluciones, ignorando pequeñas características de la función de energía; luego se desplace hacia regiones de baja energía que se vuelven cada vez más estrechas, y finalmente se mueva cuesta abajo de acuerdo con la heurística de 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 acerca a 1 a medida que se extiende el programa de recocido. [11] Este resultado teórico, sin embargo, 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 . [12]
El siguiente pseudocódigo presenta la heurística de recocido simulado como se describió anteriormente. Comienza desde un estado s 0 y continúa hasta que se han realizado un máximo de k pasos máximos . En el proceso, la llamada neighbor( s ) debe generar un vecino elegido aleatoriamente de un estado dado s ; la llamada random(0, 1) debe elegir y devolver un valor en el rango [0, 1] , de manera uniforme y aleatoria . El cronograma de recocido está definido por la llamada temperature( r ) , que debe producir la temperatura a utilizar, dada la fracción r del presupuesto de tiempo que se ha gastado hasta ahora.
Para aplicar el método de recocido simulado a un problema específico, se deben especificar los siguientes parámetros: el espacio de estados, la función de energía (objetivo) E()
, el procedimiento del generador de candidatos neighbor ()
, la función de probabilidad de aceptación P()
y el programa de recocido temperature()
Y la temperatura inicial init_temp
. Estas opciones pueden tener un impacto significativo en la efectividad del método. Desafortunadamente, no hay opciones de estos parámetros que sean buenas para todos los problemas, y no hay una forma general de encontrar las mejores opciones para un problema determinado. Las siguientes secciones brindan algunas pautas generales.
El recocido simulado puede modelarse como un paseo aleatorio en un grafo de búsqueda, cuyos vértices son todos los estados posibles y cuyos bordes son los movimientos candidatos. Un requisito esencial para la neighbor ()
función es que debe proporcionar un camino suficientemente corto en este grafo desde el estado inicial hasta 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 trillones) de estados; sin embargo, el número de vecinos de cada vértice es de bordes (viniendo de n, elija 20), y el diámetro del grafo es .
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 opciones de diseño realizadas en la implementación del algoritmo. Para cada borde del gráfico de búsqueda, la probabilidad de transición se define como la probabilidad de que el algoritmo de recocido simulado se mueva al estado cuando su estado actual es . Esta probabilidad depende de la temperatura actual especificada por , del orden en el que la función genera los movimientos de los candidatos y de la función de probabilidad de aceptación . (Tenga en cuenta que la probabilidad de transición no es simplemente , porque los candidatos se prueban en serie).temperature()
neighbor ()
P()
La especificación de neighbour()
, P()
, y temperature()
es parcialmente redundante. En la práctica, es común utilizar 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 se definió como 1 si , y 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 en que T=1 y la distribución propuesta de Metropolis-Hastings es simétrica. Sin embargo, esta probabilidad de aceptación se utiliza a menudo para el recocido simulado incluso cuando la función, que es análoga a la distribución propuesta 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 de largo plazo de los estados a una temperatura constante no necesita guardar ninguna semejanza con la distribución de equilibrio termodinámico sobre los estados de ese sistema físico, a cualquier temperatura. Sin embargo, la mayoría de las descripciones del recocido simulado suponen la función de aceptación original, que probablemente esté codificada en muchas implementaciones de SA.neighbor ()
En 1990, Moscato y Fontanari, [13] e independientemente Dueck y Scheuer, [14] 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 concluyen, al observar la analogía de la curva de "calor específico" del recocido de "actualización de umbral" que se origina 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 funciones 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 posteriormente se popularizó 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 gran clase de algoritmos que simulan un recorrido aleatorio por el panorama costo/energía. [15]
Al elegir el generador de candidatos neighbor ()
, se debe tener en cuenta que después de unas cuantas 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 es probable que la energía del estado de destino sea similar a la del estado actual. Esta heurística (que es el principio principal del algoritmo Metropolis-Hastings ) tiende a excluir tanto los movimientos candidatos muy buenos como los muy malos ; sin embargo, los primeros suelen ser mucho menos comunes que los segundos, por lo que la heurística suele ser bastante eficaz.
En el problema del viajante de comercio mencionado anteriormente, por ejemplo, se espera que el intercambio de dos ciudades consecutivas en un viaje de baja energía tenga un efecto modesto en su energía (duración); mientras que el intercambio de dos ciudades arbitrarias tiene muchas más probabilidades de aumentar su duración que de disminuirla. Por lo tanto, se espera que el generador de vecinos con intercambios consecutivos tenga un mejor desempeño que el de intercambios arbitrarios, aunque este último podría proporcionar un camino algo más corto hacia el óptimo (con intercambios, en lugar de ).
Una formulación más precisa de la heurística es que se deben probar los primeros estados candidatos para los que es grande. Para la función de aceptación "estándar" anterior, significa que es del orden de o menor. Por lo tanto, en el ejemplo del viajante de comercio anterior, se podría utilizar una función que intercambie dos ciudades al azar, donde la probabilidad de elegir un par de ciudades se desvanece a medida que su distancia aumenta más allá de .neighbor ()
Al elegir el generador candidato, neighbor ()
también se debe intentar reducir el número de mínimos locales "profundos", es decir, estados (o conjuntos de estados conectados) que tienen una energía mucho menor que todos sus estados vecinos. Estas " cuencas de captación cerradas " de la función de energía pueden atrapar el algoritmo de recocido simulado con una alta probabilidad (aproximadamente proporcional al número de estados en la cuenca) y durante un tiempo muy prolongado (aproximadamente exponencial en función de la diferencia de energía entre los estados circundantes y el fondo de la cuenca).
Como regla, es imposible diseñar un generador de candidatos que satisfaga este objetivo y también priorice candidatos con energía similar. Por otra parte, a menudo se puede mejorar enormemente la eficiencia del recocido simulado mediante cambios relativamente simples en el generador. En el problema del viajante de comercio, por ejemplo, no es difícil exhibir dos recorridos , , con longitudes casi iguales, de modo que (1) sea óptimo, (2) cada secuencia de intercambios de pares de ciudades que se convierta en pase por recorridos que sean mucho más largos que ambos, y (3) se pueda transformar en invirtiendo (invirtiendo el orden de) un conjunto de ciudades consecutivas. En este ejemplo, y se encuentran en diferentes "cuencas profundas" si el generador solo realiza intercambios de pares aleatorios; pero estarán en la misma cuenca si el generador realiza cambios aleatorios de segmentos.
La analogía física que se utiliza para justificar el recocido simulado supone que la tasa de enfriamiento es lo suficientemente baja como para que la distribución de probabilidad del estado actual esté cerca del equilibrio termodinámico en todo momento. Desafortunadamente, el tiempo de relajación (el tiempo que se debe esperar para que se restablezca el equilibrio después de 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 candidato, de una manera muy complicada. Tenga en cuenta que todos estos parámetros suelen proporcionarse como funciones de caja negra al algoritmo de recocido simulado. Por lo tanto, la tasa 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 [16] , 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.
A veces es mejor volver a una solución que era significativamente mejor en lugar de pasar siempre del estado actual. Este proceso se llama reinicio del recocido simulado. Para ello, fijamos y s
y tal vez reiniciamos el programa de recocido. La decisión de reiniciar podría basarse en varios criterios. Entre ellos, destacan el reinicio basado en un número fijo de pasos, en función de si la energía actual es demasiado alta en comparación con la mejor energía obtenida hasta el momento, el reinicio aleatorio, etc.e
sbest
ebest
{{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link)