基于群智能和聚类集成的TSP研究

发布时间：2018-06-19 08:18

本文选题：群智能 + 三角形TSP法　；参考：《宁波大学》2017年硕士论文

【摘要】：旅行商(traveling salesman problem,TSP)问题是优化组合问题中一类经典的NP问题,这类问题的目标是求得一个最优哈密顿回路,对于该类问题的求解方法源远流长,求解算法众多,其中群智能算法表现较优,这也成为人们研究的重点。群智能算法首先会分析数据集内部对象连接,由于聚类算法k-means在划分数据集中较为常见,并且效果较优,本文结合群智能算法和聚类算法k-means求解TSP。本文提出几种求解TSP的方法,包括三角形TSP法、改进的蚁群算法、受限边集空间优化改进的蚁群算法、优化基于GA(Genetic Algorithm)的EAX(Edge Assembly Crossover)法(文中将基于GA的EAX,简称为EAX)、结合改进的蚁群算法与改进的EAX。由于三角形TSP法能够快速求解TSP,本文首先以三角形TSP法为基础,针对蚁群算法中初始蚂蚁具有盲目选择的特点,提出优化蚁群算法的初始矩阵,然后研究数据集内部对象之间距离和分布,结合不同算法对数据集求解的分析,提出运用聚类算法k-means划分数据集,将该划分结果作为蚁群算法迭代中的影响因子,以此求解并得到较好的解。其次,通过对数据集本身最优解与MST(Minimum Spanning Tree)和利用三角形TSP法形成的初始矩阵相比对,发现所有数据集的解都分布在狭小的空间,以此提出受限解空间。优化初始矩阵中包含的边集,构成受限的边空间,将广泛的边空间限制在狭小范围,用这部分边集实施k-opt优化,从而可以减小时间复杂度和空间复杂度。另外,本文又通过研究发现EAX算法在形成新的TSP过程中有信息遗漏,并且用MST连接回路效率较低,进而提出以受限的边集空间替代原来的MST,并用三角形TSP法生成解替代EAX算法的初始种群。最后,本文综合分析改进的蚁群算法和优化的EAX的不足之处,以及对解空间中解的分布,提出结合改进的蚁群算法和优化的EAX求解TSP。本文用20个数据集测试以上5种算法,给出测试结果,并在文章最后列出所有算法的比对,通过实验表明,本文所提出的算法对TSPLIB中数据集求解TSP均有较优效果。
[Abstract]:Traveling salesman problem (TP) problem is a classical NP problem in optimal combinatorial problem. The goal of this kind of problem is to find an optimal Hamiltonian loop. The method of solving this kind of problem has a long history and many algorithms. Among them, swarm intelligence algorithm is better, which has become the focus of research. Firstly, the cluster intelligence algorithm will analyze the object connection in the data set. Because the clustering algorithm k-means is more common in the partition data set, and the effect is better, this paper combines the swarm intelligence algorithm and the clustering algorithm k-means to solve the k-means. This paper presents several methods for solving tsp, including triangle tsp, improved ant colony algorithm, constrained edge set space optimization, and improved ant colony algorithm. The method of optimizing EAXT Edge Assembly Crossoverbased on GA genetic algorithm (EAX) based on GA is proposed in this paper, which combines the improved ant colony algorithm with the improved EAX. Because the triangular tsp method can solve tsp quickly, this paper, based on the triangular tsp method, puts forward the initial matrix of the optimization ant colony algorithm, aiming at the blind selection of the initial ant in the ant colony algorithm. Then the distance and distribution of objects in the data set are studied. Combining with the analysis of different algorithms to solve the data set, the clustering algorithm k-means is proposed to partition the data set, and the partition result is regarded as the influence factor in ant colony algorithm iteration. By this method, a better solution is obtained. Secondly, by comparing the optimal solution of the data set itself with the initial matrix formed by the triangular tsp method, it is found that the solutions of all the data sets are distributed in a narrow space, so that the constrained solution space is proposed. The edge set contained in the initial matrix is optimized to form a restricted edge space, and the extensive edge space is confined to a narrow range. The k-opt optimization is implemented with this part of edge set, which can reduce the time complexity and space complexity. In addition, we also find that the EAX algorithm has information omission in the process of forming new tsp, and the efficiency of using MST to connect the loop is low. Then it is proposed that the original MSTs be replaced by the restricted edge-set space and the initial population of the EAX algorithm be replaced by the triangular tsp method. Finally, this paper comprehensively analyzes the shortcomings of the improved ant colony algorithm and the optimized EAX, as well as the distribution of the solution in the solution space, and proposes a combination of the improved ant colony algorithm and the optimized EAX to solve the TSPs. In this paper, 20 datasets are used to test the above five algorithms, and the test results are given. At the end of the paper, the comparison of all the algorithms is given. The experiments show that the algorithm proposed in this paper has a better effect on solving tsp in the data set of TSPLIB.
【学位授予单位】：宁波大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】