A TSP Algorithm Based On Swarm Intelligence And Clustering Ensemble

Travelling salesman problem is one of combinatorial optimization problems,which is proven to be a classic NP-complete problem.The optimal solution of TSP is optimal Hamiltonian circuit.The method of solving this problem has a long history and a very large family.Swarm Intelligence,has long been studied and can produce a relatively satisfied solution.Using this method to solve the optimal solution of the dataset,we will first analyze the internal object connection in dataset.As K-means clustering method is a common method to partition dataset,it can be combined with swarm intelligence to solve TSP.Several methods for solving TSP are proposed in this thesis : the triangle-based algorithm,the improved swarm algorithm,the restricted connections that is reconsidered to improve the solutions produced by ACO,the optimization of EAX,and improved ACO combined with the optimization of EAX.As Triangle-based algorithm can solve TSP quickly,the optimization of ACO’s initial matrix formed from its solutions is presented in this paper.By analyzing the distance of internal data and different algorithm of solving dataset on the basis of the aimless selection for ants,k-means clustering is used in order to divide the dataset and then the dataset which has been divided can improve ACO.As a result,it will be regarded as an impact factor of ACO’s iteration.Comparing FM with MST,the author discovers that the optimal solutions of dataset are distributed in a small space.Therefore,the solution of restricted space is put forward.Optimal initial matrix connects restricted connections,which are not all broad space,are used as frontier set for k-opt algorithm’s optimization.In this way,we can reduce time complexity and space complexity.In addition,the author presents that restricted space of frontier set will replace MST and initial population of EAX are substituted by triangle-based method for TSP’s offspring due to the drain message in the process of generating TSP for EAX algorithm as well as low efficiency during connecting loop.Finally,the method which hybrids improved ACO and Optimal EAX is presented to solve TSP by analyzing the deficiencies of improved ACO and Optimal EAX as well as solution distribution in the space.In this paper,20 kinds of datasets are selected,and the results of each algorithm are shown.In the end,the comparisons of all algorithms are listed.The experiment results on these datasets demonstrate the proposed method has better result.