第4卷第6期 智能系统学报 Vol.4 No.6 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/j.issn.16734785.2009.06.010 个体速度差异的蚁群算法设计及仿真 印峰，王耀南，刘炜2，周良 (1.湖南大学电气与信息工程学院，湖南长沙410082；2.湖南科技职业学院软件学院，湖南长沙410118) 摘要：针对如何提高蚁群算法搜索速度及防止算法停滞问题，提出一种改进的蚁群优化算法VACO(ACO algorithm based on ant velocity),通过构造与局部路径和蚂蚁个体速度相关的时间函数，并建立与时间函数相关的动态信息素 释放机制，加快信息素在较优路径上正反馈过程，从而提高了算法的收敛速度；采取一种连续小区间变异策略，在加 快局部搜索过程的同时可有效防止算法陷入局部最优.对典型TSP问题的仿真研究结果表明，改进后的算法在收敛 性和对较好解的探索性能得到一定程度的提高. 关键词：蚁群算法；旅行商问题；信息素；NP-难解 中图分类号：TP301.6文献标识码：A文章编号：16734785(2009)06052806 Design and simulation of an ant colony algorithm based on individual velocity differences YIN Feng,WANG Yao-nan',LIU Wei2,ZHOU Liang (1.College of Electrical and Information Engineering of Hunan University,Changsha 410082,China;2.School of Software,Hunan Vocational College of Science and Technology,Changsha 410118,China) Abstract:A new implementation of the ant colony optimization (ACO)algorithm was primarily focused on impro- ving search speed and preventing stagnation.To resolve these two issues,improvements based on velocity were pro- posed,producing a VACO algorithm.By constructing a time-function for local paths and ant velocity,and building a dynamic release mechanism for pheromones in the time-function,it accelerated positive feedback from the accu- mulation of pheromones,leading to better paths and improved convergence speed.A strategy of continuous inter- cell mutation sped up local searches and at the same time effectively prevented the algorithm being trapped in local optimums.The results showed that the proposed algorithm improves convergence and increases the possibility of finding optimal solutions. Keywords:ant colony algorithm;TSP;pheromone;NP-hard 蚁群算法是模拟自然界中真实蚁群的觅食行为 以寻找可能存在最优解的解区间，又同时充分利用 而形成的一种模拟进化算法).目前该算法已在求 当前群体的有效信息，使算法搜索的侧重点放在可 解组合优化问题、系统辨识、机器人路径规划、数据 能具有最优解的子区间内：使得算法在可以接受的 挖掘、网络路由等问题时取得了很好的效果231.然 时间内收敛到全局最优解.目前提出的各种改进的 而与其他算法相比，蚁群算法存在搜索速度较慢、容 蚁群算法均围绕对上述问题的研究展开[4刀 易出现停滞现象的缺陷.特别对于大规模优化问题， 信息素更新策略是决定算法收敛速度的关键之 如何加快其收敛速度以及防止算法陷入局部最优一 一，针对如何提高算法收敛速度的问题，目前提出的 直是蚁群算法研究中有待解决的一个热点和难点问 几种有代表性的蚁群政进算法，比如最优保留蚂蚁系 题.总体来说，解决该问题的关键在于如何处理好下 统[4(ASelite)、蚁群系统5)(ACS)、最大-最小蚂蚁 述问题之间的平衡：即使算法的搜索空间尽可能大， 系统[6](MMAS)等，均采用针对全局最优解所属边进 行信息素全局更新的策略，即通过加强对当前最优解 收稿日期：200908-12， 基金项目：国家科技支撑计划资助项目(2008BAF36B01):国家“863” 的利用来缩小算法的搜索空间，进而提高算法的收敛 计划资助项目(2008AA04Z214). 速度.另外也有学者提出动态信息素更新策略89]，其 通信作者：印峰.E-mail:yinfeng83@126.com. 本质也是对蚂蚁所走较优路径上的信息加强的动态