蚁群算法、遗传算法及二者融合后在TSP应用中的对比研究

发布时间：2018-12-27 09:15

【摘要】：旅行商问题作为组合优化问题的典型代表,很多问题都可以转化为该问题求解。随着优化理论在各行各业的广泛应用,寻找旅行商问题的最优解成为研究重点。论文以求解旅行商问题的最短巡回路径为主要研究对象,首先介绍了求解旅行商问题的背景和研究现状,阐述了蚁群算法和遗传算法以及二者融合后的原理,并建立了它们的数学模型和求解旅行商问题的步骤。在此基础上,对三种算法在TSP中的应用进行了如下研究:1、对蚁群算法、遗传算法以及二者融合后最优的参数选取进行了分析;2、在参数选取最优的情况下改变TSP的规模用三种算法分别对最短路径距离的寻优进行仿真实验;3、对三种算法在不同规模上的寻优结果进行对比分析。实验结果表明,求解TSP的最短巡回路径,当TSP规模较小时,三种算法的寻优效果没有明显的优劣之分;随着TSP规模的扩大,将蚁群算法与遗传算法融合后,寻优效果明显好于两种算法单独运算时的求解效果。
[Abstract]:As a typical representative of combinatorial optimization problems, many problems can be transformed into solving them. With the wide application of optimization theory in various industries, finding the optimal solution of traveling salesman problem becomes the focus of research. In this paper, the shortest itinerant path of traveling salesman problem is taken as the main research object. Firstly, the background and research status of solving traveling salesman problem are introduced, and the ant colony algorithm and genetic algorithm and the principle of merging them are expounded. Their mathematical models and the steps to solve the traveling salesman problem are established. On this basis, the application of the three algorithms in TSP are studied as follows: 1. The ant colony algorithm, genetic algorithm and the optimal selection of parameters after the fusion of the ant colony algorithm and genetic algorithm are analyzed. 2. Under the condition of optimal parameter selection, three algorithms are used to simulate the optimization of the shortest path distance by changing the scale of TSP; 3, the optimization results of the three algorithms on different scales are compared and analyzed. The experimental results show that there is no obvious difference between the three algorithms when the scale of TSP is small for solving the shortest circuit path of TSP. With the expansion of the TSP scale, the combination of ant colony algorithm and genetic algorithm is better than the solution of the two algorithms alone.
【学位授予单位】：山西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】