The Improved Simulated Annealing Algorithm Research And Application Based On TSP

Traveling Salesman Problem (TSP) is not only a combinatorial optimization problem but also a typical NP-hard problem, which has application value widely. In recent years, with the continuous progress in computer science, TSP is becoming the new focus of people research, also becoming an important basis for correctness and feasibility of the new algorithm. Because simulated annealing algorithm is simple and easy to implement, which has great area of use, it has been successfully applied to many aspects and has showed very good results. But simulated annealing algorithm also has weak point, that It is not very satisfactory of avoiding falling into local minimum and search capability and area of solution space.In this paper for two shortcomings of simulated annealing algorithm, improving traditional simulated annealing algorithm has been improved and proposed solutions to classic travelling salesman problem, based on multi-population and multi-operator. The algorithm draws benefits of genetic algorithm's implicit parallelism, and proposed multi-population parallelism for improving efficiency optimization, which is also search capability of global optimal solution, compared to traditional serial optimization about single solution, the improved method greatly enhanced the efficiency; For the purpose of increasing search capability and area of solution space, the paper solves it by improving function of producing state, which the methods of achieving new path use 2 transformation or 3 transformation, but now we use multi-operator for new solution space and a certain degree of probability decides to use which one for new solution space, this approach has greatly increased covering an area of solution space, Further the possibility is increased about avoiding local optimal solution and searching global optimum solution.The paper has used the improved algorithm and has been proved by travelling salesman problem of solving the problems of CHN31,ATT48 and EIL51. Simulation results show that the algorithm obtained good results, not only avoiding traditional simulated annealing algorithm easily falling into local minimum and improving the quality of searching global optimal solution, but also improving speed of algorithm's convergence. As can be seen, the algorithm improved really has improved optimization performance and optimization efficiency optimization...