Intelligent Water Drops Algorithm And Its Application Under Traveling Salesman Problem

The shortest path problem is also named the traveling salesman problem. It is one of the combining optimization problems of mathematics and the hot discussion topics in the logistics industry. The issue that is discussed and deeply studied has an important theoretical and practical significance.Firstly, several simple algorithms are introduced such as branch and bound algorithm, dynamic programming algorithm, ant colony algorithm and particle swarm algorithm in order to solve the problem of combining optimization. In addition to,according to this algorithm, a new optimization algorithm---intelligent water drops algorithm is introduced to solve combining optimization problems, the basic idea and process of this algorithm, the proof of convergence and the advantages and disadvantages of the algorithm are given. Then, through the smaller example, the algorithm is verified to be feasible and effective.Secondly, due to the shortcomings of basic intelligent water, when dealing with large-scale traveling salesman problem, the basic intelligent water algorithm takes longer time to search the optimal solution. In order to deal with the above problem,based on the reverse mutation methods and the strength of 2-exchange method, we put forward the variation characteristics of smart water droplets algorithm. The basic ideas of the algorithm is to search for the optimal path through the effect of variation, the quality of the solution and the performance of the whole group can be improved by this method. Because the number of mutations is random and the process of variation is more convenient than the process of iterative, so the speed of convergence is improved.Finally, through the MATLAB7.0, by two different ways, namely, the intelligent water and the modified algorithm, we compare the results of TSP problem in small scale and larger scale respectively. It shows that both algorithms are good in small scale problems, but in the larger scale problems, the modified algorithm is better than the previous algorithm, The results also showed that the modified algorithm not only improve the quality of the optimal solution but also improve the convergence speed of the algorithm.Therefore the modified algorithm is feasible and effective.