Recocido simulado

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

El recocido simulado se puede utilizar para resolver problemas combinatorios. Aquí se aplica al problema del viajante para minimizar la longitud de una ruta que conecta los 125 puntos.

Problema del viajante 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 los óptimos globales. ^[1] A menudo se utiliza cuando el espacio de búsqueda es discreto (por ejemplo, el problema del viajante , el problema booleano de satisfacibilidad , la predicción de la estructura de proteínas y la programación de trabajos ). Para problemas en los que encontrar un óptimo global aproximado es más importante que encontrar un óptimo local preciso en un período de tiempo fijo, el recocido simulado puede ser preferible a algoritmos exactos como el descenso de gradiente o la bifurcación y el límite .

El nombre del algoritmo proviene del recocido en metalurgia , una técnica que implica calentar y enfriar controladamente 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 fallan los algoritmos exactos; aunque normalmente logra una solución aproximada al mínimo global, podría ser suficiente para muchos problemas prácticos.

Los problemas resueltos por SA actualmente están formulados 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.

Se han introducido técnicas similares de forma independiente en varias ocasiones, entre ellas Pincus (1970), ^[2] Khachaturyan et al (1979, ^[3] 1981 ^[4] ), Kirkpatrick, Gelatt y Vecchi (1983) y Cerny (1985). ^{[5] En 1983, Kirkpatrick, Gelatt Jr., Vecchi, [6]} utilizaron este enfoque para una solución al problema del viajante . 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 lenta disminución 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 amplia de la solución óptima global. En general, los algoritmos de recocido simulados funcionan de la siguiente manera. La temperatura disminuye progresivamente desde un valor inicial positivo 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 soluciones mejores o peores, que durante la búsqueda permanecen respectivamente en 1 (o positivo). ) y disminuye hacia cero.

La simulación se puede realizar 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 debe 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 buscando 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 . Enfriando lentamente la temperatura 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 probabilísticamente entre mover el sistema al estado s* o permanecer en el estado s . Estas probabilidades finalmente llevan al sistema a pasar a estados de menor energía. Normalmente, este paso se repite hasta que el sistema alcanza un estado que sea lo suficientemente bueno para la aplicación, o hasta que se haya agotado un presupuesto de cálculo 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 determinado. Por ejemplo, en el problema del viajante, cada estado se define típicamente como una permutación de las ciudades que se van a visitar, y los vecinos de cualquier estado son el conjunto de permutaciones producidas al intercambiar dos de estas ciudades. La forma bien definida en la que se modifican los estados para producir estados vecinos se denomina "movimiento", y diferentes movimientos dan diferentes conjuntos de estados vecinos. Estos movimientos generalmente resultan en 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 la ciudad en el problema del viajante).

Las heurísticas simples como la escalada de colinas , que se mueven buscando un mejor vecino tras otro y se detienen cuando han alcanzado 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 fácilmente ser justo. 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 la solución y, aunque prefieren mejores vecinos, también aceptan peores vecinos para evitar quedarse atrapados en óptimos locales; pueden encontrar el óptimo global si se ejecutan durante un período de tiempo suficiente.

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 de los dos estados, y de un parámetro global que varía en el tiempo llamado temperatura . Los estados con menor energía son mejores que aquellos con mayor energía. La función de probabilidad debe ser positiva incluso cuando sea mayor que . Esta característica evita que el método se quede atascado en un mínimo local 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 van "cuesta abajo" (es decir, hacia valores de energía más bajos) y evitará aquellos que van "cuesta arriba". Con el procedimiento se reduce al algoritmo codicioso , que sólo 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 iba cuesta abajo cuando encontraba una manera de hacerlo, independientemente de la temperatura. Muchas descripciones e implementaciones de recocido simulado todavía 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 generalmente se elige de modo que la probabilidad de aceptar un movimiento disminuya cuando la diferencia aumenta; es decir, los movimientos pequeños cuesta arriba son más probables que los 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 energías del sistema. Para ser precisos, para un tamaño grande , 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ña. ${\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 desempeño del recocido simulado. El problema es reorganizar los píxeles de una imagen para minimizar una determinada función de energía potencial , que hace que 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 los sólidos amorfos y cristalinos , respectivamente.

El nombre y la inspiración del algoritmo exigen que se incluya una característica interesante relacionada con la variación de temperatura en las características operativas del algoritmo. 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 disminuye 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 región amplia del espacio de búsqueda que contiene buenas soluciones, ignorando pequeñas características de la función de energía; luego se desplaza hacia regiones de baja energía que se vuelven cada vez más estrechas y, finalmente, se mueve 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 garantizar una probabilidad significativa de éxito generalmente excederá el tiempo requerido para una búsqueda completa del espacio de solución . ^[12]

Pseudocódigo

El siguiente pseudocódigo presenta la heurística de recocido simulada como se describe anteriormente. Comienza desde un estado s ₀ y continúa hasta que se hayan dado un máximo de k _max pasos. En el proceso, los vecinos de llamada deben generar un vecino elegido aleatoriamente de un estado dado s ; la llamada random(0, 1) debe seleccionar y devolver un valor en el rango [0, 1] , uniformemente aleatorio . El programa de recocido está definido por la temperatura de llamada ( r ) , que debería producir la temperatura a utilizar, dada la fracción r del presupuesto de tiempo que se ha gastado hasta el momento.

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

Seleccionar 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 candidato neighbor (), la función de probabilidad de aceptación P()y el programa de recocido temperature()Y la temperatura inicial init_temp. Estas elecciones pueden tener un impacto significativo en la eficacia del método. Desafortunadamente, no existen opciones de estos parámetros que sean buenas para todos los problemas y no existe una forma general de encontrar las mejores opciones para un problema determinado. Las siguientes secciones ofrecen algunas pautas generales.

Vecino suficientemente cercano

El recocido simulado se puede modelar como un paseo aleatorio en un gráfico 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 gráfico desde el estado inicial hasta cualquier estado que pueda ser el óptimo global: el diámetro del gráfico de búsqueda debe ser pequeño. En el ejemplo anterior del viajante de comercio, 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 son aristas (viniendo de n, elija 20) y el diámetro de la gráfica 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 resultar útil considerar las probabilidades de transición que resultan de las diversas elecciones 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 pase al estado cuando su estado actual sea . Esta probabilidad depende de la temperatura actual especificada por , del orden en que la función genera los movimientos 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 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 estaba superficialmente justificada 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 propuesta de Metropolis-Hastings sea 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 estados a largo plazo a una temperatura constante no necesita tener ningún parecido con la distribución de equilibrio termodinámico sobre los estados de ese sistema. sistema físico, a cualquier temperatura. Sin embargo, la mayoría de las descripciones de recocido simulado asumen 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 base en la regla de aceptación probabilística) podría acelerar el proceso de optimización sin impactar en la calidad final. . Moscato y Fontanari concluyen al observar el análogo de la curva de "calor específico" del recocido de "actualización de umbral" procedente de 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 temperaturas cercanas". -mínimos óptimos". En cambio, propusieron que "la suavización del panorama de la función de costos 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 gran clase de algoritmos que simulan un paseo aleatorio en el panorama costo/energía. ^[15]

Generación eficiente de candidatos

Al elegir el generador candidato neighbor (), se debe considerar que después de algunas iteraciones del algoritmo de recocido simulado, se espera que el estado actual tenga mucha menos energía 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 probablemente sea similar a la del estado actual. Esta heurística (que es el principio fundamental del algoritmo de Metropolis-Hastings ) tiende a excluir tanto movimientos candidatos muy buenos como 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 anterior, por ejemplo, se espera que el intercambio de dos ciudades consecutivas en un recorrido de baja energía tenga un efecto modesto en su energía (duración); 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 vecino 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 intercambios, en lugar de ). ${\displaystyle n-1}$ ${\displaystyle n(n-1)/2}$

Una afirmación más precisa de la heurística es que se deben probar los primeros estados candidatos para los cuales sea grande. Para la función de aceptación "estándar" anterior, significa que es del orden de o menos. Por lo tanto, en el ejemplo anterior del vendedor ambulante, se podría usar una función que intercambie dos ciudades aleatorias, donde la probabilidad de elegir un par de ciudades desaparece 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}$

Evitación de barreras

Al elegir el generador candidato neighbor ()también se debe tratar de reducir el número de mínimos locales "profundos": estados (o conjuntos de estados conectados) que tienen mucha menos energía 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 largo (aproximadamente exponencial de la diferencia de energía entre los estados circundantes y el fondo de la cuenca).

Como regla general, es imposible diseñar un generador de candidatos que satisfaga este objetivo y también dé prioridad a 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 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 son mucho más largo que ambos, y (3) se puede transformar volteando (invirtiendo el orden de) un conjunto de ciudades consecutivas. En este ejemplo, y se encuentran en diferentes "cuencas profundas" si el generador realiza sólo intercambios de pares aleatorios; pero estarán en la misma cuenca si el generador realiza cambios de segmento aleatorios. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Horario de enfriamiento

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 esté 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 después de un cambio de temperatura— depende en gran medida de la "topografía" de la función energética 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 generalmente se proporcionan como funciones de caja negra para el 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 adaptativo abordan este problema conectando el programa de enfriamiento con el progreso de la búsqueda. Otros enfoques adaptativos, como el recocido termodinámico simulado, ^[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.

Se reinicia

A veces es mejor volver a una solución que era significativamente mejor que pasar siempre del estado actual. Este proceso se denomina reinicio del recocido simulado. Para hacer esto configuramos sy y equizás reiniciamos el programa de recocido. La decisión de reiniciar podría basarse en varios criterios. Entre ellos cabe destacar 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.sbestebest

Métodos relacionados

• Los algoritmos interactivos de 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 construcción de túneles estocásticos intenta superar la creciente dificultad que tienen los recorridos de recocido simulados para escapar de los mínimos locales a medida que la temperatura disminuye, mediante la construcción de túneles a través de barreras.
• La búsqueda tabú normalmente se mueve a estados vecinos de menor energía, pero tomará movimientos cuesta arriba cuando se encuentre estancada 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 la 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, agregando un bucle de retroalimentación interna para autoajustar los parámetros libres de un algoritmo a las características del problema, de la instancia y de la situación local en torno a 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 SA), sino también por "recombinación" de dos soluciones del grupo. Se utilizan criterios probabilísticos, similares a los utilizados en SA, para seleccionar los candidatos para mutación o combinación, y para descartar el exceso de soluciones 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 gradual "suaviza" degresivamente la función objetivo mientras se optimiza.
• La optimización de colonias de hormigas (ACO) utiliza muchas hormigas (o agentes) para atravesar el espacio de la solución y encontrar áreas productivas localmente.
• El método de entropía cruzada (CE) genera soluciones candidatas mediante una distribución de probabilidad parametrizada. Los parámetros se actualizan mediante la minimización de entropía cruzada, para 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 juntos la mejor armonía.
• La optimización estocástica es un conjunto general de métodos que incluye recocido simulado y muchos otros enfoques.
• La optimización de enjambre de partículas es un algoritmo modelado a partir de 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 de raíz de corredor (RRA) es un algoritmo de optimización metaheurístico para resolver problemas unimodales y multimodales inspirados en los corredores y raíces de las plantas en la naturaleza.
• Algoritmo inteligente de gotas de agua (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 de modelos a diferentes temperaturas (o hamiltonianos ) para superar las barreras potenciales.
• En la optimización multiobjetivo se han utilizado algoritmos de recocido simulado de múltiples objetivos . ^[20]

Ver también

• Recocido simulado adaptativo
• Colocación automática de etiquetas
• Optimización combinatoria
• Evolución de doble fase
• Recortes de gráficos en visión por computadora
• Algoritmo inteligente de gotas de agua.
• cadena de markov
• Dinámica molecular
• Optimización multidisciplinar
• Optimización de Enjambre de partículas
• Lugar y ruta
• recocido cuántico
• Problema del vendedor ambulante

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 Monte-Carlo para la solución aproximada de ciertos tipos de problemas de optimización restringida". Revista de la Sociedad de Investigación de Operaciones de América . 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". Física soviética, Cristalografía . 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 cristales". Acta Cristalográfica . 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, diputado (1983). "Optimización mediante recocido simulado". Ciencia . 220 (4598): 671–680. Código Bib : 1983 Ciencia... 220..671K. CiteSeerX 10.1.1.123.7607 . doi : 10.1126/ciencia.220.4598.671. JSTOR  1690046. PMID  17813860. S2CID  205939. 
7. Khachaturyan, A.; Semenovskaya, S.; Vainstein, 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 cristales". Acta Cristalográfica . 37 (A37): 742–754. Código bibliográfico : 1981AcCrA..37..742K. doi :10.1107/S0567739481001630.
9. Černý, V. (1985). "Aproximación termodinámica al problema del viajante: 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. Metrópolis, Nicolás; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Cajero, Augusta H.; Cajero, Edward (1953). "Cálculos de ecuaciones de estado mediante máquinas de computación rápida". La Revista de Física Química . 21 (6): 1087. Código bibliográfico : 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". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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, recuperado 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). "Una introducción a los enfoques de población 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". Transacciones IEEE sobre computación evolutiva . 12 (3): 269–283. doi :10.1109/TEVC.2007.900837. S2CID  12107321.

Otras lecturas

• A. Das y BK Chakrabarti (Eds.), Recocido cuántico y métodos de optimización relacionados ^{[ enlace muerto permanente ]} , Lecture Note in Physics, vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). "Paisajes de fitness correlacionados y no correlacionados y cómo notar la diferencia". Cibernética biológica . 63 (5): 325–336. doi :10.1007/BF00202749. S2CID  851736.
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.12. Métodos de recocido simulado". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8. Archivado desde el original el 11 de agosto de 2011 . Consultado el 13 de agosto de 2011 .
• Strobl, MAR; Barker, D. (2016). "Sobre transiciones de fase de recocido simuladas en la reconstrucción de la filogenia". Filogenética molecular y evolución . 101 : 46–55. doi :10.1016/j.ympev.2016.05.001. PMC  4912009 . PMID  27150349.
• V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", Revista Internacional TEORÍAS Y APLICACIONES DE LA INFORMACIÓN, VOLUMEN 6/1999

enlaces externos

• Recocido simulado Una aplicación Javascript que le permite experimentar con recocido simulado. Código fuente incluido.
• "Algoritmo de recocido simulado general" 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 una computadora cuántica Ars Technica analiza la posibilidad de que la computadora D-Wave que utiliza Google pueda, de hecho, ser un coprocesador de recocido simulado eficiente.
• [1] Un algoritmo de optimización multiobjetivo basado en recocido simulado: AMOSA.