UN ALGORITMO EVOLUTIVO PARALELO MIXTO PARA EL TSP

CARLOS FIGUEREDO Departmento de Computacion – FACYT
Universidad de Carabobo Valencia, Estado Carabobo, Venezuela
email: [email protected]
RESUMEN En este trabajo se propone el desarrollo de un algoritmo evolutivo paralelo mixto que sea capaz de resolver instancias del TSP (Travelling Sales- man Problem) de gran tamano, minimizando a su vez el tiempo de respuesta. Las herramien- tas a utilizar para alcanzar el paralelismo mixto son el paso de mensajes usando MPI y la programacion multihilos usando openMP. La plataforma computacional usada fue un cluster dual con 32 procesadores. Los resultados muestran la superioridad del programa paralelo sobre su version secuencial para los problemas tratados en este trabajo. PALABRAS CLAVE Algoritmo Evolutivo, Problema del Agente Via- jero, Programacion de Hilos, Paso de Mensajes.
ABSTRACT In this work the development of a Mixed Par- allel Evolutive Algorithm is proposed to solve TSP (Traveling Salesman Problem); one able to solve large instances of this problem and lower the execution time at the same time. The tools used in order to reach the mixed parallelism are Message Passing using MPI and Multi-Threading Programming using openMP. The computational plataform used was a dual cluster with 32 proces- sors. The results show a better performance of the parallel algorithms in respect to the sequential algorithms
KEY WORDS Evolutive Algorithm, Traveling Salesman Prob- lem, Multi-Threading Programming, Message Passing
1. INTRODUCCION
En muchos ambitos de la Industria y la Tec- nologa la resolucion de problemas complejos de optimizacion combinatoria es la base para el au- mento de la productividad y la calidad del pro- ducto. Uno de los problemas de optimizacion combinatoria mas conocido y estudiado a lo largo de la historia es el llamado TSP (Traveling Sales- man Problem) o Problema del Agente Viajero.
Este trabajo supone un aporte a la industria venezolana, debido a la gran aplicabilidad direc- ta que brinda este problema, ya que el TSP surge naturalmente como un subproblema en muchas aplicaciones de logstica y transporte. Estas aplicaciones involucran la entrega de comida a domi- cilio, las rutas de camiones de entrega de paque- tes, entre otros, lo cual redunda en beneficios a los diferentes ambitos sociales.
Tambien existen otras areas interesantes donde se aplica este problema, un ejemplo clasico es establecer el orden en que una maquina taladra agujeros en una tabla de circuitos u otros objetos, donde los agujeros seran las ciudades y el costo del viaje es el tiempo que toma la cabeza
del taladro de un agujero a otro.
La estructura del TSP tambien ocurre en el analisis de la estructura de cristales, la evaluacion de motores de turbinas de gas, en reducir problemas de almacenamiento, el secuenciamiento de trabajos en una maquina y en asignacion de rutas a flotas aereas.
Como los antecedentes mas recientes para este trabajo se cuenta con el desarrollo de P. Jog, J. Suh, y D. Van Gucht [1] quienes en 1991 proponen la aplicacion de un algoritmo genetico paralelo para el TSP, posteriormente en 1992 P. P. Mutalik, L. R. Knight, J. L. Blanton y R. L. Wain- wright [2] plantean un enfoque bastante interesante y novedoso al introducir el concepto de un algoritmo basado en Anelo Simulado Paralelo y Algoritmos Geneticos Paralelos para la resolucion de problemas de Optimizacion Combinato- ria. Este mismo ano S. Tschoke, R. Luling, M. Racke y B. Monien [3] proponen un algoritmo de Ramificar y Acotar paralelo en una red de 1024 procesadores. Posteriormente, en 1994 Schwehm [4] presenta un interesante trabajo, en donde ex- pone los diferentes modelos de poblacion para algoritmos geneticos paralelos; finalmente en el ano de 1998 L. Villamizar [5] plantea un algoritmo genetico celular paralelo para el TSP, obteniendo como resultado una clara superioridad del algoritmo genetico celular paralelo sobre uno secuencial.
En los anos sesenta ya se haban propuesto metodos de busqueda aleatoria, sin embargo, no tuvieron mayor influencia en las ten- dencias seguidas por los cientficos en el area de investigacion. En tiempos recientes, un grupo de investigadores encabezados por John Holland de la Universidad de Michigan, han reconocido que las impresionantes potencialidades del proceso de evolucion natural pueden ser aprovechadas como metodologa de resolucion de problemas complejos. Para ello es necesario enfocar el proceso de resolucion como una dinamica evolutiva y emular consecuentemente los mecanismos nat- urales de seleccion y reproduccion, de esta forma el proceso de resolucion procede de una manera auto–organizativa, sin necesidad de forzar tipo al- guno de entrenamiento, en base a la accion de un
ambiente convenientemente definido [5]. El termino algoritmo evolutivo se usa
para designar a un conjunto de tecnicas que basan su funcionamiento en metaforas de los procesos biologicos como los principios geneticos y evolucion natural. Emplean una busqueda aleatoria de varios puntos concurrentemente sobre un espacio de soluciones factibles; surgen como una herramienta poderosa para hallar soluciones muy cercanas a las optimas en problemas que anteriormente se haban considerados complejos, ademas se pueden ajustar bien para tratar con problemas de optimizacion combinatorios eficientemente [6].
Los algoritmos evolutivos requieren de mucho poder de computo y recurso de memoria, lo cual los hace interesantes para ser paraleliza- dos. De hecho, el uso de computadoras paralelas puede acelerar la ejecucion de estos algoritmos y proporcionar el espacio de memoria requerido. Los algoritmos evolutivos tienen la habilidad de explorar varias regiones del espacio de busqueda concurrentemente, debido a la evolucion casi independiente de los individuos de la poblacion. Esto muestra un paralelismo inherente existente en ellos, cuya analoga se basa en que millones de personas de una poblacion evolucionan unas independientes de otras; lo cual indica que existe un grado de paralelismo que es directamente pro- porcional al tamano de la poblacion usada en la busqueda genetica [7].
Para una informacion mas detallada y ex- haustiva sobre los Algoritmos Evolutivos es re- comendable referirse a bibliografa reconocida en esta area, tal como [8],[9],[10].
En este trabajo se plantea la realizacion de un Algoritmo Evolutivo Paralelo Mixto, que sea capaz de obtener buenos resultados para instancias o benchmarks del TSP de grandes dime- siones.
2. EL PROBLEMA DEL TSP
Uno de los problemas de optimizacion combinatoria mas conocido y estudiado a lo largo de la historia es el llamado TSP (Traveling Salesman Problem) o Problema del Agente Viajero.
El problema del TSP puede ser enuncia- do como: “Dado un numero finito de ciudades as como tambien el costo asociado de viajar entre cada par de estas cuidades, encontrar el camino con menor costo asociado, de manera tal que se recorran todas las ciudades y se regrese a la ciudad origen”[11].
La manera formal de enunciar el problema es: “Dado un grafo completo y pesado G=(N,E,d) donde,
es el numero de nodos, es el conjun-
to de arcos que conectan completamente a los nodos, y es una funcion que asigna un vector a cada arco , donde cada elemento cor- responde a una cierta medida (costo, distancia) entre y , entonces el problema es encontrar el circuito Hamiltoniano mnimo del grafo. En este estudio se consideraran problemas simetricos, es decir, para todo par de nodos ”[12].
3. DESARROLLO
Con el proposito de estudiar la diversidad de comportamiento de los algoritmos evolutivos cuando estos sufren cambios en su estructura, y poder conseguir una combinacion de elementos que proveen el mejor desempeo posible, se realizaron tres diferentes versiones. La variante principal entre estos algoritmos es el uso de Gap Generacional (porcentaje de reemplazo de individuos en cada generacion) y el criterio de insercion de la descendencia en las nuevas poblaciones.
La version 1 es un algortimo generacional con elitismo, es decir, la poblacion cambia completamente de generacion en generacion preser- vando solamente el mejor individuo, con el objetivo de asegurar que el mejor individuo en cada generacion prevalezca, y posee un criterio de insercion basado en insertar en la nueva poblacion solo a aquel individuo (hijo) que presente una mejor aptitud que el peor individuo de la poblacion anterior. Las versiones 2 y 3 poseen Gap Generacional, donde solo un porcentaje de la poblacion es reemplazada en cada generacion, presentando como variante el criterio de insercion de la descendencia en las nuevas poblaciones. En la version 2 dicho criterio, al
igual que la version 1, se basa en insertar en la nueva poblacion solo a aquel individuo (hijo) que presente una mejor aptitud que el peor individuo de la poblacion anterior. Por ultimo, la version 3 se basa en insertar en la nueva poblacion solamente al individuo cuya aptitud sea mejor a la de aquel que se encuentre en la posicion (TamanoPoblacion - GapGeneracional), es decir, al mejor individuo del porcentaje de reemplazo de la poblacion.
Mediante la realizacion de pruebas experimentales se pudo determinar que el metodo de seleccion de Whitley[13] aportaba mejoras significativas en la version 1 de los algoritmos. Mien- tras que en las versiones 2 y 3, el metodo de seleccion de la Rueda de la Ruleta arrojo mejor de- sempeno.
Un importante elemento incorporado a todas las versiones de los algortimos propuestos, es un parametro que determina la maxima cantidad de intentos que se generan para conseguir un individuo que cumpla con el criterio de insersion en la nueva poblacion. Terminado el intento de busqueda orientado por este parametro y dado el caso de no haberse cumplido el criterio de insercion, se insertara entonces a la nueva poblacion aquel padre que posea mejor aptitud.
3.1. Esquema de Paralelizacion Propuesto
El diseno del algoritmo paralelo propuesto se centra en el llamado Modelo de Islas. Di- cho modelo se basa en la existencia de una poblacion global la cual se encuentra dividida en subpoblaciones. Cada subpoblacion evoluciona en un procesador de manera independiente. Tran- scurrido un numero determinado de generaciones (dicho perodo es conocido como perodo de migracion), se lleva a cabo la migracion del mejor individuo de cada subpoblacion hacia un proceso maestro o centralizador. Una vez recibidos estos individuos por el proceso centralizador, se lleva a cabo un proceso de cruce entre ellos, sin ser reemplazados. Se maneja como criterio de de- cision, el individuo mejor adaptado, entre aque-
llos que migraron as como los resultantes del cruce; el cual procedera a reemplazar al peor individuo de las subpoblaciones, as como al del proceso centralizador.
Es importante destacar que con la intencion de llevar a cabo una exploracion mas exhausti- va del espacio de busqueda, se decidio agregar al proceso centralizador un efecto de ruido. Este efecto consiste en modificar la probabilidad de mutacion de este proceso a un valor elevado, de- jando intactos el resto de los parametros.
En la figura 1 se puede observar grafica- mente como se lleva a cabo el proceso descrito anterior mente.
Figura 1. Proceso de Migracion
3.2. Pseudo-Codigos de los Algorit- mos Evolutivos
La figura 2 muestra el esquema general de los algoritmos isecuenciales implementados.
El algoritmo paralelo consiste en la paralelizacion del algoritmo secuencial tratado anteriormente. Este hecho conlleva a compartir una estructura similar as como todos aquellos operadores geneticos que influyen en la ejecucion del algoritmo en cada subproceso. En la figura 3 se muestra como se efectua la comunicacion entre los procesos involucrados (MPI), y en la figura 4 se muestra la paralelizacion de grano fino realiza- do al algoritmo secuencial (OpenMP).
Inicio ;
Inicializar P( t ); Evaluar P( t ); Ordenar P( t ); Para
hasta (Num Generaciones) hacer
Mientras (Se Genera Nueva Pobl) hacer Mientras (No Condicion Insercion) hacer
Seleccion P( t ) de P( );
Cruce PMX P( t ); Mutacion P( t ); Evaluar P( t ); Si (Criterio Insercion) entonces
Insertar Indv P( t ); Si (No Criterio Insercion) entonces
Insertar Mejor Padre P( t ); Ordenar P( t ); Fin
Figura 2. Algoritmo Secuencial Propuesto
3.3. Pruebas Experimentales
Los algoritmos propuestos fueron desarrollados bajo el lenguaje de programacion ANSI C, en una plataforma Unix (Linux), y usando com- piladores desarrollados por Portland Group Com- piler. La arquitectura utilizada para llevar a cabo las pruebas es un Cluster Beowulf llamado Ba- bieca, con sistema operativo Linux que consta de 16 nodos duales Intel Xeon, conectadas a traves de una red Myrinet de alta velocidad, que soporta aplicaciones paralelas con MPI y OpenMP. Este Cluster esta ubicado en el Computational Science Research Center de la San Diego State Universi- ty, San Diego, California, USA.
Inicio ;
Si (Es Centralizador) entonces Recibir Mejores Ind Cruzar Mejores Ind Seleccionar Mejor Ind Enviar Mejor Ind a Subprocesos
Sino Enviar Mejor Ind a Centralizador Recibir Mejor Ind de Centralizador
Fin
Figura 3. Esquema de Comunicacion del Algorit- mo Paralelo Propuesto
3.3.1. Casos de Estudio
Las instancias del TSP utilizadas en este trabajo como casos de estudio tienen su origen en problematicas planteadas en la vida real. Todas las instancias fueron obtenidas de la biblioteca TSPLIB (http://www.iwr.uni- heidelberg.de/groups/comopt/software/TSPLIB95/).
Nombre Tamano Tipo de Problema pcb442 442 Problema de Perforacion rat783 783 Trazado de Malla pr1002 1002 Recorrido de Ciudades rl1304 1304 Recorrido de Ciudades
Cuadro 1. Casos de Estudio Utilizados en las Pruebas
Cabe destacar que el numero de nodos de
Inicio ;
Mientras (Se Genera Nueva Pobl) hacer Mientras (No Condicion Insercion) hacer
Seleccion P( t ) de P( );
Cruce PMX P( t ); #PRAGMA OMP PARALLEL SECTION
Mutacion P( t ); Evaluar P( t ); Si (Criterio Insercion) entonces
#PRAGMA OMP PARALLEL SECTION FOR Insertar Indv P( t );
Si (No Criterio Insercion) entonces #PRAGMA OMP PARALLEL SECTION FOR
Insertar Mejor Padre P( t ); Ordenar P( t );
Fin
Figura 4. Subrutina Paralela del Algoritmo Se- cuencial
cada instancia se traduce en la cantidad de ciudades a ser visitadas para completar el camino.
3.3.2. Parametros de los Algoritmos Evolutivos
Los parametros utilizados para las ejecuciones de los algoritmos secuenciales se pueden observar en el cuadro 2. Como se puede ver, estos tipos de parametros son comunes para cualquier algoritmos evolutivo.
Los parametros utilizados en las ejecuciones de los algoritmos paralelos se pueden apreciar en el cuadro 3. Se puede observar que
Tamano de la Poblacion 400 Numero de Generaciones 20.000
Probabilidad de Cruce 0,85 Probabilidad de Mutacion 0,15
Gap Generacional (Version 2 y 3) 0,30 Numero de Corridas 20
Cuadro 2. Param. de los Algoritmos Secuenciales
este conjunto de parametros difieren del caso tradicional. Parametros de usuario tales como perodo de migracion, probabilidad de cruce de centralizador y probabilidad de mutacion de centralizador son nuevos elementos que se intro- ducen en las versiones paralelas.
Tamano Global de la Poblacion 400 Numero de Generaciones 20.000
Probabilidad de Cruce 0,85 Probabilidad de Mutacion 0,15
Gap Generacional (Version 2 y 3) 0,30 Numero de Corridas 20
Perodo de Migracion 20 Prob. de Cruce de Centralizador 0,25
Prob. de Mutacion de Centralizador 0,75
Cuadro 3. Param. de los Algoritmos Paralelos
4. RESULTADOS
En esta seccion se muestran y discuten los resultados obtenidos de las ejecuciones en las arquitecturas paralelas. Esto resultados se basan en las ejecuciones realizadas con 4 y 8 procesos MPI; todos con una poblacion global de individuos.
En las siguientes figuras se muestra la con- vergencia del promedio de los mejores individuos de todas las versiones de los algoritmos secuenciales y paralelos. En las figuras 5, 6, 7 y 8 se utilizan 4 procesos (subpoblaciones), con un tamano de cada subpoblacion igual a individuos. En las figuras 9, 10, 11 y 12 se uti-
lizan 8 procesos, con un tamano de cada subpoblacion igual a individuos. Estos prome- dios se obtuvieron en base a 20 ejeciciones realizadas. Los algoritmos version 1 se referencian en las figuras como Sec Simple y Par Simple para las versiones secuenciales y paralelas respectiva- mente. Los algoritmos version 2 se referencian como Sec sin Presion y Par sin Presion, y finalmente, los algoritmos version 3 se referencian como Sec con Presion y Par con Presion. Para todas las graficas que se muestran el eje de las ab- cisas representa el numero de generaciones realizadas, y el eje de las ordenadas los logaritmo en base 10 del promedio del valor objetivo de los individuos en cada iteracion.
En estas figuras se puede observar que el algoritmo evolutivo paralelo mixto que obtuvo una mejor solucion es la version 3 paralela, el cual se encuentra estructurado con un gap generacional de y posee un criterio de presion en el proceso evolutivo. Por ejemplo, en la grafica 5, al final de las 20.000 iteraciones el algoritmo secuencial version 3 consigue el valor objetivo 151.138,4 mientras que la version paralela ya lo- gra conseguir dicho valor en la iteracion 6.653, y finalmente converge al valor objetivo 136.741,15.
5
5,1
5,2
5,3
5,4
5,5
5,6
5,7
5,8
5,9
6
Generaciones
Paralelo_con_Presión Paralelo_sin_Presión
Par_Simple Sec_Simple
Figura 5. Algs Secuenciales vs. Algs Paralelos (442 nodos – 4 procesos)
4,4
4,5
4,6
4,7
4,8
4,9
5
5,1
5,2
5,3
5,4
1 2001 4001 6001 8001 10001 12001 14001 16001 18001
Generaciones
Sec_sin_Presión Sec_con_Presión Sec_Simple Par_sin_Presión Par_con_Presión Par_simple
6
6,1
6,2
6,3
6,4
6,5
6,6
6,7
6,8
6,9
1 2250 4499 6748 8997 11246 13495 15744 17993 Generaciones
L o
g (V
a lo
r_ O
b je
tiv o
Sec_con_Presión Par_Simple
Par_sin_Presión Par_con_Presión
4.1. Tiempos de Ejecucion
A continuacion, en los cuadros compara- tivos 4 y 5 se muestran los tiempos promedio de ejecucion obtenidos para todas las versiones de los algoritmos desarrollados.
Se puede observar que el algoritmo que presenta un menor tiempo de respuesta para todas las instancias estudiadas es el paralelo mixto version 2, el cual se escuentra estructurado con un gap generacional de y no posee ningun criterio de presion en el proceso evolutivo. Sin em-
6,2
6,4
6,6
6,8
7
7,2
1 1979 3957 5935 7913 9891 11869 13847 15825 17803 19781
Generaciones
Sec_Simple Sec_sin_Presión Sec_con_Presión Par_Simple Par_sin_Presión Par_con_Presión
5
5,1
5,2
5,3
5,4
5,5
5,6
5,7
5,8
5,9
6
1 2389 4777 7165 9553 11941 14329 16717 19105 Generaciones
L o g (V
Sec_Simple
bargo, como se observo en la seccion anterior, el algoritmo que arroja mejores resultados es la version 3, aun con un tiempo de ejecucion cercano al obtenido por la version 2.
Para calcular la aceleracion obtenida por el algoritmo evolutivo paralelo mixto propuesto sobre su version secuencial, se utiliza la version 3 de los algoritmos desarrollados, por ser estos los que proveen una mejor calidad de solucion con un buen tiempo de respuesta.
La aceleracion obtenida por el algoritmo paralelo mixto se calcula a traves de la siguiente
4,4
4,5
4,6
4,7
4,8
4,9
5
5,1
5,2
5,3
5,4
1 2001 4001 6001 8001 10001 12001 14001 16001 18001
Generaciones
Sec_sin_Presión Sec_con_Presión Sec_Simple Par_sin_Presión Par_con_Presión Par_simple
6
6,1
6,2
6,3
6,4
6,5
6,6
6,7
6,8
6,9
1 2198 4395 6592 8789 10986 13183 15380 17577 19774
Generaciones
Sec_con_Presión Par_Simple
Par_sin_Presión Par_con_Presión
formula:
(1)
donde
es el tiempo que tarda el algoritmo secuencial en llegar a su mejor solucion, y
es
el tiempo tomado por el algoritmo paralelo en alcanzar este mismo valor.
En el cuadro 6 se muestra la aceleracion obtenida por el algoritmo evolutivo paralelo mix- to version 3 para todas las instancias estudiadas con 4 y 8 procesos MPI. Se puede observar que
6,2
6,4
6,6
6,8
7
7,2
1 2028 4055 6082 8109 10136 12163 14190 16217 18244
Generaciones
o )
Sec_Simple
Sec_sin_Presión
Sec_con_Presión
Par_Simple
Par_sin_Presión
Par_con_Presión
442 nodos 783 nodos Sec-Ver. 1 1098.87 segs 3336.80 segs Sec-Ver. 2 318.21 segs 868.46 segs Sec-Ver. 3 343.58 segs 991.57 segs
Par-4procs-Ver. 1 698.98 segs 1786.94 segs Par-4procs-Ver. 2 235.23 segs 660.94 segs Par-4procs-Ver. 3 257.91 segs 757.49 segs Par-8procs-Ver. 1 371.04 segs 1026.39 segs Par-8procs-Ver. 2 123.34 segs 335.06 segs Par-8procs-Ver. 3 131.44 segs 375.93 segs
Cuadro 4. Tiempos de Ejecucion de los Algorit- mos
este algoritmo en todas las instancias y con 4 procesos MPI presenta una aceleracion cuasi–lineal, y para las ejecuciones con 8 procesos MPI se obtuvo una aceleracion significativa en relacion a la version secuencial.
4.2. Comparacion de Algoritmo Evo- lutivo Paralelo Mixto vs. Deter- minstico
El algoritmo determinstico seleccionado para llevar a cabo la comparacion planteada es un algoritmo Branch and Bound (Ramificar y Acotar), desarrollado en [14]. Dicho algoritmo
1002 nodos 1304 nodos Sec-Ver. 1 5218.58 segs 8864.75 segs Sec-Ver. 2 1366.91 segs 2234.42 segs Sec-Ver. 3 1612.75 segs 2724.29 segs
Par-4procs-Ver. 1 2729.26 segs 4072.12 segs Par-4procs-Ver. 2 1003.21 segs 1610.45 segs Par-4procs-Ver. 3 1254.04 segs 2129.69 segs Par-8procs-Ver. 1 1529.52 segs 2395.38 segs Par-8procs-Ver. 2 527.01 segs 850.92 segs Par-8procs-Ver. 3 612.24 segs 1027.46 segs
Instancias 4 procs MPI 8 procs MPI 442 nodos 4.00 5.28 783 nodos 3.46 4.98
1002 nodos 3.17 4.76 1304 nodos 3.08 4.55
Cuadro 6. Tabla de Aceleracion
fue disenado e implementado bajo un esquema de programacion multihilo, haciendo uso del lenguaje de programacion ANSI C. Se selec- ciono el algoritmo evolutivo paralelo mixto version 3 para llevar a cabo la comparacion, por ser este el que arroja mejores resultados en todas las versiones paralelas.
Es importante destacar que los dos algoritmos involucrados en esta comparacion fueron ejecutados en la misma plataforma computacional, ya descrita en el captulo anterior.
En el cuadro 7 se muestran los resultados referentes a los tiempos de respuesta obtenidos por ambos algoritmos. Para el algoritmo evolutivo paralelo mixto se utilizo una instancia de 29 nodos, mientras que para el determinstico la prueba se llevo a cabo con una instancia de 17 nodos, siendo esta la instancia de mayor dimension probada en [14]. La razon por la cual el algoritmo evolutivo paralelo mixto no se estudio con una instancia de menor dimension, se debio a la inexis- tencia de dicha instancia en un formato compati- ble con las estructuras de datos manejadas por el
algoritmo. Es importante mencionar que el algoritmo evolutivo paralelo mixto llego a la solucion optima de la instancia estudiada.
Algoritmos Tiempos Alg. Determinstico 7309 segs
AE Paralelo Mixto (4 procs) 0.77 segs AE Paralelo Mixto (8 procs) 0.52 segs
En la tabla 7 se puede apreciar que a pesar que la instancia seleccionada para el algoritmo determinstico es menor a la utilizada por el algoritmo evolutivo paralelo mixto, se observa un tiempo de respuesta mucho menor por parte del algoritmo evolutivo paralelo mixto sobre el determinstico.
4.3. Modulo de Visualizacion
Para mejor apreciacion de la evolucion de los algoritmos desarrollados, se creo un modulo de visualizacion. Este modulo se implemento uti- lizando la biblioteca grafica OpenGL. La visualizacion se lleva a cabo graficando el mejor camino existente en la poblacion cada k generaciones, siendo k un valor previamente estableci- do.
Al momento de la ejecucion de un algoritmo, la visualizacion de la evolucion del mismo es opcional. Sin embargo, si se selecciona la opcion de no activar el modulo de visualizacion, los algoritmos devuelven un archivo donde se encuen- tran registrados los mejores caminos encontrados cada k generaciones en el proceso evolutivo. Este archivo permite la posterior activacion de un algoritmo de graficacion independiente, que forma parte del modulo descrito, para llevar a cabo la visualizacion.
En las figuras 13, 14 se muestra un ejemplo del funcionamiento de este modulo para una instancia de 29 ciudades. Estas figuras representan la evolucion secuencial del algoritmo en busqueda de la solucion optima.
Figura 13. Modulo de Visualizacion (1)
Figura 14. Modulo de Visualizacion(2)
AGRADECIMIENTOS
Nosotros queremos agradecer al Consejo de Desarrollo Cientfico y Huanstico de la Univer- sidad de Carabobo por el financiamiento otorga- do a traves de una ayuda menor para la investigacion. As mismo, tambien quisieramos agradecer al Computational Sciences Research Center (CSRC) de San Diego State University (SDSU), USA, por la colaboracion prestada para la realizacion de este trabajo.
5. CONCLUSIONES
Luego de realizar las pruebas experimentales con las tres versiones de los algoritmos desarrollados, en busqueda de un algoritmo evolutivo paralelo mixto para el TSP que fuera capaz de
proveer una buena solucion y un reducido tiempo de respuesta, en relacion a su equivalente secuencial, se puede concluir que el mejor algoritmo desarrollado es la version 3.
En la evaluacion de los algoritmos realiza- dos tambien se pudo observar que el uso de gap generacional en estos, ayuda a lograr una con- vergencia mas rapida, as como la obtencion de un mejor resultado final. De igual manera se aprecio el aporte conseguido mediante la imple- mentacion de un criterio de presion al momento de insertar un nuevo individuo en la poblacion, siendo la presion ejercida, el insertar a un individuo solo si este posee una mejor aptitud que el mejor individuo del porcentaje de reemplazo de la poblacion (TamanoPoblacion - GapGenera- cional).
Se pudo constatar que el uso del paralelismo mixto es una herramienta util y aplicable a los algoritmos evolutivos debido al paralelismo intrnseco en el proceso evolutivo. Los elementos utilizados para la construccion del paralelismo mixto (MPI y OpenMP) lograron ambos la aceleracion del proceso evolutivo, obteniendo tambien una mejora en la calidad de solucion. Este ultimo factor se debe al hecho que al trabajar con subpoblaciones que evolucionan de manera independiente unas de otras, existe mayor diversidad en el espacio de busqueda sobre el cual se traba- ja, siendo este un elemento determinante en todos los procesos de optimizacion combinatoria si se busca obtener una mejor solucion.
Por ultimo, se plantea evaluar para el algoritmo seleccionado distintos operadores evolutivos (cruce, mutacion y seleccion) buscando conseguir una correcta combinacion de estos que sean capaces de aportar mejoras significativas en la solucion. Desde el punto de vista del paralelismo se propone el estudio y evaluacion de otras estrategias de migracion entre subpoblaciones, as como tambien, explotar de una manera mas eficiente el paralelismo multihilo esperando obtener tiempos de respuesta mas bajos. Es importante aconsejar la evaluacion del efecto de im- plementar distintos esquemas de paralelizacion de grano grueso, como por ejemplo el esquema de Farming. Y finalmente, se propone ampliar
las funcionalidades del modulo de visualizacion, permitiendo el despliegue de informacion rele- vante al proceso evolutivo.
Referencias
[1] J. Suh P. Jog and D. Van Gucht. Parallel genetic algorithms applied to the traveling salesman problem. SIAM Journal on Optimization, 1(4):515–529, 1991.
[2] J. L. Blanton P. Mutalik, L. R. Knight and R. L. Wainwright. Solving Combinatori- al Optimization Problems Using Parallel Simulated Annealing and Parallel Genet- ic Algorithms. pages 1031–1038, 1992.
[3] M. Racke S. Tschoke, R. Luling and B. Monien. Solving the traveling salesman problem with a parallel branch- and-bound algorithm on a 1024 proces- sor network. Technical report, Depart- ment of Mathematics and Computer Sci- ence. University of Paderborn, Germany, 1992.
[4] M. Schwehm. Parallel Population Models for Genetic Algorithms. Technical report, Universitat Erlangen–Nurnberg, Erlangen, Germany, 1994.
[5] L. Villamizar. Optimizacion del Problema del Agente Viajero (TSP) Usando Algo- ritmos Geneticos Paralelos. Master’s thesis, Facultad de Ingeniera. Universidad de Carabobo. Valencia, Venezuela, 1998.
[6] P. Calgari. Parallelization of Population - Based Evolutionary Algorithms for Com- binatorial Optimization Problems. PhD thesis, Presentee Au Departement DInfor- matique. Ecole Polytechnique Federale de Lausanne. Lausanne - Francia, 1999.
[7] G. Larrazabal. Un Algoritmo Genetico Paralelo Grano Grueso. Technical report, Facultad de Ciencias y Tecnologa. Depar- tamento de Computacion. Universidad de Carabobo. Valencia, Venezuela, 1996.
[8] J. Holland. Adaptation in Natural and Ar- tificial Systems. Ann Harbord. University of Michigan Press, 1975.
[9] Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer–Verlag, 1996.
[10] D.E. Goldberg and R. Lingle. Alleles, Loci and the TSP.
[11] W. Cook D. Applegate, R. Bixby and V. Chvatal. Finding Cuts in the TSP (a Preliminary Report). Technical report, DIMACS, 1995.
[12] M. Chiarandini L. Paquete and T. Stutzle. A Study of Local Optima in the Biobjective Traveling Salesman Problem. 2002.
[13] M. Gordon and D. Whitley. Serial and Par- allel Genetic Algorithms as Function Op- timizers. Technical report, Department of Computer Science. Colorado State Univer- sity. USA, 1993.

Documents

UN ALGORITMO EVOLUTIVO PARALELO MIXTO PARA EL TSP