Esta estrategia de paralelización consiste en utilizar un conjunto estático de sub-poblaciones independientes y utilizar un operador genético adicional de migración, mediante el cual, cada cierto número de generaciones se da el intercambio de individuos entre las poblaciones, como una forma de compartir material genético entre las mismas. Esto hace necesario la introducción de un conjunto de parámetros migratorios que determinen la periodicidad del proceso de migración, la cantidad de individuos a migrar en cada ocasión y las poblaciones destino de dichos individuos.
A esta estrategia de paralelización también se le conoce como modelo de islas, algoritmos genéticos distribuidos o algoritmos genéticos de grano grueso y su escalabilidad ha sido comprobada en varios trabajos [1-5].
Existen diversos modelos de migración para los algoritmos genéticos de grano grueso, los cuales incluyen modelos en anillo, y la migración aleatoria [6].
En el modelo de anillo, se determina la población de destino de cada elemento a migrar antes de iniciar el algoritmo. (figura 1)
Figura 1: Migración en anillo entre 7 poblaciones.
En el modelo de migración aleatoria la población de destino se elige al azar en cada evento de migración. (figura 2)
Figura 2: Migración aleatoria entre 7 poblaciones.
Los efectos de la migración sobre los algoritmos genéticos en paralelo han sido abordados en [7-9]. En estos textos se obtienen resultados satisfactorios migrando porciones pequeñas de las sub-poblaciones (en el rango del 20%) lo cual es compatible con el objetivo de minimizar el uso del ancho de banda entre procesadores.
También existen diferentes estrategias para seleccionar los individuos a migrar que van desde la elección elitista de los individuos con mejor adaptación de cada población hasta la selección por torneo. La determinación dinámica de los parámetros migratorios se ha tratado en [5, 6, 10].
En este tipo de algoritmo, se denomina intervalo de migración al número de generaciones que se ejecutan en cada procesador antes del intercambio de material genético con los demás, mientras que a la cantidad de individuos que se seleccionan para migrar cada vez, se le denomina razón de migración.
Aplicación de prueba Sobre PVM
Para la aplicación de este algoritmo es conveniente tomar un ejemplo de optimización. El problema que se eligió para probarlo inicialmente es la minimización de la función de Goldstein-Price descrita en [11] la cual ha sido utilizada para el estudio de algoritmos genéticos. Esta función tiene un mínimo global en fG*(0,-1) = 3.
(1) Después de efectuar varias pruebas empíricas con el algoritmo genético sin paralelizar, se escogió un conjunto de parámetros que en principio arrojaron soluciones prometedoras, estos parámetros se utilizaron como base para hacer pruebas del efecto de la variación del tamaño de población:
• Representación real, cromosoma X = [x1,x2].
• Rango de búsqueda para X (-100,100).
• Error máximo permitido 0.1 (cuando el error es mayor, se considera una convergencia prematura).
• Número máximo de generaciones GMAX = 100.
• Selección por torneo, con tamaño de torneo Z=2.
• Probabilidad de cruce PC = 0.7.
• Parámetro de cruzamiento generado de manera uniforme en (0,1).
• Probabilidad de mutación PM =0.1.
El código fuente escrito en C con migración para optimizar la función Goldstein-Price con licencia GPL puede descargarse desde
http://sistemas.itlp.edu.mx/mcastro/mdga.tgz
REFERENCIAS BIBLIOGRÁFICAS
1. Alba, E. and J.M. Toya, Analyzing Synchronous and Asyncrhonous Parallel Distributed Genetic Algorithms. Future Generation Computer Systems, 2001. 17(4): p. 451-465.
2. Alba, E. and M. Tomassini, Parallelism and Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 2002. 6(5): p. 443-462.
3. Alba, E. and J.M. Troya, A Survey of Parallel Distributed Genetic Algorithms. 1997, Universidad de Málaga, Campus de Teatinos. p. 32.
4. Tomoyuki, H., M. Mitsunori, and T. Yusule, The Differences of Parallel Efficiency between the Two Models of Parallel Genetic Algorithms on PC Cluster Systems. Proceedings of The Fourth International Conference/Exhibition on High Performance Computing in Asia-Pacific Region, 2000: p. 945-948.
5. Berntsson, J. and M. Tang, Dynamic Optimization of Migration Topology in Internet-based Distributed Genetic Algorithms. Proceedings of the 2005 conference on Genetic and evolutionary computation GECCO '05, 2005: p. 1579-1580.
6. Hiroyasu, T., M. Miki, and M. Negami, Distributed Genetic Algorithms with Randomized Migration Rate, in IEEE Proceedings of Systems, Man and Cybernetics Conference SMC'99. 1999, IEEE Press. p. 689-694.
7. Matsumura, T., et al., Effects of Chromosome Migration on a Parallel and Distributed Genetic Algorithm. Proceedings. Third International Symposium on Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN '97), 1997: p. 357-361.
8. Rebaudengo, M. and M. Sonza Reorda, An Experimental Analysis of the Effects of Migration in Parallel Genetic Algorithms. Proceedings Euromicro WorkShop on Parallel and Distributed Processing, 1993, 1993: p. 232-238.
9. Alba, E., C. Cotta, and J.M. Troya, Numerical and Real Time Analysis of Parallel Distributed GAs with Structured and Panmictic Populations. Proceedings of the IEEE Conference on Evolutionary Computing (CEC), 1999. 2: p. 1019-1026.
10. Noda, E., et al., Devising Adaptive Migration Policies for Cooperative Distributed Genetic Algorithms. Proceedings of the IEEE Conference on Evolutionary Computation, 2002.
11. Jamshidi, M., et al., Robust Control Systems With Genetic Algorithms. Control Series, ed. R.H. Bishop. 2002, USA: CRC Press. 210.
No hay comentarios:
Publicar un comentario