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

Abstract

Simulated Annealing (SA) o Metropolis es un algoritmo de búsqueda de soluciones que em- plea 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 pre- senta una implementación del algoritmo de SA que utiliza la preservación de menores cos- tos 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 so- lució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.

Simulated Annealing (SA) or Metropolis is a search algorithm that uses meta-heuristics for solve global optimization problems, where the goal is find-out good approximations to the optimal value of a function in a large search space. Its standard implementation has a high degree of dispersion in the solutions quality due to the stochastic nature of the search pro- cedure. In this paper, an implementation of the SA algorithm that promote short paths (SPP) in global optimization problems yields better solutions keeping finite convergence times. Preservation of short paths is performed during the random generation process of a new solution (perturbation). The random selected partial path is preserved in the new solution with an inversely probability to its cost. The implementation of this algorithm was carried out in Matlab®, the results are evaluated comparing with the standard implementation in symmetrical TSP problems from the TSPLIB, the performance obtained was promising for problems of n < 200 nodes.