de recocido simulado (SA) es un Meta-algoritmo de probabilidad genérico para el problema de la optimización global, a saber localizando una buena aproximación al grado óptimo global de una función dada en un espacio de búsqueda grande . Es de uso frecuente cuando el espacio de búsqueda es discreto (e., todos los viajes que visitan un sistema dado de ciudades). En casos favorables, el recocido simulado puede ser más eficaz que la enumeración exhaustiva del espacio de búsqueda.

El nombre y la inspiración vienen del recocido en metalurgia, una técnica que implica la calefacción y el enfriamiento controlado de un material para aumentar el tamaño de sus cristales y para reducir sus defectos . El calor hace los átomos llegar a ser unstuck de sus posiciones iniciales (un mínimo local de la energía interna ) y vagar aleatoriamente a través de estados de una energía más alta; el enfriamiento lento les da más oportunidades de encontrar configuraciones con una energía interna más baja que la inicial.

Por analogía con este proceso físico, cada paso del algoritmo del SA substituye la solución actual por un " al azar; nearby" solución, elegida con una probabilidad que depende de la diferencia entre los valores correspondientes de la función y de un global T del parámetro (llamado la temperatura del ), que se disminuye gradualmente durante el proceso. La dependencia es tal que la solución actual cambia casi aleatoriamente cuando el T es grande, pero cada vez más " downhill" como el T va a cero. El permiso para el " uphill" ¡los movimientos ahorran el método de el pegarse en los mínimos locales - que son la perdición un más codicioso methods.

El método fue descrito independiente por S. Vecchi en 1983, y por V. El método es una adaptación del algoritmo, un método de la Metrópoli-Hastings de Monte Carlo para generar los estados de la muestra de un sistema termodinámico, inventados por la metrópoli y otros N.

Descripción

En el método de recocido (SA) simulado, cada s del punto del espacio de búsqueda es análogo a un estado de un cierto sistema físico, y el E ( s ) de la función que se reducirá al mínimo es análogo a la energía interna del sistema en ese estado. La meta es traer el sistema, de un estado inicial del arbitrario, a un estado con la energía posible mínima.

La iteración básica

En cada paso, el SA heurístico considera de un cierto s vecino del del s del estado actual, y el Probabilistically decide entre la mudanza del sistema a del s del del estado o permanecer puesto en el s del estado. Se eligen las probabilidades de modo que el sistema tienda en última instancia a moverse a los estados de una energía más baja. Este paso se repite típicamente hasta que el sistema alcance un estado que sea bastante bueno para el uso, o hasta el cómputo dado se ha agotado un presupuesto.

Los vecinos de un estado

Al usuario especifican a los vecinos de cada estado (el candidato del mueve ), generalmente en una manera específica a la aplicación. Por ejemplo, en el problema de vendedor que viaja, cada estado se define típicamente como viaje particular (una permutación del de las ciudades que se visitarán); y uno podría definir a los vecinos de un viaje como esos viajes que se pueden obtener de él intercambiando cualquier par de ciudades consecutivas.

Probabilidades de la aceptación

La probabilidad de hacer la transición del estado actual $s$ a un nuevos $s\text{'}$ del estado del candidato es especificada por un $P\; de\; la\; función\; de\; probabilidad\; de\; la\; aceptación\; del\; (e,\; e\text{'},\; T)$, que depende del $e\; de\; las\; energías\; =\; del\; E$ y del $e\; =\; de\; la\; E\; (s\text{'})$ de los dos estados, y en un parámetro de tiempo variable global $T$ llamó la temperatura del .

Un requisito esencial para la función de probabilidad $P$ es que debe ser diferente a cero cuando $e\; >\; e$, significando que el sistema puede moverse al nuevo estado incluso cuando es el peor (tiene una energía más alta) que la actual. Es esta característica que evita que el método el pegarse en un mínimo local del - un estado que sea peor que el mínimo global, con todo mejor que cualesquiera de sus vecinos.

Por una parte, cuando $T$ va a cero, el $P\; de\; la\; probabilidad\; (e,\; e\text{'},\; T)$ debe tender a cero si $e\; >\; e$, y a un valor positivo si . Que la manera, para los valores suficientemente pequeños de $T$, el sistema favorecerá cada vez más los movimientos que van " downhill" (a los valores de una energía más baja), y evitar los que vayan " uphill". Particularmente, cuando $T$ se convierte en 0, el procedimiento reducirá al algoritmo codicioso - que hace el movimiento solamente si va cuesta abajo.

En la descripción original del SA, el $P\; de\; la\; probabilidad\; (e,\; e\text{'},\; T)$ fue definida como 1 cuando - es decir, el procedimiento movido siempre cuesta abajo cuando encontró una manera de hacer así pues, con independencia de la temperatura. Muchas descripciones y puestas en práctica del SA 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 trabaje, y uno puede sostener que es contraproducente y contrario a su alcohol.

La función de $P$ se elige generalmente de modo que la probabilidad de aceptar un movimiento disminuya cuando la diferencia el $e\text{'}-\; e$ aumentar-que es, los pequeños movimientos ascendentes es más probable que los grandes. Sin embargo, este requisito no es terminantemente necesario, a condición de que se cumplen los requisitos antedichos.

Dado estas características, la evolución del estado $s$ depende crucial de la temperatura $T$. En línea general, la evolución de $s$ es sensible a variaciones más gruesas de la energía cuando $T$ es grande, y a variaciones más finas cuando $T$ es pequeño.

El horario del recocido

Otra característica esencial del método del SA es que la temperatura está reducida gradualmente mientras que procede la simulación. Inicialmente, $T$ se fija a un elevado valor (o al infinito), y se disminuye en cada paso según un cierto horario - que del recocido del se pueda especificar por el usuario, pero debe terminar con $T=0$ hacia el extremo del presupuesto asignado del tiempo. De esta manera, se espera que el sistema vague inicialmente hacia una región amplia del espacio de búsqueda que contiene buenas soluciones, no haciendo caso de las pequeñas características de la función de la energía; entonces mandilar hacia las regiones de poca energía que llegan a ser más estrechas y más estrechas; y finalmente movimiento cuesta abajo según la pendiente más escarpada heurística.

Convergencia al grado óptimo

Puede ser demostrado que, para cualquie problema finito dado, la probabilidad que el algoritmo de recocido simulado termina con la solución óptima global se acerca a 1 mientras que el horario de recocido es extendido. Este resultado teórico es, sin embargo, no particularmente provechoso, desde el tiempo de recocido requerido para asegurar una probabilidad significativa del éxito excederá generalmente el tiempo requerido para una búsqueda completa del espacio de solución .

Pseudo-code

El pseudo-code siguiente ejecuta el recocido simulado heurístico, como se describe anteriormente, a partir de el estado s0 y continuación a un máximo de los pasos de kmax o hasta un estado con la energía emax o se encuentra menos. La llamada neighbour debe generar a un vecino aleatoriamente elegido de un estado dado s; el random de la llamada () debe volver un valor al azar en el $1)$ de la gama. El horario del recocido es definido por el temp de la llamada (r), que debe rendir la temperatura al uso, dado la fracción r del presupuesto del tiempo que se ha expendido hasta ahora.

s: = s0; e: = estado inicial del de E //, energía. k: = 0 cuentas de la evaluación de la energía del de //. mientras que < de k; del kmax y > de e; de // del emax mientras que sigue habiendo el tiempo y no bueno bastante: sn: = selección del de // de los vecinos algún vecino. en: = cálculo del de E (sn) // su energía. si P (e, en, temp (k/kmax)) ¿> () el al azar del entonces // debe nosotros se mueve a él? s: = sn; e: = del en // sí, estado del cambio. k: = k + 1 de // un más hecho evaluación solución actual s // de la vuelta de vuelta del

Ahorrando la mejor solución vista

Como en cualquier Metaheuristic, uno debe no perder de vista la mejor solución vista hasta ahora, en una variable de estado separado. A saber:

s: = s0; e: = estado inicial del de E //, energía. sb: = s; eb: = " de la inicial del de e //; best" solución k: = 0 cuentas de la evaluación de la energía del de //. mientras que < de k; del kmax y > de e; de // del emax mientras que sigue habiendo el tiempo y no bueno bastante: sn: = selección del de // de los vecinos algún vecino. en: = cálculo del de E (sn) // su energía. ¿ si en < entonces // del eb es éste un nuevo mejor? sb: = sn; eb: = del en // sí, excepto él. si P (e, en, temp (k/kmax)) ¿> () el al azar del entonces // debe nosotros se mueve a él? s: = sn; e: = del en // sí, estado del cambio. k: = k + 1 de // un más hecho evaluación vuelta de vuelta del de // del sb del que la mejor solución encontró.

Observar que el sb del paso: = sn sucede solamente en una pequeña fracción de los movimientos. Por lo tanto, esta variación en el método básico está generalmente digno de el coste, incluso si el estado-copiado es una operación costosa.

Selección de los parámetros

Para aplicar el método del SA a un problema específico, uno debe especificar los parámetros siguientes: el espacio de estado, el E de la función de la energía (meta) () , el neighbour del procedimiento del generador del candidato () , el P de la función de probabilidad de la aceptación () , y el temp del horario del recocido () . Estas opciones pueden tener un impacto significativo en la eficacia del método. Desafortunadamente, no hay opciones de estos parámetros que sean buenos para todos los problemas, y no hay manera general de encontrar las mejores opciones para un problema dado. De hecho, se ha observado que la aplicación del método del SA es más un arte que una ciencia. Las secciones siguientes dan algunas pautas generales.

Diámetro del gráfico de búsqueda

El recocido simulado se puede modelar como caminata al azar en un gráfico de la búsqueda del, cuyas cimas son todas los estados posibles, y cuyos son bordes el candidato se mueven. Un requisito esencial para la función del neighbour () es que debe proporcionar una trayectoria suficientemente corta en este gráfico del estado inicial a cualquier estado que pueda ser el grado óptimo global. (Es decir el diámetro del gráfico de búsqueda debe ser pequeño.) ¡En el ejemplo de vendedor que viaja arriba, por ejemplo, el espacio de búsqueda para las ciudades de $n=20$ tiene $n!\; =\; 2\; 432\; 902\; 008\; 176\; 640\; estados\; de\; 000$ (quintillón de 2.5 ); con todo la función vecina del generador que intercambia dos ciudades consecutivas puede conseguir de cualquier estado (viaje) a cualquier otro estado en el $n\; (n-1)\; /2\; =\; los\; pasos\; 190$.

Probabilidades de transición

Para cada $del\; borde\; (s,\; s\text{'})$ del gráfico de búsqueda, uno define una probabilidad de transición del, que es la probabilidad que el algoritmo del SA moverá al $s\text{'}\; del\; estado\; cuando\; su\; estado\; actual\; es$ s$.\; Esta\; probabilidad\; depende\; obviamente\; de\; la\; temperatura\; actual,\; y\; es\; determinada\; por\; la\; orden\; en\; la\; cual\; los\; movimientos\; del\; candidato\; son\; generados\; por\; la\; función\; del$neighbour () , y por el P de la función de probabilidad de la aceptación () . (Nota que la probabilidad de transición es el $P\; del\; no\; simplemente\; (e,\; e\text{'},\; T)$, porque prueban a los candidatos en serie).

Las probabilidades de transición y el horario del recocido determinan la probabilidad que la iteración del SA alcanzará el grado óptimo global dentro del tiempo asignado. Por lo tanto, el neighbour de los parámetros () , el P () , y temp se deben templar junto para maximizar la ocasión de este acontecimiento.

Probabilidades de la aceptación

Realmente, el neighbour de los parámetros () , el P () , y temp son en parte redundantes. En la práctica, uno utiliza el mismo P de la función de la aceptación () para todos los problemas, y ajusta las otras dos funciones según el problema específico actual.

En la formulación original del método por el de Kirkpatrick y. al, el $P\; de\; la\; probabilidad\; de\; la\; aceptación\; (e,\; e\text{'},\; T)$ fue definida como 1 si , y $\backslash \; exp\; ((e-e\text{'})/T)$ de otra manera. Esta fórmula fue dicha para venir del algoritmo de la Metrópoli-Hastings, donde fue utilizada para generar muestras de la distribución de Maxwell-Boltzmann que gobernaba la distribución de energías de moléculas en un gas. Sin embargo, no hay justificación matemática para usar esta fórmula particular en el SA. Incluso la analogía física es engañosa: puesto que prueban a los vecinos secuencialmente en el algoritmo del SA, la probabilidad real del algoritmo del SA que se mueve desde un estado $s$ a un $s\text{'}\; del\; estado\; es\; definitivamente\; el\; no\; dado\; por\; esa\; fórmula.\; Sin\; embargo,\; esta\; fórmula\; es\; absolutamente\; popular,\; y\; es\; hard-coded\; en\; muchas\; puestas\; en\; práctica.$

Generación eficiente del candidato

Al elegir el neighbour del generador del candidato () , uno debe considerar que después de algunas iteraciones del algoritmo del SA, se espera que el estado actual tenga energía mucho más baja que un estado al azar. Por lo tanto, como regla general, uno debe sesgar el generador hacia movimientos del candidato donde está probable la energía del $s\text{'}\; del\; estado\; de\; la\; destinación\; ser\; similar\; a\; la\; del\; estado\; actual.\; Este\; heurístico\; (que\; es\; el\; principio\; fundamental\; del\; algoritmo\; de\; la\; Metrópoli-Hastings)\; tiende\; a\; excluir\; el\; "\; mismo\; good"\; movimientos\; del\; candidato\; tan\; bien\; como\; "\; mismo\; bad"\; unos;\; sin\; embargo,\; estes\; 3ultimo\; sonmuchomas\; comunes\; que\; el\; anteriores,\; así\; que\; el\; heurístico\; es\; generalmente\; absolutamente\; eficaz.$

En el problema de vendedor que viaja arriba, por ejemplo, intercambiando dos ciudades consecutivas del en un viaje de poca energía se espera tener un efecto modesto en su energía (longitud); considerando que el intercambio de dos ciudades arbitrarias del es lejos más probable aumentar su longitud que disminuirla. Así, consecutivo-intercambiar el generador vecino se espera realizarse mejor que arbitrario-intercambiar uno, aunque estes 3ultimo podrían proporcionar una trayectoria algo más corta al grado óptimo (con intercambios de $n-1$, en vez del $n\; (n-1)\; /2$).

Una declaración más exacta del heurístico es de que una intente el primer $s\text{'}$ de los estados del candidato para los cuales el $P\; (E,\; E\; (el\; s\text{'}),\; T)$ es grande. Para el " standard" la función $P$ de la aceptación arriba, significa que $E\; (s\text{'})\; -\; E$ está en la orden de $T$ o menos. Así, en el ejemplo de vendedor que viajaba arriba, uno podría utilizar una función del neighbour () que intercambia dos ciudades al azar, en donde la probabilidad de elegir un par de la ciudad desaparece mientras que su distancia aumenta más allá de $T$.

Evitación de la barrera

Cuando elegir el neighbour del generador del candidato () uno debe también intentar reducir el número de " deep" mínimos locales - estados (o sistemas de estados conectados) que tienen energía mucho más baja que todo su estado colindante. Tal " basins" cerrado de la captación ; de energía la función puede atrapar el algoritmo del SA con la alta probabilidad (áspero proporcional al número de estados en el lavabo) y por un tiempo muy largo (áspero exponencial en la diferencia de la energía entre el estado circundante y la parte inferior del lavabo).

En general, es imposible diseñar un generador del candidato que satisfaga esta meta y también dé prioridad a candidatos con energía similar. Por una parte, uno puede mejorar a menudo sumamente la eficacia del SA por los cambios relativamente simples al generador. En el problema, por ejemplo, él de vendedor que viaja no es duro exhibir dos viajes $A$, $B$, con longitudes casi iguales, tal que (0) $A$ son óptimos, (1) cada secuencia de intercambios de los ciudad-pares que convierta $A$ a $B$ pase con los viajes que son mucho más largos que ambos, y (2) $A$ se puede transformar en $B$ moviendo de un tirón (que invierte la orden de) un sistema de ciudades consecutivas. En este ejemplo, $A$ y $B$ mienten en diverso " basins" profundo; si el generador realiza solamente al azar par-intercambia; pero serán en el mismo lavabo si el generador realiza al azar segmento-mueve de un tirón.

Horario de enfriamiento

La analogía física que se utiliza para justificar el SA asume que la tarifa de enfriamiento está bajo bastante para la distribución de probabilidad del estado actual a ser el equilibrio termodinámico cercano siempre. Desafortunadamente, el tiempo de relajación del - el tiempo uno debe esperar el equilibrio que se restaurará después de que un cambio en temperatura-fuerte dependa del " topography" de la función de la energía y en la temperatura actual. En el algoritmo del SA, el tiempo de relajación también depende del generador del candidato, de una manera muy complicada. Observar que todos estos parámetros están proporcionados generalmente como funciones de la caja negra al algoritmo del SA.

Por lo tanto, la tarifa de enfriamiento ideal no se puede determinar en la práctica de antemano, y se debe empírico ajustar según cada problema. La variante del SA conocida como de recocido simulado termodinámico intenta evitar este problema dispensando con el horario de enfriamiento, y en lugar de otro automáticamente ajustando la temperatura en cada paso basado en la diferencia de la energía entre los dos estados, según las leyes de la termodinámica.

Recomenzar

Es a veces mejor moverse de nuevo a una solución que era perceptiblemente mejor algo que siempre moviéndose desde el estado actual. Esto se llama que recomienza . Para hacer esto fijamos s y e a sb y a eb y quizás recomienzan el horario del recocido. La decisión a recomenzar se podía basar en un número fijo de pasos, o basar en la energía actual que era demasiado alta de la mejor energía hasta ahora.

Métodos relacionados

El recocido de Quantum utiliza el " fluctuations" del quántum; en vez de fluctuaciones termales conseguir a través de colmo pero de barreras finas en la función de la blanco.
las tentativas estocásticas el hacer un túnel superar la dificultad cada vez mayor simularon funcionamientos del recocido tienen en el escape de mínimos locales como las disminuciones de la temperatura, “haciendo un túnel” a través de barreras.
la búsqueda Tabu se mueve normalmente al estado colindante de una energía más baja, pero tomará movimientos ascendentes cuando se encuentra pegado en un mínimo local; y evita ciclos guardando un " list" taboo; de las soluciones vistas ya.
la pendiente estocástica del gradiente funciona con muchas búsquedas codiciosas de localizaciones iniciales al azar.
los algoritmos genéticos mantienen una piscina de soluciones algo que apenas una. Las nuevas soluciones del candidato son generadas no sólo por el " mutation" (como en el SA), pero también por el " combination" de dos soluciones de la piscina. Los criterios de probabilidad, similares a ésos usados en el SA, se utilizan para seleccionar a los candidatos para la mutación o la combinación, y para desechar exceso de soluciones de la piscina.
la optimización (ACO) de la colonia de la hormiga utiliza muchas hormigas (o agentes) para atravesar el espacio de solución y para encontrar localmente áreas productivas.

el método (CE) de la Cruz-entropía genera soluciones de los candidatos vía una distribución de probabilidad dada parámetros. Los parámetros son actualizados vía la minimización de la cruz-entropía, para generar mejores muestras en la iteración siguiente.
la búsqueda de la armonía mímico a músicos en el proceso de la improvisación donde cada músico juega una nota para encontrar una mejor armonía toda junta.
la optimización estocástica es un sistema del paraguas de métodos que incluye el recocido simulado y otro numeroso se acerca.

Ver también

de recocido simulado adaptante
Cadena de Markov
Optimización combinatoria
Colocación automática de la etiqueta
Optimización multidisciplinaria
Lugar y ruta
Problema de vendedor que viaja
Búsqueda reactiva
El gráfico corta adentro la visión de computadora

.

Zenithic

Alberto Mancini

Random links:

Historia de comando | AR-10 | Mike Yates | Carmen Electra (álbum) | Una diversa clase de dolor