Ant Colony Optimization para la resolución del Problema de Steiner Generalizado

Abstract

Esta tesis presenta un estudio de la metaheurïstica Ant Colony Optimization (ACO) y de la aplicación de técnicas de computación de alto desempeño a dicha metaheurïstica. En particular, se aborda la aplicación de ACO a la resolución del Problema de Steiner Generalizado (GSP). El GSP consiste en el diseño de una subred de costo mínimo que verifique ciertos requerimientos prefijados de conexión entre pares de nodos distinguidos. En el trabajo se presentan versiones ACO con dos enfoques constructivos de la solución distintos. El primero de los enfoques se basa en incorporar aristas hasta completar un camino, mientras que el segundo determina los K caminos más cortos y realiza una selección entre ellos. También se propone una novedosa formulación de un modelo celular aplicado a la metaheurística ACO y su posible paralelización Se incluye los resultados de un estudio experimental exhaustivo de todas las propuestas formuladas en este trabajo, comprendiendo la evaluación de los enfoques basados en aristas y en caminos y el analizas del efecto del tamaño de la población, de la cantidad de caminos y de incorporar operadores de búsqueda local para el enfoque basado en caminos. El estudio permitió comprobar que la utilización de un enfoque basado en caminos con la incorporación del operador de búsqueda local iterado obtiene resultados competitivos con las mejores técnicas disponibles en la actualidad. Asimismo, se evaluaron las versiones secuencial y paralela del modelo celular propuesto, constatándose que el desempeño computacional de la implementación paralela es muy promisoria, aunque se producen leves pérdidas en la calidad de las soluciones con relación a estructurar la población en la forma tradicional