Mejoras en la calidad de las soluciones de simulated annealing mediante preservación de menores costos

Simulated Annealing (SA) o Metropolis es un algoritmo de búsqueda de soluciones que emplea meta-heurística para problemas de optimización global donde el objetivo es encontrar
buenas aproximaciones al valor óptimo de una función en un espacio de búsqueda grande. Su implementación estándar presenta dispersión en la calidad de las respuestas encontradas
debido a que explora el espacio de soluciones en forma estocástica. En este trabajo, se presenta una implementación del algoritmo de SA que utiliza la preservación de menores costos en problemas de optimización global y permite obtener soluciones mejores, con menor dispersión y manteniendo tiempos de convergencia finitos. La preservación de los menores costos se realiza durante el proceso de generación aleatoria (perturbación) de la nueva solución a partir de la solución corriente. La modificación se hace conservando una parte de la solución elegida con una probabilidad inversamente proporcional a su costo parcial. La implementación del algoritmo se llevó a cabo en Matlab® y se comparó contra el recocido simulado estándar en problemas TSP simétricos de la librería TSPLIB obteniendo soluciones excelentes para problemas de n < 200 nodos.