Algoritmos genéticos paralelos para el problema general de steiner en grafos

Abstract

Este trabajo presenta un algoritmo genético paralelo para encontrar soluciones aproximadas al Problema de Steiner Generalizado (GSP). El problema esta vinculado con la construcción de una red confiable y de mínimo costo. En la construcción de estas redes se contraponen dos objetivos: minimización del costo total de la red y la maximización de su confiabilidad. Existen muchas aplicaciones al modelo GSP pero se conocen pocas heurísticas que resuelvan el problema en forma eficiente dado que es NP-completo. Este proyecto aporta una nueva forma de encontrar soluciones aproximadas al GSP para el caso mas general de grafos utilizando un algoritmo genético. El punto esencial en la construcción del GA fue la representación de una solución factible. Se presentan dos representaciones y se comparan ventajas y desventajas de cada una. También se presentan distintos modelos de paralelismo en algoritmos genéticos y se provee una implementación para dos de ellos. Se presenta una comparación de los modelo implementados entres si con el algoritmo genético sin paralelizar.