Centro de Cálculo y Departamento de Investigación Operativa
Instituto de Computación - Facultad de Ingeniería
Entorno de la propuesta
La Facultad de Ingeniería, y en particular el Instituto de Computación han definido como una tarea prioritaria en desarrollo la vinculada a los temas de cálculo científico, incluyendo métodos numéricos y técnicas de programación paralela para el cálculo eficiente en problemas de gran porte. En este entorno, es de gran importancia la conformación de un equipo humano que maneje estos temas con rigor académico y orientación hacia aplicaciones prácticas.
En este sentido, el Instituto de Computación de la Facultad de Ingeniería cuenta con un cierta infraestructura informática (cluster de PCs, multiprocesador, máquina virtual paralela distribuida) que brinda el soporte de hardware imprescindible para realizar aplicaciones prácticas del tipo mencionado.
Complementariamente, dentro del mismo Instituto el grupo de Investigación Operativa viene desarrollando hace varios años trabajos en el área de diseño de redes de comunicaciones, con buenas propiedades en cuanto a su confiabilidad y performance. Dado que estos problemas son en general de gran consumo de tiempo de cálculo, es interesante el enfocar el empleo de algoritmos fácilmente paralelizables para resolver los mismos, lo que hasta el momento es un tema que no ha sido atacado.
Descripción del Proyecto A - Resumen de la investigación
Las técnicas de Computación Evolutiva surgieron sobre 1960, interpretando la naturaleza como una formidable máquina de resolver problemas y tratando de encontrar el origen de dicha potencialidad para utilizarla en la resolución de problemas complejos.
Los Algoritmos Genéticos constituyen uno de los paradigmas de Computación Evolutiva emergentes, basados en la simulación del principio de evolución. En los mismos, una población (de soluciones potenciales) evoluciona de acuerdo a interacciones (cruzamiento) y transformaciones únicas (mutaciones). Estos individuos se esfuerzan por sobrevivir: una selección programada en el mecanismo de cruzamiento, inclinada hacia los individuos más aptos, selecciona la generación siguiente. Luego de varias generaciones, la población converge hacia una solución óptima.
El auge de la computación paralela y distribuida ha renovado el interés práctico por los algoritmos basados en analogías de procesos naturales para la resolución de problemas de optimización en espacios de hipótesis que contienen complejas interacciones entre las distintas partes, donde el impacto de cada parte sobre la función de evaluación es difícil de especificar.
Este proyecto propone el estudio del paradigma de algoritmos genéticos, la implementación de diferentes modelos en un ambiente paralelo - distribuido, y su aplicación al caso concreto de problemas que surgen al diseñar redes de comunicaciones de alta conectividad topológica.
Los resultados obtenidos entre los diferentes modelos implementados se compararán entre sí y con otras metodologías de resolución del problema, analizando la mejora de performance obtenida al utilizar el ambiente paralelo - distribuido.
B - Fundamentación y antecedentes.
Dentro del Instituto de Computación de Facultad de Ingeniería, se han desarrollado separadamente dos líneas de trabajo en las cuales es posible enmarcar este proyecto. En el Departamento de Investigación Operativa se ha estudiado el problema de diseño de redes confiables, incluyendo el desarrollo y utilización de heurísticas de optimización. En el Centro de Cálculo se ha desarrollado el área de la computación paralela, y en particular del diseño de aplicaciones distribuidas en un cluster de computadoras, como una alternativa para atacar problemas que por su magnitud exigen un tiempo de cálculo considerable.
El formalismo de algoritmos genéticos se ha mostrado como una técnica adecuada para la resolución de problemas de optimización NP-completos, del tipo de los que surgen en el estudio de la confiabilidad de redes.
El modelo de algoritmos genéticos paralelos constituye una alternativa importante para mejorar la eficiencia de las soluciones propuestas para los problemas de grandes dimensiones resueltos mediante técnicas de programación evolutiva.
El contenido de este proyecto integra ambas líneas de trabajo con el objetivo de lograr una consolidación de las técnicas de programación evolutiva y procesamiento paralelo para la resolución de problemas de optimización de grandes dimensiones.
C - Objetivos generales y específicos
El objetivo general del proyecto consiste en el estudio de los paradigmas de algoritmos genéticos paralelos, y su aplicación al caso concreto del diseño de una red de alta conectividad topológica.
Los objetivos específicos del proyecto se mencionan a continuación :
comprensión y dominio de diferentes paradigmas de paralelismo aplicado a los algoritmos genéticos.
estudio de aplicabilidad de los paradigmas de paralelización sobre las distintas arquitecturas de máquinas paralelas disponibles en Facultad.
estudio de paradigmas adecuados para el problema del diseño de redes de comunicaciones confiables.
implementación de los paradigmas identificados como adecuados para el problema planteado.
experimentación y comparación entre los diferentes paradigmas implementados y con otras metodologías de resolución del problema; análisis de la mejora de performance obtenida al aplicar un modelo paralelo/distribuido.
D - Estrategia o actividades de investigación
Búsqueda bibliográfica y de herramientas en Internet.
Diseño y desarrollo de la aplicación.
Desarrollo de conjunto de problemas de prueba, experimentación y análisis de resultados.
E - Resultados esperados
Como resultado del proyecto, se espera obtener los siguientes resultados :
Una (o varias) implementaciones de algoritmos genéticos paralelos aplicados al problema de estudio (diseño de redes de comunicaciones confiables).
Una comprensión de la aplicabilidad de la programación evolutiva paralela para la resolución de problemas de diseño de redes de comunicaciones, en comparación con los resultados obtenidos utilizando otras metodologías.
Una evaluación actualizada de la potencia de cálculo de las arquitecturas paralelas disponibles en Facultad para la resolución de problemas complejos.
La consolidación de un grupo de trabajo en el área de programación evolutiva paralela para el cálculo eficiente aplicado a problemas de gran porte.
F - Referencias bibliográficas
Henrik Esbensen, "Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm", Proc. of The European Design and Test Conference, Paris, France. February 1994.
Shi-Wei Lee, Cheng-Shong Wu, Paper: "A K-Best Path Algorithm for Highly Reliable Communication Networks", IEICE Trans. Communication, Vol. E82-B, No.4 April 1999.
Markus Schwehm, "Parallel Population Models for Genetic Algorithms".
David E.Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison - Wesley, 1989, ISBN 0-20115767-5.
John H. Holland, "Hidden Order - How adaptation build complexity".
Colin Reeves, Paper "Hybrid Genetic Algorithms for Bin-packing and Related Problems". School of Mathematical and Information Sciences, Coventry University.
Ing. Franco Robledo, Tesis de Maestría en Informática: "Diseño Topológico de Redes". Febrero de 2000. Facultad de Ingeniería - Universidad de la República.
Samir W. Mahfound, "Finite Markov Chain Models of an Alternative Selection Strategy for the Genetic Algorithm", Complex Systems, 7(2), pp 155-170, Abril 1993.
Samir W. Mahfoud, "An Experimental Analysys of Boltzmann Tournament Selection", Ibid.
Markus Schwehm, "Parallel Models for Genetic Algorithms", Universität Erlangen-Nürnberg, IMMDVII.