论文部分内容阅读
摘 要：本文在传统蚁群算法的基础上进行了相应的改善。通过改进转移概率、信息素更新策略以及利用多步长策略进行二次路径规划。在转移概率中增加权重系数，降低蚂蚁陷入盲目搜索的可能，减少了蚂蚁死锁的数量;信息素更新原则，自适应调整提高搜索能力，降低局部收敛性，提高全局收敛性和机器人寻找目标点的工作效率;通过利用多步长策略进行二次路径规划，求解路径长度的最优解不仅降低了机器人的能耗，也降低了机器人的劳损，节约成本。实验结果显示，本文提出的算法全局搜索能力较高，收敛速度较快，能够快速的找到最优路径，可以有效提高机器人工作的效率，验证了本文算法的适用性和有效性。
关键词：蚁群算法;全局收敛;移动机器人;信息素
引言
蚁群算法是由Dorigo.M等人提出的一种新型进化的算法，在路径规划的问题上具有解决问题的明显优势[1]。但是蚁群算法也存在易陷入局部最优解和死锁等问题，为此很多学者做出了大量改进工作，比如动态化搜索算子[2]，有效提高解的质量和收敛速度;设定信息素阈值[3]，防止信息素过多或者过少而使算法收敛速度慢或者过早收敛;最大最小蚂蚁系统[3]，只在每次迭代的最优路径上强化信息素浓度，减少其他路径对蚂蚁寻找路径的影响。蚁群算法还可以与其他算法相嵌合，比如：文献[5]将人工势场产生的力与蚁群的信息素相结合，使信息素扩大到远离障碍区域的地方，提高了机器人搜索范围和速度;文献[6]将遗传算法和蚁群算法相结合，把每一次迭代完成后所产生的路径作为基础，通过不断选择的交叉不同来获得本次迭代的最佳路径。本文做出的改进具体有：1）改进状态转移概率公式，减少蚂蚁死锁的数量，进一步提高收敛速度;2）改进信息素更新策略，自适应调节信息素的挥发因子，克服蚂蚁在寻优过程中陷入局部收敛等问题;3）进行二次路径规划，优化路径长度和轉弯次数降低能耗，提高移动机器人适应性和运转效率。
1 蚁群算法核心思想
1.1栅格地图建模
栅格法是路径规划常用的模型，其中利用每个栅格的取值来表示障碍物和可移动区域，空白部分用0表示，为自由栅格，即移动机器人可以移动的区域，阴影部分用1表示，为障碍物栅格，即移动机器人不可移动的区域[7]。本文选用栅格地图建模，将栅格地图的左下角视为坐标原点，将栅格最下端的水平方向视为X轴，将栅格最左端的垂直方向视为Y轴，构建出直角坐标系，在本文中小于栅格面积1/2的视为自由栅格，大于栅格面积1/2的视为障碍物栅格。另外，本文假设每个栅格为边长为1cm的正方形。如图1所示。
2 改进蚁群算法
2.1 状态转移概率公式的改进
蚁群在路径搜索初期无法避免的会产生大量交叉路径，另外由于算法禁忌表的限制，蚂蚁很容易陷入死锁状态，最终导致“迷失”，大量蚂蚁停滞不前[8]。如图2所示。
蚂蚁k 从当前位置i 移动到下一个位置j 受到两个指标的影响：概率选择和信息素的更新。本文在状态转移概率公式中引入加权因子T（T∈（0，1）） ，提高算法的收敛速度。改进后的公式如下：
式中：τij 为位置i 到位置j 的信息素浓度;α 和β 分别是τij（t） 和ηij 的权重系数;allowk 为蚂蚁下一步尚未到达节点的集合。ηij 代表机器人在位置i 到位置j 的启发式信息，它是当前位置到目标位置的倒数：
2.2信息素更新策略
在每一次迭代完成后，按照式（3）更新到达目标点的蚂蚁所经路径的信息素，忽略掉死锁的蚂蚁，避免信息素盲目更新导致后续蚂蚁迷失，然后按照规则对信息素进行全局性指导更新，按照式（4）强化最优蚂蚁所经路径上的信息素浓度，并且设置信息素浓度的阈值，即
通过自适应调整信息素挥发因子ρ 来提高算法的全局收敛性，如果本文蚁群算法在连续n次迭代内求得最优解都没有发生变化，为防止陷入局部收敛，需要对ρ按照式（5）做自适应调整，ρmin 为ρ 的最小值，μ（μ∈（0，1）） 为信息素挥发系数，并且如果连续n次迭代求得的最优解都相同，并且小于历史最优解，那么全局信息素按照式（4）进行信息素更新。
2.3通过多步长策略进行二次路径规划
目前国内外学者针对移动机器人步长选择主要为单步长策略，这种单步长搜索方式会使移动机器人搜索到的路径过长，时间成本增加，本文算法选择多步长策略，当移动机器人采用多步长二次路径规划策略时，先通过本文的改进蚁群算法搜索出移动机器人最优单步长路径，如图3中的虚线所示，其中将虚线路径作为二次路径规划的参考，依次把当前节点与下一个节点相连，同时判断移动机器人是否与障碍物相撞，如果没有碰撞，则继续往下一个节点转移，直至撞到障碍物，那么当前节点与此节点的上一个节点连心为最佳路径，如图3中实线所示，两条路径的对比结果很明显，多步长选择策略具有明显的优势，缩短了移动机器人的路径长度、转弯次数以及降低了时间成本。
3 算法仿真对比
在同一栅格地图环境下，图4所示为本文改进算法的情况下移动机器人的路径规划轨迹，可以看出移动机器人的路径长度更短，转弯次数更少。图5所示为文献[4]的改进蚁群算法的移动机器人的轨迹，可以看出在同一栅格地图模型下，出现了陷入局部收敛的情况，转弯次数增多，从而增加了移动机器人的能源消耗。图6是传统蚁群算法，很容易看出虽然移动机器人可以到达终点，但是路径长度明显增长，转弯次数明显增多，这样不仅增加了移动机器人的能耗也增加了机器人的劳损，相比较而言成本较大，不适合现实场景的应用和收益。图7 是本文算法和文献[4]的收敛曲线和最短路径长度，通过本文算法的优化，移动机器人的收敛次数降到了13次就可达到稳定，而文献[4]的算法需要22次才能达到稳定，实验结果显示本文的算法具有较高的适用性和稳定性。在栅格地图中，文献[4]的算法的结果显示最短路径的长度是41.796，而本文的算法的结果显示最优路径的长度是36.382，提高了12.9%;文献[4]的算法的迭代次数是22，而本文算法的迭代次数是13，减少了40%。本文算法根据解的分布情况，自适应的进行信息素浓度的更新，动态强化最优路径上的信息素强度，并且利用多步长策略进行二次规划，因此在同一个栅格地图环境下，相对于文献[4]的算法，本文算法大大提高了收敛速度以及缩短了路径长度，使本文算法收敛速度快并且达到全局性最优，验证了本文算法的有效性和优越性，两种算法比较如表1所示。 4 结论
针对传统蚁群算法在复杂路径规划中的种种不足，本文提出一种改进的蚁群优化算法。该算法利用起始位置点的信息，增加权重因子，从而改进转移概率公式，用小于1对解空间更全面的搜索，有效筛选死锁的蚂蚁，提高了蚂蚁的搜索能力和速度;信息素的更新策略，提高了蚂蚁全局性的指导搜索能力;利用多步长策略进行二次路径规划，明显减少了节点的数量，节省了算法运行时间，有效的降低了移动机器人的损耗和能耗，降低成本。实验结果表明，本文算法具有更高的稳定性和收敛性。
参考文献：
[1]DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1） ： 53-66.
[2]游曉明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（03）：552-556.
[3]姚艳.一种最大最小蚂蚁系统的改进算法[J].数学的实践与认识，2014，44（15）：242-247.
[4]杨萍，赵珍，郑海霞.基于改进蚁群算法的移动机器人全局路径规划方法研究[J].机械制造与自动
[5]王晓燕，杨乐，张宇，等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策，2018，33（10）：1775-1781.
[6]汪杰君，刘江宽，黄喜军，等.基于混合遗传蚁群算法的数字微流控芯片测试路径规划[J].电子测量与仪器学报，2017，31（08）：1183-1191.
[7]曲小康，芮小平，韩莹，等.栅格成本距离计算的改进蚁群算法[J].地球信息科学学报，2016，18（08）：1052-1059.
[8]夏小云，周育人.蚁群优化算法的理论研究进展[J].智能系统学报，2016，11（01）：27-36.
基金项目：山东省科学院院地产学研协同创新基金（2018XXY-19、2019-CXY12）
作者简介：刘兆丽（1992），研究生：研究方向：物联网工程
*通讯作者：朱运海（1974），研究员;研究方向：机器人控制决策;
*通讯作者：刘成业（1979），助理研究员;研究方向：移动机器人;
（齐鲁工业大学（山东省科学院）自动化研究所 济南 250353）
关键词：蚁群算法;全局收敛;移动机器人;信息素
引言
蚁群算法是由Dorigo.M等人提出的一种新型进化的算法，在路径规划的问题上具有解决问题的明显优势[1]。但是蚁群算法也存在易陷入局部最优解和死锁等问题，为此很多学者做出了大量改进工作，比如动态化搜索算子[2]，有效提高解的质量和收敛速度;设定信息素阈值[3]，防止信息素过多或者过少而使算法收敛速度慢或者过早收敛;最大最小蚂蚁系统[3]，只在每次迭代的最优路径上强化信息素浓度，减少其他路径对蚂蚁寻找路径的影响。蚁群算法还可以与其他算法相嵌合，比如：文献[5]将人工势场产生的力与蚁群的信息素相结合，使信息素扩大到远离障碍区域的地方，提高了机器人搜索范围和速度;文献[6]将遗传算法和蚁群算法相结合，把每一次迭代完成后所产生的路径作为基础，通过不断选择的交叉不同来获得本次迭代的最佳路径。本文做出的改进具体有：1）改进状态转移概率公式，减少蚂蚁死锁的数量，进一步提高收敛速度;2）改进信息素更新策略，自适应调节信息素的挥发因子，克服蚂蚁在寻优过程中陷入局部收敛等问题;3）进行二次路径规划，优化路径长度和轉弯次数降低能耗，提高移动机器人适应性和运转效率。
1 蚁群算法核心思想
1.1栅格地图建模
栅格法是路径规划常用的模型，其中利用每个栅格的取值来表示障碍物和可移动区域，空白部分用0表示，为自由栅格，即移动机器人可以移动的区域，阴影部分用1表示，为障碍物栅格，即移动机器人不可移动的区域[7]。本文选用栅格地图建模，将栅格地图的左下角视为坐标原点，将栅格最下端的水平方向视为X轴，将栅格最左端的垂直方向视为Y轴，构建出直角坐标系，在本文中小于栅格面积1/2的视为自由栅格，大于栅格面积1/2的视为障碍物栅格。另外，本文假设每个栅格为边长为1cm的正方形。如图1所示。
2 改进蚁群算法
2.1 状态转移概率公式的改进
蚁群在路径搜索初期无法避免的会产生大量交叉路径，另外由于算法禁忌表的限制，蚂蚁很容易陷入死锁状态，最终导致“迷失”，大量蚂蚁停滞不前[8]。如图2所示。
蚂蚁k 从当前位置i 移动到下一个位置j 受到两个指标的影响：概率选择和信息素的更新。本文在状态转移概率公式中引入加权因子T（T∈（0，1）） ，提高算法的收敛速度。改进后的公式如下：
式中：τij 为位置i 到位置j 的信息素浓度;α 和β 分别是τij（t） 和ηij 的权重系数;allowk 为蚂蚁下一步尚未到达节点的集合。ηij 代表机器人在位置i 到位置j 的启发式信息，它是当前位置到目标位置的倒数：
2.2信息素更新策略
在每一次迭代完成后，按照式（3）更新到达目标点的蚂蚁所经路径的信息素，忽略掉死锁的蚂蚁，避免信息素盲目更新导致后续蚂蚁迷失，然后按照规则对信息素进行全局性指导更新，按照式（4）强化最优蚂蚁所经路径上的信息素浓度，并且设置信息素浓度的阈值，即
通过自适应调整信息素挥发因子ρ 来提高算法的全局收敛性，如果本文蚁群算法在连续n次迭代内求得最优解都没有发生变化，为防止陷入局部收敛，需要对ρ按照式（5）做自适应调整，ρmin 为ρ 的最小值，μ（μ∈（0，1）） 为信息素挥发系数，并且如果连续n次迭代求得的最优解都相同，并且小于历史最优解，那么全局信息素按照式（4）进行信息素更新。
2.3通过多步长策略进行二次路径规划
目前国内外学者针对移动机器人步长选择主要为单步长策略，这种单步长搜索方式会使移动机器人搜索到的路径过长，时间成本增加，本文算法选择多步长策略，当移动机器人采用多步长二次路径规划策略时，先通过本文的改进蚁群算法搜索出移动机器人最优单步长路径，如图3中的虚线所示，其中将虚线路径作为二次路径规划的参考，依次把当前节点与下一个节点相连，同时判断移动机器人是否与障碍物相撞，如果没有碰撞，则继续往下一个节点转移，直至撞到障碍物，那么当前节点与此节点的上一个节点连心为最佳路径，如图3中实线所示，两条路径的对比结果很明显，多步长选择策略具有明显的优势，缩短了移动机器人的路径长度、转弯次数以及降低了时间成本。
3 算法仿真对比
在同一栅格地图环境下，图4所示为本文改进算法的情况下移动机器人的路径规划轨迹，可以看出移动机器人的路径长度更短，转弯次数更少。图5所示为文献[4]的改进蚁群算法的移动机器人的轨迹，可以看出在同一栅格地图模型下，出现了陷入局部收敛的情况，转弯次数增多，从而增加了移动机器人的能源消耗。图6是传统蚁群算法，很容易看出虽然移动机器人可以到达终点，但是路径长度明显增长，转弯次数明显增多，这样不仅增加了移动机器人的能耗也增加了机器人的劳损，相比较而言成本较大，不适合现实场景的应用和收益。图7 是本文算法和文献[4]的收敛曲线和最短路径长度，通过本文算法的优化，移动机器人的收敛次数降到了13次就可达到稳定，而文献[4]的算法需要22次才能达到稳定，实验结果显示本文的算法具有较高的适用性和稳定性。在栅格地图中，文献[4]的算法的结果显示最短路径的长度是41.796，而本文的算法的结果显示最优路径的长度是36.382，提高了12.9%;文献[4]的算法的迭代次数是22，而本文算法的迭代次数是13，减少了40%。本文算法根据解的分布情况，自适应的进行信息素浓度的更新，动态强化最优路径上的信息素强度，并且利用多步长策略进行二次规划，因此在同一个栅格地图环境下，相对于文献[4]的算法，本文算法大大提高了收敛速度以及缩短了路径长度，使本文算法收敛速度快并且达到全局性最优，验证了本文算法的有效性和优越性，两种算法比较如表1所示。 4 结论
针对传统蚁群算法在复杂路径规划中的种种不足，本文提出一种改进的蚁群优化算法。该算法利用起始位置点的信息，增加权重因子，从而改进转移概率公式，用小于1对解空间更全面的搜索，有效筛选死锁的蚂蚁，提高了蚂蚁的搜索能力和速度;信息素的更新策略，提高了蚂蚁全局性的指导搜索能力;利用多步长策略进行二次路径规划，明显减少了节点的数量，节省了算法运行时间，有效的降低了移动机器人的损耗和能耗，降低成本。实验结果表明，本文算法具有更高的稳定性和收敛性。
参考文献：
[1]DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1） ： 53-66.
[2]游曉明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（03）：552-556.
[3]姚艳.一种最大最小蚂蚁系统的改进算法[J].数学的实践与认识，2014，44（15）：242-247.
[4]杨萍，赵珍，郑海霞.基于改进蚁群算法的移动机器人全局路径规划方法研究[J].机械制造与自动
[5]王晓燕，杨乐，张宇，等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策，2018，33（10）：1775-1781.
[6]汪杰君，刘江宽，黄喜军，等.基于混合遗传蚁群算法的数字微流控芯片测试路径规划[J].电子测量与仪器学报，2017，31（08）：1183-1191.
[7]曲小康，芮小平，韩莹，等.栅格成本距离计算的改进蚁群算法[J].地球信息科学学报，2016，18（08）：1052-1059.
[8]夏小云，周育人.蚁群优化算法的理论研究进展[J].智能系统学报，2016，11（01）：27-36.
基金项目：山东省科学院院地产学研协同创新基金（2018XXY-19、2019-CXY12）
作者简介：刘兆丽（1992），研究生：研究方向：物联网工程
*通讯作者：朱运海（1974），研究员;研究方向：机器人控制决策;
*通讯作者：刘成业（1979），助理研究员;研究方向：移动机器人;
（齐鲁工业大学（山东省科学院）自动化研究所 济南 250353）