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 aproximar la optimización global en un gran espacio de búsqueda para un problema de optimización . Se utiliza a menudo cuando el espacio de búsqueda es discreto (por ejemplo, el problema del viajante de comercio ). 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 orama y encuadernado .
El nombre del algoritmo proviene del recocido en metalurgia , una técnica que involucra el calentamiento y enfriamiento controlado de un material para aumentar el tamaño de sus cristales y reducir sus defectos. 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 donde fallan los algoritmos exactos; aunque suele lograr una solución aproximada al mínimo global, podría ser suficiente para muchos problemas prácticos.
Los problemas resueltos por SA están formulados actualmente por una función objetivo de muchas variables, sujeta a varias restricciones. En la práctica, la restricción puede penalizarse como parte de la función objetivo.
Técnicas similares se han introducido independientemente en varias ocasiones, incluyendo Pincus (1970), [1] Khachaturyan et al (1979, [2] 1981 [3] ), Kirkpatrick, Gelatt y Vecchi (1983) y Cerny (1985). [4] En 1983, Kirkpatrick, Gelatt Jr., Vecchi, [5] utilizaron este enfoque 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 la solución. Aceptar peores soluciones permite una búsqueda más extensa 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 positivo inicial a 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 disminuir hacia cero.
La simulación se puede realizar mediante una solución de ecuaciones cinéticas para funciones de densidad [6] [7] o mediante el método de muestreo estocástico. [5] [8] 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. [9]
Descripción general
El estado de algunos sistemas físicos y la función E ( s ) a minimizar es análogo 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.
La iteración básica
En cada paso, la heurística de recocido simulado considera algunos estados vecinos s * del estado actual s , y decide probabilísticamente entre mover el sistema al estado s * o permanecer en el estado s . En última instancia, estas probabilidades llevan al sistema a pasar 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 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 dado. Por ejemplo, en el problema del viajante de comercio, 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 alteran 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 de comercio).
Las heurísticas simples como escalar colinas , que se mueven encontrando un mejor vecino tras otro mejor vecino 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 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 a 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 atascados 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 hacer la transición desde el estado actual. a un candidato nuevo estado se especifica mediante una función de probabilidad de aceptación , eso depende de las energías y de los dos estados, y en un parámetro global variable en el tiempo llamado la temperatura . Los estados con menor energía son mejores que aquellos con mayor energía. La función de probabilidad debe ser positivo incluso cuando es mayor que . Esta característica evita que el método se atasque en un mínimo local que sea peor que el global.
Cuándo tiende a cero, la probabilidad debe tender a cero si ya 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, a valores de energía más bajos) y evitará los que vayan "cuesta arriba". Conel procedimiento se reduce al algoritmo codicioso , que hace solo 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 la 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.
La Por lo general, la función se elige de modo que la probabilidad de aceptar un movimiento disminuya cuando la diferencia aumentos, es decir, los pequeños movimientos cuesta arriba 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 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 una 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 programa de recocido
El nombre y la inspiración del algoritmo exigen que una característica interesante relacionada con la variación de temperatura se integre 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 conestablecido en 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 terminar conhacia 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 contiene buenas soluciones, ignorando pequeñas características de la función de energía; luego derivar hacia regiones de baja energía que se vuelven cada vez más estrechas; y finalmente moverse cuesta abajo de acuerdo con la heurística de descenso más empinado .
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 amplía el programa de recocido. [10] 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 la solución . [ cita requerida ]
Pseudocódigo
El siguiente pseudocódigo presenta la heurística de recocido simulado como se describe anteriormente. Comienza desde un estado s 0 y continúa hasta que se hayan dado un máximo de k pasos máximos . En el proceso, la llamada vecino ( s ) debe generar un vecino elegido al azar de un estado dado s ; la llamada aleatoria (0, 1) debe elegir y devolver un valor en el rango [0, 1] , uniformemente al azar . El programa de recocido se define 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 ahora.
- Sea s = s 0
- Para k = 0 hasta k max (exclusivo):
- T ← temperatura ( (k + 1) / k max )
- Recoger un vecino al azar, s nueva ← 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 del generador candidato neighbour()
, la función de probabilidad de aceptación P()
y el programa de recocido temperature()
Y temperatura inicial
Vecino suficientemente cerca
El recocido simulado se puede modelar como un recorrido 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 neighbour()
función es que debe proporcionar una ruta suficientemente corta en este gráfico desde el estado inicial a cualquier estado que pueda ser el óptimo global; el diámetro del gráfico de búsqueda debe ser pequeño. En el ejemplo del vendedor ambulante anterior, por ejemplo, el espacio de búsqueda para n = 20 ciudades tiene n! = 2,432,902,008,176,640,000 (2.4 trillones) estados; sin embargo, el número de vecinos de cada vértice es bordes, y el diámetro del gráfico es .
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 elecciones de diseño realizadas en la implementación del algoritmo. Por 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 temperature()
, del orden en que la neighbour()
función genera los movimientos candidatos y de la función de probabilidad de aceptación P()
. (Tenga en cuenta que la probabilidad de transición no es simplemente, porque los candidatos se prueban en serie).
Probabilidades de aceptación
La especificación de neighbour()
, 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 de acuerdo con 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 de lo contrario. Esta fórmula fue justificada superficialmente por analogía con las transiciones de un sistema físico; corresponde al algoritmo Metropolis-Hastings , en el caso donde 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 neighbour()
función, que es análoga a la distribución de la 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 se corresponden con las transiciones del sistema físico análogo y la distribución de estados a largo plazo a una temperatura constanteno es necesario que guarde semejanza alguna con la distribución del equilibrio termodinámico sobre los estados de ese 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.
En 1990, Moscato y Fontanari, [11] e independientemente Dueck y Scheuer, [12] 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 el análogo 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 cerca -mínimos óptimos ". En cambio, propusieron que "suavizar el panorama 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 gran clase de algoritmos que simulan una caminata aleatoria en el panorama de costos / energía. [13]
Generación de candidatos eficiente
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 inclinar el generador hacia movimientos candidatos donde la energía del estado de destinoes probable que sea similar al del estado actual. Esta heurística (que es el principio principal del algoritmo Metropolis-Hastings ) tiende a excluir los movimientos candidatos "muy buenos" así 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 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 ).
Una declaración más precisa de la heurística es que uno debería probar los primeros estados candidatos para cual es largo. Para la función de aceptación "estándar" arriba, significa que es del orden de o menos. Por lo tanto, en el ejemplo del vendedor ambulante anterior, se podría usar una neighbour()
función que intercambia dos ciudades al azar, donde la probabilidad de elegir un par de ciudades desaparece a medida que su distancia aumenta más allá de.
Evitación de barreras
Al elegir el generador candidato, neighbour()
también se debe intentar reducir el número de estados mínimos locales "profundos" (o conjuntos de estados conectados) que tienen una energía mucho menor que todos los estados vecinos. Tales " cuencas de captación 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 largo (aproximadamente exponencial en la diferencia de energía entre los estados circundantes y fondo del lavabo).
Como regla general, es imposible diseñar un generador candidato que satisfaga este objetivo y también priorizar 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 de comercio, por ejemplo, no es difícil exhibir dos giras, , con longitudes casi iguales, de modo que (1) es óptimo, (2) cada secuencia de intercambios de pares de ciudades que convierte a pasa por recorridos que son mucho más largos que ambos, y (3) se puede transformar en volteando (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 volteos de segmento aleatorios.
Programa 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. Lamentablemente, el tiempo de relajación —el tiempo que hay que esperar a 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 se proporcionan normalmente como funciones de caja negra para el 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 adaptativo abordan este problema conectando el programa de enfriamiento con el progreso de la búsqueda. Otro enfoque adaptativo como el recocido termodinámico simulado [14] ajusta 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.
Reinicia
A veces es mejor volver a una solución que fue significativamente mejor en lugar de pasar siempre del estado actual. Este proceso se denomina reinicio del recocido simulado. Para ello hemos establecido s
y e
a sbest
y ebest
y tal vez reinicie el programa de recocido. La decisión de reiniciar podría basarse en varios criterios. Entre estos, 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, reinicio aleatorio, etc.
Métodos relacionados
- Los algoritmos interactivos de Metropolis-Hasting (también conocidos como Sequential Monte Carlo [15] ) combinaron movimientos de recocido simulados con una aceptación-rechazo de los individuos mejor equipados 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.
- El túnel estocástico 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 el "túnel" a través de las barreras.
- La búsqueda tabú normalmente se mueve a estados vecinos de menor energía, pero tomará movimientos cuesta arriba cuando se encuentre atascada en un mínimo local; y evita los ciclos manteniendo una "lista tabú" de soluciones ya vistas.
- La evolución de fase dual 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, agregando un ciclo 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 en torno a la solución actual.
- Los algoritmos genéticos mantienen un conjunto de soluciones en lugar de solo una. Las nuevas soluciones candidatas se generan no solo por "mutación" (como en SA), sino también por "recombinación" de dos soluciones del conjunto. Los criterios probabilísticos, similares a los utilizados en SA, se utilizan para seleccionar los candidatos para la 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. [16] También se ha sugerido el recocido como un mecanismo para aumentar la diversidad de la búsqueda. [17]
- La optimización graduada "suaviza" digresivamente la función de destino mientras 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 a través de una distribución de probabilidad parametrizada. Los parámetros se actualizan mediante la minimización de la entropía cruzada, para generar mejores muestras en la siguiente iteración.
- La búsqueda de armonía imita a los músicos en el proceso de improvisación donde cada músico toca una nota para encontrar la mejor armonía entre todos.
- La optimización estocástica es un conjunto general de métodos que incluye recocido simulado y muchos otros enfoques.
- La optimización del enjambre de partículas es un algoritmo modelado sobre la inteligencia del 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 runner-root (RRA) es un algoritmo de optimización metaheurístico para resolver problemas unimodales y multimodales inspirado 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 natural 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 posibles barreras.
Ver también
- Recocido simulado adaptativo
- Cadena de Markov
- Optimización combinatoria
- Evolución de doble fase
- Colocación automática de etiquetas
- Optimización multidisciplinar
- Lugar y ruta
- Dinámica molecular
- Problema del vendedor ambulante
- Recortes de gráficos en visión artificial
- Optimización de Enjambre de partículas
- Algoritmo inteligente de gotas de agua
Referencias
- ^ Pincus, Martin (noviembre-diciembre de 1970). "Un método de 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 - a través de JSTOR.
- ^ 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.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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. doi : 10.1107 / S0567739481001630 - a través de https://ui.adsabs.harvard.edu/abs/1981AcCrA..37..742K .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Laarhoven, PJM van (Peter JM) (1987). Recocido simulado: teoría y aplicaciones . Aarts, EHL (Emile HL). Dordrecht: D. Reidel. ISBN 90-277-2513-6. OCLC 15548651 .
- ^ a b Kirkpatrick, S .; Gelatt Jr, CD; Vecchi, MP (1983). "Optimización por recocido simulado". Ciencia . 220 (4598): 671–680. Código Bibliográfico : 1983Sci ... 220..671K . CiteSeerX 10.1.1.123.7607 . doi : 10.1126 / science.220.4598.671 . JSTOR 1690046 . PMID 17813860 . S2CID 205939 .
- ^ 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.
- ^ 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 .
- ^ Černý, V. (1985). "Aproximación termodinámica al problema del viajante: un algoritmo de simulación eficiente". Revista de teoría y aplicaciones de la optimización . 45 : 41–51. doi : 10.1007 / BF00940812 . S2CID 122729427 .
- ^ Metrópolis, Nicolás; Rosenbluth, Arianna W .; Rosenbluth, Marshall N .; Teller, Augusta H .; Teller, Edward (1953). "Ecuación de cálculos de estado por máquinas de cómputo rápido". La Revista de Física Química . 21 (6): 1087. Código Bibliográfico : 1953JChPh..21.1087M . doi : 10.1063 / 1.1699114 .
- ^ Granville, V .; Krivanek, M .; Rasson, J.-P. (1994). "Recocido simulado: una prueba de convergencia". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 16 (6): 652–656. doi : 10.1109 / 34.295910 .
- ^ Moscato, P .; Fontanari, JF (1990), "Actualización estocástica versus determinista en el recocido simulado", Physics Letters A , 146 (4): 204-208, doi : 10.1016 / 0375-9601 (90) 90166-L
- ^ 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, doi : 10.1016 / 0021-9991 (90) 90201- B , ISSN 0021-9991
- ^ 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
- ^ De Vicente, Juan; Lanchares, Juan; Hermida, Román (2003). "Colocación por recocido simulado termodinámico". Physics Letters A . 317 (5–6): 415–423. Código bibliográfico : 2003PhLA..317..415D . doi : 10.1016 / j.physleta.2003.08.070 .
- ^ Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2006). "Samplers secuenciales de Monte Carlo". Revista de la Sociedad Real de Estadística, Serie B . 68 (3): 411–436. arXiv : cond-mat / 0212648 . doi : 10.1111 / j.1467-9868.2006.00553.x . S2CID 12074789 .
- ^ Moscato, Pablo (junio de 1993). "Una introducción a los enfoques de población para la optimización y funciones objetivas jerárquicas: una discusión sobre el papel de la búsqueda tabú". Anales de investigación operativa . 41 (2): 85-121. doi : 10.1007 / BF02022564 . S2CID 35382644 .
- ^ 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).
Otras lecturas
- A. Das y BK Chakrabarti (Eds.), Métodos de recocido cuántico y optimización relacionados , Nota de conferencia en Física, vol. 679, Springer, Heidelberg (2005)
- Weinberger, E. (1990). "Paisajes de fitness correlacionados y no correlacionados y cómo diferenciarlos". Cibernética biológica . 63 (5): 325–336. doi : 10.1007 / BF00202749 . S2CID 851736 .
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.12. Métodos de recocido simulados" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
- Strobl, MAR; Barker, D. (2016). "En transiciones de fase de recocido simulado en la reconstrucción de 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: "El uso del recocido simulado en el control de sistemas de fabricación flexibles", Revista internacional TEORÍAS Y APLICACIONES DE LA INFORMACIÓN, VOLUMEN 6/1999
enlaces externos
- Recocido simulado Una aplicación de Javascript que le permite experimentar con recocido simulado. Incluye código fuente.
- "Algoritmo general de recocido simulado" Un programa MATLAB de código abierto para ejercicios generales de recocido simulado.
- Lección autoguiada sobre recocido simulado Un proyecto de Wikiversity.
- Google en la superposición de usar, no usar computadora cuántica Ars Technica analiza la posibilidad de que la computadora D-Wave que está usando Google pueda, de hecho, ser un coprocesador de recocido simulado eficiente.