El recocido simulado (simulated annealing, SA) es una técnica metaheurística estocástica potente diseñada para abordar problemas de optimización global en espacios de búsqueda grandes y complejos. Inspirado en el proceso de recocido de la metalurgia, el algoritmo explora ampliamente el espacio de soluciones a «temperaturas» elevadas y se centra gradualmente en las regiones más prometedoras a medida que la temperatura desciende. Su característica distintiva es la capacidad de aceptar soluciones peores con una probabilidad que disminuye con el tiempo, lo que le permite escapar de mínimos locales y evitar la convergencia prematura.
Este método es particularmente eficaz para problemas NP-hard, como el problema del viajante, la planificación de tareas y el diseño de circuitos, en los que los algoritmos exactos resultan inviables desde el punto de vista computacional. Aunque el SA no garantiza la obtención del óptimo global, produce soluciones de alta calidad en tiempos de cálculo prácticos de forma consistente. El éxito del algoritmo depende en gran medida del ajuste preciso de sus parámetros, como la temperatura inicial, el esquema de enfriamiento y la longitud de las iteraciones en cada nivel de temperatura. Su robustez y versatilidad lo han consolidado como una herramienta fundamental en campos tan diversos como la ingeniería estructural, la química molecular, el procesamiento de imágenes y la asignación de recursos.
Principios fundamentales y origen
El recocido simulado (SA), también conocido como templado simulado, recristalización simulada o enfriamiento simulado, es una técnica metaheurística que adapta un proceso físico al ámbito de la optimización.
- Definición: El SA es un método estocástico de optimización global. Su estrategia se basa en la analogía con el recocido metalúrgico, proceso en el que un material se calienta y luego se enfría de forma controlada para alcanzar una estructura cristalina estable y de baja energía.
- Mecanismo central: El algoritmo mejora las soluciones de forma iterativa. Acepta incondicionalmente las soluciones candidatas que son mejores que la actual y, con una probabilidad decreciente, también acepta movimientos que la empeoran. Esta aceptación controlada de transiciones «cuesta arriba» es clave para evitar quedar atrapado en óptimos locales y para permitir un cambio gradual de la exploración a la explotación del espacio de soluciones.
- Origen: El SA fue desarrollado de forma independiente por Kirkpatrick, Gelatt y Vecchi (1983) y por Černý (1985). Su base teórica se encuentra en el algoritmo de Metropolis (1953), que se aplicó originalmente a la simulación de sistemas termodinámicos.
Mecanismo de funcionamiento y analogía termodinámica.
El SA establece un paralelismo directo entre la optimización y la termodinámica estadística, donde los conceptos se relacionan de la siguiente manera:
- Función objetivo: corresponde a la energía de un sistema físico. El objetivo es minimizar dicha energía.
- Solución óptima: representa una estructura cristalina de baja energía, que es un estado estable del sistema.
- Temperatura (T): Es el parámetro que regula el comportamiento estocástico. A altas temperaturas, el sistema es más volátil y explora más; a bajas, se estabiliza.
El proceso de optimización se rige por el factor de Boltzmann, exp(-ΔE/T), donde ΔE es el cambio en la energía (valor de la función objetivo) de la nueva configuración y T es la temperatura actual.
El criterio de aceptación de una nueva solución s' a partir de una solución actual s sigue la regla de Metropolis:
- Si el cambio de energía
ΔE = f(s') - f(s)es menor o igual a cero (ΔE ≤ 0), la nueva solución es mejor o igual, por lo que se acepta siempre. - Si el cambio de energía es positivo (
ΔE > 0), la nueva solución es peor. Se acepta con una probabilidadP = exp(-ΔE/T).
Esta probabilidad es alta a temperaturas elevadas, lo que fomenta la diversificación y la exploración global. A medida que T se acerca a cero, la probabilidad de aceptar malos movimientos disminuye drásticamente, haciendo que el algoritmo sea más selectivo y se comporte de manera “codiciosa” (greedy), intensificando la búsqueda en regiones prometedoras.
Componentes clave del algoritmo
El rendimiento del SA depende de la calibración precisa de su «esquema de enfriamiento». Sus componentes matemáticos y de procedimiento clave son los siguientes:
| Componente | Descripción |
| Temperatura inicial (T₀) | Se elige un valor lo suficientemente alto como para asegurar una alta probabilidad de aceptación inicial, lo que permite una exploración amplia del espacio de soluciones. El método de Medina (2001) sugiere ajustarla para que la tasa de aceptación de soluciones de mayor coste se sitúe entre el 20% y el 40%. |
| Esquema de enfriamiento | Define cómo disminuye la temperatura. El más común es el esquema geométrico: T(t+1) = α * Tt, donde α es un coeficiente de reducción típicamente en el rango de [0.8, 0.99]. Una refrigeración rápida corre el riesgo de atrapar la solución en estados metaestables, mientras que una lenta mejora la fiabilidad a un mayor coste computacional. |
| Longitud de la cadena de Markov | Es el número de iteraciones que se ejecutan en cada nivel de temperatura. Debe ser lo suficientemente largo como para que el sistema alcance un estado de equilibrio a esa temperatura antes de seguir enfriando. |
| Criterio de parada | Determina cuándo finaliza el algoritmo. Las condiciones comunes incluyen que la temperatura caiga por debajo de un umbral predefinido (p. ej., el 1% de la temperatura inicial) o que las mejoras en la solución se estabilicen. |
Variantes y mejoras
Con el fin de mejorar la eficiencia y la adaptabilidad del SA, se han desarrollado diversas variantes y modificaciones.
- Estrategia “Best-So-Far”: Mantiene en memoria la mejor solución encontrada hasta el momento, independientemente del estado actual de la búsqueda.
- Esquemas de recalentamiento: Cuando el sistema se estanca en un óptimo local, la temperatura se incrementa temporalmente para promover una nueva fase de exploración (Dowsland, 1993).
- Hibridación: Se integra el SA con otros métodos, como algoritmos genéticos, branch-and-bound o programación entera, para aprovechar sus fortalezas complementarias.
- Implementaciones paralelas: Distribuyen los ensayos entre múltiples procesadores para mejorar la escalabilidad y la velocidad de convergencia.
- Evaluaciones aproximadas de ΔE: Se utilizan en problemas de alta dimensionalidad para acelerar el cálculo.
Threshold Accepting (TA)
Una variante notable es el Threshold Accepting (TA), introducido por Dueck y Scheuer en 1990. Este método sustituye la regla de aceptación probabilística por una regla determinista: se acepta una solución subóptima si su empeoramiento es inferior a un umbral predefinido.
- Se acepta una solución subóptima si su empeoramiento (degradación) es inferior a un umbral predefinido.
Este umbral disminuye gradualmente durante la búsqueda, de forma análoga al esquema de enfriamiento del SA.
Estudios empíricos han demostrado que el TA puede tener un rendimiento comparable o incluso superior al del SA en problemas de planificación, programación y asignación de recursos (Lin et al., 1995).
Dominios de aplicación y ejemplos notables
El SA ha demostrado ser una herramienta versátil y fiable, especialmente para problemas NP-hard para los que no existen solucionadores específicos.
| Dominio | Aplicación específica y referencia |
| Enrutamiento | Resolución del Problema del Viajante de Comercio (TSP) y sus variantes con restricciones de tiempo (Kirkpatrick et al., 1983). |
| Planificación | Solución de problemas de job-shop scheduling mediante un equilibrio entre diversificación e intensificación (van Laarhoven et al., 1992). |
| Asignación de recursos | Manejo de la complejidad del Problema de Asignación Cuadrática (QAP) en el diseño de instalaciones (Connolly, 1990). |
| Procesamiento de imágenes | Métodos de relajación estocástica para resolver problemas de segmentación y restauración de imágenes (Geman y Geman, 1984). |
| Química molecular | Herramienta estándar para la cristalografía macromolecular y el refinamiento conformacional (Brünger, 1992). |
| Ingeniería estructural | – Diseño de puentes de hormigón pretensado (Martí et al., 2013).
– Optimización paramétrica de muros de contención (Yepes et al., 2008). – Optimización del tamaño y la disposición de las estructuras de acero (Bresolin et al., 2022). – Minimización de costes e impacto ambiental (CO₂) en el hormigón armado (Santoro y Kripka, 2020; Medeiros y Kripka, 2014). – Diseño de estructuras marinas bajo incertidumbre (Toğan, 2012). |
Factores críticos para el rendimiento.
El éxito en la aplicación del SA depende en gran medida de la formulación del problema:
- Representación del espacio de configuración: La forma en que se define matemáticamente el espacio de soluciones es fundamental.
- Definición de movimientos: Es esencial elegir un conjunto adecuado de «movimientos» o ajustes que permitan pasar de una solución a otra vecina. Las representaciones efectivas aseguran que las transiciones entre mínimos locales impliquen pequeñas diferencias de coste, lo que reduce las «barreras de energía».
- Función objetivo: Una función objetivo bien elegida puede modificar la distribución de los mínimos locales hacia valores de menor coste promedio, lo que aumenta la probabilidad de encontrar soluciones mejores.
- Manejo de restricciones: En los problemas con restricciones, la búsqueda puede limitarse a regiones factibles o pueden permitirse soluciones infactibles penalizándolas en la función objetivo. Este último enfoque puede simplificar la estructura de vecindad y suavizar la topología del paisaje de búsqueda, lo que mejora la convergencia.
Os dejo un vídeo que grabé hace unos años para explicar esta metaheurística. Espero que os sea de interés.
Referencias:
Bresolin, J. M., Pravia, Z. M., & Kripka, M. (2022). Discrete sizing and layout optimization of steel truss-framed structures with Simulated Annealing Algorithm. Steel and Composite Structures, 44(5), 603–617. https://doi.org/10.12989/scs.2022.44.5.603
Brünger, A. T. (1992). X-PLOR Version 3.1: A system for X-ray crystallography and NMR. Yale University Press.
Černý, V. (1985). Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 41–51. https://doi.org/10.1007/BF00940812
Connolly, D. T. (1990). An improved annealing scheme for the QAP. European Journal of Operational Research, 46(1), 93–100. https://doi.org/10.1016/0377-2217(90)90301-Q
Dowsland, K. A. (1993). Simulated annealing. In C. R. Reeves (Ed.), Modern heuristic techniques for combinatorial problems (pp. 20–69). Wiley.
Dueck, G., & Scheuer, T. (1990). Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90(1), 161–175. https://doi.org/10.1016/0021-9991(90)90201-B
Geman, S., & Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6), 721–741. https://doi.org/10.1109/TPAMI.1984.4767596
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
Lin, C. K. Y., Haley, K. B., & Sparks, C. (1995). A comparative study of threshold accepting and simulated annealing algorithms in three scheduling problems. European Journal of Operational Research, 83(2), 330–346. https://doi.org/10.1016/0377-2217(95)00011-E
Martí, J. V., González-Vidosa, F., Yepes, V., & Alcalá, J. (2013). Design of prestressed concrete precast road bridges with hybrid simulated annealing. Engineering Structures, 48, 342–352. https://doi.org/10.1016/j.engstruct.2012.09.014
Medeiros, F., & Kripka, M. (2014). Optimization of reinforced concrete columns according to cost and CO₂ emissions. Engineering Structures, 59, 185–194. https://doi.org/10.1016/j.engstruct.2013.10.045
Medina, J. R. (2001). Estimation of incident and reflected waves using simulated annealing. Journal of Waterway, Port, Coastal and Ocean Engineering, 127(4), 213–221. https://doi.org/10.1061/(ASCE)0733-950X(2001)127:4(213)
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087–1092. https://doi.org/10.1063/1.1699114
Santoro, J. F., & Kripka, M. (2020). Minimizing environmental impact in the design of reinforced concrete elements using simulated annealing. Computers and Concrete, 25(2), 111–118. https://doi.org/10.12989/cac.2020.25.2.111
Toğan, V. (2012). Optimization of monopod offshore tower under uncertainties with gradient-based and gradient-free optimization algorithms. Advances in Structural Engineering, 15(12), 2021–2032. https://doi.org/10.1260/1369-4332.15.12.2021
van Laarhoven, P. J. M., & Aarts, E. H. L. (1987). Simulated annealing: Theory and applications (Mathematics and Its Applications, Vol. 37). Springer. https://doi.org/10.1007/978-94-015-7744-1
van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992). Job shop scheduling by simulated annealing. Operations Research, 40(1), 113–125. https://doi.org/10.1287/opre.40.1.113
Yepes, V., Alcalá, J., Perea, C., & González-Vidosa, F. (2008). A parametric study of optimum earth retaining walls by simulated annealing. Engineering Structures, 30(3), 821–830. https://doi.org/10.1016/j.engstruct.2007.05.023
Yepes, V. (2026). Heuristic Optimization Using Simulated Annealing. In: Kulkarni, A.J., Mezura-Montes, E., Bonakdari, H. (eds) Encyclopedia of Engineering Optimization and Heuristics. Springer, Singapore. https://doi.org/10.1007/978-981-96-8165-5_48-1
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
