Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster
Traveling Salesman Problem (TSP) is one of the most common studied problems in combinatorial optimization. Given the list of cities and distances between them, the problem is to find the shortest tour possible which visits all the cities in list exactly once and ends in the city where it starts. Despite the Traveling Salesman Problem is NP-Hard, a lot of methods and solutions are proposed to the problem. One of them is Genetic Algorithm (GA). GA is a simple but an efficient heuristic method that can be used to solve Traveling Salesman Problem. In this paper, we will show a parallel genetic algorithm implementation on MapReduce framework in order to solve Traveling Salesman Problem. MapReduce is a framework used to support distributed computation on clusters of computers. We used free licensed Hadoop implementation as MapReduce framework.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
A Powerful Genetic Algorithm for Traveling Salesman Problem
This paper presents a powerful genetic algorithm(GA) to solve the traveling salesman problem (TSP). To construct a powerful GA, I use edge swapping(ES) with a local search procedure to determine good combinations of buil…
Traveling Salesman ProblemA Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem
Genetic algorithm includes some parameters that should be adjusting so that the algorithm can provide positive results. Crossover operators play very important role by constructing competitive Genetic Algorithms (GAs). I…
Traveling Salesman ProblemUsing Ants as a Genetic Crossover Operator in GLS to Solve STSP
Ant Colony Algorithm (ACA) and Genetic Local Search (GLS) are two optimization algorithms that have been successfully applied to the Traveling Salesman Problem (TSP). In this paper we define new crossover operator then r…
Traveling Salesman ProblemNew mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem
Traveling salesman problem (TSP) is a well-known in computing field. There are many researches to improve the genetic algorithm for solving TSP. In this paper, we propose two new crossover operators and new mechanism of …
Traveling Salesman ProblemFine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems
The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art perform…