¿Qué son las metaheurísticas?

 ¿Cómo se podrían optimizar en tiempos de cálculo razonable problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otro tipo de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que es imposible hacerlo con métodos matemáticos exactos? La respuesta son los métodos aproximados, también denominados heurísticas. Este artículo divulgativo trata de ampliar otros anteriores  donde ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Para más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto, una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al, 2008).

Desde los primeros años de la década de los 80, la investigación de los problemas de optimización combinatoria se centra en el diseño de estrategias generales que sirvan para guiar a las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.

Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.

Las metaheurísticas son susceptibles de agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de memoria que guíe de la exploración del espacio de elecciones posibles permite otro tipo de agrupamiento. En otras circunstancias se emplean perturbaciones de las opciones, de la topología del espacio de soluciones, o de la función objetivo. En la Figura se recoge una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), teniendo en común todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que existen en este momento muchas más técnicas de optimización, pero puede ser dicha clasificación un punto de partida para una mejor taxonomía de las mismas.

 

Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales.
Figura. Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales (Yepes, 2002)

Las  metaheurísticas empleadas en la optimización combinatoria en podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que éste concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los diferentes problemas de optimización combinatoria.

Referencias

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)

OSMAN, I.H.; KELLY, J.P. (Eds.) (1996). Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers.

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)

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

Comunicaciones presentadas en el 2º Congreso EIME

En plena celebración del 2º Congreso Nacional sobre Ensañanza de las Matemáticas en Ingeniería de Edificación, desarrollado los días 18 y 19 de julio de 2013 en la Universitat Politècnica de València, aprovecho para presentar los resúmenes de los trabajos que hemos presentado. Espero que sean de vuestro interés.

Los autores agradecen el aporte financiero realizado para este trabajo por el Ministerio de Ciencia e Innovación (Proyecto de Investigación BIA2011-23602) y por la Universitat Politècnica de València (Proyecto de Investigación PAID-06-12).

BÁRCENA, A.; ALCALÁ, J.; YEPES, V.; MARTÍ, J.V. (2013). Diseño automático de forjados de chapa nervada optimizados con criterios de economía y sostenibilidad. 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. 159-172. ISBN: 978-84-8363-992-4.

Los forjados mixtos con chapa colaborante son una tipología de estructuras horizontales que está experimentando un crecimiento continuo en las últimas décadas. Su optimización presenta un enorme interés para conseguir diseños más asequibles y sostenibles, que permitan un mejor aprovechamiento de los recursos necesarios. El objetivo de este trabajo es aplicar técnicas heurísticas para este tipo de forjados, permitiendo plantearse el problema de una manera más compleja, utilizando una definición completa del forjado mixto y sus componentes, mientras que al mismo tiempo satisface las restricciones de este tipo de estructuras. Los algoritmos de optimización aplicados a la estructura se basan en tres metaheurísticas: búsqueda local de descenso (DLS), recocido simulado (SA) y el umbral de aceptación (TA). Se muestran las principales características, los parámetros que deben calibrarse y los diferentes modos de selección de dichos parámetros, para cada una de las heurísticas. La comparación de los resultados ha permitido señalar la SA como la mejor heurística de todas ellas. Por último, una vez seleccionado el mejor calibración de la SA, se ha estudiado la sensibilidad del modelo y un estudio paramétrico con diferentes tramos horizontales.

GARCÍA-SEGURA, T.; YEPES, V.; ALCALÁ, J.; MARTÍ, J.V. (2013). Optimización multiobjetivo de viga en I de hormigón armado con criterios sostenibles. 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. 135-148. ISBN: 978-84-8363-992-4.

Este estudio tiene como objetivo presentar una metodología de diseño de una viga en I de hormigón armado de alta resistencia autocompactable o convencional.  Algoritmos heurísticos como recocido simulado multiobjetivo “Multiobjective Simulated Annealing” (MOSA) son utilizados para buscar dentro del espacio de soluciones factibles aquellas que mejoren criterios como coste, emisiones de CO2 o durabilidad. Se tomará como ejemplo una viga en I biapoyada de 15 m de luz definida por 20 variables. La viga deberá cumplir de acuerdo a la Instrucción de Hormigón Estructural (EHE-08) los requisitos de seguridad estructural, así como aspectos constructivos o geométricos. El análisis comparativo de los objetivos servirá como guía para el diseño sostenible de estructuras de hormigón. Los resultados obtenidos muestran una clara tendencia de diseño de estructuras de hormigón hacia la sostenibilidad.

MARTÍ, J.V.; YEPES, V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Optimización memética de vigas artesa prefabricadas con criterios sostenibles de hormigón con fibras. 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. 91-104. ISBN: 978-84-8363-992-4.

Esta comunicación describe una metodología heurística empleada para diseñar estructuras bajo criterios sostenibles, con reducción de la emisión de gases de efecto invernadero (CO2) durante la fase de ejecución. La estructura presentada es un tablero de un paso superior de carreteras de vigas artesa  prefabricadas de hormigón reforzado con fibras, empleando para ello un algoritmo memético híbrido, que combina la búsqueda poblacional de soluciones mediante algoritmos genéticos y una búsqueda por entornos variable (VDNS). Este algoritmo se aplica a un tablero formado por dos vigas isostáticas para una luz de 30 m y una losa de 12 m de ancho. La estructura analizada consta de 41 variables discretas. El módulo de la evaluación considera los estados límite último y de servicio que se aplican habitualmente para estas estructuras. El uso del algoritmo memético requiere previamente su calibración. Cada una de las heurísticas se procesa nueve veces, obteniéndose información estadística sobre el valor mínimo, el medio y las desviaciones. El procedimiento presentado permite la aplicación práctica al diseño real y su adaptación al proceso de prefabricación.

MARTÍ, J.V.; YEPES, V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Diseño de vigas en “U” de hormigón con fibras mediante la heurística SA con criterios económicos. 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. 299-309. ISBN: 978-84-8363-992-4.

Este artículo se ocupa de la optimización económica de los puentes de carreteras formados por tableros constituidos por una losa de hormigón ejecutada in situ y dos vigas artesa de hormigón reforzado con fibras metálicas pretensadas prefabricadas. Se comprueba la eficacia de la optimización heurística por el método del recocido simulado “simulated annealing” (SA). Los cálculos de las tensiones y de sus envolventes, son programados en lenguaje fortran directamente por los autores. Los algoritmos de optimización heurística se aplican a un tablero de 35 m de  luz y 12 m de ancho. Los parámetros que definen la forma de la sección de la viga se adaptan prácticamente a cualquier tipo de molde de una instalación de prefabricados. El ejemplo que se analiza consta de 60 variables discretas. El módulo de la evaluación incluye los estados límite último y de servicio que se aplican comúnmente para estas estructuras: flexión, cortante, torsor, fisuración, flechas, etc. El uso del algoritmo SA requiere previamente su calibración. La heurística se procesa 9 veces, obteniéndose información estadística sobre el valor mínimo, el medio y las desviaciones. El mejor resultado obtenido tiene un coste de 109.127 €.  Finalmente, entre las principales conclusiones de este estudio, destaca que económicamente es factible el uso de fibras de acero en el hormigón estructural y que las soluciones y los tiempos de proceso computacional son tales, que este método se puede aplicar de un modo práctico a casos reales.

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.

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 son ventajosos 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 ser formulado 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.

TORRES-MACHÍ, C.; YEPES, V.; PELLICER, E.; CHAMORRO, A. (2013). Optimización en la gestión de activos. Aplicación al mantenimiento de múltiples estructuras de edificación. 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.323-332. ISBN: 978-84-8363-992-4.

En una sociedad desarrollada en la que el nivel de inversión en nuevas infra-estructuras tiende a estabilizarse, su conservación pasa a ser uno de los retos a los que deben enfrentarse sus gestores, de forma que los recursos escasos de los que disponen, sean destinados en la mejor alternativa posible. Sin embargo, la asignación óptima de recursos de conservación es un problema que no tiene una solución directa. De hecho, la resolución del problema de asignación de recursos para el mantenimiento de una infra-estructuras presenta un problema de explosión combinatoria, pues existen ST soluciones factibles para la gestión una infraestructura con S posibles tratamientos de conservación y un periodo de análisis de T años. El objetivo de esta comunicación es presentar un modelo matemático que permite optimizar los recursos asignados al mantenimiento de una infraestructura de edificación, de forma que se maximice el nivel de servicio de la misma, cumpliendo además con unas restricciones presupuestarias y unos niveles mínimos de conservación.

YEPES, V.; ALCALÁ, J.; MARTÍ, J.V.;  GONZÁLEZ-VIDOSA, F. (2013). Cómo predimensionar muros óptimos sin calculadora usando la inteligencia artificial. 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. 119-134. ISBN: 978-84-8363-992-4.

El trabajo presenta un estudio de diseño automático de muros ménsula de hormigón armado basado en el recocido simulado, dentro de un esquema de búsqueda en entornos variables, como metaheurística de optimización económica. Cada solución se caracteriza por 20 variables de diseño: 4 geométricas relacionadas con el espesor del alzado y de la zapata, así como con las longitudes de la puntera y del talón; 4 tipos de material y 12 variables relacionadas con el armado. El trabajo estudia la importancia relativa de factores tales como el coeficiente de rozamiento suelo-zapata, el ángulo de rozamiento muro-relleno y la limitación de la flecha del alzado. Por último, se presenta un estudio paramétrico de muros de 4 a 10 metros de altura total para diferentes rellenos y condiciones de carga. Se aportan valores medios de costes, volúmenes de hormigón, espesor de alzados y zapatas, longitudes de punteras y talones que pueden ser útiles para el predimensionado económico de muros. Los resultados muestran cómo la inteligencia artificial es capaz de dimensionar de forma automática los muros ménsula de hormigón armado, detectando relaciones aportadas por la experiencia en el cálculo de este tipo de estructuras. Se aporta, como novedad de gran interés práctico, unas reglas sencillas que permiten predimensionar y estimar económicamente de forma rápida este tipo de estructuras.

YEPES, V.; MARTÍ, J.V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Métodos empleados en el proyecto HORSOST sobre diseño sostenible con hormigón no convencional. 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. 259-272. ISBN: 978-84-8363-992-4.

El objetivo fundamental del proyecto de investigación HORSOST consiste en establecer pautas de diseño eficiente de estructuras realizadas con hormigón no convencional optimizadas heurísticamente con funciones multiobjetivo relacionadas con la sostenibilidad. Se pretende avanzar en el establecimiento de nuevos diseños que permitan extraer las ventajas que aportan los hormigones especiales, en particular hormigones de alta resistencia, hormigones con fibras, hormigones autocompactantes. Para ello se utiliza el análisis del ciclo de vida de dichas estructuras (elaboración, transporte, procedimientos constructivos, mantenimiento, etc.) considerando aspectos energéticos, medioambientales, sociales y económicos. La optimización heurística permite evaluar los diseños más eficientes, comparar soluciones y generar bases de datos sobre las que aplicar herramientas procedentes de la minería de datos y del aprendizaje automático para extraer información no trivial que permita fórmulas de predimensionamiento. La posibilidad de análisis se debe a que las herramientas matemáticas empleadas presentan un carácter general. Se aplican técnicas como redes neuronales o la teoría del valor extremo además de otras herramientas más habituales como la regresión lineal múltiple o el análisis por componentes principales.

 

¿Qué es la investigación operativa?

La investigación de operaciones o investigación operativa es una rama de las matemáticas que consiste en el uso de modelos matemáticos, estadística y algoritmos con objeto de modelar y resolver problemas complejos  determinando la solución óptima y permitiendo, de este modo, tomar decisiones.  Frecuentemente trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede optimizar un objetivo definido, como la maximización de los beneficios o la minimización de costos.

Aunque su nacimiento como ciencia se establece durante la Segunda Guerra Mundial y debe su nombre a las operaciones militares, los verdaderos orígenes de la Investigación Operativa se remontan mucho más atrás en el tiempo, hasta el siglo XVII. Esta disciplina nació en Inglaterra durante la Segunda Guerra Mundial como estrategia para encontrar soluciones a problemas militares, para ello fue necesario crear un Grupo de Investigación de Operaciones Militares conformado por un grupo de científicos multidisciplinares. Al terminar la guerra este método fue empleado en darle solución a problemas generales como el control de inventarios, asignación de recursos, líneas de espera, entre otros. Esta técnica cumplió sus objetivos en la década de los cincuenta y sesenta, hasta su desarrollo total en la actualidad. Sin embargo su auge es debido, en su mayor parte, al gran desarrollo de la informática, gracias a la cual es posible resolver problemas en la práctica y obtener soluciones que de otra forma conllevarían un enorme tiempo de cálculo. Debido a este éxito, la Investigación Operativa  se extendió a otros campos tales como la industria, física, informática, economía, estadística y probabilidad, ecología, educación, servicio social, …, siendo hoy en día utilizada prácticamente en todas las áreas. Algunos de los promotores más importantes de la filosofía y aplicación de la investigación de operaciones son C.W. Churchman, R.L. Ackoff y R. Bellman. Actualmente la Investigación Operativa incluye gran cantidad de ramas como la Programación Lineal, Programación No Lineal, Programación Dinámica, Simulación, Teoría de Colas, Teoría de Inventarios, Teoría de Grafos, etc.

Os presento ahora un vídeo, que no llega a 3 minutos de duración sobre el tema. Espero que os guste.

Automatic design of concrete vaults using iterated local search and extreme value estimation

La optimización de estructuras reales de hormigón armado constituye un campo de gran interés no sólo en la investigación, sino en la aplicación real en obra. Os paso un artículo reciente donde se explica una forma de optimizar bóvedas de hormigón empleadas habitualmente en pasos inferiores como falsos túneles. Los ahorros que se pueden conseguir, en este caso, han sido de un 7% respecto a un diseño tradicional. En el caso de obras lineales de gran longitud, los ahorros pueden ser nada despreciables. La revista Latin American Journal of Solids and Structures es una revista en abierto, de donde podéis descargaros éste y otros artículos de interés.

 

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

¿Qué es un modelo matemático de optimización?

La optimización significa hallar el valor máximo o mínimo de una cierta función, definida en un dominio. En los problemas de decisión que generalmente se presentan en la vida empresarial existen una serie de recursos escasos (personal, presupuesto, tiempo), o de requisitos mínimos a cumplir (producción, horas de descanso), que condicionan la elección de la solución adecuada, ya sea a nivel estratégico, táctico e incluso operativo. Por lo general, el propósito perseguido al tomar una decisión consiste en llevar a cabo el plan propuesto de una manera óptima: mínimos costos o máximo beneficio.

Desgraciadamente, la complejidad de las situaciones reales es de tal magnitud que en numerosas ocasiones son inviables los métodos matemáticos de resolución exactos, de modo que los problemas de optimización planteados frecuentemente se resuelven con métodos aproximados que proporcionan soluciones factibles que sean satisfactorias.

Os dejamos aquí un pequeño vídeo para divulgar lo que significa un modelo matemático de optimización. Espero que os guste.

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