Algoritmos evolutivos aplicados a problemas de diseño de redes confiables

Abstract

Los problemas de diseño topológico de redes de información caen dentro de la categoría de problemas de optimización combinatoria. En muchos casos, cuando el tamaño de la instancia del problema crece, los tiempos de resolución del mismo a través de técnicas exhaustivas pueden resultar inadmisibles. Por esta razón las heurísticas en general y la computación evolutiva en particular, son una alternativa válida para atacar este tipo de problemas. Este trabajo se centra en la resolución de problemas de diseño óptimo de redes confiables utilizando técnicas evolutivas. A continuación se muestra un esquema del desarrollo del mismo. En el capítulo 2 se realiza una revisión de las metodologías existentes aplicadas para resolver problemas de diseño de redes. La complejidad matemática asociada a la resolución de la obtención de la topología óptima se discute en el Capítulo 3. El abordaje del diseño de una red de comunicaciones cuando la función objetivo es el costo de implementación y la restricción recae sobre la confiabilidad del sistema, está plasmado en este capitulo, ubicando al problema dentro de una clase de problemas de optimización combinatoria. Este diseño se utiliza como problema test para analizar el comportamiento de un algoritmo estocástico. En el capítulo 4 se realiza una revisión de las técnicas proporcionadas por la computación evolutiva para resolver problemas de optimización. El mismo contiene los conceptos básicos relacionados con la aplicación de Algoritmos Evolutivos (AE), basados en AG, para resolver problemas de optimización. En el capítulo 5 se describe el diseño de un algoritmo evolutivo con conocimiento específico del problema para encontrar una topología de mínimo costo sujeto a restricciones de confiabilidad entre todas las terminales de la red. El Capítulo 6 contiene ejemplos de diseño de redes resueltos a través de las metodologías propuestas en esta tesis. Las conclusiones y futuras líneas de investigación se presentan en el Capítulo 7.