Algoritmos genéticos paralelos y su aplicación al diseño de redes de comunicaciones confiables

Abstract

Esta Tesis presenta el estudio de las técnicas de computación evolutiva y la aplicación de técnicas de procesamiento de alta performance para implementar modelos de algoritmos genéticos capaces de ejecutar en un ambiente paralelo distribuido. Se aborda la aplicación de algoritmos evolutivos al caso concreto de problemas que surgen al diseñar redes de comunicaciones de alta conectividad topológica. En particular, se concentró el estudio sobre una clase de problemas de diseño de redes de comunicaciones que pueden modelarse bajo el denominado Problema de Steiner Generalizado. Dada una red de comunicaciones con ciertos nodos distinguidos denominados nodos terminales, el Problema de Steiner Generalizado propone diseñar una subred de mínimo costo que verifique un conjunto de requisitos prefijados de conectividad entre pares de nodos terminales. En el trabajo se evalúan diferentes algoritmos evolutivos puros e híbridos en sus versiones secuenciales y paralelas, presentando un estudio comparativo que reporta resultados satisfactorios tanto desde el punto de vista de la calidad de resultados obtenidos como desde el punto de vista de la mejora de eficiencia computacional alcanzada por las versiones paralelas de los algoritmos con respecto a sus contrapartes secuenciales.