Categoría: optimización
¿Qué son las metaheurísticas?
¿Cómo se podrían optimizar, en tiempos de cálculo razonables, problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otros tipos de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que resulta imposible resolverlos con métodos matemáticos exactos? La respuesta consiste en métodos aproximados, también denominados heurísticos. Este artículo divulgativo trata de ampliar otros anteriores en los que ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. 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 sobre los problemas de optimización combinatoria se centra en el diseño de estrategias generales que guíen 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 diseñados para resolver problemas de optimización combinatoria difíciles, 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 que combinan 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 pueden 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 la memoria que guíe la exploración del espacio de posibles elecciones permite otro tipo de agrupamiento. En otras circunstancias, se emplean perturbaciones en las opciones, en la topología del espacio de soluciones o en la función objetivo. En la Figura se presenta una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), que comparten todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que en este momento existen muchas más técnicas de optimización, pero dicha clasificación puede ser un punto de partida para una mejor taxonomía de dichas técnicas.
Las metaheurísticas empleadas en la optimización combinatoria 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 este 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 distintos 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)
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 Enseñ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 presentados. 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 ha experimentado 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 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. Por último, una vez seleccionada la mejor calibración de la SA, se ha estudiado la sensibilidad del modelo y se ha realizado un análisis 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 el recocido simulado multiobjetivo “Multiobjective Simulated Annealing” (MOSA) se utilizan para buscar, dentro del espacio de soluciones factibles, aquellas que mejoren criterios como el coste, las emisiones de CO2 o la 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 con la Instrucción de Hormigón Estructural (EHE-08), los requisitos de seguridad estructural, así como los de los aspectos constructivos o geométricos. El análisis comparativo de los objetivos servirá de guía para el diseño sostenible de estructuras de hormigón. Los resultados obtenidos muestran una clara tendencia en el 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 de sostenibilidad, con el objetivo de reducir 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, que emplea un algoritmo memético híbrido que combina la búsqueda poblacional de soluciones mediante algoritmos genéticos con una búsqueda en entornos variables (VDNS). Este algoritmo se aplica a un tablero formado por dos vigas isostáticas, con 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 evaluación considera los estados límite último y de servicio que se aplican habitualmente a estas estructuras. El uso del algoritmo memético requiere calibrarlo previamente. Cada una de las heurísticas se procesa nueve veces, obteniéndose información estadística sobre el valor mínimo, el valor medio y las desviaciones. El procedimiento presentado permite su 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 mediante 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 evaluación incluye los estados límite último y de servicio que se aplican comúnmente a estas estructuras: flexión, cortante, torsor, fisuración, flechas, etc. El uso del algoritmo SA requiere calibrarlo previamente. La heurística se aplica 9 veces, obteniéndose información estadística sobre el valor mínimo, el valor 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 resultan ventajosos frente a soluciones más convencionales en ciertas condiciones de iluminación. El proceso de diseño de estos forjados puede plantearse como un problema de optimización que, abordado con métodos heurísticos, puede formularse de manera plenamente realista. Se pueden encontrar diseños completos de forjados optimizados no solo con criterios de economía, sino también con criterios de sostenibilidad, y así comparar ambos casos. Los resultados obtenidos en este trabajo muestran una clara tendencia a presentar cantos muy estrictos en los óptimos. Aplicando criterios de sostenibilidad, se tiende a hormigones de mayor resistencia que con criterios económicos. Finalmente, se han realizado pruebas de sensibilidad a los precios, que muestran una gran 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 infraestructuras 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 sin una solución directa. De hecho, la resolución del problema de asignación de recursos para el mantenimiento de una infraestructura presenta un problema de explosión combinatoria, pues existen ST soluciones factibles para la gestión de 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 variables 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 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 sobre muros de 4 a 10 metros de altura total, para distintos rellenos y condiciones de carga. Se aportan valores medios de costes, volúmenes de hormigón, espesores de alzados y zapatas, y longitudes de punteras y talones, que pueden resultar útiles para el predimensionado económico de muros. Los resultados muestran cómo la inteligencia artificial es capaz de dimensionar automáticamente los muros ménsula de hormigón armado, detectando relaciones aportadas por la experiencia en el cálculo de este tipo de estructuras. Se aportan, como novedad de gran interés práctico, unas reglas sencillas que permiten predimensionar y estimar económicamente y rápidamente 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 de hormigón no convencional, optimizadas heurísticamente mediante 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 cuales aplicar herramientas procedentes de la minería de datos y del aprendizaje automático para extraer información no trivial que permita fórmular predimensionamientos. La posibilidad de análisis se debe a que las herramientas matemáticas empleadas son de carácter general. Se aplican técnicas como las redes neuronales o la teoría del valor extremo, además de otras herramientas 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, se trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite analizar la toma de decisiones, teniendo en cuenta la escasez de recursos, para determinar cómo optimizar un objetivo definido, como la maximización de los beneficios o la minimización de los costes.
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, lo que requirió la creación de un Grupo de Investigación de Operaciones Militares compuesto por científicos multidisciplinares. Al terminar la guerra, este método se empleó para resolver problemas generales como el control de inventarios, la asignación de recursos y las líneas de espera, entre otros. Esta técnica cumplió sus objetivos en las décadas de los cincuenta y sesenta, hasta su pleno desarrollo en la actualidad. Sin embargo, su auge se debe en gran medida al desarrollo de la informática, gracias a la cual es posible resolver problemas y obtener soluciones que, de otro modo, requerirían un enorme tiempo de cálculo. Debido a su éxito, la investigación operativa se extendió a otros campos, como la industria, la física, la informática, la economía, la estadística y la probabilidad, la ecología, la educación, el servicio social, entre otros, y actualmente se utiliza prácticamente en todas las áreas. Algunos de los promotores más importantes de la filosofía y la aplicación de la investigación de operaciones son C.W. Entre ellos se encuentran Churchman, R. L. Ackoff y R. Bellman. Actualmente, la investigación operativa incluye una amplia gama de ramas, como la programación lineal, la programación no lineal, la programación dinámica, la simulación, la teoría de colas, la teoría de inventarios, la teoría de grafos, entre otras.
Os presento ahora un vídeo sobre el tema que no llega a 3 minutos de duración. Espero que os guste.
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
La paradoja de elegir
En las clases introductorias a una asignatura que denominamos «Modelos predictivos y de optimización de estructuras de hormigón» empezamos a hablar sobre el problema de la toma de decisiones. Este es el punto de partida que originó en la Segunda Guerra Mundial una disciplina matemática que algunos denominan investigación de operaciones.
En este artículo, traigo a colación un vídeo en el que el psicólogo Barry Schwartz señala un principio central de las sociedades occidentales: la libertad de elección. Según Schwartz, elegir no nos ha hecho más libres, sino más paralizados; no más felices, sino más insatisfechos.
Desconozco si estaréis de acuerdo con esta paradoja, pero es un buen punto de partida para debatir en clase cuestiones tan interesantes como las siguientes: ¿por qué es tan difícil tomar una decisión?, ¿qué pasa cuando hay muchas posibilidades de elegir algo?, ¿qué relación existe entre el coste de oportunidad y la posibilidad de elegir algo?, o ¿estáis de acuerdo en que un aumento desmesurado en la capacidad de elegir disminuye la satisfacción?
Uno de los aspectos que me gusta abordar con estas reflexiones es plantear a los alumnos de posgrado que la realidad es mucho más compleja de lo que parece y que la enseñanza tradicional en el campo de las ingenierías, que enseña a solucionar un problema de una sola manera (normalmente la solución correcta en un examen), no se ajusta a la realidad, donde siempre hay muchas posibles soluciones, muchas de ellas válidas. El problema consiste en elegir una de ellas con criterio.
Os paso el vídeo a continuación. Está en inglés, pero podéis ver aquí una versión subtitulada en castellano. 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 solo en la investigación, sino también en su aplicación en obra. Os paso un artículo reciente que explica una forma de optimizar las 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 de acceso abierto, por lo que podéis descargar este y otros artículos de interés.
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.