Categoría: optimización

Introducción: Atrapado en lo «suficientemente bueno».

¿Alguna vez has sentido que encontraste una solución funcional a un problema, pero tenías la persistente sensación de que existía una respuesta mucho mejor? En la vida y en la tecnología, es fácil quedarse atascado en una solución «buena», pero no óptima, en un callejón sin salida conocido como «mínimo local». Salir de ahí requiere una estrategia poco convencional.

Es aquí donde entra en juego el recocido simulado, una ingeniosa metaheurística estocástica que toma su inspiración de la metalurgia. Desarrollado de forma independiente por Kirkpatrick, Gelatt y Vecchi en 1983 y por Černý en 1985, este algoritmo es, en esencia, una estrategia de búsqueda inteligente que utiliza la aleatoriedad de forma controlada para encontrar soluciones óptimas en problemas de gran complejidad.

Este artículo explora las lecciones más sorprendentes y contraintuitivas que este poderoso algoritmo puede enseñarnos para abordar y resolver problemas verdaderamente complejos.

1. El secreto está en la metalurgia: un algoritmo que piensa como un herrero.

La genialidad del recocido simulado radica en su analogía directa con el proceso de recocido de metales. El herrero calienta el metal a altas temperaturas y luego lo enfría lentamente y de forma controlada para eliminar sus imperfecciones y lograr una estructura interna sólida y estable. El algoritmo hace exactamente lo mismo, pero en el mundo abstracto de los datos y las soluciones.

Los conceptos clave de esta analogía son:

• «Temperatura» alta: al principio, el algoritmo opera a una «temperatura» elevada. Esto corresponde a una fase de exploración amplia, en la que se consideran muchísimas soluciones posibles, incluso las que parecen malas, para obtener una visión global del problema.
• «Enfriamiento» controlado: a medida que avanza el proceso, la «temperatura» se reduce gradualmente. Este «enfriamiento» suele seguir un programa geométrico (como Tt + 1 = α·Tt), lo que obliga al algoritmo a ser más selectivo. Se pasa de la exploración a la explotación, enfocándose progresivamente en las regiones más prometedoras.
• «Energía» del sistema: en el algoritmo, la «energía» de una configuración corresponde a la función objetivo que se busca optimizar (por ejemplo, minimizar el coste, la distancia o el error).
• «Estructura cristalina estable» de baja energía: el objetivo final del recocido es lograr un estado de mínima energía que, en el ámbito de la optimización, representa la solución óptima o casi óptima del problema.

2. La estrategia contraintuitiva: aceptar un empeoramiento para poder mejorar.

La característica más paradójica y, a la vez, más poderosa del recocido simulado es su capacidad para aceptar movimientos que, en un principio, empeoran la solución actual. Esa es la esencia de la exploración: a diferencia de los algoritmos «codiciosos» que solo aceptan mejoras, este método sabe que, a veces, hay que atravesar un pequeño valle para escalar una montaña más alta.

No se trata de un error, sino de una estrategia deliberada para evitar quedar atrapado en los mínimos locales. Antes de reducir la temperatura, el algoritmo ejecuta una serie de iteraciones (una cadena de Markov) para explorar a fondo el entorno de la solución actual. La probabilidad de aceptar un «mal» movimiento es mayor cuando la «temperatura» es alta y disminuye a medida que el sistema se «enfría», según el factor de Boltzmann exp(-ΔE/T). Al principio, la exploración es agresiva, pero al final el algoritmo se vuelve mucho más selectivo.

«Esta aceptación controlada de transiciones no mejoradoras permite al algoritmo escapar de los mínimos locales y evitar una convergencia prematura».

3. La perfección es enemiga de lo práctico: por qué «casi óptimo» es un gran resultado.

Teóricamente, para garantizar que el recocido simulado encuentre la solución globalmente óptima, podría requerir un tiempo de ejecución infinito. Sin embargo, su verdadero valor no radica en la perfección teórica, sino en su gran pragmatismo. La lección fundamental aquí es el equilibrio entre la perfección teórica y la aplicación práctica.

El algoritmo «produce de forma consistente soluciones de alta calidad en escalas de tiempo computacionales prácticas». En ingeniería, logística o finanzas, donde los recursos y el tiempo son limitados, una solución excelente entregada a tiempo es mucho más valiosa que una solución perfecta que nunca se entrega. El recocido simulado encarna este principio de diseño esencial: optimizar para el mundo real, no para un ideal teórico.

4. De vendedores viajeros a puentes de hormigón: la asombrosa versatilidad del algoritmo.

La solidez del recocido simulado se evidencia en la increíble diversidad de problemas que puede resolver. Su capacidad para explorar paisajes de soluciones complejos lo convierte en una herramienta fiable cuando no existen solucionadores específicos para un problema.

Algunos de sus campos de aplicación más impactantes incluyen:

• Rutas y logística: Ha demostrado su eficacia al resolver el problema del vendedor viajero (TSP), encontrando rutas óptimas para conectar múltiples ciudades.
• Procesamiento de imágenes: Se utiliza en la restauración de imágenes dañadas o con ruido, así como para resolver problemas de segmentación complejos.
• Química molecular: Es una herramienta estándar en la cristalografía de macromoléculas que permite determinar la estructura tridimensional de moléculas complejas.
• Ingeniería estructural: Permite realizar optimizaciones de gran impacto, como el diseño de puentes de hormigón pretensado, muros de contención de bajo coste y, en especial, la minimización simultánea del coste y de las emisiones de CO₂ en el diseño de columnas de hormigón armado.

5. A veces, una regla simple supera al azar: la alternativa determinista.

Un giro interesante en la historia de este algoritmo es la variante llamada «Aceptación por umbral» (TA, por sus siglas en inglés). Este método sustituye la regla de aceptación probabilística del recocido simulado por una regla determinista mucho más sencilla.

En lugar de calcular una probabilidad, TA solo acepta una solución peor si el empeoramiento es inferior a un umbral predefinido. Este umbral, al igual que la temperatura del algoritmo original, disminuye gradualmente a lo largo del proceso. Lo sorprendente es el resultado: estudios empíricos han demostrado que, en ciertos problemas como la planificación de tareas, la planificación forestal y la asignación de recursos, este método más simple «puede tener un rendimiento comparable o incluso superior al SA». Una lección de que, a veces, la solución más elegante no es la más compleja.

Conclusión: ¿te atreves a dar un paso atrás?

La gran lección del recocido simulado es una profunda metáfora de la resolución de problemas: el progreso no siempre es una línea recta. La verdadera optimización requiere dominar el cambio gradual, desde una exploración audaz hasta una explotación enfocada. Aceptar retrocesos temporales y controlados no es un signo de fracaso, sino una estrategia inteligente para alcanzar un objetivo mucho más alto a largo plazo.

La próxima vez que te enfrentes a un problema complejo, ¿te atreverás a explorar un camino que parezca peor al principio para encontrar una solución verdaderamente excepcional al final?

En esta conversación puedes escuchar las ideas más interesantes sobre el tema.

Este vídeo resume bien los conceptos más importantes del Simulated Annealing.

Te dejo un documento que puede interesarte.

Recocido_Simulado_Del_Caos_a_la_Solución

Referencia:

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.

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:

1. 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.
2. Si el cambio de energía es positivo (ΔE > 0), la nueva solución es peor. Se acepta con una probabilidad P = 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:

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.

Factores críticos para el rendimiento.

El éxito en la aplicación del SA depende en gran medida de la formulación del problema:

1. Representación del espacio de configuración: La forma en que se define matemáticamente el espacio de soluciones es fundamental.
2. 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».
3. 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.
4. 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.

En este vídeo se recogen bien las principales ideas de este algoritmo.

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.