基于聚类分析的增强型蚁群算法  

Enhanced ant colony optimization algorithm based on clustering analysis

作　　者：任志刚[1,2] 冯祖仁[1,2] 柯良军[1,2] 张兆军[1,2] 

机构地区：[1]西安交通大学系统工程研究所,西安710049 [2]西安交通大学制造系统工程国家重点实验室,西安710049

出　　处：《控制与决策》2010年第8期1201-1206,共6页Control and Decision

基　　金：国家自然科学基金项目(60875043;60905044);国家973计划项目(2007CB311006)

摘　　要：针对蚁群算法存在的早熟收敛、搜索时间长等不足,提出一种增强型蚁群算法.该算法构建了一优解池,保存到当前迭代为止获得的若干优解,并提出一种基于邻域的聚类算法,通过对优解池中的元素聚类,捕获不同的优解分布区域.该算法交替使用不同簇中的优解更新信息素,兼顾考虑了搜索的强化性和分散性.针对典型的旅行商问题进行仿真实验,结果表明该算法获得的解质量高于已有的蚁群算法.Due to the shortcomings of ant colony optimization（ACO） algorithm,such as premature convergence and exorbitantly long computation time,an enhanced ACO algorithm is proposed.It constructs a good solution pool which holds a certain number of best solutions found so far.These solutions are clustered by a developed neighbourhood-based clustering algorithm,and accordingly some different regions which contain good solutions can be captured.The proposed ACO algorithm alternately employs the good solutions belonging to different clusters to update pheromone.By this means,both the intensification and the diversification of search are consulted.Simulation experiment is conducted on typical travelling salesman problems.The results show that,the presented algorithm is more efficient in generating high-quality solutions.

关 键 词：蚁群算法 早熟收敛 聚类分析 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]