simulated annealing – El blog de Víctor Yepes

Analogía física y conceptos fundamentales de la metaheurística “Simulated Annealing”

Figura 1. Proceso de recocido del acero. https://www.win-therm.com.my/what-is-annealing-heat-treatment-process-annealing/

En un artículo anterior describimos la metaheurística conocida como “Recocido simulado” o “Cristalización simulada”, que en inglés se conoce como “Simulated Annealing”. Para los que no estéis familiarizados con la optimización, os dejo en este enlace una descripción de lo que son las metaheurísticas.

En la década de 1980, Kirkpatrick et al. (1983), mientras trabajaban en el diseño de circuitos electrónicos, y de manera independiente, Cerny (1985), investigando el problema del TSP (Traveling Salesman Problem), consideraron la aplicación del algoritmo de Metrópolis en algunos de los desafíos de optimización combinatoria que surgen en este tipo de diseño. Para lograrlo, creyeron que era posible establecer una analogía entre los parámetros presentes en la simulación termodinámica y aquellos que se encuentran en los métodos de optimización local. En la Figura 2 se puede ver dicha analogía.

Figura 2. Analogía entre la termodinámica y la optimización (Díaz *et al*., 1996)

Como se puede observar, en el ámbito de la optimización, el concepto físico de temperatura no tiene un significado literal, sino que debe ser considerado como un parámetro, T, que necesita ser ajustado. De esta manera, podemos encontrar similitudes entre los procesos que tienen lugar cuando las moléculas de una sustancia se distribuyen en diferentes niveles energéticos en busca de un equilibrio a una temperatura específica y los procesos de minimización en la optimización local (o, en el caso de maximización, de manera similar).

En el primer caso, con una temperatura fija, la distribución de las partículas sigue la distribución de Boltzmann. Por lo tanto, cuando una molécula se desplaza, su movimiento será aceptado en la simulación si esto resulta en una disminución de la energía, o con una probabilidad proporcional al factor de Boltzmann si no es así. En el contexto de la optimización, al fijar el parámetro T, introducimos una perturbación y aceptamos directamente la nueva solución si su costo disminuye, o bien con una probabilidad proporcional al “factor de Boltzmann” en caso contrario.

La clave del recocido simulado es su estrategia heurística de búsqueda local. La elección del nuevo elemento del entorno, N(s), se hace de manera aleatoria, lo que puede llevar a quedar atrapado en óptimos locales. Para evitar esto, el recocido simulado permite, con una probabilidad decreciente a medida que nos acercamos a la solución óptima, el movimiento hacia soluciones peores. Al analizar el factor de Boltzmann en función de la temperatura, observamos que a medida que esta disminuye, la probabilidad de aceptar una solución peor disminuye rápidamente.

Figura 3. Valor del factor de Boltzmann en función de la temperatura y de δ (Díaz *et al*., 1996)

En consecuencia, la estrategia a seguir en el recocido simulado implica comenzar con una temperatura alta. Esto permite la posibilidad de aceptar soluciones peores en las primeras etapas, cuando estamos a gran distancia del óptimo global. A medida que se avanza hacia el óptimo global, se reducirá gradualmente la temperatura, disminuyendo así la probabilidad de aceptar soluciones peores. El nombre de este algoritmo proviene del proceso metalúrgico de “recocido” utilizado, por ejemplo, para eliminar las tensiones internas en el acero laminado en frío. En este proceso, el material se somete a un calentamiento rápido y luego se enfría de manera lenta y controlada durante horas.

A continuación os dejo un nomograma, elaborado junto con los profesores Trevor Blight y Pedro Martínez Pagán, para calcular la probabilidad en función de la temperatura y de δ. Aquí también resulta sencillo comprobar cómo varía dicha probabilidad en función de los valores anteriores.

Os dejo también 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.

DÍAZ, A. et al. (1996). Optimización heurística y redes neuronales en dirección de operaciones e ingeniería. Editorial Paraninfo, Madrid, 235 pp.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

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)

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Optimización heurística de un nuevo tipo de cercha pretensada

Acaban de publicarnos un artículo en Materials, revista indexada en el primer cuartil del JCR. En este caso se ha optimizado, mediante un algoritmo de optimización heurística, un nuevo tipo de cercha metálica pretensada. El trabajo se enmarca dentro del proyecto de investigación HYDELIFE que dirijo como investigador principal en la Universitat Politècnica de València. En este caso, se trata de una colaboración entre nuestro grupo de investigación e investigadores de Georgia.

Este artículo presenta nuevos enfoques para el cálculo, el diseño y la optimización de cerchas pretensadas con un elemento de unión. Los sistemas estructurales con grandes luces, como cerchas, vigas, pórticos, etc., están sometidos a un riesgo considerable de pérdida de capacidad de carga debido a los diferentes tipos de cargas utilizadas. Algunos métodos de diseño tradicionales definen los valores del pretensado en el elemento de unión y las fuerzas internas en los elementos de la celosía para evitar esta pérdida de capacidad de carga. Sin embargo, la precisión y los límites de la determinación de las fuerzas no son necesariamente conocidos. Los autores proponen un nuevo tipo de celosía pretensada y algunos nuevos enfoques en el proceso de diseño y cálculo para resolver estos inconvenientes. Los principales objetivos del estudio fueron diseñar una innovadora y nueva forma geométrica de celosía arqueada pretensada, que permite el desarrollo de una fuerza de pretensado de alto valor, para optimizar una nueva celosía para reducir el peso propio, aumentando la capacidad de carga en comparación con sus análogos. Durante el estudio se empleó el recocido simulado. Un nuevo avance en la optimización de la celosía arqueada pretensada sugerido por los autores reduce el peso propio y mejora la capacidad de carga de la celosía entre un 8 y un 17%, dependiendo de la luz.

Abstract:

This paper represents new approaches for calculating, designing, and optimizing prestressed arched trusses with a tie member. Structural systems with long spans, such as trusses, beams, frames, etc., are subjected to a considerable/substantial risk of losing load-carrying capacity because of the different types of loads used. Some traditional design methods define the values of prestressing force in the tie member and internal forces in the truss elements to avoid this load capacity loss. However, the accuracy and limits of the determination of the forces are not necessarily known. The authors offer a new type of prestressed arched truss and some new approaches in the design and calculation process to solve these disadvantages. The study’s main objectives were to design an innovative and new geometric form of prestressed arched truss, which allows the development of high-value prestressing force, to optimize a new truss for reducing self-weight, increasing load-carrying capacity compared to its analogs. The force, stiffness matrix, and simulated annealing methods were used during the study. A new advance to the optimization of prestressed arched truss suggested by the authors reduces the self-weight and improves the load capacity of the truss by 8–17%, depending on the span.

Keywords:

Prestressed truss; stiffness matrix method; tensile element; compressed element; optimization; simulated annealing.

Reference:

PARTSKHALADZE, G.; ALCALÁ, J.; MEDZMARIASHVILI, E.; CHAVLESHVILI, G.; SURGULADZE, B., I.; YEPES, V. (2022). Heuristic Optimization of a New Type Prestressed Arched Truss. Materials, 15(22): 8144. DOI:10.3390/ma15228144

Descargar (PDF, 1.12MB)

Diseño de experimentos para la calibración de la heurística de optimización de muros de contrafuertes

Variables geométricas del muro de contrafuertes

En la actualidad, los técnicos se enfrentan al desafío de encontrar soluciones estructurales más eficientes cumpliendo con todas las restricciones de seguridad y funcionalidad. Como ayuda a este reto, surgen las técnicas de optimización heurísticas. El algoritmo aplicado en este artículo es el Recocido Simulado o Simulated Annealing (SA). La estructura sobre la que se emplea esta metodología es un muro de contrafuertes de hormigón armado de 11 metros de altura. La eficiencia del algoritmo depende de la elección de los parámetros más adecuados que lo definen. Para ello, se realiza un diseño de experimentos factorial fraccionado que permite, a través de un análisis estadístico, detectar aquellos parámetros de la heurística que más afectan al resultado de la solución obtenida.

Referencia:

MARTÍ, J.V.; MARTÍNEZ-MUÑOZ, D.; YEPES, V. (2022). Diseño de experimentos para la calibración de la heurística de optimización de muros de contrafuertes. VIII Congreso de la Asociación Española de Ingeniería Estructural ACHE. Santander, 2022, 10 pp.

Descargar (PDF, 450KB)

Optimización de tableros de puentes mixtos con metaheurística de trayectoria

Variables de la sección transversal del puente mixto

La optimización de puentes es un problema complejo debido al gran número de variables que intervienen. En este trabajo se ha realizado la optimización de un puente mixto en cajón considerando el coste como función objetivo. Para ello se ha aplicado el Recocido Simulado (SA) como ejemplo de algoritmo basado en la búsqueda de soluciones mediante trayectorias para la optimización de la estructura. Se observa que la adición de celdas a las secciones transversales del puente mejora no sólo el comportamiento de la sección sino también los resultados de la optimización. Finalmente, se observa que el diseño propuesto de doble acción compuesta materializando losas en el ala inferior sobre apoyos, permite eliminar los rigidizadores longitudinales continuos. Este método automatiza el proceso de optimización de un diseño inicial de un puente de material compuesto, que tradicionalmente se ha basado en la propia experiencia del técnico, permitiendo alcanzar resultados de forma más eficiente.

Referencia:

MARTÍNEZ-MUÑOZ, D.; SÁNCHEZ-GARRIDO, A.J.; MARTÍ, J.V.; YEPES, V. (2021). Composite bridge deck optimization with trajectory-based algorithms. 6th International Conference on Mechanical Models in Structural Engineering, CMMoST 2021, 1-3 December, Valladolid, Spain, pp. 174-187. ISNB: 978-84-09-39323-7

Descargar (PDF, 589KB)

Optimización heurística de pórticos de paso de carretera de hormigón armado

A continuación recojo uno de los primeros trabajos que hizo nuestro grupo de investigación en el año 2005 sobre optimización heurística de estructuras de hormigón. Se trata de la optimización mediante varias heurísticas (máximo gradiente, aceptación por umbrales y recocido simulado) de un pórtico de paso de carretera de hormigón armado. En este caso se consideraron 28 variables para definir una solución de pórtico. Este artículo se publicó en la revista Hormigón y Acero. Espero que os sea de interés.

Referencia:

CARRERA, J.M.; ALCALÁ, J.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2005). Optimización heurística de pórticos de paso de carretera de hormigón armado. Hormigón y Acero, 236: 85-95.

Descargar (PDF, 318KB)

Optimización de pasarelas peatonales de sección en cajón y hormigón de alta resistencia

Acaban de publicarnos un artículo en la revista International Journal of Computational Methods and Experimental Measurements un artículo en el que optimizamos pasarelas peatonales de sección en cajón y hormigón de alta resistencia. Se trata de una publicación en abierto, por lo que os dejamos a continuación el artículo completo para su lectura y descarga.

ABSTRACT:

This paper deals with the economic optimization of high-performance post-tensioned concrete box-girder pedestrian bridges. To this end, a program analyzes and evaluates the structural restrictions following Spanish codes for structural concrete and bridge design loads. This problem includes 33 discrete design variables that define the geometry, the concrete, the reinforcing steel bars and the post-tensioned steel. Various acceptance criteria are proposed to modify a variant of the simulated annealing algorithm with a neighborhood move based on the mutation operator from the genetic algorithms (SAMO). An objective methodology based on the extreme value theory is used to determine the number of experimental tests required to provide a solution with user-defined accuracy as compared to a global optimum solution. Results indicate that the local optima found by SAMO2 fits a three parameter Weibull distribution and improves the cost results for this structural problem. The minimum value obtained by SAMO2 differed just 0.34% compared to the theoretical minimum value so that, from the structural engineering perspective, the divergence was small enough to be accepted. High strength concrete performance was further studied in a concrete strength parametric study to acquire more evidence-based knowledge on its implications for economic efficiency. Finally, the study showed that high-strength concrete decreases the cost by 4.5% and the amount of concrete by 26%.

KEYWORDS:

Box-girder bridge, extreme value theory, high-strength concrete, post-tensioned concrete, simulated annealing, Structural optimization

REFERENCE:

YEPES, V.; PÉREZ-LÓPEZ, E.; GARCÍA-SEGURA, T.; ALCALÁ, J. (2019). Optimization of high-performance concrete post-tensioned box-girder pedestrian bridges. International Journal of Computational Methods and Experimental Measurements, 7(2):118-129. DOI: 10.2495/CMEM-V7-N2-118-129

Descargar (PDF, 649KB)

Optimización de estructuras de hormigón mediante Simulated Annealing

A continuación os dejo un capítulo de un libro de Simulated Annealing, escrito en abierto para su libre difusión, donde explicamos varias aplicaciones del algoritmo de Cristalización Simulada aplicada a estructuras de hormigón armado. En particular: muros ménsula, pórticos de carreteras, marcos de carreteras y pórticos de edificación. Su referencia es:

GDE Error: Error al recuperar el fichero. Si es necesario, desactiva la comprobación de errores (404:Not Found)

¿Qué es la optimización por cristalización simulada?

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 en 1985 de forma independiente. Estos autores se inspiraron en los trabajos sobre Mecánica Estadística de Metrópolis et al. (1953). La metaheurística despliega una estructura que se inserta cómodamente en la programación, mostrando además 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 los modelos matemáticos de optimización.

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” 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. 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 menor o igual que cero); en caso contrario, será aceptada con una probabilidad (e^(-^D/T) si D>0, donde T es el parámetro temperatura) decreciente con el aumento de la diferencia entre los costes de la solución candidata y la actual. 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, con independencia de la solución inicial, el algoritmo converge estadísticamente a la solución óptima (Lundy y Mees, 1986). En cualquier caso, SA proporciona generalmente soluciones valiosas, aunque no informa si ha llegado al óptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque sí comparable, ante otros específicos que aprovechan información adicional del problema. El algoritmo es lento, especialmente si la función objetivo es costosa en su 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.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

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.

Diseño heurístico de puentes de hormigón pretensado como ejemplo de docencia de posgrado

Este artículo describe la impartición de un curso de posgrado en el diseño automatizado y optimización económica de estructuras de hormigón. El contenido forma parte de un Máster en Ingeniería de Hormigón que comenzó en octubre de 2007. El curso aplica los algoritmos heurísticos al diseño práctico de estructuras reales de hormigón, tales como muros, pórticos y marcos de pasos inferiores de carreteras, pórticos de edificación, bóvedas, pilas, estribos y tableros de puentes. Se presentan como casos prácticos dos tableros de puente de hormigón pretensado usados en la obra pública de construcción de carreteras. En primer lugar, se aplica SA a un tablero de un puente peatonal de viga artesa de hormigón prefabricado. El segundo ejemplo aplica TA a un tablero de losa continua de hormigón postesado. Los casos estudiados indican que la optimización heurística es una buena opción para diseñar estructuras de hormigón pretensado reduciendo los costes.

Influencia del empleo de vigas planas en edificación

¿Resulta razonable el uso masivo de las vigas planas en las estructuras de edificación? Si lo que se pretende es no condicionar el compartimentado interior en una vivienda, esta solución puede ser acertada. Pero en un artículo que publicamos en la revista Hormigón y Acero en el año 2008, quisimos comprobar cómo afectaba al coste este tipo de estructuras. El artículo completo se puede descargar en abierto en la siguiente dirección: http://e-ache.com/modules/hormigonyacero/hormigonyacero.php?revista=1541.

Creo que algunas de las conclusiones a las que llegamos son realmente interesantes, como el incremento más que significativo de coste de este tipo de estructuras respecto a las vigas descolgadas.

PAYÁ, I.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2008). Influencia del empleo de vigas planas y del tipo de hormigón en el diseño óptimo de pórticos de edificación. Hormigón y Acero, 248(59):43-52.

RESUMEN

Este artículo utiliza la cristalización simulada para el diseño de pórticos de edificación de hormigón armado optimizados económicamente. Se analiza la influencia del uso de hormigones de distinta resistencia característica a compresión, del empleo de vigas planas o descolgadas y de la agrupación de variables para simplificar la ejecución de la estructura. Para ello, se optimizan pórticos de 2 vanos de 5 m de luz y de 8 plantas con una altura por planta de 3 m. El número de variables de diseño de estos problemas varía entre 101 y 153. El trabajo concluye que el empleo de un solo tipo de hormigón HA-25 para toda la estructura incrementa su coste únicamente un 3.02%. Si además se agrupan variables, para facilitar la constructibilidad, existe un incremento adicional del 0.52%, lo cual es poco significativo. Sin embargo, el empleo de vigas planas encarece el coste en un 41.69% respecto al caso de vigas descolgadas, cuando el hormigón empleado es HA-25.

SUMMARY

This paper uses the Simulated Annealing algorithm for the design of economically optimized reinforced concrete frames commonly used in building construction. The influence of the following factors is analyzed: a) the concrete compressive strength, b) the beams depth (same as the one of the floor slabs or higher) and c) the grouping of some of the design variables. The structures studied are two bays and eight floors frames, being the span length of 5 m. and the columns height of 3 m. The number of design variables of these problems varies between 101 and 153. Results show that the use of a single concrete grade (25 MPa) in the structure increases its cost only by 3.02%. If, besides some variables are grouped in order to increase the frame constructability, the optimized structure is only 0.52% more expensive. However, if, additionally, beams of the same depth as the floor slabs are used, the cost of the optimized structure increases by 41.69%.

Descargar (PDF, 175KB)