Asynchronous Parallel Distributed Genetic Algorithm with Elite Migration

In most of the popular implementation of Parallel GAs the whole population is divided into a set of subpopulations, each subpopulation executes GA independently and some individuals are migrated at fixed intervals on a ring topology. In these studies, the migrations usually occur 'synchronously' among subpopulations. Therefore, CPUs are not used efficiently and the communication do not occur efficiently either. A few studies tried asynchronous migration but it is hard to implement and setting proper parameter values is difficult. The aim of our research is to develop a migration method which is easy to implement, which is easy to set parameter values, and which reduces communication traffic. In this paper, we propose a traffic reduction method for the Asynchronous Parallel Distributed GA by migration of elites only. This is a Server-Client model. Every client executes GA on a subpopulation and sends an elite information to the server. The server manages the elite information of each client and the migrations occur according to the evolution of sub-population in a client. This facilitates the reduction in communication traffic. To evaluate our proposed model, we apply it to many function optimization problems. We confirm that our proposed method performs as well as current methods, the communication traffic is less, and setting of the parameters are much easier.

Authors:

• Kazunori Kojima
• Masaaki Ishigame
• Goutam Chakraborty
• Hiroshi Hatsuo
• Shozo Makino

Keywords:

• Parallel Distributed Genetic Algorithm (PDGA)
• asynchronousPDGA
• Server-Client configuration
• Elite Migration

References:

[1] Holland, J.H.: "Adaption in Natural and Artificial Systems", University
of Michigan Press (1975).
[2] Goldberg, D.E.: "Genetic Algorithm in Search Optimization and Machine
Learning", Addison Wesley (1989).
[3] Erick Cant'u-Paz: "Efficient and Accurate Parallel Genetic Algorithms",
Kluwer Academic publishers (2000)
[4] Fogarty, T.C., and Huang, R.: "Implementing the genetic algorithm on
transputer based parallel processing systems", Parallel Problem Solving
from Nature, pp.145-149 (1991).
[5] Hauser, R., and M¨anner, R.: "Implementation of standard genetic algorithm
on MIMD machines" Parallel Problem Solving from Nature, PPSN
III, pp.504-513 (1994)
[6] J.P. Cohoon, W.N. Martin, and D.S. Richards: "A Multi-population
Genetic Algorithm for Solving the k-Partition Problem on Hypercubes",
Proc. of ICGA-91, pp.244-248 (1991).
[7] C.C. Petty, and M.R. Leuze: "Theoretical Investigation of a Parallel
Genetic Algorithm", Proc. of ICGA-89, pp.398-405 (1989).
[8] R. Tanese: "Parallel Genetic Algorithm for a Hypercube", Proc. of ICGA-
87, pp.177-183 (1987).
[9] R. Tanese: "Distributed Genetic Algorithms", Proc. of ICGA-89, pp.434-
439 (1989).
[10] Munetomo M., Yoshiaki T., and Yoshiharu S., "An Efficient Sigma
Exchange Algorithm for a Subpopulation-Based Asynchronously Parallel
Genetic Algorithm and Its Evaluation", IPSJ, vol.35, no.9, pp. 1815-1827,
1994.
[11] R.J. Collins, and D.R. Jefferson: "Selection in Massively Parallel Genetic
Algorithms", Proc. of ICGA-91, pp.249-256 (1991).
[12] B. Manderick, and P. Spiessens: "Fine-grained Parallel Genetic Algorithms",
Proc. of ICGA-89, pp.428-433 (1989).
[13] P. Spiessens, and B. Manderick: "A Massively Parallel Genetic Algorithm,
Implementation and First Analysis", Proc. of ICGA-91, pp.279-285
(1991).
[14] D.E. Brown, C.L. Huntley, and A.R. Spillane: "A Parallel Genetic
Heuristics for the Quadratic Assignment Problem", Proc. of ICGA-89,
pp.406-415 (1989).
[15] M. Gorges-Schleuter: "ASPARAGOS: An Asynchronous Parallel Genetic
Optimization Strategy", Proc. of ICGA-89, pp.422-427 (1989).
[16] Sachio K., Hidefumi S., and Susumu A.: "Parameter-free Genetic
Algorithm (PfGA) Using Adaptive Search with Variable-Size Local
Population and Its Extension to Parallel Distributed Processing", IEICE
Transactions(D-II), Vol.J82-D-II, No.3, pp.512-521 (1999).
[17] Susumu A., and Hidefumi S.: "Effects of Migration Methods in Parallel
Distributed Parameter-Free Genetic Algorithm", IEICE Transactions(D-I),
Vol.J83-D-I, No.8, pp.834-843 (2000).
[18] Tomoyuki H., Mitsunori M., Masahiro H., and Yusuke T.: "A New Model
of Distributed Genetic Algorithm for Cluster Systems: Dual Individual
DGA", Proc. of PDPTA, Vol.1, pp.477-483 (2000).
[19] P. Pacheco: "Parallel Programming with MPI", Baifu-kan (2001)