基于群智能和聚类集成的TSP研究
A TSP Algorithm Based on Swarm Intelligence and Clustering Ensemble
旅行商(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均有较优效果.
- 作者：
- 庞永明
- 学位授予单位：
- 宁波大学
- 专业名称：
- 工程硕士(专业学位)
- 授予学位：
- 硕士
- 学位年度：
- 2017年
- 导师姓名：
- 钟才明；钟志光
- 中图分类号：
- TP18
- 关键词：
- 群智能；三角形TSP法；k-means；受限解空间；TSP
- Swarm intelligence； Triangle-based method for TSP； K-means； Restricted solution space； TSP