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

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

2、rationfactor adjusting ZHANG Yong-qiang , WANG Xiao-dong(School of Science, Xian Polytechnic University, Xian , China) Abstract: The basic ant colony algorithm converges slowly, is prone to plunge into partial optimum and results in search stagnation. In this paper, an improved ant colony algorithm

3、is proposed. New algorithm introduces positive and negative feedback regulation of pheromone increment size, and the pheromone evaporation factor randomized to adjust the amount of pheromone on the path. The simulation results of traveling salesman problem show that improved algorithm has been bette

4、r path length is 15438 than the basic ant colony algorithm(15602).Key words: ant colony algorithm; pheromone; TSP针对蚁群算法易陷于局部最优解，搜索时间长等缺点，近年来学者们做了大量工作.为了克服算法停滞现象，限制了残留信息量，德国学者Thomas sttzle与Jolger Hoos提出了最大最小蚁群系统算法1，将各条路径上的信息素浓度限制在一定的范围内，避免某条路径的信息量远大于其他路径，使蚂蚁过于集中.针对蚁群算法存在的搜索时间长、易限于局部最优解等缺陷，刘瑞杰，胡小兵2提出基

5、于动态调节信息素增量的蚁群算法；孟祥萍，片兆宇，沈中玉等3提出了基于方向信息素协调的蚁群算法；张家善，王志宏4引入信息素调节系数，提出了基于信息素的改进蚁群算法及其在TSP中的应用；郑卫国，田其冲，张磊5对蚂蚁进行区分，控制信息素浓度，提出了基于信息素强度的改进蚁群算法；侯文静，马永杰等6提出了一种改进的蚁群算法，通过在初始化信息素矩阵中采用候选节点列表减少劣质解，在局部搜索中采用聚类进行二次搜索，缩小了算法的搜索范围、改善了解空间的质量，提基金项目：陕西省教育厅专项科研计划项目， 14JK1299作者简介： 张永强(1989-)，男，陕西省宝鸡市人，硕士，研究方向：智能算法，E-mail:a

6、. 王晓东(1974-)，女，陕西省咸阳市人，副教授，硕士生导师，E-mail:.高了搜索速度；柳长安，鄢小虎等7提出了根据目标点自适应调整启发函数，提高算法的收敛速度，借鉴狼群分配原则对信息素进行更新，避免搜索陷入局部最优；申铱京，刘阳阳等8提出了一种改进的蚁群算法，改进算法采用信息素挥发因子自适应调整机制，调节算法收敛速度，保证算法的全局搜索能力等.算法改进工作主要是从全局搜索能力9、收敛速度以及精度10等方面进行改进；蚁群算法的改进，大量是从蚁群算法的路径选择11-12、信息素更新准则13、局部搜索与全局搜索14-1

7、6等方面做了改进.本文针对基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点，通过比较当前路径长度与平均路径长度大小，若当前路径长度小于平均路径长度，则运用正反馈调节信息素增量；若当前路径长度大于平均路径长度，则运用负反馈调节信息素增量；并用(0,1)上的一个随机变量代替信息素挥发因子，使得蚁群算法自动调整路径上的信息素量，进而改进蚁群算法，并将改进后的蚁群算法运用到TSP路径优化中，得到了比基本蚁群算法更优的路径.1 蚁群算法蚁群算法是由意大利学者Dorigo M等在20世纪90年代初提出的一种新型的模拟进化算法17-18.每只蚂蚁开始搜索时是从任意一个节点出发，在时刻以概率选择下一个节点，

8、此概率计算公式如(1)式所示： (1)其中表示的是信息素的重要程度，表示的是启发因子的重要程度，表示的是指没有访问过的节点，表示在时刻第只蚂蚁在节点选择节点的概率，表示路径上的启发因子；表示在路径上留下的信息素大小，在节点每被访问一次，都会以一定的方式更新，信息素的表达式为： (2)其中表示信息素的挥发因子，初始时刻，随后按(8)式变化： = (3)其中表示一次旅游结束后蚂蚁目前访问的总路径长度，是常量.2 蚁群算法的改进2.1 对选择信息素增量的改进信息素增量直接影响路径上信息素量的大小，而路径上的信息素量直接影响蚁群算法的收敛速度.为了使后来蚂蚁在搜索过程中避免重复走以前蚂蚁所走过较长距离

9、的路径从而提高蚁群算法的收敛速度，本文通过正负反馈对信息素增量进行改进：若当前蚂蚁搜索路径长度小于以前所有蚂蚁搜索路径长度的平均值，则加强当前路径上信息素的增量(即正反馈)，使后来蚂蚁进行搜索时要在该路径基础上找到比其更优的路径；若当前蚂蚁搜索路径长度大于以前所有蚂蚁搜索路径长度的平均值，则减弱当前路径上信息素的增量(即负反馈)，使后来蚂蚁进行搜索时撇弃该路径.故对信息素增量改进如下： (4)其中表示信息素增量，为第次搜索经过路径的总长度，表示在第次搜索之前搜索过的所有路径的平均长度，表示信息素的挥发因子，是常量.2.2 对挥发因子的改进挥发因子的大小也是影响路径上的信息素量大小的重要因素，从

10、而影响蚁群算法的全局搜索能力和收敛速度.在传统蚁群算法中，挥发因子是(0, 1)上的一个常数，如果给定的过大，则路径上的信息素量减少，导致算法收敛速度降低，但可以使蚂蚁遍历所有路径，有助于蚂蚁找到全局最优路径；若给定的偏小，路径上的信息素量将增大，使算法急剧收敛，虽节约了算法的搜索时间，但可能导致算法陷入局部搜索.这种在“探索”和“利用”之间很难找到一种理想的平衡，使得蚁群算法在搜索过程中既避免出现停滞又能具有较强的全局搜索能力.所以为了达到此种平衡去寻找合适的信息素挥发因子，取是(0, 1)上的一个随机变量，即0与1之间任意的一个数.若取大了有助于全局搜索；若取小了有利于加快收敛速度；这样随

11、机改变着路径上的信息素量，经过一定的迭代，可以找到全局最优解.对挥发因子改进如下： (5)2.3 算法实现按照以上的改进来确定搜索步骤，每次搜索开始时，在路径节点处随机放置只蚂蚁.搜索开始后，每只蚂蚁遍历所有节点；在每次迭代过程中找到最优解，迭代完成时，每次迭代得到的最优解组成优解池，在优解池中找到全局最优解.算法步骤如下：Step 1：初始化蚁群算法中的参数，设置迭代计数器初始值；Step 2：随机选择每只蚂蚁的初始位置，初始化禁忌表；Step 3：只蚂蚁按概率函数(1)式选择下一个节点，将所选节点添加到中； Step 4：若禁忌表未满转至Step 3，若已满，得出蚂蚁此次的最优路径长度，并

12、且更新的值，并记录本次迭代最佳路线；Step 5：按(2)式更新信息素，其中信息素增量按(4)式更新，挥发因子按(5)式确定，禁忌表清零；Step6：判断迭代次数是否满足条件，若满足，则迭代次数，并转至Step 2，开始新一轮的迭代，若不满足，转至Step 7；Step 7：算法结束，输出最优路径长度.3 用改进蚁群算法求解TSP为了测试改进后的蚁群算法的可行性，选取网络公布的Benchmark31作为测试数据，对TSP路线优化和仿真，用基本蚁群算法和改进后的蚁群算法对其求解.在Windows7环境下，运用Matlab7.0语言编程，算法参数选择如下：，取迭代次数250为终止条件，蚂蚁个数为3

13、1，两种算法均运行10次，运行结果见表1，其中基本蚁群算法运行最优结果见图1，改进蚁群算法运行最优结果见图2，最优结果迭代图见图3.表1 两种算法运行10次结果对比（路径总长度）Table 1 Both algorithms run 10 times results contrast (total path length)序号 基本蚁群算法 改进蚁群算法1 15602 155502 15829 156023 15973 155904 15602 156025 15948 155746 15818 155907 15884 154838 15948 155929 15772 1596010 15

14、602 15632平均路径长度 15798 15618由表1可以看出基本蚁群算法最优路径长度为15602，平均路径长度为15798；改进蚁群算法最优路径长度为15483，平均路径长度为15618.改进蚁群算法比基本蚁群算法能够找到更短的路径.100015002000250030003500400045005001000150020002500300035004000 14121311231656724891031817192425202122262827303129115图1 基本蚁群算法运行图Fig.1 Basic ant colony algorithm diagram在图1中，用基本蚁群

15、算法求得该TSP线路优化问题的最短距离为15602，最优解路径为14121311231656724891031817192425202122262827303129115.10001500200025003000350040004500500100015002000250030003500400031293027282625242021221831719231165164289107131214151图2 改进的蚁群算法运行图Fig.2 Improved ant colony algorithm Graph在图2中，用改进后的蚁群算法求得该TSP线路优化问题的最短距离为15483，最优解路径为

16、31293027282625242021221831719231165164289107131214151.0501001502002501.51.551.61.651.71.751.81.85x 104基本蚁群算法改进蚁群算法迭代次数路径长度图3算法迭代图Fig.3 Iterative Algorithm Figure图3为基本蚁群算法与改进蚁群算法的迭代图，图中虚线表示基本蚁群算法最优路径长度与迭代次数之间的关系，实线表示改进蚁群算法最优路径长度与迭代次数之间的关系.从图3中可以看出改进蚁群算法迭代曲线最低点在基本蚁群算法迭代曲线最低点的下方，虽然改进蚁群算法在迭代次数较大的情况下找到了全

17、局最优路径长度，但它找到的最优路径长度比基本蚁群算法找到的最优路径长度更优.4 结论路径优化问题是人们外出旅游线路考虑的现实问题，本文通过利用正负反馈机制改进信息素增量和挥发因子随机化改进基本蚁群算法，并用改进的蚁群算法对31个节点的TSP路线进行路径优化，实验结果表明，改进的蚁群算法比基本蚁群算法得到了较优路径.本文改进的蚁群算法对求解路径优化问题具有一定的参考价值.参考文献1 Stutzle T, Hoos H. MAX-Min ant system and local search for the traveling salesman problem C/ Proceedings of

18、the 1997 IEEE International Conference on Evolutionary Computation, Indianapolis. USA: IEEE, 1997: 309-314.2刘瑞杰，胡小兵.基于动态调节信息素增量的蚁群算法J. 计算机应用研究，2012,29(1):135-151.LIU Ruijie,HU Xiaobing. Ant colony algorithm based on dynamic adjustment of incremental of pheromoneJ. Application Research of Computers,

19、2012,29(1):135-151.3孟祥萍，片兆宇，沈中玉等.基于方向信息素协调的蚁群算法J.控制与决策，2013,28(5):782-786.MENG Xiangping, PIAN Zhaoyu, SHEN Zhong-yu,etal .Ant algorithm based on direction-coordinatingJ. Control and Decision, 2013,28(5):782-786.4张家善，王志宏.基于信息素的改进蚁群算法及其在TSP中的应用J.数学的实践与认识，2013,43(22):157-160.ZHANG Jiashan, WANG Zhihon

20、g.Improved Ant Colony Algorithm Based on Pheromone and Application in the TSPJ. Mathematics in Practice and Theory, 2013,43(22):157-160.5郑卫国，田其冲，张磊.基于信息素强度的改进蚁群算法J.计算机仿真，2010,27(7):191-193.ZHENG Weiguo，TIAN Qithong, ZHANG Lei. An Improved Ant Colony Algorithm Based on PheromoneJ.Computer Simulation,

21、 2010,27(7):191-193.6侯文静，马永杰，张燕等，求解TSP的改进蚁群算法J.计算机应用研究，2010,27(6):2087-2089.HOU Wenjing,MA Yongjie,ZHANG Yan,etal.Improved ant colony algorithm for solving TSPJ. Application Research of Computers, 2010,27(6):2087-2089.7柳长安，鄢小虎，刘春阳等，基于改进蚁群算法的移动机器人动态路径规划方法J.电子学报，2011,39(5):1220-1224.LIU Chang,YAN Xiao

22、hu, LIU Chunyang,etal. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization AlgorithmJ. Acta Electronica Sinica, 2011,39(5):1220-1224.8申铱京，刘阳阳，黄永平等，求解TSP问题的快速蚁群算法J.吉林大学学报，2013,43(1):147-151.SHEN Xuanjing,LIU Yangyang, HUANU Yongping,etal.Fast ant colony algorithm for solv

23、ing traveling salesman problemJ. Journal of Jilin University, 2013,43(1):147-151.9张 毅，贺兴时，杨新社. 基于模拟退火与高斯扰动的布谷鸟算法J.纺织高校基础科学学报，2015，28(04)：515-521.ZHANG Yi，HE Xingshi，YANG Xinshe. A Cuckoo Search Algorithm based on Simulated Annealing and gaussian disturbanceJ. Basic Sciences Journal of Textile Univer

24、sities，2015，28(4)：515-521.10刘召军，高兴宝. 融合自适应混沌差分进化的粒子群优化算法J.纺织高校基础科学学报，2015，(1)：116-123.LIU Zhaojun，GAO Xingbao. Particle Swarm Optimization Algorithm by integrating adaptive chaos differential evolutionJ. Basic Sciences Journal of Textile Universities，2015，(1)：116-123.11姜坤霖，李美安，张宏伟.面向旅行商问题的蚁群算法改进J.计算

25、机应用，2015,35(S2):114-117.JIANG Kunlin，LI Meian，ZHANG Hongwei.Improved ant colony algorithm for travelling salesman problemJ. Journal of Computer Applications, 2015,35(S2):114-117.12张志协，曹阳.基于改进型蚁群算法的最优路径问题求解J.计算机系统应用，2012,21(10):76-80.ZHANG Zhixie, CAO Yang.Solving Optimal Path Problem Based on Improv

26、ed Ant Colony AlgorithmJ. ComputerSystems&Applications, 2012,21(10):76-80.13王宝生，屈宝存.蚁群算法在求解TSP问题中的改进研究J.电子设计工程，2014,22(22):14-18.WANG Baosheng,QU Baocun.The improvement of ant colony algorithm in solving TSPJ. Electronic Design Engineering ,2014,22(22):14-18.14Akihiro Uchida, Yasuaki Ito, Koji Nakano. Accelerating ant colony optimisation for the travel