En el corazón de nuestra civilización digital late un motor invisible que solemos dar por sentado. Lo que en el siglo IX nació como una serie de reglas rígidas para el cálculo algebraico —el legado de Al-Juarismi— ha evolucionado hasta convertirse en el concepto moderno de algoritmo: una sofisticada «receta» diseñada para manipular información mediante operaciones elementales. En la actualidad, los algoritmos no son solo curiosidades matemáticas, sino la infraestructura lógica que decide desde la ruta de un camión de reparto hasta la resistencia de un viaducto de hormigón. Sin embargo, ¿comprendemos realmente las leyes que rigen su eficiencia o somos ciegos ante las reglas que separan lo posible de lo imposible?
El concepto de algoritmo ha evolucionado desde una acepción antigua, centrada en reglas para operaciones algebraicas, hacia una visión moderna: un conjunto prescrito de reglas o instrucciones bien definidas para resolver un problema específico en un número finito de pasos. En esencia, se trata de un método para manipular información mediante operaciones elementales.
A continuación, desvelamos cinco realidades esenciales para navegar por este universo de precisión y complejidad.
1. Los pilares del rigor: más allá del simple «paso a paso».
A menudo se define el algoritmo como una lista de instrucciones, pero para la ciencia de la computación esta definición es insuficiente. Un algoritmo debe ser un baluarte contra la ambigüedad, ese «fantasma en la máquina» que detiene en seco cualquier proceso lógico. Un método solo alcanza la categoría de algoritmo si cumple cuatro condiciones necesarias, pero no suficientes.
Precisión: cada instrucción debe indicar exactamente qué acción realizar, sin margen de interpretación.
Finitud: el proceso debe tener un final garantizado tras un número determinado de pasos.
Efectividad: cada operación debe poder ser ejecutada por el ejecutor (humano o máquina) en un tiempo finito.
Entrada y salida: debe existir un punto de partida de datos y un resultado concreto.
La finitud no es solo una exigencia teórica, sino también una restricción física. En un mundo de recursos limitados, un proceso que no termina nunca no es una solución, sino un abismo de consumo de energía.
2. El enigma de P vs. NP
Existe una frontera que divide los problemas en dos grandes categorías. Por un lado, la clase P, que agrupa los problemas que podemos resolver rápidamente (de forma eficiente). Por otro lado, está la clase NP, que incluye problemas cuya solución, aunque difícil de encontrar, puede verificarse con rapidez una vez que la tenemos. La gran pregunta que obsesiona a los genios desde 1971 es si resolver es intrínsecamente más difícil que verificar.
«¡Hoy en día no se ha podido demostrar que P = NP!»
Científicamente, sabemos que P ⊂ NP, pero el gran misterio radica en el «empate». Si se demostrara que P = NP, significaría que para la mayoría de los retos complejos de nuestra era —desde la criptografía hasta el diseño estructural— existen algoritmos de una eficiencia asombrosa que aún no hemos logrado ver.
3. La tiranía del tiempo: el análisis del «peor caso».
En ingeniería y computación, el rendimiento no es cuestión de suerte. Para medirlo, recurrimos a la teoría del análisis asintótico de funciones, que nos permite predecir cómo crecerá el esfuerzo de cálculo a medida que aumenta la dimensión del problema (n). Para un especialista, no basta con saber cuánto tarda un algoritmo de media; lo vital es el análisis del peor caso. Este define el coste máximo de aplicar el algoritmo a cualquier problema de tamaño n.
Aquí es donde la matemática se vuelve tangible. Imagine que n representa el número de ciudades que un camión debe visitar.
Complejidad polinómica (O(n^k)): El tiempo crece de forma controlada. Estos problemas se consideran «resolubles eficientemente».
Complejidad exponencial: El tiempo de cálculo aumenta de forma exponencial. Un ligero aumento en el número de ciudades puede hacer que el ordenador necesite más tiempo que la edad del universo para hallar la respuesta.
Orden de magnitud de un algoritmo
4. El drama de los problemas NP-completos.
Dentro del vasto territorio de la clase NP, existe una «aristocracia» del caos: los problemas NP-completos (NPC). El ejemplo más célebre es el problema del viajante (O(n² 2^n)). Estos problemas son fascinantes porque están interconectados: si alguien lograra encontrar un algoritmo polinómico para resolver un problema NPC, automáticamente todos los problemas NP pasarían a ser resolubles de manera eficiente.
Mientras ese día no llegue, los problemas NPC representan el muro contra el que choca la potencia bruta. En ellos, añadir un solo dato más a la entrada no solo implica trabajo, sino que multiplica la dificultad hasta el punto de que la realidad física se vuelve incapaz de soportar el cálculo.
5. El arte de la heurística: la sabiduría de lo «suficientemente bueno».
¿Qué debe hacer un ingeniero ante un problema cuya solución perfecta tardaría milenios en aparecer? La respuesta está en las heurísticas y las metaheurísticas. Se trata de algoritmos aproximados que actúan como un «Plan B» inteligente cuando la perfección se convierte en el enemigo de lo posible.
Sin embargo, el orden de los factores sí altera el producto. Si un problema de optimización se presenta en forma algebraica, es imperativo intentar primero las técnicas clásicas. No tiene sentido utilizar una heurística si los métodos Simplex (para problemas lineales) o de gradiente (para problemas no lineales) pueden proporcionarnos la respuesta exacta. Solo cuando estas herramientas fallan o su lentitud resulta inasumible, recurrimos a la intuición algorítmica.
Conclusión: Hacia una nueva frontera de optimización.
El viaje desde las antiguas reglas de cálculo hasta la optimización de las estructuras de hormigón modernas nos enseña que el límite de la ingeniería no está en la potencia de los procesadores, sino en la elegancia de nuestros métodos. El éxito consiste en saber navegar entre el rigor asintótico y la flexibilidad heurística.
En última instancia, nos enfrentamos a una pregunta que definirá el futuro de nuestra capacidad técnica: ¿residirá el progreso en la búsqueda incansable del algoritmo perfecto que demuestre que P = NP o en perfeccionar nuestra capacidad para utilizar la intuición heurística y construir un mundo «suficientemente bueno» antes de que se agote el tiempo?
En esta conversación podéis escuchar las ideas más interesantes sobre este tema.
El vídeo resume bien los conceptos más importantes de la algoritmia y la complejidad computacional.
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.
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
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 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:
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
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
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
Acaban de publicarnos un artículo en Applied Sciences, revista indexada en el JCR. Se trata de la optimización heurística de un depósito elevado de agua de hormigón armado bajo acciones sísmicas. El trabajo se enmarca en el proyecto de investigación HYDELIFE, que dirijo como investigador principal en la Universitat Politècnica de València.
Este artículo trata del diseño sísmico de las columnas de 35 depósitos elevados de almacenamiento de agua de hormigón armado. Los depósitos constan de un tronco cónico superior, una columna de sección cuadrada hueca variable y una cimentación superficial sobre una capa de arena. Las cinco alturas de columna consideradas son de 20, 25, 30, 35 y 40 m. Los cinco depósitos se someten a siete grados de carga sísmica, caracterizados por la aceleración pico del suelo de referencia, según el Eurocódigo 8. Los depósitos elevados se diseñan según las prescripciones completas del Eurocódigo 2, del Eurocódigo 8 y del Código Estructural español. Esto incluye las cargas variables por sismicidad, viento, nieve, etc., junto con la acción del peso propio y las cargas muertas. El método de diseño de optimización considerado es una variante del algoritmo del solterón, un método de aceptación de umbral adaptativo con un movimiento de vecindad basado en el operador de mutación de los algoritmos genéticos. Los resultados de las columnas muestran la alta no linealidad del problema, ya que las fuerzas sísmicas horizontales dependen de la rigidez y la altura de las columnas. Las principales características de los depósitos optimizados proporcionan orientación para el diseño práctico de este tipo de depósitos de agua elevados de hormigón armado.
This paper deals with the seismic column design of 35 elevated RC water storage tanks. Tanks comprise a top conic trunk reservoir, a column with variable hollow square cross-sections, and a shallow foundation on a sand layer. The five-column heights considered are 20, 25, 30, 35, and 40 m. The five tanks are subjected to seven degrees of seismic loading characterized by the reference peak ground acceleration in Eurocode 8. The elevated tanks are designed against the full prescriptions of Eurocode 2, Eurocode 8, and the Spaniard Structural Code of Practice. This includes variable loads for seismicity, wind, snow, etc., as well as the effects of self-weight and dead loads. The optimization design method considered is a variant of the old bachelor algorithm, an adaptive threshold acceptance method with a neighborhood move based on the mutation operator from genetic algorithms. Column results show the high nonlinearity of the problem since the horizontal seismic forces depend on the rigidity and height of the columns. The main features of the optimized tanks give guidance for the practical design of this kind of elevated RC water tank.
Keywords:
Concrete structures; economic optimization; elevated water tanks; old bachelor algorithm; seismic loading; structural design
En ese trabajo se muestran las características principales de los forjados de losa postesa obtenidos tras aplicar métodos heurísticos de optimización. Estos forjados presentan ventajas frente a soluciones más convencionales a partir de ciertas luces. El proceso de diseño de estos forjados se puede plantear como un problema de optimización, que abordado con métodos heurísticos puede formularse de un modo totalmente realista. Se pueden encontrar diseños completos de forjados optimizados no solo con criterios de economía, sino también de sostenibilidad, pudiendo comparar ambos casos. Los resultados obtenidos en este trabajo muestran una clara tendencia a disponer cantos muy estrictos en los resultados óptimos. Aplicando criterios de sostenibilidad se tiende a hormigones de mayores resistencias que con criterios económicos. Finalmente se han realizado pruebas de sensibilidad a los precios, que muestran mucha independencia de los forjados óptimos frente a las variaciones de precios ensayadas.
RODRÍGUEZ-CALDERITA, A.M.; ALCALÁ, J.; YEPES, V.; MARTÍ, J.V. (2013). Optimización heurística aplicada al diseño automático de forjados de losa postesa. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 63-75. ISBN: 978-84-8363-992-4.
Charles Darwin en una fotografía tomada por J.M. Cameron en 1869.
Resulta fascinante comprobar cómo aplicando los mecanismos básicos de la evolución ya descrita por Darwin en su obra fundamental, El origen de las especies por medio de la selección natural, o la preservación de las razas preferidas en la lucha por la vida, publicada en 1859, se pueden generar algoritmos capaces de optimizar problemas complejos. Este tipo de metaheurísticas inspiradas en la Naturaleza ya se comentaron en artículos anteriores cuando hablamos de la optimización por colonias de hormigas o de la cristalización simulada. Aunque es un algoritmo ampliamente conocido por la comunidad científica, voy a intentar dar un par de pinceladas con el único afán de divulgar esta técnica. La verdad es que las implicaciones filosóficas que subyacen tras la teoría de Darwin son de una profundidad difícil de entender cuando se lleva a sus últimos extremos. Pero el caso es que estos algoritmos funcionan perfectamente en la optimización de estructuras de hormigón, problemas de transporte y otros problemas difíciles de optimización combinatoria.
Para aquellos interesados, os paso en las referencias un par de artículos donde hemos aplicado los algoritmos genéticos para optimizar rutas de transporte aéreo o pilas de puente huecas de hormigón armado.
Sin embargo, para aquellos otros que queráis un buen libro para pensar, os recomiendo «La peligrosa idea de Darwin», de Daniel C. Dennett. A más de uno le hará remover los cimientos más profundos de sus creencias. Os paso la referencia al final.
Básicamente, los algoritmos genéticos “Genetic Algorithms, GA”, simulan el proceso de evolución de las especies que se reproducen sexualmente. De manera muy general, se puede decir que en la evolución de los seres vivos, el problema al que cada individuo se enfrenta diariamente es el de la supervivencia. Para ello cuenta, entre otras, con las habilidades innatas provistas en su material genético. A nivel de los genes, el problema consiste en la búsqueda de aquellas adaptaciones beneficiosas en un medio hostil y cambiante. Debido en parte a la selección natural, cada especie gana cierta “información” que es incorporada a sus cromosomas.
Durante la reproducción sexual, un nuevo individuo, diferente de sus padres, se genera a través de la acción de dos mecanismos fundamentales: El primero es el cruzamiento, que combina parte del patrimonio genético de cada progenitor para elaborar el del nuevo individuo; el segundo es la mutación, que supone una modificación espontánea de esta información genética. La descendencia será diferente de los progenitores, pero mantendrá parte de sus características. Si los hijos heredan buenos atributos de sus padres, su probabilidad de supervivencia será mayor que aquellos otros que no las tengan. De este modo, los mejores tendrán altas probabilidades de reproducirse y diseminar su información genética a sus descendientes.
Holland (1975) estableció por primera vez una metaheurística basada en la analogía genética. Un individuo se puede asociar a una solución factible del problema, de modo que se pueda codificar en forma de un vector binario “string”. Entonces un operador de cruzamiento intercambia cadenas de los padres para producir un hijo. La mutación se configura como un operador secundario que cambia, con una probabilidad pequeña, algunos elementos del vector hijo. La aptitud del nuevo vector creado se evalúa de acuerdo con una función objetivo.
Los pasos a seguir con esta metaheurística serían los siguientes:
Generar una población de vectores (individuos).
Mientras no se encuentre un criterio de parada:
Seleccionar un conjunto de vectores padre, que serán reemplazados de la población.
Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores hijo.
Aplicar una mutación a cada descendiente.
Evaluar a los hijos.
Introducir a los hijos en la población.
Eliminar a aquellos individuos menos eficaces.
Normalmente este proceso finaliza después de un numero determinado de generaciones o cuando la población ya no puede mejorar. La selección de los padres se elige probabilísticamente hacia los individuos más aptos. Al igual que ocurre con en la Naturaleza, los sujetos con mayor aptitud diseminan sus características en toda la población.
Esta descripción de los GA se adapta a cada situación concreta, siendo habitual la codificación de números enteros en vez de binarios. Del mismo modo se han sofisticado los distintos operadores de cruzamiento y mutación.
DENNETT, D.C. (1999). La peligrosa idea de Darwin. Galaxia Gutenberg. Círculo de Lectores, Barcelona.
HOLLAND, J.H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.
MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections.Computers & Structures, 88: 375-386. ISSN: 0045-7949. (link)
MEDINA, J.R.; YEPES, V. (2003). Optimization of touristic distribution networks using genetic algorithms. Statistics and Operations Research Transactions, 27(1): 95-112. ISSN: 1696-2281. (pdf)
PONZ-TIENDA, J.L.; YEPES, V.; PELLICER, E.; MORENO-FLORES, J. (2013). The resource leveling problem with multiple resources using an adaptive genetic algorithm. Automation in Construction, 29(1):161-172. DOI:http://dx.doi.org/10.1016/j.autcon.2012.10.003. (link)
YEPES, V. (2003). Apuntes de optimización heurística en ingeniería. Editorial de la Universidad Politécnica de Valencia. Ref. 2003.249. Valencia, 266 pp. Depósito Legal: V-2720-2003.
Figura 1. Desgraciadamente, no existe la comida gratis. https://medium.com/@LeonFedden/the-no-free-lunch-theorem-62ae2c3ed10c
Después de años impartiendo docencia en asignaturas relacionadas con la optimización heurística de estructuras de hormigón, y tras muchos artículos científicos publicados y más donde he sido revisor de artículos de otros grupos de investigación, siempre se plantea la misma pregunta: De todos los algoritmos que utilizamos para optimizar, ¿cuál es el mejor? ¿Por qué dice en su artículo que su algoritmo es el mejor para este problema? ¿Por qué no nos ponemos de acuerdo?
Para resolver esta cuestión, dos investigadores norteamericanos, David Wolpert y William Macready, publicaron un artículo en 1997 donde establecieron un teorema denominado «No free lunch«, que traducido sería algo así como «no hay comida gratis». Dicho teorema establece que, por cada par de algoritmos de búsqueda, hay tantos problemas en el que el primer algoritmo es mejor que el segundo como problemas en el que el segundo algoritmo es mejor que el primero.
Este teorema revolucionó la forma de entender el rendimiento de los algoritmos. Incluso una búsqueda aleatoria en el espacio de soluciones podría dar mejores resultados que cualquier algoritmo de búsqueda. La conclusión es que no existe un algoritmo que sea universalmente mejor que los demás, pues siempre habrá casos donde funcione peor que otros, lo cual significa que todos ellos se comportarán igual de bien (o de mal) en promedio.
De hecho, se podría decir que un experto en algoritmos genéticos podría diseñar un algoritmo genético más eficiente que, por ejemplo, un recocido simulado, y viceversa. Aquí el arte y la experiencia en un problema y en una familia de algoritmos determinados, suele ser decisivo. En la Figura 2 se puede ver cómo un algoritmo muy especializado, que conoce bien el problema, puede mejorar su rendimiento, pero pierde la generalidad de poder usarse en cualquier tipo de problema de optimización que no sea para el que se diseñó.
Figura 2. El uso del conocimiento del problema puede mejorar el rendimiento, a costa de la generalidad. https://medium.com/@LeonFedden/the-no-free-lunch-theorem-62ae2c3ed10c
¿Qué consecuencias obtenemos de este teorema? Lo primero, una gran decepción, pues hay que abandonar la idea del algoritmo inteligente capaz de optimizar cualquier problema. Lo segundo, que es necesario incorporar en el algoritmo cierto conocimiento específico del problema, lo cual equivale a una «carrera armamentística» para cada problema de optimización. Se escriben y escribirán miles de artículos científicos donde un investigador demuestre que su algoritmo es mejor que otro para un determinado problema.
Una forma de resolver este asunto de incorporar conocimiento específico del problema es el uso de la inteligencia artificial en ayuda de las metaheurísticas. Nuestro grupo de investigación está abriendo puertas en este sentido, incorporando «deep learning» en el diseño de los algoritmos (Yepes et al., 2020; García et al., 2020a; 2020b), o bien redes neuronales (García-Segura et al., 2017). Incluso, en este momento, me encuentro como editor de un número especial de la revista Mathematics (primer decil del JCR) denominado: “Deep Learning and Hybrid-Metaheuristics: Novel Engineering Applications”, al cual os invito a enviar vuestros trabajos de investigación.
Si nos centramos en un tipo de problema determinado, por ejemplo, la optimización de estructuras (puentes, pórticos de edificación, muros, etc.), el teorema nos indica que necesitamos gente formada y creativa para optimizar el problema concreto al que nos enfrentamos. Es por ello que no existen programas comerciales eficientes capaces de adaptarse a cualquier estructura para optimizarla. Tampoco son eficientes las herramientas generales «tools» que ofrecen algunos programas como Matlab para su uso inmediato e indiscriminado.
Por tanto, no se podrá elegir entre dos algoritmos solo basándose en lo bien que trabajaron anteriormente en un problema determinado, pues en el siguiente problema pueden optimizar de forma deficiente. Por tanto, se exige conocimiento intrínseco de cada problema para optimizarlo. Es por ello que, por ejemplo, un experto matemático o informático no puede, sin más, dedicarse a optimizar puentes atirantados.
Figura 1. Diseño tradicional de estructuras por prueba y error (Yepes, 2017)
El diseño de las estructuras se ha basado fundamentalmente en la experiencia del ingeniero proyectista. La topografía y las condiciones de tráfico, entre otros, determinan el diseño de un puente. A partir de ahí, las dimensiones de la sección transversal, el tipo de hormigón y la disposición general de las armaduras se definen atendiendo a la experiencia profesional y a las recomendaciones y criterios de diseño (Figura 1). A continuación, se ajustan el resto de variables, tras comprobar el cumplimiento de los estados límite último y de servicio. Si el proyectista quiere mejorar el diseño propuesto, normalmente se realiza un proceso de prueba y error, de forma que tras varios tanteos, se intenta reducir el consumo de materiales, y por tanto, el coste de la estructura. Frente a este planteamiento, los métodos heurísticos emplean técnicas basadas en la inteligencia artificial para seleccionar un diseño, analizar la estructura, controlar las restricciones y rediseñar la estructura modificando las variables hasta conseguir optimizar la función objetivo.
Cohn y Dinovitzer (1994) revisaron la investigación realizada en su momento en relación con la optimización de las estructuras y señalaron la brecha existente entre los estudios teóricos y la aplicación en problemas estructurales reales. Sarma y Adeli (1998) analizaron años más tarde los estudios relacionados con la optimización matemática de las estructuras, complementada más recientemente por Hare et al. (2013) que estudiaron la aplicación de los algoritmos heurísticos en la optimización estructural. Los algoritmos heurísticos difieren en cuanto a planteamiento y aplicabilidad de los métodos matemáticos exactos. De hecho, la optimización heurística resulta muy efectiva pues, aunque no garantiza la obtención del óptimo global del problema, proporciona soluciones casi óptimas en tiempos de cálculo razonables. Esta ventaja cobra importancia en la optimización de estructuras reales, donde el número de variables crece extraordinariamente de forma que desborda el tiempo de cálculo de los métodos exactos de optimización. Además, la programación matemática requiere el cálculo de gradientes de las restricciones, mientras que la optimización heurística incorpora las restricciones de diseño de una manera directa (Lagaros et al., 2006).
Las técnicas metaheurísticas utilizan estrategias de búsqueda para localizar óptimos locales en grandes espacios de soluciones de forma efectiva. Un ejemplo de ello son los Algoritmos Genéticos (Genetic Algorithms, GAs), que son procedimientos de búsqueda poblacionales inspirados en la evolución natural (Holland, 1975). Así, los GAs generan soluciones de alta calidad a través del cruce genético con otros individuos de una población y la mutación de algunas de sus características a lo largo de generaciones. Los padres suelen seleccionarse atendiendo a su aptitud (Coello, 1994) y los hijos mantienen ciertas características de sus padres. En cada generación sobreviven los hijos con mayores aptitudes. Además, para evitar la convergencia prematura del algoritmo, se utiliza un operador de mutación, al igual que ocurre en la Naturaleza, que cambia aleatoriamente de vez en cuando alguna de las características de las nuevas soluciones. Una variante a esta técnica son los Algoritmos Meméticos (Moscato, 1989), donde cada individuo de la nueva generación se mejora mediante una búsqueda local con el objetivo de mejorar los genes para que los padres obtengan mejores resultados en las siguientes generaciones. Esta técnica, por tanto, aplica los GAs a poblaciones de óptimos locales.
La inteligencia de enjambre (swarm intelligence) es una metaheurística poblacional empleada en los problemas de optimizacón. Estos algoritmos imitan el comportamiento colectivo de los sistemas descentralizados y auto-organizados, tales como algunas colonias de insectos, basándose en la interacción entre los vecinos, pero que siguen un patrón global. Los algoritmos de enjambre difieren en filosofía de los algoritmos genéticos porque utilizan la cooperación en lugar de la competencia (Dutta et al., 2011). Entre los algoritmos pertenecientes a este grupo, basados en el comportamiento biológico, destaca la optimización de colonias de hormigas (Ant Colony Optimization, ACO), la optimización de enjambre de partículas (Particle Swarm Optimization, PSO), las colonias de abejas artificiales (Artificial Bee Colony, ABC), la optimización en enjambres de luciérnagas (Glowworm Swarm Optimization, GSO), entre otros. ACO basa su estrategia en el comportamiento de las hormigas, que dejan un rastro de feromonas para encontrar alimento de forma efectiva (Colorni et al., 1991); PSO simula un sistema social simplificado (Kennedy y Eberhart, 1995); ABC imita el comportamiento alimentario forrajero de las abejas (Karaboga y Basturk, 2008); GSO imita un movimiento de las luciérnagas hacia los vecinos más brillantes (Krishnanand y Ghose, 2009).
Las metaheurísticas poblacionales presentan una amplia capacidad de búsqueda en paralelo y una fuerte robustez. Sin embargo, para mejorar la intensificación de la búsqueda, estos algoritmos suelen combinarse con otras heurísticas de búsqueda local. Esta hibridación consigue explotar la diversificación en la búsqueda poblacional con la intensificación de la búsqueda local. Luo y Zhang (2011) comprobaron que el algoritmo híbrido presenta una convergencia más rápida, una mayor precisión y es más efectivo en la optimización de problemas ingenieriles. Blum et al. (2011) estudiaron las ventajas de la hibridación de las metaheurísticas en el caso de la optimización combinatoria.
El recocido simulado (Simulated Annealing, SA), propuesto por Kirkpatrick et al. (1983), constituye uno de los algoritmos utilizados en la optimización estructural. Este algoritmo se basa en el fenómeno físico del proceso de recocido de los metales. La energía de un sistema termodinámico se compara con la función de coste evaluada para una solución 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” con un parámetro de control al que se denomina temperatura. Su reducción adecuada permite, con una elevada probabilidad, que un sistema termodinámico adquiera un mínimo global de energía. SA presenta la ventaja de admitir soluciones de peor calidad al principio de la búsqueda, lo cual permite eludir óptimos locales de baja calidad. La aceptación por umbrales (Threshold Accepting, TA), propuesto por Dueck y Scheuer (1990), tolera también opciones de peor calidad para eludir los óptimos locales. La diferencia entre SA y TA es que el criterio de aceptación de una solución peor es probabilista en el primer caso y determinista en el segundo. Los algoritmos genéticos se han hibridado con el recocido simulado en el diseño óptimo de puentes prefabricados de hormigón pretensado (Martí et al., 2013; Martí et al., 2016) y vigas en I de hormigón armado (RC) (Yepes et al., 2015a). Otras estrategias de hibridación también han demostrado su eficiencia con PSO (Shieh et al., 2011, Valdez et al., 2011, Wang et al., 2013) y ACO (Behnamian et al, 2009, Chen et al., 2012).
Qu et al. (2011) señalaron la lentitud en la convergencia de los algoritmos GSO; del mismo modo Zhang et al. (2010) apuntaron ciertas deficiencias de estos algoritmos en la búsqueda del óptimo global. Es por ello que se ha hibridado SA con GSO (García-Segura et al., 2014c, Yepes et al., 2015b) para combinar la diversificación de la búsqueda de GSO con la intensificación de la búsqueda de SA para encontrar de forma efectiva un óptimo de elevada calidad. García-Segura et al. (2014c) mostraron cómo un algoritmo híbrido de optimización de enjambre de luciérnagas (SAGSO) obtuvo resultados considerablemente mejores en cuanto a calidad y tiempo de cálculo. SAGSO superó al GSO en términos de eficiencia, precisión y convergencia. Sin embargo, se requiere una buena calibración para garantizar soluciones de alta calidad con un tiempo de cómputo corto.
La búsqueda de la armonía (Harmony Search, HS) constituye una heurística propuesta por Geem et al. (2001) inspirada en el jazz, donde se trata de armonizar u construir sucesiones de acordes razonables. Las notas, los instrumentos y la mejor armonía representan los valores, las variables y el óptimo global. Alberdi y Khandelwal (2015) compararon ACO, GA, HS, PSO, SA y TS en la optimización del diseño de marcos de acero, comprobando que los mejores resultados se obtenían con HS. La búsqueda de la armonía se ha utilizado para optimizar columnas rectangulares de hormigón armado (de Medeiros y Kripka, 2014), forjados compuestos (Kaveh y Shakouri Mahmud Abadi, 2010) y pórticos planos de hormigón armado (Akin y Saka, 2015). Alia y Mandava (2011) recogieron en su trabajo las variantes utilizadas para hibridar con HS. García-Segura et al. (2015) emplearon un algoritmo de búsqueda de la armonía hibridada con la aceptación por umbrales para encontrar diseños óptimos sostenibles de puentes peatonales de hormigón postesado.
La optimización de los puentes atrajo la atención de los ingenieros a partir de la década de los años 70, incluyendo los puentes viga de acero, (Wills, 1973), el refuerzo de los puentes losa (Barr et al., 1989), los puentes viga de hormigón pretensado (Aguilar et al., 1973, Lounis y Cohn, 1993), y los puentes en cajón postesados construidos “in situ” (Bond, 1975; Yu et al., 1986). Desde la aparición de la inteligencia artificial, se ha puesto mayor énfasis en el uso de técnicas de optimización heurística para optimizar las estructuras. Srinivas y Ramanjaneyulu (2007) usaron redes neuronales artificiales y algoritmos genéticos para optimizar el coste de un puente de vigas en T. Rana et al. (2013) propusieron una optimización evolutiva para minimizar el coste de una estructura de puente continuo de hormigón pretensado de dos tramos. Martí et al. (2013) implementaron un algoritmo de recocido simulado híbrido para encontrar las soluciones más económicas de puentes prefabricados de hormigón pretensado de vigas artes. El uso de refuerzos de fibra de acero en ese tipo de puente se estudió posteriormente con algoritmos meméticos (Martí et al., 2015). Se propusieron algoritmos genéticos para optimizar las cubiertas poliméricas reforzadas con fibras híbridas y los puentes atirantados (Cai y Aref, 2015).
También se han optimizado otro tipo de estructuras con algoritmos heurísticos, como los forjados prefabricados (de Albuquerque et al., 2012), columnas de hormigón armado (Park et al., 2013; Nigdeli et al., 2015), columnas de acero (Kripka y Chamberlain Pravia, 2013), marcos espaciales de acero (Degertekin et al., 2008), marcos de hormigón armado (Camp y Huq, 2013), pórticos de hormigón armado (Payá-Zaforteza et al., 2010), vigas en I de hormigón armado (García-Segura et al., 2014c; Yepes et al., 2015a), pórticos de carreteras (Perea et al., 2008), pilas altas de viaductos (Martínez et al., 2011; 2013), muros de contención (Gandomi et al., 2015; Pei y Xia, 2012; Yepes et al., 2008, 2012; Molina-Moreno et al., 2017a), zapatas de hormigón armado (Camp y Assadollahi, 2013; Camp y Huq, 2013), bóvedas de pasos inferiores en carreteras (Carbonell et al., 2011) y estribos de puentes (Luz et al., 2015).
Akin, A.; Saka, M.P. (2015). Harmony search algorithm based optimum detailed design of reinforced concrete plane frames subject to ACI 318-05 provisions. Computers & Structures, 147, 79–95.
Alberdi, R.; Khandelwal, K. (2015). Comparison of robustness of metaheuristic algorithms for steel frame optimization. Engineering Structures, 102, 40–60.
Alia, O.M.; Mandava, R. (2011). The variants of the harmony search algorithm: an overview. Artificial Intelligence Review, 36(1), 49–68.
Behnamian, J.; Zandieh, M.; Fatemi Ghomi, S.M.T. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 36(6), 9637–9644.
Blum, C.; Puchinger, J.; Raidl, G.R.; Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11(6), 4135–4151.
Bond, D. (1975). An examination of the automated design of prestressed concrete bridge decks by computer. Proceedings of the Institution of Civil Engineers, 59(4), 669–697.
Cai, H.; Aref, A.J. (2015). A genetic algorithm-based multi-objective optimization for hybrid fiber reinforced polymeric deck and cable system of cable-stayed bridges. Structural and Multidisciplinary Optimization, 52(3), 583–594.
Camp, C.V.; Assadollahi, A. (2013). CO2 and cost optimization of reinforced concrete footings using a hybrid big bang-big crunch algorithm. Structural and Multidisciplinary Optimization, 48(2), 411–426.
Camp, C.V.; Huq, F. (2013). CO2 and cost optimization of reinforced concrete frames using a big bang-big crunch algorithm. Engineering Structures, 48, 363–372.
Carbonell, A.; González-Vidosa, F.; Yepes, V. (2011). Design of reinforced concrete road vaults by heuristic optimization. Advances in Engineering Software, 42(4), 151-159.
Chen, S.M.; Sarosh, A.; Dong, Y.F. (2012). Simulated annealing based artificial bee colony algorithm for global numerical optimization. Applied Mathematics and Computation, 219(8), 3575–3589.
Coello, C. (1994). Uso de Algoritmos Genéticos para el Diseño Óptimo de Armaduras. In Congreso Nacional de Informática “Herramientas Estratégicas para los Mercados Globales”, pp. 290–305. Fundación Arturo Rosenblueth, México, D.F.
Cohn, M.Z.; Dinovitzer, A.S. (1994). Application of Structural Optimization. Journal of Structural Engineering, 120(2), 617–650.
Colorni, A.; Dorigo, M.; Maniezzo, V. (1991). Distributed optimization by ant colonies. In Proceeding of ECALEuropean Conference on Artificial Life, pp. 134–142. Paris: Elsevier.
de Albuquerque, A.T.; El Debs, M.K.; Melo, A.M.C. (2012). A cost optimization-based design of precast concrete floors using genetic algorithms. Automation in Construction, 22, 348–356.
de Medeiros, G.F. Kripka, M. (2014). Optimization of reinforced concrete columns according to different environmental impact assessment parameters. Engineering Structures, 59, 185–194.
Degertekin, S.O.; Saka, M.P.; Hayalioglu, M.S. (2008). Optimal load and resistance factor design of geometrically nonlinear steel space frames via tabu search and genetic algorithm. Engineering Structures, 30(1), 197–205.
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.
Dutta, R.; Ganguli, R.; Mani, V. (2011). Swarm intelligence algorithms for integrated optimization of piezoelectric actuator and sensor placement and feedback gains. Smart Materials and Structures, 20(10), 105018.
Gandomi, A.H.; Kashani, A.R.; Roke, D.A.; Mousavi, M. (2015). Optimization of retaining wall design using recent swarm intelligence techniques. Engineering Structures, 103, 72–84.
García-Segura, T.; Yepes, V. (2016). Multiobjective optimization of post-tensioned concrete box-girder road bridges considering cost, CO2 emissions, and safety. Engineering Structures, 125, 325–336.
García-Segura, T.; Yepes, V.; Alcalá, J. (2014a). Life cycle greenhouse gas emissions of blended cement concrete including carbonation and durability. The International Journal of Life Cycle Assessment, 19(1), 3–12.
García-Segura, T.; Yepes, V.; Alcalá, J. (2014b). Sustainable design using multiobjective optimization of high-strength concrete I-beams. In The 2014 International Conference on High Performance and Optimum Design of Structures and Materials HPSM/OPTI (Vol. 137, pp. 347–358). Ostend, Belgium.
García-Segura, T.; Yepes, V.; Alcalá, J.; Pérez-López, E. (2015). Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges. Engineering Structures, 92, 112–122.
García-Segura, T.; Yepes, V.; Frangopol, D.M. (2017a). Multi-objective design of post-tensioned concrete road bridges using artificial neural networks. Structural and Multidisciplinary Optimization, 56(1):139-150.,
García-Segura, T.; Yepes, V.; Frangopol, D.M.; Yang, D. Y. (2017b). Lifetime reliability-based optimization of post-tensioned box-girder bridges. Engineering Structures, 145, 381-391.
García-Segura, T.; Yepes, V.; Martí, J.V.; Alcalá, J. (2014c). Optimization of concrete I-beams using a new hybrid glowworm swarm algorithm. Latin American Journal of Solids and Structures, 11(7), 1190–1205.
Geem, Z.W.; Kim, J.H.; Loganathan, G.V. (2001). A new heuristic optimization algorithm: Harmony search. Simulation, 76(2), 60–68.
Hare, W.; Nutini, J.; Tesfamariam, S. (2013). A survey of non-gradient optimization methods in structural engineering. Advances in Engineering Software, 59, 19–28.
Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, USA.
Karaboga, D.; Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing, 8(1), 687–697.
Kaveh, A.; Shakouri Mahmud Abadi, A. (2010). Cost optimization of a composite floor system using an improved harmony search algorithm. Journal of Constructional Steel Research, 66(5), 664–669.
Kennedy, J.; Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 – International Conference on Neural Networks, Vol. 4, pp. 1942–1948. IEEE.
Kripka, M.; Chamberlain Pravia, Z.M. (2013). Cold-formed steel channel columns optimization with simulated annealing method. Structural Engineering and Mechanics, 48(3), 383–394.
Krishnanand, K.N.; Ghose, D. (2009). Glowworm swarm optimisation: a new method for optimising multi-modal functions. International Journal of Computational Intelligence Studies, 1(1), 93–119.
Lagaros, N.D.; Fragiadakis, M.; Papadrakakis; M.; Tsompanakis, Y. (2006). Structural optimization: A tool for evaluating seismic design procedures. Engineering Structures, 28(12), 1623–1633.
Luz, A.; Yepes, V.; González-Vidosa, F.; Martí, J.V. (2015). Diseño de estribos abiertos en puentes de carretera obtenidos mediante optimización híbrida de escalada estocástica. Informes de la Construcción, 67(540), e114.
Martí, J.V.; García-Segura, T.; Yepes, V. (2016). Structural design of precast-prestressed concrete U-beam road bridges based on embodied energy. Journal of Cleaner Production, 120, 231–240.
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.
Martí, J.V.; Yepes, V.; González-Vidosa, F. (2015). Memetic algorithm approach to designing precast-prestressed concrete road bridges with steel fiber reinforcement. Journal of Structural Engineering, 141(2), 04014114.
Martínez-Martín, F. J.; González-Vidosa, F.; Hospitaler, A.; Yepes, V. (2013). A parametric study of optimum tall piers for railway bridge viaducts. Structural Engineering and Mechanics, 45(6), 723–740.
Martínez-Martín, F.J.; González-Vidosa, F.; Hospitaler, A.; Yepes, V. (2012). Multi-objective optimization design of bridge piers with hybrid heuristic algorithms. Journal of Zhejiang University: Science A, 13(6), 420–432.
Molina-Moreno, F.; García-Segura, T.; Martí, J.V.; Yepes, V. (2017a). Optimization of Buttressed Earth-Retaining Walls using Hybrid Harmony Search Algorithms. Engineering Structures, 134, 205-216.
Molina-Moreno, F.; Martí, J.V.; Yepes, V. (2017b). Carbon embodied optimization for buttressed earth-retaining walls: implications for low-carbon conceptual designs. Journal of Cleaner Production, 164, 872-884.
Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program (report 826). Caltech, Pasadena, California, USA.
Nigdeli, S.M.; Bekdas, G.; Kim, S.; Geem, Z. W. (2015). A novel harmony search based optimization of reinforced concrete biaxially loaded columns. Structural Engineering and Mechanics, 54(6), 1097–1109.
Park, H.; Kwon, B.; Shin, Y.; Kim, Y.; Hong, T.; Choi, S. (2013). Cost and CO2 emission optimization of steel reinforced concrete columns in high-rise buildings. Energies, 6(11), 5609–5624.
Payá, I.; Yepes, V.; González-Vidosa, F.; Hospitaler, A. (2008). Multiobjective optimization of reinforced concrete building frames by simulated annealing. Computer-Aided Civil and Infrastructure Engineering, 23(8), 596–610.
Payá-Zaforteza, I.; Yepes, V.; González-Vidosa, F.; Hospitaler, A. (2010). On the Weibull cost estimation of building frames designed by simulated annealing. Meccanica, 45(5), 693–704.
Payá-Zaforteza, I.; Yepes, V.; Hospitaler, A.; González-Vidosa, F. (2009). CO2-optimization of reinforced concrete frames by simulated annealing. Engineering Structures, 31(7), 1501–1508.
Pei, Y.; Xia, Y. (2012). Design of Reinforced Cantilever Retaining Walls using Heuristic Optimization Algorithms. Procedia Earth and Planetary Science, 5, 32–36.
Qu, L.; He, D.; Wu, J. (2011). Hybrid Coevolutionary Glowworm Swarm Optimization Algorithm with Simplex Search Method for System of Nonlinear Equations. Journal of Information & Computational Science, 8(13), 2693– 2701.
Rana, S.; Islam, N.; Ahsan, R.; Ghani, S.N. (2013). Application of evolutionary operation to the minimum cost design of continuous prestressed concrete bridge structure. Engineering Structures, 46, 38–48.
Sarma, K.C.; Adeli, H. (1998). Cost optimization of concrete structures. Journal of Structural Engineering, 124(5), 570–578.
Shieh, H.L.; Kuo, C.C.; Chiang, C.M. (2011). Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification. Applied Mathematics and Computation, 218(8), 4365–4383.
Srinivas, V.; Ramanjaneyulu, K. (2007). An integrated approach for optimum design of bridge decks using genetic algorithms and artificial neural networks. Advances in Engineering Software, 38(7), 475–487.
Valdez, F.; Melin, P.; Castillo, O. (2011). An improved evolutionary method with fuzzy logic for combining Particle Swarm Optimization and Genetic Algorithms. Applied Soft Computing, 11(2), 2625–2632.
Wang, E.; Shen, Z. (2013). A hybrid Data Quality Indicator and statistical method for improving uncertainty analysis in LCA of complex system – application to the whole-building embodied energy analysis. Journal of Cleaner Production, 43, 166–173.
Wills, J. (1973). A mathematical optimization procedure and its application to the design of bridge structures. Wokingham, Berkshire, United Kingdom.
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.
Yepes, V.; Díaz, J.; González-Vidosa, F.; Alcalá, J. (2009). Caracterización estadística de tableros pretensados para carreteras. Revista de la Construcción, 8(2), 95-109.
Yepes, V.; García-Segura, T.; Moreno-Jiménez, J.M. (2015a). A cognitive approach for the multi-objective optimization of RC structural problems. Archives of Civil and Mechanical Engineering, 15(4), 1024–1036.
Yepes, V.; González-Vidosa, F.; Alcalá, J.; Villalba, P. (2012). CO2-optimization design of reinforced concrete retaining walls based on a VNS-threshold acceptance strategy. Journal of Computing in Civil Engineering, 26(3), 378–386.
Yepes, V.; Martí, J.V.; García-Segura, T. (2015b). Cost and CO2 emission optimization of precast–prestressed concrete U-beam road bridges by a hybrid glowworm swarm algorithm. Automation in Construction, 49, 123–134.
Yepes, V.; Martí, J.V.; García-Segura, T.; González-Vidosa, F. (2017). Heuristics in optimal detailed design of precast road bridges. Archives of Civil and Mechanical Engineering, 17(4), 738-749.
Yepes, V.; Torres-Machí, C.; Chamorro, A.; Pellicer, E. (2016). Optimal pavement maintenance programs based on a hybrid greedy randomized adaptive search procedure algorithm. Journal of Civil Engineering and Management, 22(4), 540-550.
Yepes, V. (2017). Trabajo de investigación. Concurso de Acceso al Cuerpo de Catedráticos de Universidad. Universitat Politècnica de València, 110 pp.
Yu, C.H.; Gupta, N.C. Das; Paul, H. (1986). Optimization of prestressed concrete bridge girders. Engineering Optimization, 10(1), 13–24.
Zhang, J.; Zhou, G.; Zhou, Y. (2010). A New Artificial Glowworm Swarm Optimization Algorithm Based on Chaos Method. In B. Cao, G. Wang, S. Chen, & S. Guo (Eds.), Quantitative Logic and Soft Computing 2010, Vol. 82, pp. 683–693. Berlin, Heidelberg: Springer Berlin Heidelberg.
En algunos posts anteriores hemos comentado lo que es un modelo matemático de optimización, qué son las metaheurísticas, o cómo poder optimizar las estructuras de hormigón. A continuación os presentamos un Polimedia donde se explica brevemente cómo podemos optimizar siguiendo la técnica de optimización heurística mediante aceptación por umbrales. Podréis comprobar cómo se trata de un caso similar a la famosa técnica de la cristalización simulada. Espero que os sea útil.
Podéis consultar, a modo de ejemplo, algunos artículos científicos que hemos escrito a ese respecto en las siguientes publicaciones:
CARBONELL, A.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2011). Heuristic optimization of reinforced concrete road vault underpasses.Advances in Engineering Software, 42(4): 151-159. ISSN: 0965-9978. (link)
MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections.Computers & Structures, 88: 375-386. ISSN: 0045-7949. (link)
YEPES, V.; MEDINA, J.R. (2006). Economic Heuristic Optimization for Heterogeneous Fleet VRPHESTW.Journal of Transportation Engineering, ASCE, 132(4): 303-311. (link)
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.
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)
En el corazón de nuestra civilización digital late un motor invisible que solemos dar por sentado. Lo que en el siglo IX nació como una serie de reglas rígidas para el cálculo algebraico —el legado de Al-Juarismi— ha evolucionado hasta convertirse en el concepto moderno de algoritmo: una sofisticada «receta» diseñada para manipular información mediante operaciones elementales. En la actualidad, los algoritmos no son solo curiosidades matemáticas, sino la infraestructura lógica que decide desde la ruta de un camión de reparto hasta la resistencia de un viaducto de hormigón. Sin embargo, ¿comprendemos realmente las leyes que rigen su eficiencia o somos ciegos ante las reglas que separan lo posible de lo imposible?
