摘要
针对一类带聚类特征的旅行商问题(TSP),研究了一种新型的带聚类处理的C-均值蚁群混合算法.为加快收敛速度,算法首先用C-均值算法对TSP中的城市进行特别聚类处理,然后再利用蚁群算法对分类结果进行处理来得到最终解.算法还集成了一种C-均值搜索算子,并引入了局部搜索策略2-opt,以提高搜索性能.在聚类数目给定的情况下,所提算法能够得到所求TSP的全局较优解,与基本蚁群算法、遗传算法和模拟退火算法比较,它具有更快的收敛速度和更高的收敛精度,并可扩展到一类相关的具有聚类特征的组合优化问题之中.实验结果表明,所提算法是有效的.
To solve the traveling salesman problem with the characteristics of clustering,a novel hybrid algorithm,the ant colony algorithm combined with the C-means algorithm,is presented.In order to improve the speed of convergence,the traveling salesman problem(TSP)data is specially clustered by the C-means algorithm,then,the result is processed by the ant colony algorithm to solve the problem.The proposed algorithm treats the C-means algorithm as a new search operator and adopts a kind of local searching strategy—2-opt,so as to improve the searching performance.Given the cluster number,the algorithm can obtain the preferable solving result.Compared with the three other algorithms—the ant colony algorithm,the genetic algorithm and the simulated annealing algorithm,the proposed algorithm can make the results converge to the global optimum faster and it has higher accuracy.The algorithm can also be extended to solve other correlative clustering combination optimization problems.Experimental results indicate the validity of the proposed algorithm.
基金
The National Key Technology R&D Program of China during the 11th Five-Year Plan Period(No.2006BAH02A06)
关键词
旅行商问题
蚁群算法
C-均值算法
聚类特征
traveling salesman problem
ant colony optimization
C-means
characteristics of clustering
