Algoritmos genéticos aplicados al diseño de una red de comunicaciones confiable

Abstract

Durante el diseño de una red de comunicaciones, varias consideraciones deben ser tenidas en cuenta, dentro de las cuales se encuentran ciertas características de confiabilidad referentes a la topología de interconexión de sus nodos. Se podría decir que la confiabilidad global de una red es una medida que evalúa la probabilidad de éxito en la comunicación entre pares de nodos. Tanto en la evaluación de la confiabilidad de estas redes como en el diseño optimo de las mismas, surge la necesidad de resolver distintos problemas, algunos de ellos con soluciones rápidas (como por ejemplo, cortes mínimos y flujos máximos), y otros NP-completos (como el calculo de árboles de Steiner de peso máximo). Para atacar los problemas de optimización NP-completos, una alternativa es el uso de metaheurísticas genéricas de optimización combinatoria (como las conocidas Algoritmos Genéticos, Simulated Annealing, etc), que intentan dar una alternativa flexible. Este proyecto ataca el problema denominado Generalizado de Steiner (GSP) por medio de los Algoritmos Genéticos (AG) en su versión serial, para ello se proponen tres implementaciones del AG con diferentes representaciones del problema. Se presentan diversos resultados experimentales derivados de la realización de pruebas de comparación entre las diferentes instancias del AG, y su comparación con resultados obtenidos por otras metodologías de resolución.