蚂蚁算法[1]近年在许多领域得到应用并获成果，在移动机器人全局路径规划研究上也有应用[2]。作为通用型随机优化方法，蚂蚁算法较遗传算法﹑模拟退火算法有较好的适应性，较可视图法有较高的效率，在克服局部极小解方面要好于人工势场法。
但是，传统的蚂蚁算法也存在缺陷。如，路径点转移方向未能快速确保为收敛方向；所有路径点同时转移容易导致各点配合不好而使总距离长度产生振荡。
本文根据蚂蚁嗅觉引导行为原理，使路径点位置转移方向确保为收敛方向，减少迭代计算中概率选择公式的运算量；在每次迭代过程中不遍历修改全体蚂蚁的位置，仅调整最迫切需要转移的蚂蚁个体，从而避免总距离长度出现振荡；对改进后的算法进行了计算机仿真，结果表明，新算法达到预期目标。2 蚂蚁的嗅觉引导行为
蚂蚁具有嗅觉功能，可以感知其它蚂蚁在路径上留下的信息素和食物弥散在空气中的气味。蚁群能够根据食物气味逐步修改已有的路径，最终找出从窝巢至食物的最短路径。
虽然机理很复杂，但可以将蚂蚁的嗅觉引导行为表示为图1的模型。设食物气味呈辐射状向四周散发，其浓度沿径向等梯度减弱，蚁群沿着曲折的路径向食物前进，Pi-1→Pi→Pi+1是其中的两段。当蚂蚁沿这两段路径行走同样距离时，如果所嗅到的食物气味浓度的增幅更大，则认定路径点Pi后的新路线能够更快地趋近于食物，蚁群会逐步调整此转弯点的位置，反之则蚁群不会对已有路线进行修改。图1说明蚂蚁的嗅觉引导行为的原理，其中，
当α>β时，△r1<△r2，显然，蚂蚁将察觉在行走同样距离△d的情况下，沿线段Pi-1Pi比沿线段PiPi+1，食物气味浓度的增幅更大，即路径点后的路线要优于先前的路线，蚂蚁将调整路径点的位置，修改行走路线。当α<β时，△r1>△r2，虽然路径点后的路线要劣于先前的路线，但蚂蚁的智商决定蚁群将暂时继续沿着留有信息素的旧路线行走，而不会立即对已有路径做出修改。同理可推知当α=β，即△r1=△r2时，蚁群也不会立即对路径做出修改。
实际上，当α≤β时，蚂蚁对本路径点位置的调整要等到蚁群调整过其他路径点的位置并且导致本路径点处的α>β后，再对已有行走路径做出修改。
3 基于嗅觉引导行为的算法改进
本文根据α-β的值对传统蚂蚁算法作了两个方面改进，一是确定蚂蚁位置的转移方向专注于总距离的收敛方向，大幅度减少概率选择公式中的求和运算；二是对迭代算法进行改进，按照需要修改的迫切程度来决定迭代过程中修改的路径点，避免总距离长度出现振荡。
3．1 位置转移方向及概率选择公式求和项
蚂蚁对路径点的调整行为发生在路径点Pi附近很小的一个邻域内（见图2）。所以，α可以用线段Pi-1Pi的延长线PiPi'与终点至Pi连线的夹角α'代替。
由前述可知，仅当α'>β时，蚁群将把Pi点在线段Pi1Pi2上向Pi1方向移动。如果将这一事实运用于转移的目的分点的选择，则概率选择公式中的求和运算将减少一半。随着迭代次数的增加，求和的项数还将逐次减少。公式中，u（≥0）为能见度的相对重要性，v（≥0）为迹的重要性。
3．2 迭代计算中被调整的路径点
每次迭代前，计算所有路径点处的α-β的值，选择α>β且|α-β|大的路径点进行调整。每次迭代调整一个转移点位置，经过若干次迭代，每个转移点的位置至少被调整过一次。
3．3 改进后的蚂蚁算法
下面是按伪码形式表述的改进后的蚂蚁算法：
Begin
初始化：
for k←1 to m do
for j←1 to n do
置bkj←c（较小的正数）；
置△bkj←Q（一次蚂蚁一次留下的信息素量）；
将m条调整直线中点作为转移点，并将该点集V0记为初始路径P0和最优路径P1；
Loop：
for k←1 to m do
计算αk-βk ；
在所有αk>βk的转移点中找出具有最大值的点(k, j)；
确定点(k, j)转移的目标分点范围(k, g)～(k, h)，g∈(0,1,…, n)，h∈(0,1,…, n)；
for j←g to h do
计算概率公式Pkj；
找出最大Pkj值对应的分点(kmax, jmax)并将路径点(k, j)转移到(kmax, jmax)；
在相邻直线的转移点上加△bkj，即bk-1, j= bk-1, j+△bk, j, bk-1, j= bk-1, j+△bk, j
置(k, j) ←(kmax, jmax)；
将分点(k, j)置换于P0中；
将P0与P1相比较；
若更优
P1←P0；
若路径与障碍物不相交且无退化行为
goto Loop；
输出P1；
End
其中，m为蚂蚁个数；dkj为第k只蚂蚁转移到第j个分点时，新的总路径距离；akj为第k个蚂蚁在第j个分点时的能见度，取akj =1/ dkj；bkj为第k只蚂蚁所在直线段的第j个分点的轨迹强度；△bkj为第k只蚂蚁移动到第j个分点时所留下的轨迹信息量，按蚂蚁密度模型取为
;
4 仿真计算与分析
设已经用链接图法[3]对含有障碍物的环境建模，且已经用Dijkstra算法求得了链接图最短路径，如图3中次粗线所示。现在用本文改进的蚂蚁算法在计算机上对图中次粗的路径进行调整。算法设定的运行参数为{m，n，u，v，Q}={6，100，0.9，0.1，0.05}，算法对转移点位置的调整顺序和修改后对应的总距离见表1，所得最优路径编码表示为P=0.118，0.000，0.254，1.000，0.650，迭代的次数是8次，比原算法少2次，收敛速度比原算法快至少约1/5。从表中可知，总距离是单调较少的。
表1 转移点位置修改的顺序及对应的总距离
我们又对其它环境的链接图最短路径用本文改进的蚂蚁算法进行了调整，最终都得到了预期的结果，即收敛速度得到了提高，且不出现总距离振荡。
5 结束语
蚂蚁算法作为一种仿生的随机搜索寻优算法，最早应用于旅行商（TSP）问题，现在在组合优化、人工智能、网络通信等许多领域开展研究和应用。在移动机器人链接图最短路径基础上进行调整以获得点到点寻优全局路径规划的最短路径，实际上也是一个类似TSP的问题。通过本文的工作，由链接图最短路径获得全局最短路径的任务得到了优化，说明本文方法的是正确的。
【