基于细菌觅食蚁群算法的无人车路径规划

卢泓宇 肖银宝

摘 要：随着目前人工智能的日渐普及，无线通信、网络传输和传感器技术等得到了长足的发展，人们对机器的自动化智能化要求越来越高。与此同时人们对无人驾驶技术需求越来越高，针对路况及各种可能会出现的异常问题缺少合理高效的路径优化，这使得对路径规划的研究有着重要的意义。对此，本文主要对现有的传统蚁群算法进行研究，同时考虑到当前传统蚁群算法的一些缺点，引用细菌觅食算法进行尝试改进，加深对这两个算法的认识，并进行归纳总结。

关键词：人工智能；路径规划；无人驾驶；蚁群算法；细菌觅食算法

Path Planning of Unmanned Vehicle

Based on Bacteria Forageant Colony Algorithm

Lu Hongyu1 Xiao Yinbao2

1.School of Mechanical and Electrical Engineering and Automation， Foshan University of Science and Technology

GuangdongFoshan 528225;

2.Songming County Bureau of Science，Technology and Industrial Information Technology YunnanKunming 650000

Abstract：With the increasing popularity of artificial intelligence，wireless communication，network transmission and sensor technology have been greatly developed，and people have higher and higher requirements for automation and intelligence of machines.At the same time，the demand for unmanned driving technology is getting higher and higher，and there is a lack of reasonable and efficient route optimization for road conditions and various possible abnormal problems，which makes the research on route planning of great significance.In this regard，this paper mainly studies the existing traditional ant colony algorithm，and at the same time，considering some shortcomings of the current traditional ant colony algorithm，references the bacterial foraging algorithm to try to improve，deepen the understanding of the two algorithms，and make a summary.

Keywords：artificial intelligence；path planning；unmanned driving；ant colony algorithm；bacterial foraging algorithm

1 概述

由于人工智能的迅猛发展，使得无人驱动技术在近几年得到科研工作者的重视。得力于网络传输、传感器技术的发展，路径规划的方案因此更加多样化，因此本文主要通過细菌觅食算法对蚁群算法的改进来提高路径规划的效率。

2 研究方案

蚁群算法是来源于模拟蚂蚁为了生存去寻找所需的补给的行为从中提炼出的一种用来寻求所有路径中最短路径的随机找寻算法。蚂蚁通过某种信息机制在寻找食物的路径上留取信息素，通过不断迭代，获得最短路径。但是随着对蚁群算法的不断研究深入，逐渐发现它的缺陷在不断扩大，由此需要对其进行优化，例如，收敛速度过慢的原因是由于搜索范围的扩大导致陷入了局部环境下的最优路径，此时便需要细菌觅食算法的介入进行改进。细菌觅食算法是通过实现人类肠道中大肠杆菌的吞噬食物的行为的一种仿生类优化算法。由于蚁群算法有较强的鲁棒性，而且相比其他算法，对初始路线要求不高，参数少设置简单，便于用于组合性的优化问题的求解。而细菌觅食算法中的复制操作与趋向操作适合对蚁群算法进行优化，可以提高算法效率，跳出局部最优解，获取全局的搜索能力，使得算法更加精确。

3 传统蚁群算法实现及其缺点

首先是对初始路径的选择。在算法最开始的阶段，将一定数量的蚂蚁随机地放到一些固定数量的城市，与此同时，将各只蚂蚁的记录表tabu的第一个锚点设定为它目前处于的城市。此时便可以得知各路径上的信息素量是相等的，接下来将各只蚂蚁在路径上寻找所残留的信息素量和遗留式信息（就是两城市之间的距离）不存在干扰的情况下选择下一座需要寻觅的城市，直到将所有的城市遍历完成。

pkij=τij（t）α·ηij（t）β∑s∈Jkτis（t）α·ηis（t）β（指数为两个经验系数）

P=两城市信息素浓度α·两城市距离的倒数β总和（去某一个城市的概率）

其次，便是信息素的增量与蒸发：

Tau=（1－r）Tau+Q/L

其中Tau是信息素量，r是蒸发系数，Q是信息素增量，L是两城市之间的距离。

在采用传统蚁群算法解决路径规划问题会有两个缺点：（1）早期由于各个节点之间信息浓度较低，蚁群算法又是一个大空间搜索算法，盲目地搜索必然会导致蚁群在初始阶段产生大量的无效路径，问题规模越大，早期搜索性能越差。（2）传统蚁群算法的后期开发能力有限，非常容易陷入局部最優的情况。

4 对细菌觅食算法的复制操作的引入

4.1 复制操作的引入

蚁群算法求解旅行商问题的方法如下，开始时有m只蚂蚁随机分布，并且保证没有蚂蚁在同一个位置，蚁群需要经历n个城市，然后让蚂蚁开始启动，记录下每个城市之间的距离，通过公式计算出当时城市之间的信息素浓度。然后在此之后再独立选取下一座城市，同时记录下信息素的浓度，在寻求路径期间记录下信息素挥发的状态，在经过所有城市后实时更新直至遍历所有的城市。

在蚁群算法生成解的时间段引入复制操作，而复制操作是指当细菌的生命周期即将结束时，即达到分裂上限，细菌则开始进行繁殖，遵循自然界中优胜劣汰的规则，对那些适应不了环境的细菌进行淘汰，对那些寻找食物能力比较强的细菌进行复制繁衍。而蚁群算法在蚁群寻访完所有城市后的时间点，即第一次寻访完毕后，各只蚂蚁都寻求到了专属自己的对应的路线即无人车行驶的路线。同时各只蚂蚁留下的路线则一一对应当前每个细菌的位置，同时记录下蚂蚁所行进的路径长度，然后我们对所有蚂蚁留下的路径长度进行从长到短的排列，而其中最短的路径即为我们本次所需要的。而细菌觅食中的复制操作此时开始优化，选出其中优良适宜的细菌个体（即路线长度相对短的蚂蚁）对这些进行复制发育，同时对那些劣质的细菌进行淘汰（即路线长度过长的蚂蚁）。通过上述操作我们优化了蚁群算法的收敛速度，以及全局的收敛性。

4.2 复制操作的具体实现

复制操作根据细菌当时得出的适应程度的函数值，从中选出那些较劣等的细菌去继承那些优秀的细菌的位置及步长。同时为了保持菌群的稳定，要让复制后的细菌数量和原始的细菌数量保持一致，同时要记录当前细菌的成长度，建立一个成长度函数来记录。与此同时，我们记录细菌进行的趋向操作次数，还有其中具体的趋向操作、复制操作、迁徙操作后的适应程度的函数数值，而其中得出数值越高的细菌则表明这个细菌的寻找食物的能力更加强大。与此同时将细菌的种群按照成长度进行排序，对其中成长度不错的细菌进行复制和保留，在此期间要保证总体的细菌数量和初始的一致。当蚂蚁寻访完自己所需要的城市后，蚂蚁们都拥有了专属于自己的一条行驶轨迹，这时我们将各只蚂蚁的轨迹逐一对应我们之前留下的优秀细菌。与此同时算出上次更迭的过程中蚂蚁走过的轨迹长度总值即细菌的成长度，在此时通过细菌觅食算法的复制刚进行的操作，对成长度的细菌（即总轨迹相对小的蚂蚁）对其进行复制，同时删除那些成长度小的细菌（即所有轨迹长度比较长的蚂蚁），此时便可以改良蚁群算法的收敛速率，以及对于全局的收敛性。因为细菌觅食算法最初没有对离散性问题有过多的设计，所以在针对此类问题时需要我们对其中的趋向操作进行一些有效的改进优化，对其中翻转的操作进行保留，就是对细菌的位置开始逆转，在经过这个操作后使得总路线长度变小的细菌来替换之前的细菌位置，这样算法就不会陷入局部最优的情况，这样就解决了算法的全局搜索能力了。

5 对细菌觅食算法的趋向的操作的引入

由于蚁群算法是在不断寻求最佳轨迹的进程之中，而算法是依靠蚂蚁留下信息素进行运行的关键，但是如果我们设置下来的一些路线蚂蚁们几乎不会经过，那么那条轨迹上之前的信息素就会逐渐消失，这时我们设置的蚂蚁去往这些路径的概率就会变小，那么这时算法就陷入了局部最优的尴尬情况。而我们为了优化提升这一状况，尽可能去改善这个算法对全局掌控的搜索能力，在此时将细菌觅食算法中的一个操作导入即趋向操作。趋向操作指的是细菌觅食算法模拟肠道中细菌寻找食物的过程中的两个运动翻转和前进。细菌由于觅食的原因它们便往那些营养程度高的地方前进，同时翻转远离那些环境差没有食物的地方。为了更好地优化上面提到的不连续的概率问题，需要对算法中的趋向操作进行一些必要的优化，同时保留其中重要的翻转运动。我们通过概率性地改变细菌的移动的方向就是对细菌目前所处的地点进行反向趋向，在这个操作后那些总路线长度变小的细菌便可以保留，然后去替换原来不够优秀的细菌，这样算法便可以冲出局部最优这个难堪的处境，与此同时全局的搜索能力得到大幅度的提升。

5.1 趋向操作的一些具体细节

趋向操作是指细菌觅食算法在模拟肠道中细菌寻找食物的过程中的所要进行翻转和前进两个基本的动作。因为细菌往往会寻找那些食物多的位置进行前进这个运动，同时在这个时候用翻转运动去远离那些没有食物以及环境差的地方。我们记录细菌在某次趋向操作以及当时的复制操作，还有第一次迁徙操作后的位置，通过公式记录。

5.2 算法的具体过程

第一步：对整个细菌觅食算法的参数进行初始化，将每只蚂蚁当前的地点和细菌一一对应，同时计算城市间的距离矩阵。

第二步：构建解的空间，将一定数量的蚂蚁随机放在固定数量的城市上，根据公式计算出每只蚂蚁去往下一个城市的概率，选择下一个城市，加入轨迹路线记录库中，不间断地重复操作上述过程，直到所有的蚂蚁都回到了自己最开始的位置上再结束。

第三步：计算各只蚂蚁途经的轨迹长度，通过这步找到之前细菌刚开始所处在的位置，记录这些位置点，生成新的表。

第四步：引入细菌觅食算法的复制操作，将所有细菌留下的轨迹长度从长到短地进行排列，同时淘汰那些路线较长的细菌，同时留下路线较短的细菌，对这些细节进行复制，变成两个完全相同的细菌。

第五步：引入细菌觅食算法的趋向操作，即翻转操作，对各个细菌当前所处的方位即蚂蚁所前进的路线进行固定方向的翻转操作。如果在这个翻转操作结束后，我们所需的轨迹长度变短即得到应有的优化，那么这时将目前细菌所处的位置更新改变，同时定点标出为最佳的。

第六步：不停重复第二步到第五步，更新所有的信息素，直到被清空然后再进行新的迭代。

第七步：当算法达到最大的迭代次数时，此时将其停止，并将最优路线以及其长度记录输出。

6 分析总结

本文主要是应用细菌觅食算法对蚁群算法的改进以便更好地适应目前在路径规划方面的需求，同时加入对离散型问题的求解，使得算法能够应付多种情况。

6.1 主要创新点

（1）通过对传统蚁群算法的改进，提高其搜索性能，跳出局部最优，避免搜寻时间过长导致出现其他问题。

（2）优化参数的选择，使得在多种情况下都可以获得最佳的路径，可以更好地适应复杂情况。

（3）结合两种算法，对算法的局限性的补足，提高算法的精确度与效率。

（4）对蚁群算法中的弊端进行了较大的改进，使其更适应目前路径规划问题。

6.2 后续研究方向

虽然对蚁群算法的一些缺陷进行了一定量的优化，但是对于大规模的问题仍然需要更多的实验去进行改进。后面会加大模型的多样性，去提高算法的精确程度。

参考文献：

［1］毛寿祺，杨平，高迪驹，等.基于细菌觅食蚁群算法的无人船路径规划［J］.控制工程，2023：19.

［2］龙洋，苏义鑫，廉城，等.混合细菌觅食算法求解无人艇路径规划问题［J］.华中科技大学学报（自然科学版），2022，50（03）：6873.

［3］胡章芳，冯淳一，罗元.改进粒子群优化算法的移动机器人路径规划［J］.计算机应用研究，2021，38（10）：30893092.

［4］罗丹.机器人路径规划方法分析［J］.电脑编程技巧与维护，2020（10）：125126+147.

［5］賈翠玲，徐明娜，王利利，等.基于混合细菌觅食和蚁群算法的机器人路径规划研究［J］.制造业自动化，2013，35（08）：6569.

［6］李梓远，黄卫华，章政，等.基于层次地图模型的改进蚁群路径规划［J］.组合机床与自动化加工技术，2023（02）：1417.

［7］邱晓磊.基于蚁群算法的网球机器人路径规划算法研究［J］.太原学院学报（自然科学版），2022，40（04）：7278.

［8］杨雷博，周俊.改进蚁群算法下的车间物料配送路径规划研究［J］.制造业自动化，2022，44（11）：128131.

［9］宋宇，张浩，程超.基于改进蚁群算法的物流机器人路径规划［J］.现代制造工程，2022（11）：3540+47.

［10］赵倩楠，李志锟，黄宜庆.优化复式蚁群算法的机器人路径规划研究［J］.安徽工程大学学报，2022，37（05）：5158.

项目：本文受到广东高校重点领域专项新一代信息技术重点领域专项项目（2021ZDZX1019）的技术及经费支持

作者简介：卢泓宇（1996— ），男，汉族，江苏连云港人，硕士研究生在读，专业：人工智能，研究方向：大数据应用；肖银宝（1973— ），男，汉族，云南昆明人，硕士，助理研究员，研究方向：科技管理及信息化。