Influence of the migration policy in parallel distributed GAs with structured and panmictic populations

被引:52
作者
Alba, E [1 ]
Troya, JM [1 ]
机构
[1] Univ Malaga, Dpto Lenguajes & Ciencias Computat, E-29071 Malaga, Spain
关键词
parallel genetic algorithms; complex search spaces; migration policy; entropy; basic island evolution;
D O I
10.1023/A:1008358805991
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Parallel genetic algorithms (PGAs) have been traditionally used to overcome the intense use of CPU and memory that serial GAs show in complex problems. Non-parallel GAs can be classified into two classes: panmictic and structured-population algorithms. The difference lies in whether any individual in the population can mate with any other one or not. In this work, they are both considered as two reproductive loop types executed in the islands of a parallel distributed GA. Our aim is to extend the existing studies from more conventional sequential islands to other kinds of evolution. A key issue in such a coarse grain PGA is the migration policy, since it governs the exchange of individuals among the islands. This paper investigates the influence of migration frequency and migrant selection in a ring of islands running either steady-state, generational, or cellular GAs. A diversity analysis is also offered from an entropy point of view. The study uses different problem types, namely easy, deceptive, multimodal, NP-Complete, and epistatic search landscapes in order to provide a wide spectrum of problem difficulties to support the results. Large isolation values and random selection of the migrants are demonstrated as providing a larger probability of success and a smaller number of visited points. Also, interesting observations on the relative performance of the different models are offered, as well as we point out the considerable benefits that can accrue from asynchronous migration.
引用
收藏
页码:163 / 181
页数:19
相关论文
共 44 条
  • [1] Alba E., 1993, Artificial Neural Nets and Genetic Algorithms. Proceedings of the International Conference, P683
  • [2] Alba E., 1999, Parallel and Distributed Processing. 11th IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing. Proceedings, P248
  • [3] ALBA E, 1999, THESIS U MALAGA SPAI
  • [4] Alba Enrique, 1999, Complexity, V4, P31, DOI 10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO
  • [5] 2-4
  • [6] [Anonymous], 1991, FDN GENETIC ALGORITH, DOI DOI 10.1016/B978-0-08-050684-5.50009-4
  • [7] [Anonymous], PARALLEL DISTRIBUTED
  • [8] [Anonymous], P 2 INT C GEN ALG
  • [9] [Anonymous], P 4 INT C GEN ALG
  • [10] [Anonymous], 1997, 7 INT C GENETIC ALGO