Red de conocimiento informático - Conocimiento de la instalación - Introducción al principio del recocido simulado

Introducción al principio del recocido simulado

En los problemas de optimización, esperamos encontrar una solución óptima, pero en realidad esto es difícil de lograr. Especialmente cuando el problema es complejo y la dimensión del espacio de soluciones es alta, debemos buscar todas las soluciones factibles en el enorme espacio de soluciones y determinar la solución óptima. La cantidad de cálculo necesaria para hacer esto es enorme y casi imposible de completar con tiempo y recursos informáticos limitados. En problemas prácticos, no necesitamos una solución óptima exacta, sino solo una solución óptima aproximada. Esta solución óptima aproximada debe estar lo suficientemente cerca de la solución óptima perfecta.

El algoritmo Simulated Annealing (SA) imita el proceso de recocido en termodinámica. Al calentar el metal a una temperatura alta, el movimiento térmico de las moléculas dentro del metal será muy intenso en este momento y la estructura molecular interna sufrirá grandes cambios y luego dejará que la temperatura disminuya lentamente; del movimiento térmico de las moléculas se debilita gradualmente y las moléculas internas Los cambios estructurales son pequeños y gradualmente se estabilizan. Cuando buscamos la solución óptima a un problema, primero podemos dar una solución inicial. En este momento, la temperatura es relativamente alta y existe una alta probabilidad de que la solución inicial cambie y se genere una nueva solución a medida que la temperatura disminuye, y la probabilidad de que la solución cambie gradualmente disminuye. Supongamos que necesitamos resolver el valor mínimo de una función f(x), entonces el proceso del algoritmo de recocido simulado se describe a continuación:

Hay muchas formas de generar nuevas soluciones. Tome la codificación binaria como. un ejemplo. Si una solución es 01001101, puede seleccionar aleatoriamente un bit para negar. Si se selecciona el tercer bit, el tercer bit se invierte bit a bit y la nueva solución es 01101101. Este proceso es algo similar a la mutación genética en los algoritmos genéticos. En la descripción del algoritmo anterior, cada valor de temperatura solo genera una nueva solución una vez, pero en problemas reales se puede generar varias veces.

La clave del algoritmo reside en el criterio Metropolis. Si el valor de la función de la nueva solución es pequeño, es natural considerar la nueva solución como la solución actual; si el valor de la función de la nueva solución es grande, todavía tiene una cierta probabilidad de ser seleccionada como la solución actual. Esta probabilidad está relacionada con df. Cuanto mayor es df, peor es la nueva solución y menor es la probabilidad de que sea seleccionada como la solución actual. Además, esta probabilidad también está relacionada con la temperatura actual; temperatura, mayor es la probabilidad (similar a las moléculas Cuanto más intenso es el ejercicio térmico).

Referencias

[1] Lee Jacobson, Recocido simulado para principiantes, /tutorial-post/simulated-annealing-algorithm-for-beginners/6