期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2019
卷号：10
期号：8
页码：97-107
出版社：Science and Information Society (SAI)
摘要：Achieving an optimal solution for NP-complete
problems is a big challenge nowadays. The paper deals with the
Traveling Salesman Problem (TSP) one of the most important
combinatorial optimization problems in this class. We
investigated the Parallel Genetic Algorithm to solve TSP. We
proposed a general platform based on Hadoop MapReduce
approach for implementing parallel genetic algorithms. Two
versions of parallel genetic algorithms (PGA) are implemented, a
Parallel Genetic Algorithm with Islands Model (IPGA) and a
new model named an Elite Parallel Genetic Algorithm using
MapReduce (EPGA) which improve the population diversity of
the IPGA. The two PGAs and the sequential version of the
algorithm (SGA) were compared in terms of quality of solutions,
execution time, speedup and Hadoop overhead. The experimental
study revealed that both PGA models outperform the SGA in
terms of execution time, solution quality when the problem size is
increased. The computational results show that the EPGA model
outperforms the IPGA in term of solution quality with almost
similar running time for all the considered datasets and clusters.
Genetic Algorithms with MapReduce platform provide better
performance for solving large-scale problems.
关键词：Genetic algorithms; parallel genetic algorithms;
Hadoop MapReduce; island model; traveling salesman problem
