基于K均值聚类改进的蚁群算法研究

摘要

蚁群优化算法(ACO)在求解TSP(traveling salesman problem)问题时,其算法的时间复杂度为O(m·n2·t)(其中t表示循环次数,n为城市数,m为蚂蚁数),搜索时间比较长。利用K-means聚类的方法得到多个类,每一个类都看作是一个小的TSP问题,然后在每个类内部和类之间利用改进的蚁群算法寻找最优路径,通过实验仿真,验证了此方法不但能提高解的精度,而且还加快了运行速度。

关键词

蚁群算法 / K-means / 聚类

基金资助

合肥学院自然科学研究一般项目(13KY04ZR); 大学生创新创业训练项目(201311059068)