Recocido Simulado (Simulated Annealing)

El recocido simulado (simulated annealing) es una metaheurística de optimización probabilística: busca una solución cercana a la óptima en espacios enormes aceptando, de vez en cuando, empeorar temporalmente para no quedarse atrapada. Su nombre viene de la metalurgia: el recocido consiste en calentar un metal y enfriarlo despacio para que sus átomos se ordenen en una estructura de baja energía. La técnica traslada esa idea a la optimización.

Origen

La formulación moderna la propusieron Scott Kirkpatrick, C. Daniel Gelatt y Mario Vecchi en 1983, en el artículo «Optimization by Simulated Annealing», publicado en la revista Science; Vlado Černý llegó de forma independiente al mismo método en 1985. Se apoya en un procedimiento anterior, el algoritmo de Metropolis (Metropolis y colaboradores, 1953), nacido en la física para simular sistemas de muchas partículas.

Cómo funciona

El método parte de una solución y de una «temperatura» alta, y en cada paso propone una solución vecina. Si mejora, se acepta; si empeora, se acepta con una probabilidad que depende de cuánto empeora y de la temperatura del momento. Esa probabilidad tiene la forma exp(−ΔE/T), donde ΔE es el empeoramiento y T la temperatura. Al principio, con T alta, el sistema explora con libertad y escapa de los óptimos locales; a medida que la temperatura baja según un programa de enfriamiento, las soluciones peores se aceptan cada vez menos y la búsqueda se concentra en afinar.

Para qué sirve

Es una herramienta clásica de optimización combinatoria, donde el número de soluciones posibles crece de forma explosiva. Dos trabajos primarios fijan usos concretos: Kirkpatrick estudió en 1984 diseño asistido de circuitos, partición de grafos y el problema del viajante; y un artículo de 1999 evaluó dos heurísticas para planificación job-shop. Eso demuestra aplicaciones, no cuánto se usa hoy cada una. Su atractivo es su sencillez y que no necesita conocer la estructura interna del problema.

Sus límites

El recocido simulado no está exento de inconvenientes. Su convergencia es lenta y sus resultados dependen mucho del programa de enfriamiento: si se enfría demasiado rápido, se estanca en una solución mediocre; si demasiado despacio, tarda una eternidad. Hajek demostró en 1988 una condición necesaria y suficiente para converger en probabilidad al conjunto de mínimos globales; para el programa T(t)=c/log(1+t), c debe alcanzar al menos la profundidad del mínimo local no global más profundo. Es una garantía asintótica bajo condiciones precisas, no una promesa de rendimiento práctico rápido.