La cristalización simulada (también llamado recocido simulado) “Simulated Annealing, SA” constituye una de las estrategias a las que se recurre en la resolución de los problemas de optimización combinatoria. Kirkpatrick, Gelatt y Vecchi la propusieron por primera vez en 1983, y Cerny la propuso de forma independiente en 1985. Estos autores se inspiraron en los trabajos de Metrópolis et al. (1953) sobre Mecánica Estadística. La metaheurística despliega una estructura que se inserta cómodamente en la programación y, además, muestra una considerable habilidad para escapar de los óptimos locales. Fue una técnica que experimentó un auge considerable en la década de los 80 para resolver problemas de optimización mediante modelos matemáticos.
La energía de un sistema termodinámico se compara con la función de coste evaluada para una solución admisible de un problema de optimización combinatoria. En ambos casos se trata de evolucionar de un estado a otro de menor energía o coste. El acceso de un estado metaestable a otro se alcanza introduciendo “ruido” mediante un parámetro de control, denominado temperatura. Su reducción adecuada permite, con una probabilidad elevada, que un sistema termodinámico adquiera un mínimo global de energía. Conceptualmente, es un algoritmo de búsqueda por entornos que selecciona candidatos de forma aleatoria. La alternativa se aprueba si perfecciona la solución actual (D ≤ 0); en caso contrario, será aceptada con una probabilidad e^(-D/T), donde T es el parámetro de temperatura, si D > 0. El proceso se repite cuando la propuesta no es admitida. La selección aleatoria de soluciones degradadas permite eludir los mínimos locales. La cristalización simulada se codifica fácilmente, incluso en problemas complejos y con funciones objetivo arbitrarias. Además, independientemente de la solución inicial, el algoritmo converge estadísticamente a la solución óptima (Lundy y Mees, 1986). En cualquier caso, SA suele ofrecer soluciones valiosas, aunque no informa si ha alcanzado el óptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque sí comparable, frente a otros específicos que aprovechan información adicional del problema. El algoritmo es lento, especialmente si la función objetivo es costosa en términos de tiempo de computación. Además, la cristalización simulada pierde terreno frente a otros métodos más simples y rápidos, como el descenso local, cuando el espacio de las soluciones es poco abrupto o escasean los mínimos locales.
Os dejo un vídeo explicativo:
Referencias
CERNY, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm. Journal of Optimization Theory and Applications, 45: 41-51.
KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.
LUNDY, M.; MEES, A. (1986). Convergence of an Annealing Algorithm. Mathematical programming, 34:111-124.
METROPOLIS, N.; ROSENBLUTH, A.W.; ROSENBLUTH, M.N.; TELLER, A.H.; TELER, E. (1953). Equation of State Calculation by Fast Computing Machines. Journal of Chemical Physics, 21:1087-1092.
GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)