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