| 520 |
## |
$a Introducción: En diversas áreas se plantean frecuentemente difíciles problemas de optimización. La búsqueda de las soluciones a tales problemas puede encararse aplicando métodos de búsqueda exacta, o métodos de búsqueda heurísticos. Cada método tiene sus fortalezas y sus debilidades, los métodos de búsqueda exacta permiten encontrar soluciones óptimas, mientras que los métodos heurísticos producen soluciones cercanas al óptimo. Pero por otro lado, las soluciones encontradas con los métodos de búsqueda exacta pueden llegar tarde mientras que las soluciones encontradas con los métodos heurísticos se logran en tiempos razonables. De modo que la naturaleza del problema a resolver, determina finalmente el método más apropiado. Entre los métodos heurísticos tienen gran aceptación aquellos que realizan el proceso de búsqueda emulando los mecanismos de la evolución y herencia de las especies naturales, a raíz de ello se los conoce como Algoritmos Genéticos. Aquí, se parte de una generación de individuos que representan soluciones potenciales, y mediante la aplicación de operadores genéticos y de una función de evaluación, se obtienen sucesivas generaciones. Las características de los operadores genéticos es tal que cada nueva generación contiene individuos que representan soluciones de mejor calidad. En la búsqueda de mejoras en la perfomance de los algoritmos genéticos, se han incorporado modificaciones a las características básicas de los operadores genéticos. Esto ha conducido a nuevos métodos que hoy se conocen como Algoritmos Evolutivos. Una de las tantas áreas en donde surgen problemas de optimización es en la de sistemas de computación distribuidos, particularmente cuando se debe resolver el problema de la asignación de procesadores a los procesos, ya sean procesos independientes o procesos que ejecutan módulos de un programa paralelo. La naturaleza de estos problemas determina que son preferibles soluciones oportunas, cercanas al óptimo, a soluciones óptimas tardías. A raíz de ello, los algoritmos evolutivos aparecen como una estrategia adecuada para la resolución de estos problemas. Una cuestión clave en los algoritmos evolutivos es definir adecuadamente la representación para las soluciones potenciales, y las características de los operadores genéticos. Estos factores son determinantes para el éxito de la búsqueda. Luego de la revisión de problemas centrales de administración de recursos en sistemas distribuidos y de las soluciones propuestas a través de distintas heurísticas, incluidas las evolutivas el presente trabajo trata el problema de la asignación de procesadores a módulos que conforman un programa paralelo. Se asume un sistema distribuido organizado en clusters y mediante un algoritmo evolutivo se busca una asignación tal que el tráfico entre cluster sea minimizado. Dentro de cada cluster seleccionado, el módulo será ejecutado en un nodo determinado aplicando algún criterio de balance de carga. En las etapas finales de esta tesis, haciendo uso de un sistema específicamente desarrollado para ello, y en base a un problema de asignación de clusters con óptimo conocido, se presenta un análisis de solucioens obtenidas aplicando diversas combinaciones de valores de parámetros del algoritmo evolutivo. Finalmente, se realiza una interpretación de los resultados justificando la bondad de la técnica como una alternativa válida en problemas de administración de recursos en un sistema distribuido. CALIFICACION DEPARTAMENTO DE GRADUADOS Calificación de la defensa oral: Sobresaliente - 10 (diez) Fecha: 18/12/02 |
