Alternative strategies for asynchronous migration-controlled schemes in parallel genetic algorithm


  • Claudio Ochoa Departamento de Informática, Universidad Nacional de San Luis (UNSL), San Luis, Argentina.
  • Raúl Hector Gallard Departamento de Informática, Universidad Nacional de San Luis (UNSL), San Luis, Argentina.


Parallel genetic algorithms, island model, migration schemes, acceptance threshold, dynamic arbiter


Migration of individuals allows a fruitful interaction between subpopulations in the island model, a well known distributed approach for evolutionary computing, where separate subpopulations evolve in parallel. This model is well suited for a distributed environment running a Single Program Multiple Data (SPMD) scheme. Here, the same Genetic Algorithm (GA) is replicated in many processors and attempting better convergence, through an expected improvement on genetic diversity, selected individuals are exchanged periodically. For exchanging, an individual is selected from a source subpopulation and then exported towards a target subpopulation. Usually, the imported string is accepted on arrival and then inserted into the target subpopulation. Our earlier experiments on controlled migration showed an improvement on results when contrasted against those obtained by conventional migration approaches. This paper describes extended implementations of alternative strategies to oversee migration in asynchronous schemes for an island model and enlarges a previous work on three processors with a set of softer testing functions [9]. All of them try to decrease the risk of premature convergence. A first strategy attempts to prevent unbalanced p ropagation of genotypes by applying an acceptance threshold parameter to each incoming string. A second one permits independent evolution of subpopulations and acts only when a possible stagnation is detected. In such condition an attempt to evade falling towards a local optimum is done by inserting an expected d issimilar individual to improve genetic diversity. A third alternative strategy combines both previous mentioned strategies. The results presented are those obtained on the functions that showed to be more difficult for the island model using a replication of a simple GA. A description of the corresponding system architecture supporting the PGA implementation is described and results for the parallel distributed approach among 3, 6 and 12 processors is discussed.


Download data is not yet available.


[1] Arredondo D., Printista M., Gallard R. - Un Sistema Distribuido para el Procesamiento Paralelo de Algoritmos Genticos - Proceeding s of the Primer Congreso Argentino de Ciencias de la Computaci-252, Universidad Nacional del Sur, Bahia Blanca, October 1995.
[2] Belding T.C. - The Distributed Genetic Algorithm Revisited - Proceedings of the Sixth International Conference on Genetic Algorithms, pp 114-121, Morgan Kauffman, 1995.
[3] Cohoon J.P., Hedge S.U., Martin W.N., Richards D. - Puntuacted Equilibria: A Parallel Genetic Algorithm - Proceedings of the Second International Conference on Genetic Algorithms, pp 148-154, Lawrence Erlbaum Associates Publishers, 1987.
[4] Foster I. - Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering - ISBN 0-201-57594-9, Addison Wesley, 1994.
[5] Holland J.H. - Adaptation in Natural and Artificial Systems, Ann Arbor, The University of Michi gan Press, 1975.
[6] Horn J., Goldberg D. - Genetic Algorithms Difficulty and the Modality of Fitness Landscapes - Fundations of Genetic Algorithms (FOGA-94), pp 243-269, Morgan Kaufmann, 1995.
[7] Levine, D. - A Parallel Genetic Algorithm for the Set Partitioning Problem - Ph D Thesis,Illinois Institute of Technology and Argone National Lab. (ANL -94/23), 1994.
[8] Ochoa C., Gallard R. - Parallel Genetic Algorithms: A Feasible Distributed Implementation- Proceedings of the Segundo Congreso Argentino de Ciencias de la Computaci-199, Universidad Nacional de San Luis, San Luis, Novembe r 1996.
[9] Ochoa C., Gallard R. - Strategies for Migration Overseeing in Asynchronous Schemes of Parallel Genetic Algorithms - Accepted for it publication in the International ICSC Symposium on Soft Computing : SOCO'97.
[10] Shyh-Chang Lin, Punch W., Goodman E. - Coarse-Grain Parallel Genetic Algorithms:Categorizations and New Approach. Parallel & Distributed Processing, Dallas TX, Oct. 1994.
[11] Tanese R. - Distributed Genetic Algorithms - Proceedings of the Third International Conference on Genetic Algorithms, pp 434-439, Morgan Kauffman, 1989.
[12] Whitley D. - An Executable Model of a Simple Genetic Algorithm - Fundations of Genetic Algorithms-2 (FOGA-92), pp 45-62, Morgan Kaufmann, 1993.
[13] Whitley D., Mathias K., Rana S., Dzubera J. - Building Better Test Functions - Proceedings of the Sixth International Conference on Genetic Algorithms, pp 239-246, Morgan Kauffman, 1995.




How to Cite

Ochoa, C., & Gallard, R. H. (1999). Alternative strategies for asynchronous migration-controlled schemes in parallel genetic algorithm. Journal of Computer Science and Technology, 1(01), 18 p. Retrieved from



Original Articles

Most read articles by the same author(s)