Performance analysis of synchronous and asynchronous distributed genetic algorithms on multiprocessors

被引:18
作者
Abdelhafez, Amr [1 ,2 ]
Alba, Enrique [1 ]
Luque, Gabriel [1 ]
机构
[1] Univ Malaga, Dept Lenguajes & Ciencias Comp, ETS Ingn Informat, Campus Teatinos, E-29071 Malaga, Spain
[2] Assiut Univ, Fac Sci, Assiut 71515, Egypt
关键词
Parallel distributed computing; Genetic algorithms; Synchronization; MPI; Speed-up; EVOLUTIONARY ALGORITHMS; PARALLEL; OPTIMIZATION; SEARCH; MODEL;
D O I
10.1016/j.swevo.2019.06.003
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Because of their effectiveness and flexibility in finding useful solutions, Genetic Algorithms (GM) are very popular search techniques for solving complex optimization problems in scientific and industrial fields. Parallel GM (PGAs), and especially distributed ones have been usually presented as the way to overcome the time-consuming shortcoming of sequential GM. In the case of applying PGAs, we can expect better performance, the reason being the exchange of knowledge during the parallel search process. The resulting distributed search is different compared to what sequential pansnictic GM do, then deserving additional studies. This article presents a performance study of three different PGAs. Moreover, we investigate the effect of synchronizing communications over modern shared-memory multiprocessors. We consider the master-slave model along with synchronous and asynchronous distributed GM (dGAs), presenting their different designs and expected similarities when running in a number of cores ranging from one to 32 cores. The master-slave model showed a competitive numerical effort versus the other dGAs and demonstrated to be able to scale-up well over multiprocessors. We describe how the speed-up and parallel performance of the dGAs is changing as the number of cores enlarges. Results of the island model show that synchronous and asynchronous dGAs have different numerical performances on a multiprocessor, the asynchronous algorithm having a faster execution, thus more attractive for time demanding applications. Our results and statistical analyses help in developing a novel body of knowledge on PGAs running in shared memory multiprocessors (versus overwhelming literature oriented to distributed memory clusters), something useful for researchers, beginners, and final users of these techniques.
引用
收藏
页码:147 / 157
页数:11
相关论文
共 48 条
[1]  
Abdelbafez A, 2017, IEEE C EVOL COMPUTAT, P2677, DOI 10.1109/CEC.2017.7969632
[2]   A component-based study of energy consumption for sequential and parallel genetic algorithms [J].
Abdelhafez, Amr ;
Alba, Enrique ;
Luque, Gabriel .
JOURNAL OF SUPERCOMPUTING, 2019, 75 (10) :6194-6219
[3]   Parallel heterogeneous genetic algorithms for continuous optimization [J].
Alba, E ;
Luna, F ;
Nebro, AJ ;
Troya, JM .
PARALLEL COMPUTING, 2004, 30 (5-6) :699-719
[4]  
Alba E, 2005, WILEY SER PARA DIST, P1, DOI 10.1002/0471739383
[5]   Influence of the migration policy in parallel distributed GAs with structured and panmictic populations [J].
Alba, E ;
Troya, JM .
APPLIED INTELLIGENCE, 2000, 12 (03) :163-181
[6]  
Alba E., 2004, International Journal of Applied Mathematics and Computer Science, V14, P317
[7]   Parallel evolutionary algorithms can achieve super-linear performance [J].
Alba, E .
INFORMATION PROCESSING LETTERS, 2002, 82 (01) :7-13
[8]   Improving flexibility and efficiency by adding parallelism to genetic algorithms [J].
Alba, E ;
Troya, JM .
STATISTICS AND COMPUTING, 2002, 12 (02) :91-114
[9]   Analyzing synchronous and asynchronous parallel distributed genetic algorithms [J].
Alba, E ;
Troya, JM .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2001, 17 (04) :451-465
[10]  
Alba Enrique, 1999, Complexity, V4, P31, DOI 10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO