Los algoritmos genéticos

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:

  1. Generar una población de vectores (individuos).
  2. Mientras no se encuentre un criterio de parada:
    1. Seleccionar un conjunto de vectores padre, que serán reemplazados de la población.
    2. Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores hijo.
    3. Aplicar una mutación a cada descendiente.
    4. Evaluar a los hijos.
    5. Introducir a los hijos en la población.
    6. 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.

Os dejo a continuación un vídeo explicativo que he elaborado para mis clases de “Modelos predictivos y de optimización heurística de estructuras de hormigón“, del Máster Universitario en Ingeniería del Hormigón, de la Universitat Politècnica de València.

Referencias:

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.

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

¿Cuál es el mejor algoritmo para optimizar un problema? “No free lunch”

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.

Referencias:

GARCÍA, J.; YEPES, V.; MARTÍ, J.V. (2020a). A hybrid k-means cuckoo search algorithm applied to the counterfort retaining walls problem. Mathematics,  8(4), 555.

GARCÍA, J.; MARTÍ, J.V.; YEPES, V. (2020b). The buttressed  walls problem: An application of a hybrid clustering particle swarm optimization algorithm. Mathematics,  8(6):862.

GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M. (2017). Multi-Objective Design of Post-Tensioned Concrete Road Bridges Using Artificial Neural Networks. Structural and Multidisciplinary Optimization, 56(1):139-150.

WOLPERT, D.H.; MACREADY, W.G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82.

YEPES, V.; MARTÍ, J.V.; GARCÍA, J. (2020). Black hole algorithm for sustainable design of counterfort retaining walls. Sustainability, 12(7), 2767.

A continuación os dejo el artículo original “No Free Lunch Theorems for Optimization”. Se ha convertido en un clásico en optimización heurística.

Descargar (PDF, 698KB)

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

El aprendizaje profundo (deep learning) en la optimización de estructuras

Figura 1. Relación de pertenencia entre la inteligencia artificial, el aprendizaje automático y el aprendizaje profundo

En este artículo vamos a esbozar las posibilidades de la inteligencia artificial en la optimización de estructuras, en particular, el uso del aprendizaje profundo. El aprendizaje profundo (deep learning, DL) constituye un subconjunto del aprendizaje automático (machine learning, ML), que a su vez lo es de la inteligencia artificial (ver Figura 1). Si la inteligencia artificial empezó sobre los años 50, el aprendizaje automático surgió sobre los 80, mientras que el aprendizaje profundo nació en este siglo XXI, a partir del 2010, con la aparición de grandes superordenadores y por el aumento de los datos accesibles. Como curiosidad, uno de los grandes hitos del DL se produjo en 2012, cuando Google fue capaz de reconocer un gato entre los más de 10 millones de vídeos de Youtube, utilizando para ello 16000 ordenadores. Ahora serían necesarios muchos menos medios.

En cualquiera de estos tres casos, estamos hablando de sistemas informáticos capaces de analizar grandes cantidades de datos (big data), identificar patrones y tendencias y, por tanto, predecir de forma automática, rápida y precisa. De la inteligencia artificial y su aplicabilidad a la ingeniería civil ya hablamos en un artículo anterior.

Figura 2. Cronología en la aparición de los distintos tipos de algoritmos de inteligencia artificial. https://www.privatewallmag.com/inteligencia-artificial-machine-deep-learning/

Si pensamos en el cálculo estructural, utilizamos modelos, más o menos sofistificados, que permiten, si se conocen con suficiente precisión las acciones, averiguar los esfuerzos a los que se encuentran sometidos cada uno de los elementos en los que hemos dividido una estructura. Con dichos esfuerzos se identifican una serie de estados límite, que son un conjunto de situaciones potencialmente peligrosas para la estructura y comparar si la capacidad estructural del elemento analizado, dependiente de las propiedades geométricas y de sus materiales constituyentes, supera el valor último de la solicitación a la que, bajo cierta probabilidad, puede llegar a alcanzar el elemento estructural analizado.

Estos métodos tradicionales emplean desde hipótesis de elasticidad y comportamiento lineal, a otros modelos con comportamiento plástico o no lineales más complejos. Suele utilizarse, con mayor o menos sofisticación, el método de los elementos finitos (MEF) y el método matricial de la rigidez. En definitiva, en determinados casos, suelen emplearse los ordenadores para resolver de forma aproximada, ecuaciones diferenciales parciales muy complejas, habituales en la ingeniería estructural, pero también en otros campos de la ingeniería y la física. Para que estos sistemas de cálculo resulten precisos, es necesario alimentar los modelos con datos sobre materiales, condiciones de contorno, acciones, etc., lo más reales posibles. Para eso se comprueban y calibran estos modelos en ensayos reales de laboratorio (Friswell y Mottershead, 1995). De alguna forma, estamos retroalimentando de información al modelo, y por tanto “aprende”.

Figura 2. Malla 2D de elementos finitos, más densa alrededor de la zona de mayor interés. Wikipedia.

Si analizamos bien lo que hacemos, estamos utilizando un modelo, más o menos complicado, para predecir cómo se va a comportar la estructura. Pues bien, si tuviésemos una cantidad suficiente de datos procedentes de laboratorio y de casos reales, un sistema inteligente extraería información y sería capaz de predecir el resultado final. Mientras que la inteligencia artificial debería alimentarse de una ingente cantidad de datos (big data), el método de los elementos finitos precisa menor cantidad de información bruta (smart data), pues ha habido una labor previa muy concienzuda y rigurosa, para intentar comprender el fenómeno subyacente y modelizarlo adecuadamente. Pero, en definitiva, son dos procedimientos diferentes que nos llevan a un mismo objetivo: diseñar estructuras seguras. Otro tema será si éstas estructuras son óptimas desde algún punto de vista (economía, sostenibilidad, etc.).

La optimización de las estructuras constituye un campo científico donde se ha trabajado intensamente en las últimas décadas. Debido a que los problemas reales requieren un número elevado de variables, la resolución exacta del problema de optimización asociado es inabordable. Se trata de problemas NP-hard, de elevada complejidad computacional, que requiere de metaheurísticas para llegar a soluciones satisfactorias en tiempos de cálculo razonables.

Una de las características de la optimización mediante metaheurísticas es el elevado número de iteraciones en el espacio de soluciones, lo cual permite generar una inmensa cantidad de datos para el conjunto de estructuras visitadas. Es el campo ideal para la inteligencia artificial, pues permite extraer información para acelerar y afinar la búsqueda de la solución óptima. Un ejemplo de este tipo es nuestro trabajo (García-Segura et al., 2017) de optimización multiobjetivo de puentes cajón, donde una red neuronal aprendía de los datos intermedios de la búsqueda y luego predecía con una extraordinaria exactitud el cálculo del puente, sin necesidad de calcularlo. Ello permitía reducir considerablemente el tiempo final de computación.

Sin embargo, este tipo de aplicación es muy sencilla, pues solo ha reducido el tiempo de cálculo (cada comprobación completa de un puente por el método de los elementos finitos es mucho más lenta que una predicción con una red neuronal). Se trata ahora de dar un paso más allá. Se trata de que la metaheurística sea capaz de aprender de los datos recogidos utilizando la inteligencia artificial para ser mucho más efectiva, y no solo más rápida.

Tanto la inteligencia artificial como el aprendizaje automático no son una ciencia nueva. El problema es que sus aplicaciones eran limitadas por la falta de datos y de tecnologías para procesarlas de forma rápida y eficiente. Hoy en día se ha dado un salto cualitativo y se puede utilizar el DL, que como ya hemos dicho es una parte del ML, pero que utiliza algoritmos más sofisticados, construidos a partir del principio de las redes neuronales. Digamos que el DL (redes neuronales) utiliza algoritmos distintos al ML (algoritmos de regresión, árboles de decisión, entre otros). En ambos casos, los algoritmos pueden aprender de forma supervisada o no supervisada. En las no supervisadas se facilitan los datos de entrada, no los de salida. La razón por la que se llama aprendizaje profundo hace referencia a las redes neuronales profundas, que utilizan un número elevado de capas en la red, digamos, por ejemplo, 1000 capas. De hecho, el DL también se le conoce a menudo como “redes neuronales profundas”. Esta técnica de redes artificiales de neuronas es una de las técnicas más comunes del DL.

Figura. Esquema explicativo de diferencia entre ML y DL. https://www.privatewallmag.com/inteligencia-artificial-machine-deep-learning/

Una de las redes neuronales utilizadas en DL son las redes neuronales convolucionales, que es una variación del perceptrón multicapa, pero donde su aplicación se realiza en matrices bidimensionales, y por tanto, son muy efectivas en las tareas de visión artificial, como en la clasificación y segmentación de imágenes. En ingeniería, por ejemplo, se puede utilizar para la monitorización de la condición estructural, por ejemplo, para el análisis del deterioro. Habría que imaginar hasta dónde se podría llegar grabando en imágenes digitales la rotura en laboratorio de estructuras de hormigón y ver la capacidad predictiva de este tipo de herramientas si contaran con suficiente cantidad de datos. Todo se andará. Aquí os dejo una aplicación tradicional típica (Antoni Cladera, de la Universitat de les Illes Balears), donde se explica el modelo de rotura de una viga a flexión en la pizarra y luego se rompe la viga en el laboratorio. ¡Cuántos datos estamos perdiendo en la grabación! Un ejemplo muy reciente del uso del DL y Digital Image Correlation (DIC) aplicado a roturas de probetas en laboratorio es el trabajo de Gulgec et al. (2020).

Sin embargo, aquí nos interesa detenernos en la exploración de la integración específica del DL en las metaheurísticas con el objeto de mejorar la calidad de las soluciones o los tiempos de convergencia cuando se trata de optimizar estructuras. Un ejemplo de este camino novedoso en la investigación es la aplicabilidad de algoritmos que hibriden DL y metaheurísticas. Ya hemos publicado algunos artículos en este sentido aplicados a la optimización de muros de contrafuertes (Yepes et al., 2020; García et al., 2020a, 2020b). Además, hemos propuesto como editor invitado, un número especial en la revista Mathematics (indexada en el primer decil del JCR) denominado “Deep learning and hybrid-metaheuristics: novel engineering applications“.

Dejo a continuación un pequeño vídeo explicativo de las diferencias entre la inteligencia artificial, machine learning y deep learning.

Referencias:

FRISWELL, M.; MOTTERSHEAD, J. E. (1995). Finite element model updating in structural dynamics (Vol. 38). Dordrecht, Netherlands: Springer Science & Business Media.

GARCÍA, J.; MARTÍ, J.V.; YEPES, V. (2020a). The buttressed  walls problem: An application of a hybrid clustering particle swarm optimization algorithm. Mathematics,  8(6):862. https://doi.org/10.3390/math8060862

GARCÍA, J.; YEPES, V.; MARTÍ, J.V. (2020b). A hybrid k-means cuckoo search algorithm applied to the counterfort retaining walls problem. Mathematics,  8(4), 555. DOI:10.3390/math8040555

GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M. (2017). Multi-Objective Design of Post-Tensioned Concrete Road Bridges Using Artificial Neural Networks. Structural and Multidisciplinary Optimization, 56(1):139-150. DOI:1007/s00158-017-1653-0

GULGEC, N.S.; TAKAC, M., PAKZAD S.N. (2020). Uncertainty quantification in digital image correlation for experimental evaluation of deep learning based damage diagnostic. Structure and Infrastructure Engineering, https://doi.org/10.1080/15732479.2020.1815224

YEPES, V.; MARTÍ, J.V.; GARCÍA, J. (2020). Black hole algorithm for sustainable design of counterfort retaining walls. Sustainability, 12(7), 2767. DOI:10.3390/su12072767

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

Sesión temática en CMN2021: Optimization, metaheuristics and evolutionary algorithms in civil engineering

En el marco del próximo congreso CMN2021 (Congress on Numerical Methods in Engineering) que se celebrará en Las Palmas de Gran Canaria del 28 al 30 de junio de 2021, hemos organizado una sesión temática coordinada por David Greiner, Diogo Ribeiro y Víctor Yepes que versa sobre optimización, metaheurísticas y algoritmos evolutivos en ingeniería civil. Os dejo a continuación una breve descripción del congreso y un resumen de la sesión temática propuesta.

El objetivo del Congreso de Métodos Numéricos en Ingeniería (CMN) es actuar como un foro en que se recopilen los trabajos científicos y técnicos más relevantes en el área de los métodos numéricos y la mecánica computacional, así como sus aplicaciones prácticas. CMN 2021, organizado conjuntamente por las sociedades de métodos numéricos española (SEMNI), portuguesa (APMTAC) y por el Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería (SIANI) de la Universidad de Las Palmas de Gran Canaria (ULPGC). Los anteriores congresos conjuntos de ambas sociedades fueron celebrados en Madrid (2002), en Lisboa (2004), en Granada (2005), Porto (2007), Barcelona (2009), Coimbra (2011), Bilbao (2013), Lisboa (2015), Valencia (2017) y Minho (2019). Habiendo sido Las Palmas de Gran Canaria la sede del Primer Congreso CMN organizado por SEMNI en 1990, (General Chairs: Gabriel Winter y Miguel Galante), retorna 31 años después a su primera sede. El programa científico del CMN 2021 estará estructurado en sesiones temáticas según las distintas especialidades de los métodos numéricos. Las comunicaciones presentadas en el congreso constituirán una referencia de los avances recientes y de las líneas de trabajo futuras. Asimismo, investigadores internacionales de reconocido prestigio impartirán una serie de conferencias plenarias. El enlace a la web del congreso es la siguiente: https://congress.cimne.com/cmn2021

Descargar (PDF, 129KB)

Optimización heurística mediante aceptación por umbrales

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)

 

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

¿Es fácil optimizar estructuras de hormigón?

Es más, ¿es posible que un ordenador sea capaz de diseñar de forma automática estructuras óptimas sin darle ninguna pista o información previa? Estoy convencido que a la vuelta de un par de años, todos los programas comerciales tendrán paquetes de optimización estructural que permitirán reducciones de coste en torno al 5-15% respecto a los programas actuales. Ya os adelanto que esta nueva tecnología va a traer consigo nuevas patologías en las estructuras de hormigón, que con la optimización se parecen más a las estructuras metálicas. Con el tiempo habrá que introducir capítulos o restricciones en las futuras versiones de la EHE o de los Eurocódigos. En este post vamos a continuar comentando aspectos relacionados con la modelización matemática, la optimización combinatoria, las metaheurísticas y los algoritmos.

Toda esta aventura la empezamos en el año 2002, con el primer curso de doctorado sobre optimización heurística en la ingeniería civil, que luego hemos ido ampliando y mejorando en el actual Máster Oficial en Ingeniería del Hormigón. Ya tenemos varias tesis doctorales y artículos científicos al respecto para aquellos de vosotros curiosos o interesados en el tema. Para aquellos que queráis ver algunas aplicaciones concretas, os recomiendo el siguiente capítulo de libro que escribimos sobre la optimización de distintas estructuras con un algoritmo tan simple como la cristalización simulada. Para aquellos otros que tengáis más curiosidad, os dejos algunas publicaciones de nuestro grupo de investigación en el apartado de referencias.

Os paso, para abrir boca, una forma sencilla de optimizar a través de este Polimedia. Espero que os guste.

Referencias:

  • MOLINA-MORENO, F.; MARTÍ, J.V.; YEPES, V. (2017). Carbon embodied optimization for buttressed earth-retaining walls: implications for low-carbon conceptual designs. Journal of Cleaner Production, 164:872-884. https://authors.elsevier.com/a/1VLOP3QCo9NDzg 
  • GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M.; YANG, D.Y. (2017). Lifetime Reliability-Based Optimization of Post-Tensioned Box-Girder Bridges. Engineering Structures, 145:381-391. DOI:10.1016/j.engstruct.2017.05.013 OPEN ACCESS
  • GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M. (2017). Multi-Objective Design of Post-Tensioned Concrete Road Bridges Using Artificial Neural Networks. Structural and Multidisciplinary Optimization, 56(1):139-150. doi: 10.1007/s00158-017-1653-0
  • 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. DOI: 10.1016/j.acme.2017.02.006
  • MOLINA-MORENO, F.; GARCÍA-SEGURA; MARTÍ, J.V.; YEPES, V. (2017). Optimization of Buttressed Earth-Retaining Walls using Hybrid Harmony Search Algorithms. Engineering Structures, 134:205-216. DOI: 10.1016/j.engstruct.2016.12.042
  • 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. DOI: 10.1016/j.engstruct.2016.07.012.
  • 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. DOI: 10.1016/j.jclepro.2016.02.024
  • 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. DOI: 10.1016/j.engstruct.2015.03.015 (link)
  • 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. DOI: 10.3989/ic.14.089
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2015). Memetic algorithm approach to designing of precast-prestressed concrete road bridges with steel fiber-reinforcement. Journal of Structural Engineering ASCE, 141(2): 04014114. DOI:10.1061/(ASCE)ST.1943-541X.0001058 (descargar versión autor)
  • YEPES, V.; GARCÍA-SEGURA, T.; MORENO-JIMÉNEZ, J.M. (2015). A cognitive approach for the multi-objective optimization of RC structural problems. Archives of Civil and Mechanical Engineering, 15(4):1024-1036. doi:10.1016/j.acme.2015.05.001
  • YEPES, V.; MARTÍ, J.V.; GARCÍA-SEGURA, T. (2015). 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. DOI: 10.1016/j.autcon.2014.10.013 (link)
  • GARCÍA-SEGURA, T.; YEPES, V.; MARTÍ, J.V.; ALCALÁ, J. (2014). Optimization of concrete I-beams using a new hybrid glowworm swarm algorithm. Latin American Journal of Solids and Structures,  11(7):1190 – 1205. ISSN: 1679-7817. (link)
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; LUZ, A. (2013). Diseño automático de tableros óptimos de puentes de carretera de vigas artesa prefabricadas mediante algoritmos meméticos híbridos. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, DOI: http://dx.doi.org/10.1016/j.rimni.2013.04.010.
  • TORRES-MACHÍ, C.; YEPES, V.; ALCALA, J.; PELLICER, E. (2013). Optimization of high-performance concrete structures by variable neighborhood search. International Journal of Civil Engineering, 11(2):90-99 . ISSN: 1735-0522. (link)
  • MARTÍNEZ-MARTÍN, F.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2013). A parametric study of optimum tall piers for railway bridge viaducts. Structural Engineering and Mechanics45(6): 723-740. (link)
  • MARTINEZ-MARTIN, F.J.; GONZALEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2012). Multi-objective optimization design of bridge piers with hybrid heuristic algorithms. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering, 13(6):420-432. DOI: 10.1631/jzus.A1100304. ISSN 1673-565X (Print); ISSN 1862-1775 (Online).  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; YEPES, V.; ALCALÁ, J. (2013). Design of prestressed concrete precast road bridges with hybrid simulated annealing. Engineering Structures48:342-352. DOI:10.1016/j.engstruct.2012.09.014. ISSN: 0141-0296.(link)
  • 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 ASCE, 26 (3):378-386. DOI: 10.1061/(ASCE)CP.1943-5487.0000140. ISNN: 0887-3801. (link)
  • CARBONELL, A.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2011). Búsqueda exhaustiva por entornos aplicada al diseño económico de bóvedas de hormigón armado. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 27(3):227-235.  (link) [Global best local search applied to the economic design of reinforced concrete vauls]
  • 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. (2011). Estudio paramétrico de pilas para viaductos de carretera. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 27(3):236-250. (link)
  • MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; ALCALÁ, J. (2011). Design of tall bridge piers by ant colony optimization. Engineering Structures, 33:2320-2329.
  • PEREA, C.; YEPES, V.; ALCALÁ, J.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2010). A parametric study of optimum road frame bridges by threshold acceptance. Indian Journal of Engineering & Materials Sciences, 17(6):427-437. ISSN: 0971-4588.  (link)
  • 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. DOI 10.1007/s11012-010-9285-0. ISSN: 0025-6455.  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F. (2010). Design of prestressed concrete precast pedestrian bridges by heuristic optimization. Advances in Engineering Software, 41(7-8): 916-922. http://dx.doi.org/10.1016/j.advengsoft.2010.05.003
  • 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)
  • PAYÁ, I.; YEPES, V.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2009). CO2-Efficient Design of Reinforced Concrete Building Frames. Engineering Structures, 31: 1501-1508. ISSN: 0141-0296. (link)
  • 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. ISSN: 0141-0296.  (link)
  • PEREA, C.; ALCALÁ, J.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2008). Design of Reinforced Concrete Bridge Frames by Heuristic Optimization. Advances in Engineering Software, 39(8): 676-688. ISSN: 0965-9978.  (link)
  • 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. ISSN: 1093-9687.  (link)
  • PAYÁ, I.; YEPES, V.; CLEMENTE, J.J.; GONZÁLEZ-VIDOSA, F. (2006). Optimización heurística de pórticos de edificación de hormigón armado. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 22(3): 241-259. [Heuristic optimization of reinforced concrete building frames]. (link)

¿Las hormigas nos pueden enseñar a optimizar puentes?

A veces la Naturaleza nos sorprende cada día más. ¿Es posible que el comportamiento de las hormigas pueda servirnos para optimizar estructuras complejas, como por ejemplo un puente? Pues vamos a ver que sí. Este post es continuación de otros anteriores donde hablamos de la posibilidad de optimizar estructuras de hormigón. La optimización por colonia de hormigas (ant colony optimization) va a ser una metaheurística que nos va a permitir realizar este tipo de operaciones. A continuación vamos a contar los fundamentos básicos y en las referencias os dejo, incluso, algunos artículos donde hemos podido utilizar esta técnica de forma exitosa.

Colorni, Dorigo y Maniezzo (1991) sugirieron la idea de imitar el comportamiento de los insectos para encontrar soluciones a los problemas de optimización combinatoria. El principio de la metaheurística denominada como “Ant System Optimization, ACO” se basa en el comportamiento colectivo de las hormigas en la búsqueda de alimentos para su subsistencia, que son capaces de encontrar el camino más corto entre una fuente de comida y su hormiguero. Primero las hormigas exploran el entorno de su hormiguero de forma aleatoria. Tan pronto como un individuo encuentra una fuente de comida, evalúa su cantidad y calidad y transporta un poco al hormiguero. Durante el regreso, la hormiga deja por el camino una señal odorífera, depositando una sustancia denominada feromona, para que las demás puedan seguirla. Después de un tiempo, el camino hacia el alimento se indicará por un rastro oloroso que crece con el número de hormigas que pasen por él, y que va desapareciendo en caso contrario. El resultado final es la optimización del trabajo de todo el hormiguero en su búsqueda de comida.

En la Figura se muestra cómo las hormigas encuentran el camino más corto. En a) las hormigas deben decidir un camino; en b) se toma uno al azar; en c), dado que la velocidad de una hormiga se considera aproximadamente constante, las que llegan antes vuelven eligiendo el camino con más acumulación de feromona. En d), se circula por el camino más corto, desapareciendo por evaporación el rastro en el camino más largo.

Las hormigas y el camino más corto

La analogía a una metaheurística de optimización puede establecerse de la siguiente forma:

  • La búsqueda de alimento por las hormigas es equivalente a la exploración de soluciones factibles de un problema combinatorio.
  • La cantidad de alimento hallada en un lugar es similar al valor de la función objetivo.
  • El rastro de feromona es la memoria adaptativa del método.

Un esquema básico de la metaheurística sería el siguiente:

  1. Iniciar un rastro de feromona.
  2. Mientras no se encuentre un criterio de parada:
    1. Para cada hormiga artificial, construir una nueva solución usando el rastro actual y evaluar la solución que está siendo construida.
    2. Actualizar el rastro de feromona.

El componente más importante de un Sistema de Hormigas es la gestión de las huellas odoríferas. En su versión estándar, los rastros se usan en relación con la función objetivo para construir nuevas soluciones. Una vez se ha construido, éstos se actualizan de la siguiente forma: primero todos los rastros se debilitan para simular la evaporación del feronoma; después aquellos que corresponden a los elementos que se han empleado para la construcción, se refuerzan teniendo en cuenta la calidad de la solución.

El siguiente vídeo os puede ayudar a comprender el comportamiento de las hormigas. Espero que os guste.

Referencias:

COLORNI, A.; DORIGO, M.; MANIEZZO, V. (1991). Distributed optimization by ant colonies, in VARELA, F.J.; BOURGINE, P. (eds.) Proceedings of the First European Conference on Artificial Life (ECAL-91). The MIT Press: Cambrige, MA, 134-142.

MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; ALCALÁ, J. (2011). Design of tall bridge piers by ant colony optimization. Engineering Structures, 33:2320-2329.

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. (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.

Teoría del valor extremo y optimización estructural

A continuación dejo una presentación que hicimos para el VII Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados MAEB 2010, que se celebró en Valencia del 8 al 10 de septiembre de 2010.

El artículo, denominado “Teoría del valor extremo como criterio de parada en la optimización heurística de bóvedas de hormigón estructural” establece un criterio de parada para un algoritmo multiarranque de búsqueda exhaustiva de máximo gradiente basado en una codificación Gray aplicado a la optimización de bóvedas de hormigón. Para ello se ha comprobado que los óptimos locales encontrados constituyen valores extremos que ajustan a una función Weibull de tres parámetros, siendo el de  posición, γ, una estimación del óptimo global que puede alcanzar el algoritmo. Se puede estimar un intervalo de confianza para γ ajustando una distribución Weibull a muestras de  óptimos locales extraídas mediante una técnica bootstrap de los óptimos disponibles. El algoritmo multiarranque se detendrá cuando se acote el intervalo de confianza y la diferencia entre el menor coste encontrado y el teórico ajustado a dicha función Weibull.

Referencia:

YEPES, V.; CARBONELL, A.; GONZÁLEZ-VIDOSA, F. (2010). Teoría del valor extremo como criterio de parada en la optimización heurística de bóvedas de hormigón estructural. Actas del VII Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados MAEB 2010, Valencia, 8-10 septiembre, pp. 553-560. Garceta Grupo Editorial. ISBN: 978-84-92812-58-5.

Introducción a la optimización heurística en ingeniería

Este pasado mes de octubre, estando como profesor visitante en la Universidad Católica de Chile, tuve la oportunidad de impartir un seminario introductorio a la optimización heurística en ingeniería. A continuación os paso la presentación. Espero que os guste.

Descargar (PDF, 3.02MB)

Optimización económica de redes de transporte

Trascendencia del transporte

La trascendencia económica del sector del transporte genera costos sociales y medioambientales de gran envergadura. Esta actividad supone aproximadamente un sexto del Producto Interno Bruto (PIB) de los países industrializados (ver Yepes, 2002). Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del PIB de Estados Unidos en 1978, constituyendo más del 45% de todos los costos logísticos de las organizaciones. En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector en el valor añadido bruto del año 1997 se situó en un 4.6%. En cuanto al empleo, 613,400 personas se encontraban ocupadas en el año 1999 en el sector de transportes en España, lo cual representa el 3.69% de la población activa. La distribución física representa para las empresas entre la sexta y la cuarta parte de las ventas y entre uno y dos tercios del total de los costos logísticos (Ballou, 1991). Continue reading “Optimización económica de redes de transporte”