Algoritmo del solterón aplicado a la optimización de rutas con flotas heterogéneas VRPHESTW

Me ha parecido interesante rescatar una pequeña publicación, que ya tiene 10 años, donde se aplicaba un algoritmo de optimización heurística curioso: Old Bachelor Acceptance, o “algoritmo del solterón“. En este caso, aplicado a la optimización de redes de transporte con flotas heterogéneas. Resulta curioso ver cómo determinados comportamientos sociales (colonias de hormigas), principios naturales (teoría de la evolución) o recreaciones de nuestro cerebro (redes neuronales) son capaces de resolver problemas complejos de optimización.

Espero que os sea de interés.

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

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.

Descargar (PDF, 141KB)

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.

¿Cómo decidir cuando tenemos un dilema? El óptimo de Pareto

Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios;  si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado “óptimo de Pareto“. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.

 

 

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”

¿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 algoritmo?

Algoritmo de Euclides
Algoritmo de Euclides

Un algoritmo es un conjunto prescrito de reglas o instrucciones bien definidas para la resolución de un problema. En general, se trata de encontrar el método más “eficiente”, no siendo baladí el modo de medir dicha eficiencia. Para resolver esta circunstancia, en la década de los 70 numerosos científicos se interesaron por la complejidad computacional de los problemas y los algoritmos. En muchos casos se asimila el rendimiento algorítmico a la medida del tiempo medio de ejecución empleado por un procedimiento para completar su operación con un conjunto de datos. Además, es posible relacionar el esfuerzo de cálculo con la dimensión del problema a resolver.

Un algoritmo muestra una complejidad polinómica si necesita un tiempo O(nk), donde n muestra la dimensión de entrada y k es una constante independiente de n. Si la función que denota la complejidad no está acotada por un polinomio, el algoritmo presenta una complejidad en tiempo exponencial.

 Un problema de decisión es aquel que puede ser contestado con una afirmación o una negación. Llamemos P a la clase de problemas de decisión que pueden ser resueltos en tiempo cálculo que crece de forma polinomial ante incrementos lineales del número de elementos que intervienen, y NP aquellos solubles en un tiempo polinomial indeterminado, es decir, que se puede resolver en tiempo polinomial con una máquina Turing no determinística (ordenador). Un ordenador no determinístico puede ser contemplado como un autómata capaz de ejecutar un número ilimitado (pero finito) de ejecuciones en paralelo. Sólo los problemas en P son resolubles eficientemente mediante algoritmos, no conociéndose un procedimiento polinomial de resolución para los NP, siendo obvio que P pertenezca NP. Si lo contrario también ocurriera, P pertenecería a NP, querría decir que para la mayoría de los problemas de interés existen algoritmos eficientes que los resolvieran. Sin embargo, no se conoce la forma de demostrar que la igualdad P=NP sea cierta, ni tampoco que haya problemas en NP que no estén en P, es decir, la existencia de algún problema en NP que no se pueda resolver en tiempo polinómico (ver Díaz et al., 1996).

Un problema X se dice que es NP-completo (NPC) si cualquier problema en NP se puede transformar en X en tiempo polinomial. En este sentido, los NPC son una clase de problemas en NP muy difíciles. Si un solo problema en NPC se resolviera en tiempo polinomial, entonces todos los problemas NP también lo harían, lo cual no está demostrado a fecha de hoy. Sin embargo, no es necesario demostrar que un problema pertenece a NP para ofrecer evidencias de que es imposible resolverlo eficientemente. Sea Y un problema de decisión que no se conoce si es NP. Si un problema en NP-completo puede transformarse en Y, entonces Y no puede resolverse en tiempo polinomial (salvo que se demuestre que P=NP). Este problema Y sería como mínimo tan difícil como los NPC, llamándose NP-hard (NPH). Es decir, pueden existir problemas NPH que no sean NPC. A efectos prácticos únicamente nos interesa confirmar la NP-dificultad de un problema.

En la vida real existen numerosos problemas prácticos para los cuales se desconocen algoritmos eficientes (Yepes, 2002), pero cuya dificultad intrínseca no ha conseguido demostrar nadie. Es posible que existan realmente algoritmos eficientes, aunque también puede ocurrir que estos problemas sean intrínsecamente difíciles; no obstante, se carecen de las técnicas necesarias para demostrarlo. La importancia práctica de estos problemas ha asegurado que cada uno de ellos por separado haya sido objeto de esfuerzos sostenidos para hallar un método de solución eficiente. Por este motivo, se cree que no existen tales algoritmos. Como nadie, de momento, ha encontrado algoritmos eficientes para los problemas NP-completos, en cuanto se demuestra que un problema pertenece a esta clase, muchos investigadores tienden a pensar que no merece la pena buscar algoritmos eficientes para ellos. Lamentablemente, muchos de los problemas importantes que aparecen en Investigación Operativa son NP-completos. En Garey y Johnson (1979) se encuentra una visión más completa de la complejidad computacional.

REFERENCIAS

DÍAZ, A.; GLOVER, F.; GHAZIRI, H.M.; GONZÁLEZ, J.L.; LAGUNA, M.; MOSCATO, P.; TSENG, F.T. (1996). Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería. Paraninfo, Madrid. 235 pp.

GAREY, M.R.; JOHNSON, D.S. (1979). Computers and Intractability – A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.

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.