Study Of Parallel Genetic Algorithm Based On Spark Solving The Traveling Salesman Problem

By today's accelerate popularization of Internet,information transfer faster and faster,the data is becoming larger,so a lot of problems are associated with a large amount of data as they arise.In our daily life,these questions are often unable to use mathematical model to summarize,the typical problem is the traveling salesman problem.A general way to solve these problems is optimization algorithm.These algorithms can reach an approximate solution for the answer.Genetic Algorithm is a classical optimization Algorithm,it has many advantages when solving specific issues.It is simple for mathematical modeling and it does not need relevant knowledge.So the applicability of GA is more stronger than other optimization algorithms.But the GA also has some drawbacks.The searching space of genetic algorithm is limited in stand-alone environment,not in the later stages of the algorithm is run to get the optimal solution effectively,and,with the increase of the number of iterations,the time-consuming genetic algorithm is significantly increased,probably can't acceptable time to obtain the optimal solution.The parallel genetic algorithm can make use of the advantage of multi-core hardware platform,now makes a lot of problems increases further,the search space for complex systems,especially the complex system can produce a huge amount of data,has a strong ability of optimization.Therefore,parallel genetic algorithm,genetic algorithm has been the focus of the research object.This paper proposes a Simulate Fine-grained Coarse-grained Parallel Genetic Algorithm.By introducing a fine-grained model of information communication method,the algorithm can improve the shortcomings of traditional coarse-grained parallel model.In order to further enhance the search ability of the genetic algorithm,we find an appropriate evolution strategy which fit in the parallel process.In the process of evolution,suitable genetic operators are introduced through the comparison between different solutions.Finally,taking the advantage of the Spark's interactive model,the algorithm is accelerated.There are experiments to enhance the result.The experiment applies the improved algorithm to traveling salesman problem in berlin52 data sets.The results shows that compared with the traditional parallel model,the improved algorithm can significantly shorten the calculation time,increase the searching scope,and the premature phenomenon is improved.