Aplicaciones en la industria del problema de Steiner y su resolución mediante algoritmos genéticos

Abstract

En el siglo XIX se empezó a formular el problema de Steiner fruto de la curiosidad de algunos matemáticos, como Fermat, que querían obtener: puntos estratégicos en el espacio que permitiesen minimizar la distancia a otros puntos dados. Sin embargo, la verdadera utilidad del problema surgió con la revolución industrial y las nuevas tecnologías. Para aquel entonces, el matemático Steiner estaba completamente inmerso en la resolución del problema. Así, las redes de infraestructuras, las redes eléctricas, las tuberías de aguas y, en general, todos los problemas referentes a la optimización de caminos fueron las aplicaciones que dio expansión al problema de Steiner. Años más tarde, gracias al desarrollo de las computadoras, fue posible la creación de algoritmos heurísticos que facilitasen la resolución de problemas NPCompletos. Como el algoritmo de Steiner, del que no es posible su resolución en tiempo polinomial. Sin ir más lejos, los algoritmos genéticos surgieron como necesidad para la resolución del problema, con cada vez más aplicaciones sofisticadas. Tal es el caso de la posible inclusión de los más de 1000 transistores que llega a tener un microprocesador, la minimización de las rutas, la estructura mínima energética de las proteínas o la optimización de un porfolio de acciones… Todas ellas son ejemplo de aplicaciones que motivan el desarrollo de la metaheurística. Es por ello, el presente documento que explica este problema tan peculiar de tanta utilidad actualmente. Comenzando por una reseña histórica, se realiza una pequeña introducción del problema. Para avanzar en el tema, en la sección 2 se abarca la teoría del problema de Steiner, así como las primeras técnicas de resolución exactas. Durante la sección 3, se informa de la diversa índole de aplicaciones del problema con casos prácticos y reales. A continuación, en la sección 4 se explica el método de resolución que da respuesta al algoritmo genético implementado en este documento. Se aborda tanto el algoritmo genético como el árbol de mínima expansión (MST). Seguidamente, en la sección 5 se muestra el programa implementado. Este, con más de 10 funciones y 400 líneas de código será detalladamente explicado función a función mostrándose sus diagramas de flujo y pseudocódigos. Finalmente, la sección 6 culmina con la resolución real de problemas de Steiner utilizando el programa implementado en MATLAB. Para terminar, durante las conclusiones obtenidas se podrá ver cómo la complejidad de los problemas solucionados dificulta la obtención del óptimo, debido a que el problema es NP-Completo. Por otro lado, el ajuste de parámetros claves, como el número de iteraciones y la densidad de nodos terminales, podrán disminuir significativamente el tiempo de implementación y el error respecto al óptimo cometido por las técnicas heurísticas. Por ello, se pretende finalmente destacar cómo los algoritmos genéticos resultan ser técnicas muy potentes de resolución mejorando los resultados considerablemente para la mayoría de los casos. Además, el MST se interpone como un algoritmo de peso para problemas de difícil resolución por su breve implementación. Por todo ello, se pretende hacer llegar la gran utilidad del problema. Se muestran aplicaciones de una gran importancia para no solo la optimización económica o energética, sino también, para la investigación del hombre sobre sus antepasados y morfología. A parte, la implementación real del problema de Steiner complementa al documento. Este permite dar a conocer a sus lectores la posibilidad de generar algoritmos válidos para la resolución del problema.