具有多态特征和聚类处理的蚁群算法  

Ant Colony Algorithm with Polymorphism and Clustering Processing

作　　者：段凤玲[1] 李龙澍[1] 曹文婷[1] 

机构地区：[1]安徽大学计算机科学与技术学院,安徽合肥230039

出　　处：《计算机技术与发展》2009年第12期77-80,共4页Computer Technology and Development

基　　金：国家自然科学基金项目(602730430);安徽省自然科学基金项目(050420204);安徽省教育厅自然科学基金项目(2006KJ098B);安徽省高校拔尖人才基金项目(05025120);安徽大学研究生创新基金项目(20073005)

摘　　要：现实蚁群中,蚁群的觅食是一种典型的聚类行为,文中针对一些带聚类特征的TSP,提出了新型的带聚类处理的多态蚁群算法。该算法思想是根据聚类特征对TSP中的城市进行处理,将待求问题分成许多小规模的子问题。对于每个子问题,融合多态蚁群算法,引入不同种类的蚁群。通过对每个子问题进行求解,得到类内最短距离。最后按文中给出的规则合并所有子问题的解得到最优解。算法实验测试结果表明,该算法能将局域搜索与全局搜索相结合,极大提高了算法的收敛速度和求解速度。In reality,the act of finding fodo for ant is a typical clustering behavior. Aiming TSP with clustering, raise a new algorithm, which is integration of polymorphic ACA and improved ACA with clustering. The thonght of the algorithm decomposes TSP into many sub - problems based on the characteristic of clustering, and then solves every sub- prohtem. While solving every, sub- problem, it merges polymorphic ACA, introduces different types of ant colony, and merges Local Search and Global search. At last, it merges all the solutions of the sub- problems, and gets the bestanswer of the problem. Experiment result has proved that it can greatly improve convergence rate and solution speed of algorithm.

关 键 词：蚁群算法 旅行商问题 聚类 多态蚁群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]