Es normal que el recocido simulado tenga soluciones diferentes cada vez, porque el recocido simulado en sí es un algoritmo aleatorio, y el cambio a una peor solución no es inevitable sino probabilístico, es decir, cada vez que Cuando se ejecuta el algoritmo, las soluciones a las que se transfiere el proceso de ejecución pueden ser completamente diferentes.
En cuanto al problema TSP, es un problema NP-difícil y no se puede encontrar ninguna solución con complejidad de tiempo polinomial.
Si se requiere una solución precisa, los métodos actualmente factibles incluyen enumeración, bifurcación y vinculación, programación dinámica, etc. Sin embargo, el rango de datos aplicable de estos métodos es muy pequeño. Una vez que la escala de datos aumenta, se vuelven más grandes. no podrá hacer nada.
Entonces, en la mayoría de los algoritmos aleatorios más utilizados actualmente, como colonias de hormigas, genética, etc., el recocido simulado es uno de ellos. Una característica importante de estos algoritmos es acercarse a la solución óptima a través de la aleatoriedad, pero. También puede haber interpretaciones erróneas.
Solo el método exhaustivo puede garantizar la solución óptima, pero el tiempo de ejecución del método exhaustivo suele ser inaceptable cuando la cantidad de datos es relativamente grande, por lo que se utilizan varios métodos de aproximación.
La generación y aceptación de nuevas soluciones en el algoritmo de recocido simulado se puede dividir en los siguientes cuatro pasos:
El primer paso es utilizar una función de generación para generar una nueva solución ubicada en el espacio de la solución a partir de la solución actual; para facilitar el cálculo y la aceptación posteriores y reducir el tiempo que lleva el algoritmo, generalmente se elige un método que pueda generar una nueva solución a partir de la nueva solución actual mediante una transformación simple, como por ejemplo. reemplazar o intercambiar todo o parte de los elementos que constituyen la nueva solución. Nota El método de transformación utilizado para generar una nueva solución determina la estructura de vecindad de la nueva solución actual, teniendo así un cierto impacto en la selección del programa de enfriamiento.
El segundo paso es calcular la diferencia de la función objetivo correspondiente a la nueva solución. Debido a que la diferencia de la función objetivo es generada solo por la parte de transformación, es mejor calcular la diferencia de la función objetivo de forma incremental. Resulta que para la mayoría de las aplicaciones esta es la forma más rápida de calcular la diferencia en la función objetivo.
El tercer paso es juzgar si se acepta la nueva solución. La base para el juicio es un criterio de aceptación. El criterio de aceptación más comúnmente utilizado es el criterio de Metropolis: si ΔT<0, acepte S′ como el. nueva solución actual S. De lo contrario, acepte S′ como la nueva solución actual S con probabilidad exp(-ΔT/T).
El cuarto paso es reemplazar la solución actual con la nueva solución cuando se determina que la nueva solución es aceptada. Esto solo necesita implementar la parte de transformación de la solución actual correspondiente al momento en que se genera la nueva solución. , y al mismo tiempo modificar el valor de la función objetivo. Eso es todo. En este punto, la solución actual implementa una iteración. Sobre esta base se puede iniciar la siguiente ronda de pruebas. Cuando se considere descartada la nueva solución, la siguiente ronda de pruebas continuará basándose en la solución actual original.