Spark-based Parallel Simulated Annealing Algorithm And Its Application In TSP Problem

The Traveling Salesman Problem(TSP)is a combinatorial optimization problem proposed earlier.Considering the application value of this problem in various fields,researchers start from the intersection of computer,mathematics,operations research and other disciplines,and focus on solving the problem of travel.business problem.The TSP problem itself is an NP-hard problem.According to the current research situation,the simulated annealing algorithm can only approximately solve the TSP problem with a small number of cities,and the solution effect decreases with the increase of the number of cities.The researchers focused on exploring simulated annealing algorithms capable of solving large-scale TSP problems.Spark is an open source platform that can be applied to large-scale data processing.It has the advantages of fast running speed and easy programming,making Spark more suitable for iterative computing.In this paper,the simulated annealing algorithm is improved to solve the TSP problem and Spark is used to parallelize the simulated annealing algorithm to solve the TSP problem quickly and efficiently.The main research work is as follows:(1)According to the characteristics of the traveling salesman problem,the cooling function of the simulated annealing algorithm is improved,and the repeated cooling increases the memory function of the algorithm,thereby maintaining the optimal solution.Use the roulette method to select the neighborhood structure,optimize the solution in three ways: large-scale neighborhood search algorithm,exchange and insertion,and use the 2-OPT operator to enhance the local search ability,effectively solving the traditional simulated annealing algorithm.Solve the problem of slow TSP solution time and poor solution effect.Several TSPLIB datasets are selected for experiments,and the simulation results show that the method has good convergence effect and strong robustness,and can effectively solve the traveling salesman problem.(2)The traditional simulated annealing algorithm has problems such as low solution quality and slow convergence speed.Parallel programming is used to accelerate optimization and a parallel strategy for cross-cooperative experiments is proposed.Several populations are stored in Resilient Distributed Dataset(RDD)in parallel.Run the disturbance to generate a new solution,select the current optimal path and each population for OX crossover,use 2-opt for optimization,and finally use the large-scale neighborhood search algorithm to perturbation to generate a new solution,effectively solving the traditional parallel simulated annealing algorithm.The problem of poor global search ability.Compared with other parallel algorithms of Spark framework,the solution quality and running time are tested.The results show that the algorithm has greatly improved the solution accuracy and running time.