Recocido simulado

Técnica de optimización probabilística y metaheurística

El recocido simulado se puede utilizar para resolver problemas combinatorios. En este caso, se aplica al problema del viajante de comercio para minimizar la longitud de una ruta que conecta los 125 puntos.

Problema del viajante de comercio en 3D para 120 puntos resuelto con recocido simulado.

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 de comercio , 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]

Descripción general

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.

Recocido simulado en busca de un máximo. El objetivo aquí es llegar al punto más alto. En este ejemplo, no es suficiente utilizar un algoritmo simple de ascenso de colinas , ya que hay muchos máximos locales . Al enfriar la temperatura lentamente se encuentra el máximo global.

La iteración básica

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.

Los vecinos de un estado

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.

Probabilidades de aceptación

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. ${\displaystyle s}$ ${\displaystyle s_{\mathrm {new} }}$ ${\displaystyle P(e,e_{\mathrm {new} },T)}$ ${\displaystyle e=E(s)}$ ${\displaystyle e_{\mathrm {new} }=E(s_{\mathrm {new} })}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle e_{\mathrm {new} }}$ ${\displaystyle e}$

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. ${\displaystyle T}$ ${\displaystyle P(e,e_{\mathrm {new} },T)}$ ${\displaystyle e_{\mathrm {new} }>e}$ ${\displaystyle T}$ ${\displaystyle T=0}$

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. ${\displaystyle P(e,e_{\mathrm {new} },T)}$ ${\displaystyle e_{\mathrm {new} }<e}$

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. ${\displaystyle P}$ ${\displaystyle e_{\mathrm {new} }-e}$

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. ${\displaystyle T}$ ${\displaystyle s}$ ${\displaystyle T}$ ${\displaystyle s}$ ${\displaystyle T}$

El programa de recocido

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 de modo de minimizar una determinada función de energía potencial , que hace 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), que produjeron resultados similares a los de los sólidos amorfos y cristalinos , respectivamente.

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 . ${\displaystyle T}$ ${\displaystyle T=0}$

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]

Pseudocódigo

El siguiente pseudocódigo presenta la heurística de recocido simulado como se describió anteriormente. Comienza desde un estado s ₀ 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.

• Sea s = s ₀
• Para k = 0 hasta k _máx. (exclusivo):
  • T ← temperatura( 1 - (k+ 1 ) / k _máx )
  • Elige un vecino al azar, s _nuevo ← vecino( s )
  • Si P ( E ( s ), E ( s _nuevo ), T ) ≥ aleatorio(0, 1) :
    • s ← s _nuevo
• Salida: el estado final s

Selección de los parámetros

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 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.

Vecino suficientemente cercano

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 . ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$ ${\displaystyle n-1}$

Probabilidades de transición

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). ${\displaystyle (s,s')}$ ${\displaystyle s'}$ ${\displaystyle s}$temperature()neighbor ()P() ${\displaystyle P(e,e',T)}$

Probabilidades de aceptación

La especificación de neighbour(), P()y temperature()es parcialmente redundante. En la práctica, es habitual 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. ${\displaystyle P(e,e',T)}$ ${\displaystyle e'<e}$ ${\displaystyle \exp(-(e'-e)/T)}$neighbor () ${\displaystyle T}$

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]

Generación eficiente de candidatos

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. ${\displaystyle s'}$

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 ). ${\displaystyle n-1}$ ${\displaystyle n(n-1)/2}$

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 . ${\displaystyle s'}$ ${\displaystyle P(E(s),E(s'),T)}$ ${\displaystyle P}$ ${\displaystyle E(s')-E(s)}$ ${\displaystyle T}$neighbor () ${\displaystyle T}$

Evitar barreras

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. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Programa de enfriamiento

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.

Reinicios

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 sy 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.esbestebest

Métodos relacionados

• Los algoritmos de interacción Metropolis-Hasting (también conocidos como Monte Carlo secuencial ^[17] ) combinan movimientos de recocido simulados con una aceptación-rechazo de los individuos mejor adaptados equipados con un mecanismo de reciclaje interactivo.
• El recocido cuántico utiliza "fluctuaciones cuánticas" en lugar de fluctuaciones térmicas para atravesar barreras altas pero delgadas en la función objetivo.
• La tunelización estocástica intenta superar la creciente dificultad que tienen las simulaciones de recocido para escapar de los mínimos locales a medida que la temperatura disminuye, mediante la "tunelización" a través de barreras.
• La búsqueda tabú normalmente se mueve hacia estados vecinos de menor energía, pero tomará movimientos ascendentes cuando se encuentre atrapada en un mínimo local; y evita ciclos manteniendo una "lista tabú" de soluciones ya vistas.
• La evolución de doble fase es una familia de algoritmos y procesos (a los que pertenece el recocido simulado) que median entre la búsqueda local y global explotando los cambios de fase en el espacio de búsqueda.
• La optimización de búsqueda reactiva se centra en combinar el aprendizaje automático con la optimización, añadiendo un bucle de retroalimentación interno para autoajustar los parámetros libres de un algoritmo a las características del problema, de la instancia y de la situación local alrededor de la solución actual.
• Los algoritmos genéticos mantienen un conjunto de soluciones en lugar de una sola. Las nuevas soluciones candidatas se generan no sólo por "mutación" (como en el caso de los algoritmos genéticos), sino también por "recombinación" de dos soluciones del conjunto. Se utilizan criterios probabilísticos, similares a los utilizados en los algoritmos genéticos, para seleccionar las soluciones candidatas a mutación o combinación y para descartar las soluciones sobrantes del conjunto.
• Los algoritmos meméticos buscan soluciones empleando un conjunto de agentes que cooperan y compiten en el proceso; a veces las estrategias de los agentes implican procedimientos de recocido simulados para obtener soluciones de alta calidad antes de recombinarlas. ^[18] El recocido también se ha sugerido como un mecanismo para aumentar la diversidad de la búsqueda. ^[19]
• La optimización graduada "suaviza" de forma digresiva la función de destino mientras se optimiza.
• La optimización de colonias de hormigas (ACO) utiliza muchas hormigas (o agentes) para recorrer el espacio de la solución y encontrar áreas localmente productivas.
• El método de entropía cruzada (CE) genera soluciones candidatas a través de una distribución de probabilidad parametrizada. Los parámetros se actualizan mediante la minimización de la entropía cruzada, de modo de generar mejores muestras en la siguiente iteración.
• La búsqueda de armonía imita a los músicos en la improvisación, donde cada músico toca una nota para encontrar la mejor armonía juntos.
• La optimización estocástica es un conjunto general de métodos que incluye el recocido simulado y muchos otros enfoques.
• La optimización de enjambre de partículas es un algoritmo modelado en inteligencia de enjambre que encuentra una solución a un problema de optimización en un espacio de búsqueda, o modela y predice el comportamiento social en presencia de objetivos.
• El algoritmo corredor-raíz (RRA) es un algoritmo de optimización metaheurística para resolver problemas unimodales y multimodales inspirado en los corredores y raíces de las plantas en la naturaleza.
• Algoritmo de gotas de agua inteligentes (IWD) que imita el comportamiento de las gotas de agua naturales para resolver problemas de optimización
• El templado paralelo es una simulación de copias del modelo a diferentes temperaturas (o hamiltonianos ) para superar las barreras potenciales.
• Se han utilizado algoritmos de recocido simulado multiobjetivo en la optimización multiobjetivo . ^[20]

Véase también

• Recocido simulado adaptativo
• Colocación automática de etiquetas
• Optimización combinatoria
• Evolución de dos fases
• Recortes de gráficos en visión artificial
• Algoritmo inteligente de gotas de agua
• Cadena de Markov
• Dinámica molecular
• Optimización multidisciplinaria
• Optimización de enjambre de partículas
• Lugar y ruta
• Recocido cuántico
• Problema del viajante de comercio

Referencias

1. "¿Qué es el recocido simulado?". www.cs.cmu.edu . Consultado el 13 de mayo de 2023 .
2. Pincus, Martin (noviembre-diciembre de 1970). "Un método de Montecarlo para la solución aproximada de ciertos tipos de problemas de optimización restringida". Revista de la Sociedad de Investigación de Operaciones de Estados Unidos . 18 (6): 967–1235. doi :10.1287/opre.18.6.1225.
3. Khachaturyan, A.: Semenovskaya, S.: Vainshtein B., Armen (1979). "Enfoque estadístico-termodinámico para la determinación de las fases de amplitud de la estructura". Cristalografía de física soviética . 24 (5): 519–524.{{cite journal}}: CS1 maint: multiple names: authors list (link)
4. Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1981). "El enfoque termodinámico para el análisis de la estructura de los cristales". Acta Crystallographica . A37 (5): 742–754. Código Bibliográfico :1981AcCrA..37..742K. doi :10.1107/S0567739481001630.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Laarhoven, camioneta PJM (Peter JM) (1987). Recocido simulado: teoría y aplicaciones. Aarts, EHL (Emile HL). Dordrecht: D. Reidel. ISBN 90-277-2513-6.OCLC 15548651  .
6. Kirkpatrick, S.; Gelatt Jr, CD; Vecchi, MP (1983). "Optimización mediante recocido simulado". Science . 220 (4598): 671–680. Bibcode :1983Sci...220..671K. CiteSeerX 10.1.1.123.7607 . doi :10.1126/science.220.4598.671. JSTOR  1690046. PMID  17813860. S2CID  205939. 
7. Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1979). "Enfoque estadístico-termodinámico para la determinación de las fases de amplitud de la estructura". Sov.Phys. Cristalografía . 24 (5): 519–524.
8. Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1981). "El enfoque termodinámico para el análisis de la estructura de los cristales". Acta Crystallographica . 37 (A37): 742–754. Código Bibliográfico :1981AcCrA..37..742K. doi :10.1107/S0567739481001630.
9. Černý, V. (1985). "Enfoque termodinámico para el problema del viajante de comercio: Un algoritmo de simulación eficiente". Revista de teoría y aplicaciones de optimización . 45 : 41–51. doi :10.1007/BF00940812. S2CID  122729427.
10. Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1953). "Cálculos de ecuaciones de estado mediante máquinas de computación rápida". The Journal of Chemical Physics . 21 (6): 1087. Bibcode :1953JChPh..21.1087M. doi :10.1063/1.1699114. OSTI  4390578. S2CID  1046577.
11. Granville, V.; Krivanek, M.; Rasson, J.-P. (1994). "Recocido simulado: una prueba de convergencia". IEEE Transactions on Pattern Analysis and Machine Intelligence . 16 (6): 652–656. doi :10.1109/34.295910.
12. Nolte, Andreas; Schrader, Rainer (1997), "Una nota sobre el comportamiento en tiempo finito del recocido simulado", Operations Research Proceedings 1996 , vol. 1996, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 175–180, doi :10.1007/978-3-642-60744-8_32, ISBN 978-3-540-62630-5, consultado el 6 de febrero de 2023
13. Moscato, P.; Fontanari, JF (1990), "Actualización estocástica versus determinista en recocido simulado", Physics Letters A , 146 (4): 204–208, Bibcode :1990PhLA..146..204M, doi :10.1016/0375-9601(90)90166-L
14. Dueck, G.; Scheuer, T. (1990), "Aceptación de umbral: Un algoritmo de optimización de propósito general que parece superior al recocido simulado", Journal of Computational Physics , 90 (1): 161–175, Bibcode :1990JCoPh..90..161D, doi :10.1016/0021-9991(90)90201-B, ISSN  0021-9991
15. Franz, A.; Hoffmann, KH; Salamon, P (2001), "La mejor estrategia óptima para encontrar estados fundamentales", Physical Review Letters , 86 (3): 5219–5222, doi :10.1103/PhysRevLett.86.5219, PMID  11384462
16. De Vicente, Juan; Lanchares, Juan; Hermida, Román (2003). "Colocación mediante recocido termodinámico simulado". Letras de Física A. 317 (5–6): 415–423. Código bibliográfico : 2003PhLA..317..415D. doi :10.1016/j.physleta.2003.08.070.
17. Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2006). "Muestreadores secuenciales de Monte Carlo". Revista de la Royal Statistical Society, Serie B . 68 (3): 411–436. arXiv : cond-mat/0212648 . doi :10.1111/j.1467-9868.2006.00553.x. S2CID  12074789.
18. Moscato, Pablo (junio de 1993). "Introducción a los enfoques poblacionales para la optimización y las funciones objetivo jerárquicas: una discusión sobre el papel de la búsqueda tabú". Anales de investigación de operaciones . 41 (2): 85–121. doi :10.1007/BF02022564. S2CID  35382644.
19. Moscato, P. (1989). "Sobre evolución, búsqueda, optimización, algoritmos genéticos y artes marciales: hacia algoritmos meméticos". Programa de computación concurrente de Caltech (informe 826).
20. Deb, Bandyopadhyay (junio de 2008). "Un algoritmo de optimización multiobjetivo basado en recocido simulado: AMOSA". IEEE Transactions on Evolutionary Computation . 12 (3): 269–283. doi :10.1109/TEVC.2007.900837. S2CID  12107321.

Lectura adicional

• A. Das y BK Chakrabarti (Eds.), Recocido cuántico y métodos de optimización relacionados, Nota de clase en Física, vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). "Paisajes de aptitud correlacionados y no correlacionados y cómo diferenciarlos". Cibernética biológica . 63 (5): 325–336. doi :10.1007/BF00202749. S2CID  851736.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.12. Métodos de recocido simulado". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado desde el original el 11-08-2011 . Consultado el 13-08-2011 .
• Strobl, MAR; Barker, D. (2016). "Sobre transiciones de fase de recocido simulado en la reconstrucción de la filogenia". Filogenética molecular y evolución . 101 : 46–55. Bibcode :2016MolPE.101...46S. doi :10.1016/j.ympev.2016.05.001. PMC  4912009 . PMID  27150349.
• V.Vassilev, A.Prahova: "El uso del recocido simulado en el control de sistemas de fabricación flexibles", Revista internacional INFORMATION THEORIES & APPLICATIONS, VOLUMEN 6/1999

Enlaces externos

• Recocido simulado Una aplicación de Javascript que le permite experimentar con el recocido simulado. Código fuente incluido.
• "Algoritmo general de recocido simulado" Archivado el 23 de septiembre de 2008 en Wayback Machine. Un programa MATLAB de código abierto para ejercicios generales de recocido simulado.
• Lección autoguiada sobre recocido simulado Un proyecto de Wikiversidad.
• Google en superposición de usar, no usar computadora cuántica Ars Technica analiza la posibilidad de que la computadora D-Wave que utiliza Google pueda, de hecho, ser un eficiente coprocesador de recocido simulado.
• [1] Un algoritmo de optimización multiobjetivo basado en recocido simulado: AMOSA.