Hadoop MapReduce for Parallel Genetic Algorithm to Solve Traveling Salesman Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 8
Abstract
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.
Authors and Affiliations
Entesar Alanzi, Hachemi Bennaceur
Keywords
Related Articles
- EP ID EP626571
- DOI 10.14569/IJACSA.2019.0100814
- Views 81
- Downloads 0
Socialization of Information Technology Utilization and Knowledge of Information System Effectiveness at Hospital Nurses in Medan, North Sumatra
Background of this research is the globalization and development of science, especially in the field of information and communication technology and communication that has influenced and has implications for changes and...
Quizzes: Quiz Application Development Using Android-Based MIT APP Inventor Platform
This work deals with the development of Android-based multiple-choice question examination system, namely: Quizzes. This application is developed for educational purposes, allowing the users to prepare the multiple choic...
Generation of Sokoban Stages using Recurrent Neural Networks
Puzzles and board games represent several important classes of AI problems, but also represent difficult complexity classes. In this paper, we propose a deep learning based alternative to train a neural network model to...
Backstepping Control of Induction Motor Fed by Five-Level NPC Inverter
In this paper we will present a contribution to the backstepping control for induction motor (IM) based on the principle of Field Orientated Control (FOC). This law is established step by step while ensuring the stabilit...
Investigate the Performance of Document Clustering Approach Based on Association Rules Mining
The challenges of the standard clustering methods and the weaknesses of Apriori algorithm in frequent termset clustering formulate the goal of our research. Based on Association Rules Mining, an efficient approach for We...