龙源期刊网 http://www.qikan.com.cn
改进蚁群算法及其应用研究
作者：段文超 崔锐 许柏松 陈立军 来源：《数字技术与应用》2013年第02期
摘要：针对蚁群算法在求解组合优化问题过程中出现局部收敛或停滞的现象，本文提出了一种蚁群算法。在保证有较好寻优能力的前提下实现算法更为快速的收敛，并选取TSPLIB数据作为测试样本，比较了改进蚁群算法和基本蚁群算法的准确性以及迭代次数。实验结果表明改进后的蚁群算法在寻优能力以及收敛速度方面均显著提高。 关键词：蚁群算法 收敛速度 信息素挥发系数
中图分类号：O224 文献标识码：A 文章编号：1007-9416（2013）02-0115-01 1 引言
20世纪90年代初，意大利学者DORIGO等人受到自然界中蚂蚁群体觅食行为的启发提出了一种模拟进化算法—蚁群算法。蚁群算法因其较强的寻优能力在解决非线性和多约束条件的组合优化问题方面应用广泛。然而，在取得良好效果的同时也出现了收敛速度慢、易停滞等缺点。针对这些问题，文献[1]提出了一种最大最小蚁群算法MMAS（MAX-MIN Ant System），通过限定信息素浓度的范围，提高算法的全局搜索能力；文献[2]提出的带交叉算子的蚁群算法，扩大解的局部搜索空间，增强最优解的信息素浓度，从而加快算法的收敛；文献[3]提出了一种将遗传算法植入到蚁群算法中的混合算法，用遗传算法生成信息素分布来克服蚁群算法收敛较慢的问题。蚁群算法的优劣取决于收敛速度以及收敛的准确性，两者之间有一定的相互制约的关系，某种程度上说，收敛速度过快，会使得搜索变得不充分，易出现局部收敛，得到最优解的稳定性降低；反之，为了增加解的多样性，避免局部收敛而得到最优解，又会使收敛速度变慢。寻找一种既能增加解得多样性又能提高收敛速度的改进算法，是研究蚁群算法的关键技术之一，为此本文提出了串级控制并行交互蚁群算法。 2 蚁群算法基本原理
蚁群算法通过模拟自然界蚂蚁寻找到食物并返回蚁穴的过程来实现对问题的求解。研究表明，蚂蚁会在它经过的路径上留下信息素，信息素是蚂蚁之间传递信息的一种介质，会随着时间的推移逐渐挥发。信息素浓度越高则蚂蚁选择该条路径的概率越大，这种正反馈的作用，使得蚂蚁最终能够找到一条最短路径。
为便于描述，我们以TSP问题对蚁群算法做简单的介绍。TSP问题是在给定n个城市，并已知每两个城市之间的距离，要寻找到一条经过这n个城市且不重复的最短路径。其数学模型定义变量有：
龙源期刊网 http://www.qikan.com.cn
m表示人工蚁群数量；dij（i，j=1，2，…，n）表示城市i与城市j之间的距离；τij（t）表示t时刻在ij连线上的信息量；ηij=1/dij反映由城市i转移到j的启发程度；Pkij（t）表示在t时刻蚂蚁k由城市i转移到j的概率；α和β分别为信息素τij（t）和启发因子ηij的重要程度；Tabuk（k=1，2，…，m）用于记录蚂蚁k当前所走过的城市，t时刻蚂蚁k从城市i到城市j的转移概率Pkij（t）为：
M.Dorigo曾给出三种蚁群算法不同模型，分别称之为ant cycle system、ant density system、ant quantity system。三种模型中，第一种模型是在一次循环完成后更新信息素，利用的是整体信息；而后两种模型是在蚂蚁每走一步后更新信息素，利用的都是局部信息。经过实验对比，在求解旅行商问题时第一种模型性能较好。因此，通常以该模型作为蚁群算法的基本模型。定义如下：
其中，Q为常数，表示蚂蚁完成一次循环所释放的信息素总量，LK为蚂蚁k在本次循环中的总路径长度。 3 蚁群算法的改进
蚁群算法中，信息素挥发系数ρ的设定直接影响着算法的全局搜索能力，ρ较大时，会使得很少被搜索到的路径上信息素趋近于零，正反馈的作用容易导致算法出现局部收敛；ρ取值较小时，信息素挥发的慢，正反馈的作用被削弱，提高算法随机性的同时也降低了收敛速度。自适应的调整信息素挥发系数ρ能够有效的提高算法的全局搜索能力。初始时，信息素挥发系数选取一个相对较大的初值，能够快速的搜索到较优路径，然后通过不断减小ρ，扩大搜索空间，使算法能够逃脱局部收敛现象从而得到最优解。
当算法在N次循环后求得的最优值没有变化时，通过修改信息素挥发系数ρ逐步加强算法的全局搜索能力，调整如下：
上式中，ρmin为信息素挥发系数的最小值，防止ρ过小影响算法的收敛速度。λ的取值范围通常在 （0.5，1）之间，实验表明，当λ取值过小，每次信息素挥发系数ρ的修改幅度过大，会影响算法收敛的稳定性。
本文采用并行交互蚁群策略与自适应调整信息素挥发系数的方法构成串级回路，用并行交互策略加快算法收敛速度，使其能够快速的找到一个备选的最优解，起到了粗调的作用。经过一段时间各种群得到的最优解差别不大时，当连续多次得到的全局最优值无变化时，交互机制失去作用，此时得到的不一定是最优解，因此用自适应修改信息素挥发系数的方法扩大搜索空间，使其能够打破停滞现象，当某一种群跳脱局部收敛后交互机制又能够重新发挥作用，直到算法找到最优值。 4 实验与结论
龙源期刊网 http://www.qikan.com.cn
本文在TSPLIB中选取ch150TSP作为研究对象，对改进前后的算法进行比较，实验结果表明本文提出的改进方法较之基本蚁群算法无论是在收敛速度还是准确性方面都有了明显的提高。 参考文献
[1]Krzysztof Socha-Toshua Knowles， Michael Sampels.A MAX-MIN Ant System for the University Course Timetabling Problem[M].2000.
[2]陈烨.带杂交算子的蚁群算法[J].计算机工程，2001，27（12）：27-30.
[3]王峰峰，王仁明，伍佳.求解TSP问题的一种改进蚁群算法[J].自动化技术与应用，2010，29（7）：1-3.