Asynchronous Parallel Distributed Genetic Algorithm with Elite Migration

Authors: Kazunori Kojima, Masaaki Ishigame, Goutam Chakraborty, Hiroshi Hatsuo, Shozo Makino

Abstract:

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.

Keywords: Parallel Distributed Genetic Algorithm (PDGA), asynchronousPDGA, Server-Client configuration, Elite Migration

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331645

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)