Recocido Simulado

El recocido simulado, propuesto por Kirkpatrick Gelatt y Vecchi (1983) y de forma independiente por Cerny (1985), es una metaheurística de solución única que emula el enfriamiento lento de metales para formar estructuras cristalinas de baja energía. El algoritmo comienza con una temperatura inicial alta T0 y evalúa cada movimiento del vecindario mediante Δ = f(nuevo) − f(actual): los movimientos que mejoran (Δ < 0) se aceptan siempre y los que empeoran (Δ > 0) con probabilidad Metropolis P = exp(−Δ / T). La aceptación de movimientos empeorantes es el rasgo definitorio que permite escapar de cuencas de óptimo local. La temperatura desciende según un plan de enfriamiento: geométrico T_k+1 = αT_k con α ∈ [0.85, 0.99], logarítmico (Geman y Geman 1984, convergente en teoría pero lento) o adaptativo. El plan de enfriamiento, la temperatura inicial (regla práctica: tasa de aceptación inicial cercana al 80 por ciento), el número de intentos por temperatura y el criterio de parada son parámetros críticos. Frente a los algoritmos genéticos, mantiene una sola solución, no requiere población y usa memoria mínima. Aplicaciones: colocación VLSI, ruteo de vehículos, scheduling, layout de instalaciones. En problemas combinatorios compite estrechamente con tabu search. Referencias: Aarts y Korst (1989), Henderson Jacobson Johnson (2003).