基于吸引场的蚁群算法在TSP中的应用  

Application of an ant colony optimization based on attractive field in TSP

作　　者：王雷[1] 李明[1] 刘志虎[1] 

机构地区：[1]安徽工程大学机械与汽车工程学院,安徽芜湖241000

出　　处：《江苏大学学报（自然科学版）》2015年第5期573-577,582,共6页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金资助项目(51305001;71171002);安徽省自然科学基金资助项目(1308085ME65);安徽省高等教育提升计划省级自然科学研究项目(TSKJ2014B12)

摘　　要：针对传统蚁群算法容易陷入局部最优解等缺陷,提出了一种基于吸引场的改进的蚁群算法.首先,详细分析了基于信息素的吸引场原理,在此基础上建立了基于信息素的吸引场模型.其次,设计了吸引场因子,给出了信息素更新策略,使相距较近的蚂蚁之间能更好地进行协作.最后,针对标准的30个城市的旅行商问题,使用所提出的算法与基本蚁群算法、其他改进的蚁群算法进行优化分析,并进行了结果对比.结果表明:所提出的蚁群算法可以获得TSP问题的最优解423.74,Oliver30问题计算结果最优值为423.74,平均值为423.96,具有较好的搜索全局最优解的能力.To overcome the default of local optimal solution in the traditional ant colony algorithm,a modified ant colony optimization（ AFACO） was proposed based on attractive field. The principle of attraction field based on pheromone was analyzed in detail to establish the attractive field model. The attractive field factor based on pheromone was designed,and the pheromone updating strategy was provided to improve the collaboration among ants nearby. For the standard 30 city traveling salesman problem,the optimization results from the proposed algorithm were compared with those from basic ant colony algorithm and some other improved ant colony. The results show that the optimal solution of TSP problem is 423. 74,while the optimal and the mean solution of Oliver30 are 423. 74 and 423. 96,respectively,which shows the improved ant colony algorithm has good ability for searching the global optimal solution.

关 键 词：路径规划 旅行商问题 蚁群算法 信息素 吸引场 

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