Ingeniero

PEDECIBA Informática
Instituto de Computación – Facultad de Ingeniería
Universidad de la República
Montevideo, Uruguay

TESIS DE MAESTRÍA
EN INFORMÁTICA
ALGORITMOS GENÉTICOS PARALELOS Y
SU APLICACIÓN AL DISEÑO DE REDES
DE COMUNICACIONES CONFIABLES
SERGIO NESMACHNOW
JULIO 2004

Orientador de Tesis: Dr. Ing. Héctor Cancela
Supervisor: Dr. Ing. Héctor Cancela

Algoritmos GenéticosParalelos y su Aplicación al
Diseño de Redes de Comunicaciones Confiables
Sergio Nesmachnow
ISSN
Tesis de Maestría en Informática
Reporte Técnico RT04-07
PEDECIBA
Instituto de Computación – Facultad de Ingeniería
Universidad de la República.
Montevideo, Uruguay, Julio de 2004.

ALGORITMOS GENÉTICOS PARALELOS Y SU APLICACIÓN
AL DISEÑO DE REDES DE COMUNICACIONES CONFIABLES

RESUMENEsta 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 conectividadtopoló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 requisitosprefijados 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 alcanzadapor las versiones
paralelas de los algoritmos con respecto a sus contrapartes secuenciales.
Palabras clave: Algoritmos genéticos paralelos, redes de comunicaciones confiables.

I

II

ÍNDICE

RESUMEN …………………………………………………………………………

I

ÍNDICE ….…………………………………………………………………………

III

CAPÍTULO 1. INTRODUCCIÓN ……………………………………………………

1

CAPÍTULO 2. TÉCNICAS DE COMPUTACIÓN EVOLUTIVA……………………….
2.1. INTRODUCCIÓN …………………………………………….………….
2.2. TÉCNICAS DE COMPUTACIÓN EVOLUTIVA …………………………….
2.3. RESEÑA HISTÓRICA ……………………………………………………
2.3.1. PRIMERAS PROPUESTAS …………………….………………..
2.3.2. ESTRATEGIAS DE EVOLUCIÓN ……………………………….
2.3.3. PROGRAMACIÓN EVOLUTIVA ………………………………..
2.3.4. ALGORITMOS GENÉTICOS ……………………………………
2.4. ALGORITMOS GENÉTICOS …………………………………………….
2.4.1. REPRESENTACIÓN DESOLUCIONES ………………………….
2.4.2. FUNCIÓN DE FITNESS ………………………………………..
2.4.3. OPERADORES ………………………………………………..
2.4.4. MODELOS DE EVOLUCIÓN ……………………………………
2.4.5. FORMALIZACIÓN DEL MECANISMO DE LOS ALGORITMOS
GENÉTICOS …………………………………………………...
2.4.6. COMPARACIÓN DE LOS ALGORITMOS GENÉTICOS CON OTRAS
TÉCNICAS HEURÍSTICAS ……………………………………...
2.5. CONCLUSIONES ………………………………………………………..
2.6. NOTA SOBRE LASREFERENCIAS BIBLIOGRÁFICAS ……………………..

5
5
6
7
7
10
11
12
13
14
15
16
18

CAPÍTULO 3. ALGORITMOS GENÉTICOS Y TÉCNICAS DE PROGRAMACIÓN DE
ALTA PERFORMANCE ……………………………………………..
3.1. INTRODUCCIÓN ………………………………………………………..
3.2. TÉCNICAS DE PROGRAMACIÓN DE ALTA PERFORMANCE ………………
3.2.1. ARQUITECTURAS DE COMPUTADORES PARALELOS …………..
3.2.2. CLASIFICACIÓN DE ARQUITECTURAS PARALELAS …………...3.2.3. PARADIGMAS DE PROGRAMACIÓN PARALELA ……………….
3.2.4. TÉCNICAS Y HERRAMIENTAS PARA EL DISEÑO E
IMPLEMENTACIÓN DE APLICACIONES PARALELAS ……………
3.2.5. LA BIBLIOTECA MPI …………………………………………
III

18
19
20
20
21
21
22
22
24
26
27
28

ÍNDICE

3.2.6.

MEDIDAS DE PERFORMANCE …………………………………
3.2.6.1. MODELO DE PERFORMANCE ………………………..
3.2.6.2. SPEEDUP Y EFICIENCIA DE UN...