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.
[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)
[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)
@article{"International Journal of Business, Human and Social Sciences:53277", author = "Kazunori Kojima and Masaaki Ishigame and Goutam Chakraborty and Hiroshi Hatsuo and Shozo Makino", title = "Asynchronous Parallel Distributed Genetic Algorithm with Elite Migration", 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", volume = "2", number = "6", pages = "647-7", }