簇类特征城市群间的TSP问题研究  

Research on Traveling Salesman Problemof Cluster Class Featured Large City Groups

作　　者：王兴[1] 

机构地区：[1]武汉科技大学信息科学与工程学院,湖北武汉430081

出　　处：《自动化仪表》2013年第3期14-16,20,共4页Process Automation Instrumentation

摘　　要：针对现实生活中旋行商问题(TSP)大量样本集一般具有呈区域分布的簇类特性,提出了一种基于平衡聚类的免疫遗传算法。首先分析了城市样本点的分布特征,采用平衡聚类算法将城市样本点聚成K个不同的类,并找出类与类之间的最短路径;然后采用免疫遗传算法得到类内部城市间的最短路径;最终得到全局最短路径。仿真试验证明,该算法明显提高了收敛速度。In real life, normally a large number of sample sets of TSP features regional distributed cluster characteristic, in accordance with this situation, the immune genetic algorithm based on balanced clustering is proposed. Firstly, the distribution characteristic of the city sample points are put forward, by adopting balanced clustering algorithm, the city sample points are changed into K different classes, and the shortest route among classes is found, then by using immune genetic algorithm, the shortest route among cities inside the class is obtained from the sample points in class, finally the global shortest route is derived. The simulation test verifies that the algorithm obviously enhances the convergence speed.

关 键 词：簇类特征 免疫遗传算法 数据挖掘 收敛速度 最短路径 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]