基于信息素更新和挥发因子调整改进蚁群算法

《基于信息素更新和挥发因子调整改进蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于信息素更新和挥发因子调整改进蚁群算法张永强王晓东（西安工程大学理学院，陕西西安710048）摘要：基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点，本文运用正负反馈调节信息素增量大小，并将信息素挥发因子随机化，使得蚁群算法自动调整路径上的信息素量.改进后的蚁群算法运用到31个城市的TSP线路优化中，改进蚁群算法比基本蚁群算法(15602)得到更优路径长度为15483.关键词：蚁群算法；信息素；TSP中图分类号：TP312文献标志码：AImprovedantcolonyoptimizationalgori

2、thmbasedonpheromoneupdatingandevaporationfactoradjustingZHANGYong-qiang,WANGXiao-dong(SchoolofScience,Xi’anPolytechnicUniversity,Xi’an710048,China)Abstract:Thebasicantcolonyalgorithmconvergesslowly,ispronetoplungeintopartialoptimumandresultsinsearchstagnati

3、on.Inthispaper,animprovedantcolonyalgorithmisproposed.Newalgorithmintroducespositiveandnegativefeedbackregulationofpheromoneincrementsize,andthepheromoneevaporationfactorrandomizedtoadjusttheamountofpheromoneonthepath.Thesimulationresultsoftravelingsalesman

4、problemshowthatimprovedalgorithmhasbeenbetterpathlengthis15438thanthebasicantcolonyalgorithm(15602).Keywords:antcolonyalgorithm;pheromone;TSP针对蚁群算法易陷于局部最优解，搜索时间长等缺点，近年来学者们做了大量工作.为了克服算法停滞现象，限制了残留信息量，德国学者Thomassttzle与JolgerHoos提出了最大最小蚁群系统算法[1]，将各条路径上的信息素浓度限制在

5、一定的范围内，避免某条路径的信息量远大于其他路径，使蚂蚁过于集中.针对蚁群算法存在的搜索时间长、易限于局部最优解等缺陷，刘瑞杰，胡小兵[2]提出基于动态调节信息素增量的蚁群算法；孟祥萍，片兆宇，沈中玉等[3]提出了基于方向信息素协调的蚁群算法；张家善，王志宏[4]引入信息素调节系数，提出了基于信息素的改进蚁群算法及其在TSP中的应用；郑卫国，田其冲，张磊[5]对蚂蚁进行区分，控制信息素浓度，提出了基于信息素强度的改进蚁群算法；侯文静，马永杰等[6]提出了一种改进的蚁群算法，通过在初始化信息素矩阵中采用候选节点

6、列表减少劣质解，在局部搜索中采用聚类进行二次搜索，缩小了算法的搜索范围、改善了解空间的质量，提基金项目：陕西省教育厅专项科研计划项目，14JK1299作者简介：张永强(1989-)，男，陕西省宝鸡市人，硕士，研究方向：智能算法，E-mail:akuzyq@sina.com.王晓东(1974-)，女，陕西省咸阳市人，副教授，硕士生导师，E-mail:wangxiaodong1225@126.com.高了搜索速度；柳长安，鄢小虎等[7]提出了根据目标点自适应调整启发函数，提高算法的收敛速度，借鉴狼群分配原则对信息

7、素进行更新，避免搜索陷入局部最优；申铱京，刘阳阳等[8]提出了一种改进的蚁群算法，改进算法采用信息素挥发因子自适应调整机制，调节算法收敛速度，保证算法的全局搜索能力等.算法改进工作主要是从全局搜索能力[9]、收敛速度以及精度[10]等方面进行改进；蚁群算法的改进，大量是从蚁群算法的路径选择[11-12]、信息素更新准则[13]、局部搜索与全局搜索[14-16]等方面做了改进.本文针对基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点，通过比较当前路径长度与平均路径长度大小，若当前路径长度小于平均路径长度，则运

8、用正反馈调节信息素增量；若当前路径长度大于平均路径长度，则运用负反馈调节信息素增量；并用(0,1)上的一个随机变量代替信息素挥发因子，使得蚁群算法自动调整路径上的信息素量，进而改进蚁群算法，并将改进后的蚁群算法运用到TSP路径优化中，得到了比基本蚁群算法更优的路径.1蚁群算法蚁群算法是由意大利学者DorigoM等在20世纪90年代初提出的一种新型的模拟进化算法[17-18].每只蚂蚁开始搜索时是从任