Research And Improvement About TSP Algorithm

The traveling salesman problem (TSP) is the classic problem of combination optimization problem and is also an NP-complete problem. It is the simplify form of many optimization problems such as genome mapping, planetary exploration, the drilling of circuit boards, circuit board welding, traffic scheduling, job scheduling and so on. Since the TSP is an NP-complete problem and hard to be solved, it is also used as a standard processor tests and standard problem for compare the algorithms. Therefore, the TSP study has both important theoretical and practical values.The early1990s, inspired by ant foraging behavior in nature, the Italian scholar by Dorigo M, et proposed the ant colony algorithm. It is a population-based heuristic evolutionary algorithm with strong robustness, parallelism, scalability, flexibility and easy to be integrated with other methods. At the same time, it is a search algorithm which combines distributed computation, positive feedback mechanisms and greedy principle. After Ant colony algorithm proposed, the concerns of many scholars are aroused, and those scholars apply it into various fields of optimization problems. So far, the ant colony algorithm works in many areas, such as function optimization, network routing, robot path planning, system identification, data mining, as well as circuit wiring, and all these applications have achieved good results.In several ant colony optimization algorithms, the Max-Min ant colony algorithm is the best. This paper presents a detailed experimental analysis on Max-Min ant system. By comparing experiments with different algorithm parameters, we decided the most appropriate algorithm parameters. Through the study of Max-Min ant system for each iteration of the loop, we identify suitable conditions for judging algorithm convergence.The comparative study of real optimal loop algorithm for constructing loop in TSP, we found that the loop containing the true optimal edge is generally short. At the same time, the loop length and the true optimal number of edges contained in it are inversely proportional. That is to say, the more real optimal edges the loop contains, the shorter the length of the loop is. Accordingly, in turn, the shorter loop has greater probabilities to contain more optimal edges. Inspired by this, this paper proposes a new solution strategy based on the quality edge. The algorithm runs the historical information to choose a quality edge which is probably the true optimal edge. Through modified routing rules, the path of the ants is as limited as possible in the quality edge, in an attempt to reduce the solution space of the algorithm. Through the improvement of the experimental simulation of the algorithm, we found that the improved algorithm accelerates the process of the ants construct high-quality solution, but also makes the algorithm has a large probability to find the real optimal solution, and also this experiment has improved the performance of the algorithm for solving problems.