《基于双向蚁群算法的路径规划研究》由会员分享，可在线阅读，更多相关《基于双向蚁群算法的路径规划研究（19页珍藏版）》请在金锄头文库上搜索。
1、 基于双向蚁群算法的路径规划研究 申铉京,施英杰,黄永平,王玉(1.吉林大学 计算机科学与技术学院,吉林 长春 130012;2.吉林大学 软件学院,吉林 长春 130012)蚁群算法1是经典的仿生学优化算法之一,与Dijstra2、Bellman-Ford3以及A*算法4等寻路算法相比,在寻求最短路径上始终具有更加优越的效果。此外,在解决路径问题时,与其他的优化算法如模拟退火算法5及遗传算法6更具优势。然而,该算法的收敛速度缓慢,陷入局部最优解难以跳出始终都是困扰着蚁群算法效率的一大问题7。针对上述问题,相关学者提出了不同的解决方案8-9。针对收敛速度问题,文献10在每个路口加入了东南西北4
2、个指针,从而使蚁群在路口时能够优先选择指向终点的路径来提高蚁群算法的效率。然而,该方法所选择的环境为真实道路环境(十字路口等),且仅涉及4个方向,因此将其用于解决机器人路径规划时可能造成陷入局部最优解等问题。在文献11中,作者通过利用双向搜索的思想,首先通过A*算法初始化一条次优路径,加强次优路径上的初始信息素的值在初期给蚂蚁一个引导作用防止蚂蚁进行盲目搜索。然后通过改变算法的信息素更新策略提高了算法的搜索精度,但依旧无法解决搜索全局最优解困难的问题。此外,由于A*预处理的存在,导致该方法的解集合可能更小。在文献12中,作者引入自适应信息素挥发系数,使信息素挥发系数随着迭代次数发生改变,从而加
3、快了搜索的速度,但在搜索精度方面仍有些许的不足,如在算法前中期无法找到最优解,那本次算法就无法获得全局最优解。文献13在信息素更新过程中对最优路径进行信息素奖励,对最差路径进行信息素惩罚,从而提高了算法的搜索速度和收敛能力。但不足之处在于某些情况优先选择离终点较近的节点可能会使蚂蚁走过更长的路径到达终点,且在长的路径上设立了信息素惩罚,在路径搜索时会减小某些同时存在于长路径和最短路径上的节点被选择的概率,会对搜索精度和收敛速度造成影响。相关学者也提出了许多方法致力于解决算法容易陷入局部最优解以及搜索精度不足等问题。如在在文献14中,作者在启发信息中加入了对下一可行节点到目标节点的距离,同时在信
4、息素更新过程中,对最优路径进行奖励而对最差路径进行惩罚减少其路径上的信息素,在路径搜索中有着较为明显的效果提升,但对长路径的信息素惩罚项以及对蚂蚁的死锁处理依旧存在导致其节点选择时容易使蚂蚁错过最短路径。文献15中,作者通过控制蚁群的种群相似度来调节解的多样性,并对蚁群算法的信息素更新策略进行调整,有效降低了算法所获得的最短路径的长度。在文献16中,作者通过禁忌栅格来避免路径死锁问题,加快了算法的搜索速度,同时采用正反方向蚂蚁,让蚂蚁根据2种不同的搜索策略来进行搜索,有效地提高了算法的收敛速度和搜索精度,然而其采用的折返搜索策略,虽在一定程度上提高了搜索效率,但也增大了算法的搜索时间。在文献1
5、7中,作者在蚁群的启发函数中加入了当前节点、待选节点以及终点之间的距离关系,并采取信息素扩散方法使某个节点上的信息素向附近节点扩散,从而有效地提高了算法的搜索精度,但同时因为信息素扩散,可能会导致某些差的路径上信息素过大,从而对算法的效率和收敛速度造成影响。文献18中,作者通过修改启发式、蚂蚁转移概率及信息素更新公式来提高算法的效率,在最短路径和收敛速度方面都有着不错的提升。同时也有学者将蚁群算法与其他算法进行融合来解决其收敛速度缓慢以及搜索精度不足的问题19。如文献20中作者将蚁群算法与萤火虫算法进行融合用来解决车辆路径选择问题,作者在蚁群算法中加入信息素摇动,通过避免信息素在开放区域上停滞
6、而逃脱局部最优。在文献21中,作者在势场蚁群算法的基础上提出了基于势场跳转的蚁群算法,将跳点搜索算法引入到鱼群算法中,引入了势场合力递减系数从而减小蚁群陷入局部最优的问题,并对势场蚁群算法的初始信息素浓度、信息素更新策略和启发信息做了一定的改进,使算法的搜索速度有着明显的提升。在其他领域也存在对于路径规划问题良好解决办法。文献22考虑到除路径长度以外的环境因素对最优路径选择所产生的影响,选择的最优路径评价指标不止局限于长度,还包括行走需要的时间、费用以及损耗等问题,并通过实验证明了实时环境下基于多目标的路径选择模型更具有实用价值。该思想同样可应用于机器人路径规划。因此,在最优路径长度相近的情况
7、下,缩小平均转角可以有效减少机器人行走所需要的时间。通过上述分析,本文提出一种改进蚁群算法用于解决传统蚁群算法收敛缓慢以及搜索精度不足等问题,其基本思想为：让蚂蚁根据编号分别从不同的起始位置出发向起点或终点进行路径搜索,在搜索到对应的路径后根据新的信息素更新规则对全局信息素进行更新。1)让蚂蚁从地图上非起点和目标节点的可行节点出发,向起点或目标节点去进行搜索,通过让蚂蚁从不同的起点出发来增加解的多样性以获得全局最优解。2)设立新的全局信息素更新规则,对每次迭代中寻找到的最优路径进行奖励而不对最差路径进行惩罚以增加走过最优路径的蚂蚁对下一轮迭代蚂蚁的引导作用。3)提出了自适应角度参数并将其使用在
8、蚂蚁转移概率中以提高算法的收敛速度,并与新的信息素更新规则共同作用来降低搜索到的路径的总旋转角度,使机器人在路径上的旋转角度有所下降最后在Matlab仿真实验中证实了该方法是有效可行的,且寻优效率相对其他算法要高。1 蚁群算法概述蚁群算法是一种用来寻找优化路径的概率型算法,是由Dorigo15提出的一种仿生学群体智能优化算法,其灵感来源于蚂蚁在觅食过程表现出的群体智能行为,即在蚂蚁觅食过程中,单只蚂蚁的行为比较简单,但是蚁群整体却可以体现一些智能的行为。1.1 蚁群算法转移概率蚂蚁在觅食时会在自己走过的路径上留下信息素,而蚁群内的蚂蚁对信息素具有感知能力,它们会沿着不同路径中信息素浓度高的路径
9、行走,每只走过该路径的蚂蚁都会在路径上留下信息素,这样经过一段时间后,蚁群就会沿着最短的路径到达食物源。蚁群算法的转移概率公式为：(1)式中：k为当前蚂蚁的编号;是信息素启发式因子,代表信息素浓度对转移概率的影响。的值越大,蚂蚁就更倾向于选择其他蚂蚁选择过的路径,搜索的随机性减弱,同时降低了解的多样性,扼杀了一些地图中找到全局最优解的概率。越小,蚁群的搜索范围也就越小,容易陷入局部最优。ij为i、j路径上的信息素浓度。信息素浓度为期望启发因子使算法成为正反馈搜索,该值过大,容易导致蚂蚁选择局部最优路径,虽然收敛速度加快,但无法获得全局最优路径。为启发函数,其值为i、j两点之间距离的倒数,启发函
10、数的表达式为：(2)1.2 信息素的挥发蚁群在某个节点根据其迁移概率选择下一个需要选择的节点,并在走过的路径上留下信息素。为了防止随着迭代次数增加,路径上的信息素浓度过多,遮盖掉路径上的启发信息,需要在迭代过程中对路径上的信息素进行一定的更新,更新策略为：ij=(1-)ij+ij(t)(3)式中：是信息素挥发系数,(1-)是信息素的残留系数,如果值过小,会导致路径上信息素残留过多,无法有效区别最短路径和较长路径之间的差距,如果该值过大,在无效路径被排除的同时有可能将有效路径上的信息素也大幅度地消除,增加了算法所需要的时间。是该条路径上信息素的增量,其值为：(4)式中Q为蚁群算法的信息素强度系数
11、。2 基于角度参数的双向蚁群算法蚁群算法存在着容易陷入局部最优解、迭代速度慢以及搜索不到最优解等一系列问题,同时在解决静态环境的机器人路径规划中并没有考虑到机器人转动的问题。因此,本文在蚁群算法的基础上提出改进算法用于解决机器人路径规划的问题。本文算法将蚁群的出发位置进行改变以增大蚂蚁的搜索空间来解决蚁群算法初期搜索盲目以及搜索精度不足等问题,使算法在地图中获取更加多样化的解集合,提高了获得全局最优解的概率。同时对蚁群的信息素更新规则进行了改进,增加走过较短路径的蚂蚁的信息素对下轮迭代的作用以解决蚁群算法容易陷入局部最优解无法跳出。提出了角度参数并将其加入到蚂蚁转移概率中,使其能够在蚁群算法的
12、寻路过程中通过角度参数对蚂蚁起到引导作用,让蚂蚁在分叉路口能够更容易的找到距离目标节点较近的路径提高搜索精度,同时能够减少机器人在路径规划中转过的角度总和,从而减小机器人在转弯时所花费的时间。算法伪代码如表1所示,算法流程图如图1所示。图1 栅格地图Fig.1 Raster map表1 基于角度参数的双向蚁群算法伪代码Table 1 Pseudocode of bidirectional ant colony algorithm based on angle parameters表2 信息素奖励系数算法性能影响Table 2 Pheromone reward coefficient algor
13、ithm performance impact2.1 双向蚁群算法传统的蚁群算法由于每次进行寻路的蚂蚁都是从固定的起点向终点进行搜索,会导致在算法初期蚂蚁的搜索比较盲目。且在算法的初期,蚂蚁总是在起点附近进行寻找,而距离起点较远的节点却很少有蚂蚁到达,这种情况导致蚁群算法解的多样性较差,且降低了蚁群算法的效率。文献11中采用类似的思想来改进蚂蚁的起始位置,但与本文不同的是,文献11将蚂蚁按照编号不同分别放在起点/终点上,再让其向终点/起点进行路径搜索。虽然收敛速度有所降低,但在某些地图中,该算法仍容易使蚁群陷入局部最优而导致其无法获取全局最优解。针对传统蚁群算法搜索精度不足的问题,本文提出的改
14、进算法对蚂蚁的起始位置进行改进,首先将之前的起点和终点设置为目标点1和目标点2,再将蚂蚁放在栅格地图中的一系列节点所组成的起点集合上,使蚂蚁在起点集合中的不同节点上分别向目标点1或目标点2进行搜索。因此,起始位置的改进不仅增加解的多样性以提高找到最优解的概率,而且还能使每只蚂蚁只搜索半张地图就可以搜索到自己对应的“目的地”,从而缩短蚁群算法的整体时间。起点集合的选择依据如图1所示,在该栅格地图中,机器人若想从起点到达终点,其可行路线只有包含节点2的A路线和包含节点1的B路线,即不存在一条从起点到终点的路径能够既不包括节点1,也不包括和节点1位于同一行的节点2。同理,大规模的地图上,也不会出现一
15、条从起点到终点的路径能够不包含起点到终点间任意一行或一列中的所有节点。因此在算法中我们只需要将一行或者一列的所有可行节点加入一个集合中,并让蚂蚁从该集合中的点出发向着自己所属的目标节点去寻路,就可以在一次迭代中寻找到从多个起始节点出发的路径,让蚂蚁能在迭代初期就走过一些在蚁群算法中不被考虑的节点,增加解的多样性,从而提高算法的搜索精度和搜索效率。基于上述起点选择理论,本文所使用的获得起点集合的方法为：对该栅格地图的行和列进行遍历,选择行或列中可行节点最少的一行或一列,将其加入初始节点集合中,在算法的过程中,每只蚂蚁根据自己的编号在起点集合中寻找自己所属的起点,并根据编号寻找自己对应目的地是初始
16、起点还是初始终点。如图2所示,在进行遍历之后,发现该列是地图中所存在的可行节点最少的一列,因此将该列中的可行节点作为蚂蚁的初始节点结合,开始寻路时,将2只蚂蚁作为蚂蚁1和蚂蚁2放在某一相同起点并开始向各自对应的终点进行路径规划。图2 起点集合选择及蚂蚁行走路线Fig.2 Starting point set selection and ant walking route算法将蚁群需要搜索的地图分为两部分,每只蚂蚁只需要在各自的搜索范围进行搜索。因此,地图两侧的信息素互不干涉,每只蚂蚁只需要维护自己对应搜索范围的信息素矩阵即可。该起点位置改进优势如下：1)将原本较大的地图分割为2部分较小的地图,使蚂蚁能够更容易搜索到最优解;2)蚂蚁能够
