La aritmética de recocido simulada (SAA) es un algoritmo de probabilidad general que se utiliza para encontrar la solución óptima a una proposición en un espacio de búsqueda grande. El recocido simulado fue inventado por S. Kirkpatrick, C.D.Gelatt y M.P.Vecchi en 1983. V.?ern & yacute también inventaron de forma independiente este algoritmo en 1985. El algoritmo de recocido simulado es uno de los métodos eficaces para resolver el problema de TSP.
A la hora de buscar la solución óptima a un problema, podemos dar primero 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).