| TSP is not only a typical combinatorial optimization problem, but also a NP-hard problem, which is easy-to-describe but difficult to deal with. For a long time, people have been looking for an efficient, fast approximation algorithm to solve a Large-scale problem accurately in a reasonable time.Among them, typical of intelligent optimization algorithms have Ant Colony algorithm and Genetic algorithm as well as mix of both algorithms and so on.This paper mainly study the solution of TSP based on one Improvement of Genetic and Ant Colony algorithm. The main research works are as follows:(1) With the characteristics of TSP problem,in the early TSP problem solving with application of the Delaunay triangulation of the candidate set of strategies to reduce the search space of the solving of problems, and further accelerate the searching speed. And as the basis for use the improvement of algorithm solving TSP.(2) That stress on analyse the shortcomings of Ant colony algorithm,Genetic algorithm the traditional mix of both algorithm. For which insufficient, made a number of improvements to the mix of algorithm:1) That introduces a dynamic integration of strategy can ensure the best integration time for the two algorithms; 2) That introduces grey prediction model to estimate the delimitation of pheromone in MMAS; 3) The introduction of cloud association rules, to achieve the parameters adaptive adjusting by themselves in the mix of algorithms.After these improvements,made Genetic algorithms and Ant Colony algorithm to a better mix of dynamic, full play to their strengths more effectively used to solve the TSP problem.To verify the algorithm performance, this paper use the TSPLIB experimental data to compare and analyse the running results of the improved algorithm, MMAS and the Genetic and Ant Colony algorithm that before that improved. The results show that the improved algorithm proposed in this paper relatively better performance.
|
PDF Full Text Request