Título:
Ant Colony Optimization para la resolución del Problema de Steiner Generalizado
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Pedemonte, Martín
Tutor:
Cancela, Héctor
Tipo de documento:
Tesis de maestría
Editor:
Palabras clave:
Ant Colony Optimization
Computación de alto desempeño
Problema de Steiner
Metaheurísticas
Computación de alto desempeño
Problema de Steiner
Metaheurísticas
Descriptores:
Año de publicación:
2009
Contenido:
Resumen:
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
Descripción:
Editorial:
UR. FI-INCO,
EN:
Financiadores:
Citación:
PEDEMONTE, M. "Ant Colony Optimization para la resolución del Problema de Steiner Generalizado". Tesis de maestría, Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación – PEDECIBA, 2009.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/2955
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Título Obtenido:
Magíster en Informática
Facultad o Servicio que otorga el Título:
Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación – PEDECIBA
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| tesis-pedemonte.pdf | — | 3.15 MB | Adobe PDF |