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