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

La revolución de la digitalización en la ingeniería civil

En una entrada anterior que denominé “La ingeniería de caminos en el siglo XXI, ¿quo vadis?, puse de manifiesto la incertidumbre que suponía la desaparición de la titulación de ingeniero de caminos, canales y puertos con motivo de la reestructuración de las enseñanzas universitarias en grado y máster. Las preguntas que dejaban en el aire adquirían un tinte dramático cuando se contextualizaban en una situación de profunda crisis económica, especialmente fuerte en el sector de la construcción.

Otra reflexión sobre el futuro de la profesión la dejé en la entrada “¿Qué entendemos por “Smart Construction”? ¿Una nueva moda?“. Allí dejé constancia de las modas que igual que aparecen, desaparecen, pero que suponen cambios sustanciales en una profesión como la de ingeniero civil. Allí expresé mi esperanza de que el término de “construcción inteligente” tuviera algo más de recorrido y pudiera suponer un punto de inflexión en nuestro sector. Este término presenta, como no podía ser de otra forma, numerosas interpretaciones y tantas más aplicaciones. Es un concepto que se asocia al diseño digital, a las tecnologías de la información y de la comunicación, la inteligencia artificial, al BIM, al Lean Construction, la prefabricación, los drones, la robotización y automatización, a la innovación y a la sostenibilidad, entre otros muchos conceptos. Entre estos conceptos, uno que me interesa especialmente es la asociación con el de los nuevos métodos constructivos (término que incluye nuevos productos y nuevos procedimientos constructivos). Su objetivo es mejorar la eficiencia del negocio, la calidad, la satisfacción del cliente, el desempeño medioambiental, la sostenibilidad y la previsibilidad de los plazos de entrega. Por lo tanto, los métodos modernos de construcción son algo más que un enfoque particular en el producto. Involucran a la gente a buscar mejoras, a través de mejores procesos, en la entrega y ejecución de la construcción.

Al hilo de estas reflexiones, me ha gustado especialmente el vídeo ganador del concurso de la Asociación de Ingenieros de Caminos, Canales y Puertos, ingeniería en 200 segundos, que presenta Juan Antonio Martínez Ortega, y que trata del impacto de la digitalización en la ingeniería civil. Atento al “diablillo de Laplace“. ¡Enhorabuena para Juan Antonio!

 

¿Qué es y para qué sirve una red neuronal artificial?

Parece que hoy día, al igual que hace algunos milenios, la profesión de “oráculo” es una de las más demandadas, especialmente cuando se afrontan tiempos difíciles y el ser humano pretende predecir qué va a pasar para tomar la decisión correcta. Una de las profesiones de más futuro, según algunos, es la relacionada con “Big Data“. Pues bien, este post trata de introducir, de forma muy somera, una herramienta que es extraordinariamente potente para predecir relaciones fuertemente no lineales de grandes volúmenes de datos. También es una herramienta que, mal empleada, nos engaña. Todo empezó cuando nuestro Premio Nobel Santiago Ramón y Cajal empezó a describir nuestro sistema nervioso.
Las redes de neuronas artificiales (denominadas habitualmente como RNA o en inglés como: “ANN”) son un paradigma de aprendizaje y procesamiento automático inspirado en la forma en que funciona el sistema nervioso de los animales. Se trata de un sistema de interconexión de neuronas que colaboran entre sí para producir un estímulo de salida. En inteligencia artificial es frecuente referirse a ellas como redes de neuronas o redes neuronales. Forman parte de los denominados “Sistemas Inteligentes“, dentro de la rama de la Inteligencia Artificial.

Nuestro grupo de investigación ha publicado algunos artículos empleando esta herramienta en el ámbito del hormigón:

  • 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
  • MARTÍ-VARGAS, J.R.; FERRI, F.J.; YEPES, V. (2013). Prediction of the transfer length of prestressing strands with neural networks. Computers and Concrete, 12(2):187-209. DOI: http://dx.doi.org/10.12989/cac.2013.12.2.187.

Un tutorial muy interesante sobre este tema es: http://www.gc.ssr.upm.es/inves/neural/ann2/anntutorial.html , así como el siguiente: http://sabia.tic.udc.es/mgestal/cv/RNAtutorial/index.html

¿Queréis usar una red neural on-line? Os paso el siguiente enlace: http://playground.tensorflow.org/

Os dejo también unos cuantos vídeos que os pueden ampliar información sobre el tema. Espero que os gusten.

Este programa de Redes creo que puede ampliar algo más la filosofía subyacente del aprendizaje y la inteligencia:

También dejo una presentación de clase sobre el tema:

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

Tesis doctoral: Modelos predictivos de las características prestacionales de hormigones fabricados en condiciones industriales

2016-06-03 11.35.53Ayer 3 de junio de 2016 tuvo lugar la defensa de la tesis doctoral de D. Ferran Navarro Ferrer denominada “Modelos predictivos de las características prestacionales de hormigones fabricados en condiciones industriales”, dirigida por  Víctor Yepes Piqueras. La tesis recibió la calificación de “Sobresaliente Cum Laude” por unanimidad. Presentamos a continuación un pequeño resumen de la misma.

Resumen:

En la actualidad el hormigón es el material más empleado en la construcción debido a su moldeabilidad, a su capacidad de resistir esfuerzos de compresión y a su economía. Las prestaciones del hormigón dependen de su composición, de las condiciones de curado y del método y condiciones de mezclado. Las especificaciones básicas del hormigón demandadas por el peticionario al fabricante son la resistencia a compresión y la consistencia, que indica la trabajabilidad del mismo. Esta tesis es una contribución al conocimiento y la investigación de la influencia de diferentes parámetros en la resistencia a compresión y la consistencia del hormigón fabricado en condiciones industriales y la elaboración de modelos predictivos de dichas características prestacionales.

La mayor parte de los hormigones que se emplean en construcción se fabrican en centrales de hormigón preparado o en centrales de obra, y se corresponden con hormigones de resistencia entre 25 y 30 N=mm2, consistencia blanda o fluida, colocación mediante vertido o bombeo y compactación mediante vibración. Las condiciones de producción de hormigones en planta se ven afectadas por los condicionantes del proceso industrial y del negocio en sí, siendo controlada la cantidad de agua existente en la mezcla indirectamente.

2016-06-02 18.45.05En este trabajo se presenta una extensa base de datos construida con miles de resultados de ensayos de resistencia a compresión y consistencia realizados sobre hormigones fabricados en la misma planta y con diferentes dosificaciones, tipos de cemento y aditivos. Se tienen en consideración otros aspectos como la inclusión de fibras, la temperatura ambiente y del hormigón o la hora de realización de las probetas. Se crea una segunda base de datos de ensayos realizados en un periodo de tiempo corto con el mismo cemento y aditivo y teniendo en cuenta la relación agua/cemento exacta. Además, se ha realizado la conveniente caracterización de los materiales constituyentes de los hormigones ensayados.

Para analizar la influencia de los diferentes parámetros y factores tecnológicos y ambientales en la resistencia a compresión, en la evolución de la misma con el tiempo y en la consistencia del hormigón, se ha utilizado primeramente estadística clásica, concretamente análisis de regresión lineal múltiple, análisis de varianza (ANOVA) y análisis multivariante. También se ha verificado el ajuste de los datos experimentales a modelos existentes en la bibliografía y a nuevos modelos de comportamiento propuestos.

Finalmente se han elaborado redes neuronales artificiales para predecir la resistencia a compresión o la consistencia de un hormigón en función de diversas variables de entrada, al igual que para la obtención de modelos de comportamiento. Los resultados obtenidos mediante la aplicación de redes neuronales artificiales han sido más eficientes y mejores que los obtenidos mediante métodos estadísticos.

 

 

Métodos no convencionales de investigación basados en la inteligencia artificial

El pasado mes de octubre tuve la ocasión de impartir un seminario en la Universidad Católica de Chile denominado “Métodos de investigación no convencionales basados en la inteligencia artificial”. Os paso la presentación que hice. Espero que os guste.

Descargar (PDF, 2.26MB)