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

基于信息素更新和挥发因子调整改进蚁群算法张永强王晓东（西安工程大学理学院，陕西西安710048）摘要：基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点，本文运用正负反馈调节信息素增量大小，并将信息素挥发因子随机化，使得蚁群算法自动调整路径上的信息素量.改进后的蚁群算法运用到31个城市的TSP线路优化中，改进蚁群算法比基本蚁群算法(15602)得到更优路径长度为15483.关键词：蚁群算法；信息素；TSP中图分类号：TP312文献标志码：AImprovedantcolonyoptimizationalgorithmbasedonpheromoneupdatingandevaporationfactoradjustingZHANGYong-qiang,WANGXiao-dong(SchoolofScience,Xi’anPolytechnicUniversity,Xi’an710048,China)Abstract:Thebasicantcolonyalgorithmconvergesslowly,ispronetoplungeintopartialoptimumandresultsinsearchstagnation.Inthispaper,animprovedantcolonyalgorithmisproposed.Newalgorithmintroducespositiveandnegativefeedbackregulationofpheromoneincrementsize,andthepheromoneevaporationfactorrandomizedtoadjusttheamountofpheromoneonthepath.Thesimulationresultsoftravelingsalesmanproblemshowthatimprovedalgorithmhasbeenbetterpathlengthis15438thanthebasicantcolonyalgorithm(15602).Keywords:antcolonyalgorithm;pheromone;TSP针对蚁群算法易陷于局部最优解，搜索时间长等缺点，近年来学者们做了大量工作.为了克服算法停滞现象，限制了残留信息量，德国学者Thomassttzle与JolgerHoos提出了最大最小蚁群系统算法[1]，将各条路径上的信息素浓度限制在一定的范围内，避免某条路径的信息量远大于其他路径，使蚂蚁过于集中.针对蚁群算法存在的搜索时间长、易限于局部最优解等缺陷，刘瑞杰，胡小兵[2]提出基于动态调节信息素增量的蚁群算法；孟祥萍，片兆宇，沈中玉等[3]提出了基于方向信息素协调的蚁群算法；张家善，王志宏[4]引入信息素调节系数，提出了基于信息素的改进蚁群算法及其在TSP中的应用；郑卫国，田其冲，张磊[5]对蚂蚁进行区分，控制信息素浓度，提出了基于信息素强度的改进蚁群算法；侯文静，马永杰等[6]提出了一种改进的蚁群算法，通过在初始化信息素矩阵中采用候选节点列表减少劣质解，在局部搜索中采用聚类进行二次搜索，缩小了算法的搜索范围、改善了解空间的质量，提高了搜索速度；柳长安，鄢小虎等[7]提出了根据目标点自适应调整启发函数，提高算法的收敛速度，借鉴狼群分配原则对信息素进行更新，避免搜索陷入局部最优；申铱京，刘阳阳等[8]提出了一种改进的蚁群算法，改进算法采用信息素挥发因子自适应调整机制，调节算法收敛速度，保证算基金项目：陕西省教育厅专项科研计划项目，14JK1299作者简介：张永强(1989-)，男，陕西省宝鸡市人，硕士，研究方向：智能算法，E-mail:[e-mail].王晓东(1974-)，女，陕西省咸阳市人，副教授，硕士生导师，E-mail:[e-mail].法的全局搜索能力等.算法改进工作主要是从全局搜索能力[9]、收敛速度以及精度[10]等方面进行改进；蚁群算法的改进，大量是从蚁群算法的路径选择[11-12]、信息素更新准则[13]、局部搜索与全局搜索[14-16]等方面做了改进.本文针对基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点，通过比较当前路径长度与平均路径长度大小，若当前路径长度小于平均路径长度，则运用正反馈调节信息素增量；若当前路径长度大于平均路径长度，则运用负反馈调节信息素增量；并用(0,1)上的一个随机变量代替信息素挥发因子，使得蚁群算法自动调整路径上的信息素量，进而改进蚁群算法，并将改进后的蚁群算法运用到TSP路径优化中，得到了比基本蚁群算法更优的路径.1蚁群算法蚁群算法是由意大利学者DorigoM等在20世纪90年代初提出的一种新型的模拟进化算法[17-18].每只蚂蚁开始搜索时是从任意一个节点出发，在t时刻以概率P选择下一个节点，此概率计算公式如(1)式所示：否则,0,)()()(kNjijijijijkijallowedjtttpkj(1)其中表示的是信息素的重要程度，表示的是启发因子的重要程度，kjN表示的是指没有访问过的节点，()kijpt表示在时刻t第k只蚂蚁在节点i选择节点j的概率，1/ijijd，表示路径ij上的启发因子；ij表示在路径ij上留下的信息素大小，在节点每被访问一次，ij都会以一定的方式更新，信息素的表达式为：1()(1)()mkijijijktnt(2)其中表示信息素的挥发因子，01，初始时刻kijC，随后kij按(8)式变化：kij=否则,0,/kKallowedjLQ(3)其中KL表示一次旅游结束后蚂蚁k目前访问的总路径长度，Q是常量.2蚁群算法的改进2.1对选择信息素增量的改进信息素增量直接影响路径上信息素量的大小，而路径上的信息素量直接影响蚁群算法的收敛速度.为了使后来蚂蚁在搜索过程中避免重复走以前蚂蚁所走过较长距离的路径从而提高蚁群算法的收敛速度，本文通过正负反馈对信息素增量进行改进：若当前蚂蚁搜索路径长度小于以前所有蚂蚁搜索路径长度的平均值，则加强当前路径上信息素的增量(即正反馈)，使后来蚂蚁进行搜索时要在该路径基础上找到比其更优的路径；若当前蚂蚁搜索路径长度大于以前所有蚂蚁搜索路径长度的平均值，则减弱当前路径上信息素的增量(即负反馈)，使后来蚂蚁进行搜索时撇弃该路径.故对信息素增量改进如下：*/*/iiavekijiQLLLQL，,否则(4)其中kij表示信息素增量，iL为第i次搜索经过路径的总长度，aveL表示在第i次搜索之前搜索过的所有路径的平均长度，表示信息素的挥发因子，01，Q是常量.2.2对挥发因子的改进挥发因子的大小也是影响路径上的信息素量大小的重要因素，从而影响蚁群算法的全局搜索能力和收敛速度.在传统蚁群算法中，挥发因子是(0,1)上的一个常数，如果给定的过大，则路径上的信息素量减少，导致算法收敛速度降低，但可以使蚂蚁遍历所有路径，有助于蚂蚁找到全局最优路径；若给定的偏小，路径上的信息素量将增大，使算法急剧收敛，虽节约了算法的搜索时间，但可能导致算法陷入局部搜索.这种在“探索”和“利用”之间很难找到一种理想的平衡，使得蚁群算法在搜索过程中既避免出现停滞又能具有较强的全局搜索能力.所以为了达到此种平衡去寻找合适的信息素挥发因子，取是(0,1)上的一个随机变量，即0与1之间任意的一个数.若取大了有助于全局搜索；若取小了有利于加快收敛速度；这样随机改变着路径上的信息素量，经过一定的迭代，可以找到全局最优解.对挥发因子改进如下：(0,1)unifrnd(5)2.3算法实现按照以上的改进来确定搜索步骤，每次搜索开始时，在路径节点处随机放置m只蚂蚁.搜索开始后，每只蚂蚁遍历所有节点；在每次迭代过程中找到最优解，迭代完成时，每次迭代得到的最优解组成优解池，在优解池中找到全局最优解.算法步骤如下：Step1：初始化蚁群算法中的参数，，，Q，_maxNC，m，设置迭代计数器初始值1NC；Step2：随机选择每只蚂蚁的初始位置，初始化禁忌表tabu；Step3：m只蚂蚁按概率函数(1)式选择下一个节点，将所选节点添加到tabu中；Step4：若禁忌表tabu未满转至Step3，若已满，得出蚂蚁此次的最优路径长度NCL，并且更新bestL的值，并记录本次迭代最佳路线；Step5：按(2)式更新信息素，其中信息素增量按(4)式更新，挥发因子按(5)式确定，禁忌tabu表清零；Step6：判断迭代次数是否满足条件_maxNCNC，若满足，则迭代次数1NCNC，并转至Step2，开始新一轮的迭代，若不满足，转至Step7；Step7：算法结束，输出最优路径长度bestL.3用改进蚁群算法求解TSP为了测试改进后的蚁群算法的可行性，选取网络公布的Benchmark31作为测试数据，对TSP路线优化和仿真，用基本蚁群算法和改进后的蚁群算法对其求解.在Windows7环境下，运用Matlab7.0语言编程，算法参数选择如下：1，5，100Q，取迭代次数250为终止条件，蚂蚁个数为31，两种算法均运行10次，运行结果见表1，其中基本蚁群算法运行最优结果见图1，改进蚁群算法运行最优结果见图2，最优结果迭代图见图3.表1两种算法运行10次结果对比（路径总长度）Table1Bothalgorithmsrun10timesresultscontrast(totalpathlength)由表1可以看出基本蚁群算法最优路径长度为15602，平均路径长度为15798；改进蚁群算法最优路径长度为15483，平均路径长度为15618.改进蚁群算法比基本蚁群算法能够找到更短的路径.序号基本蚁群算法改进蚁群算法115602155502158291560231597315590415602156025159481557461581815590715884154838159481559291577215960101560215632平均路径长度1579815618图1基本蚁群算法运行图Fig.1Basicantcolonyalgorithmdiagram在图1中，用基本蚁群算法求得该TSP线路优化问题的最短距离为15602，最优解路径为14→12→13→11→23→16→5→6→7→2→4→8→9→10→3→18→17→19→24→25→20→21→22→26→28→27→30→31→29→1→15.图2改进的蚁群算法运行图Fig.2ImprovedantcolonyalgorithmGraph在图2中，用改进后的蚁群算法求得该TSP线路优化问题的最短距离为15483，最优解路径为31→29→30→27→28→26→25→24→20→21→22→18→3→17→19→23→11→6→5→16→4→2→8→9→10→7→13→12→14→15→1.1000150020002500300035004000450050010001500200025003000350040003129302728262524202122183171923116516428910713121415110001500200025003000350040004500500100015002000250030003500400014121311231656724891031817192425202122262827303129115图3算法迭代图Fig.3IterativeAlgorithmFigure图3为基本蚁群算法与改进蚁群算法的迭代图，图中虚线表示基本蚁群算法最优路径长度与迭代次数之间的关系，实线表示改进蚁群算法最优路径长度与迭代次数之间的关系.从图3中可以看出改进蚁群算法迭代曲线最低点在基本蚁群算法迭代曲线最低点的下方，虽然改进蚁群算法在迭代次数较大的情况下找到了全局最优路径长度，但它找到的最优路径长度比基本蚁