An Improved Ant Colony Algorithm Based On Spark In TSP

The objective of combinatorial optimization is to find the optimal solution from a feasible solution set under a given constraint condition.Among the many algorithms for solving combinatorial optimization problems,ant colony algorithm is one of the most widely used algorithms,but because it is a probability based group search algorithm,there are two fatal weaknesses: first,the search is easy to stagnate and fall into the local optimal;second,it takes a lot of time to deal with large-scale data.In order to solve these problems,people have proposed a variety of improvement methods,but most of the schemes are difficult to achieve a balance in these two aspects.Therefore,an improved optimization algorithm is urgently needed,which can not only improve the quality of search,but also quickly solve it.Based on ant system algorithm(ACS),a series of improvement measures are introduced.According to the natural parallelism existing in the process of feasible deconstruction and the computing characteristics of Spark distributed framework,an improved ant colony algorithm based on Spark is proposed.This paper mainly focuses on the following aspects:(1)The traditional ant colony algorithm and its improved algorithm are easy to fall into the local optimum,which has the defects of poor solution quality.In the middle and above scale traveling salesman problem,its solution speed is also not satisfactory.In order to improve the above problems,this paper proposes a local search technology with acceleration function and adopts the strategy of increasing the number of ants.The improved algorithm not only improves the ability to find the optimal solution,but also reduces the effect of a sharp increase in the time cost caused by increasing the complexity of the algorithm and saves the running time relatively.(2)Spark is a new parallel computing framework based on memory operation.It allows data to load to cluster memory and query it many times,which is very suitable for machine learning and algorithm research.It is because of the natural parallelism of ant colony algorithm and the great advantage of Spark in parallel computing.After combining the two,the paper can not only give play to the global optimization ability of the ant colony algorithm in solving the TSP problem,but also improve the local search quality by improving the measures,and the search speed is greatly accelerated based on the Spark cluster.So as to better solve the combinatorial optimization problem similar to TSP problem.The simulation results show that the improved algorithm has significantly improved the solution quality.In the face of large scale TSP problem,not only has the higher ability to find the optimal solution,but also benefits from the parallel computing power of the Spark cluster,and the running time has been greatly reduced compared with the previous algorithms.While guaranteeing the improvement of the solution quality,the new algorithm effectively improves the computation speed and improves the overall performance greatly.