智能水滴算法及其在旅行商中的应用

发布时间：2018-10-10 13:28

【摘要】：最短路径问题又称为旅行商问题(Traveling Saleman Problem,TSP),此问题是数学中的组合优化问题之一,也是物流业中讨论的热门话题。对该问题进行讨论和深入的研究具有重要的理论意义和现实意义。首先,本文介绍了解决组合优化问题的四种算法如分支定界算法、动态规划算法、蚁群算法和粒子群算法,接着介绍了一种新的求解组合优化问题的算法---智能水滴算法,并证明了它的收敛性,讨论了该算法的优缺点,并将其应用到最短路径问题中,通过小规模的实例验证了该算法的可行性和有效性。其次,本文提出了一种具有变异特性的智能水滴算法。考虑到智能水滴算法在处理大规模旅行商问题(最短路径问题)时存在一定的局限性,如搜索到最优解的质量不高或搜索到最优解时所需要时间较长等问题,本文在智能水滴算法的基础上加入变异机制的作用,借用逆转变异的方法,利用2-opt方法简便高效的特点,提出了具备变异特性的智能水滴算法。该算法的基本思想是让算法搜索到的最优路径经过变异的作用,得到新的解(新的路径),从而可以提高最优解的质量,进而提高整个群体的性能。又因为变异的次数是随机性的并且变异的这个过程用到的运算量比智能水滴算法中的迭代过程要简便的多,从而在运算量上节省了时间,进而提高了算法的收敛速度。最后,通过MATLAB7.0实现了具备变异特性的智能水滴算法,并对中国10个城市和34个城市的TSP问题,分别采用智能水滴算法和改进的智能水滴算法进行仿真实验,结果表明改进的智能水滴算法相较于智能水滴算法,在求解小规模(10个城市)问题时虽然没有相对的优劣势,但在求解相对大规模(34个城市)问题时,表现出相对的优势,它不仅提高了最优解的质量而且加快了算法的收敛速度,故该改进算法具有一定的可行性和有效性。
[Abstract]:The shortest path problem, also known as the traveling salesman problem (Traveling Saleman Problem,TSP), is one of the combinatorial optimization problems in mathematics, and is also a hot topic in the logistics industry. It is of great theoretical and practical significance to discuss and further study this problem. Firstly, this paper introduces four algorithms to solve combinatorial optimization problems, such as branch and bound algorithm, dynamic programming algorithm, ant colony algorithm and particle swarm optimization algorithm. The convergence of the algorithm is proved, the advantages and disadvantages of the algorithm are discussed, and it is applied to the shortest path problem. The feasibility and effectiveness of the algorithm are verified by a small scale example. Secondly, an intelligent water droplet algorithm with mutation property is proposed. Considering that intelligent water droplet algorithm has some limitations in dealing with large-scale traveling salesman problem (shortest path problem), such as the quality of searching the optimal solution is not high or the time required to search the optimal solution is longer, etc. In this paper, the function of mutation mechanism is added on the basis of intelligent water droplet algorithm. By using the method of reverse mutation and the simple and efficient characteristic of 2-opt method, an intelligent water drop algorithm with mutation characteristics is put forward in this paper. The basic idea of the algorithm is to get a new solution (new path) through the mutation of the optimal path which can improve the quality of the optimal solution and then improve the performance of the whole population. Because the number of mutation is random and the operation of the mutation is much simpler than the iterative process in the intelligent water drop algorithm, the computation time is saved and the convergence speed of the algorithm is improved. Finally, the intelligent water drop algorithm with mutation characteristic is realized by MATLAB7.0. The TSP problem of 10 cities and 34 cities in China is simulated by intelligent water drop algorithm and improved intelligent water drop algorithm, respectively. The results show that compared with the intelligent droplet algorithm, the improved intelligent droplet algorithm has no relative advantages and disadvantages in solving small scale (10 cities) problems, but it shows relative advantages in solving relatively large scale problems (34 cities). It not only improves the quality of the optimal solution, but also accelerates the convergence rate of the algorithm, so the improved algorithm is feasible and effective.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【参考文献】