基于趋化行为的改进蚁群算法及路径规划应用*

于红斌，张志军，苏 沛

（1．河南师范大学计算机与信息工程学院，新乡453007；2．河南省高校“计算智能与数据挖掘”工程技术研究中心，新乡453007）

基于趋化行为的改进蚁群算法及路径规划应用*

于红斌1，2，张志军1，苏 沛1

（1．河南师范大学计算机与信息工程学院，新乡453007；2．河南省高校“计算智能与数据挖掘”工程技术研究中心，新乡453007）

针对蚁群算法个体的薄弱性，提出了一种基于细菌趋化的集成算法。算法中蚂蚁个体借助细菌的趋向性不仅弥补了自身觅食的盲目性，也使蚂蚁个体具备了障碍检测预警能力，从而提高了整个蚁群的路径规划效率。另外，通过设置叛逆蚂蚁，保障了蚁群路径选择的多样性，提高了路径规划效果。实验表明，算法能在多障碍物环境下有效地解决机器人路径规划问题。

趋化行为；蚁群算法；路径规划；多障碍物，障碍检测；叛逆蚂蚁

1 引 言

路径规划不仅是移动机器人研究领域的热点问题，也是基本问题。在特定环境下，依据指定准则为移动机器人找到一条安全有效的路径是解决该问题的关键。近年来，相关学者为此进行了大量研究［1－8］，其中仿生智能算法由于处理复杂环境信息的优越性而受到了极大关注。针对蚂蚁算法的特点，提出一种改进的蚁群算法，借鉴细菌在觅食过程中的趋化行为［10］改进蚂蚁的迁移概率函数，使其具有自适应能力，提高蚂蚁群体路径规划的效率；引入叛逆蚂蚁策略，增加蚁群路径选择多样性，避免局部最优路径，提高路径规划的效果。

2 相关概念

2．1 细菌趋化反应及运动机制

动力细菌会本能的对化学物质的刺激表现出趋向性［2］。在无化学刺激物或正反刺激物浓度相当的条件下，细菌会先直线游动一段距离，然后翻滚一次改变运动方向，即以游动、翻滚交替变换的方式体现出其对运动方向的随机选择性。而在化学吸引剂作用下，细菌不再出现翻滚行为，而是直线游动到高浓度吸引剂的方向，表现出其正趋化性；遇到驱斥剂时，细菌立即产生翻滚运动并沿其浓度梯度递减方向游动以避开刺激源，表现负趋化性［9］。细菌这种趋利避害的行为与蚁群觅食活动不谋而合，因此可以利用细菌的这一特点对蚁群仅凭信息素迁移的单一机制进行优化，以提高蚁群向目标逼近的速度，从而保证算法的收敛性。

其中，F由细菌g所处环境中的化学物质决定。

2．2 蚁群信息素优化函数

蚁群算法中，若t时刻蚂蚁a位于地图坐标点P（x，y），其信息素由决定，则信息素的更新多数依据当前迭代中的最优路径，即：

3 改进的蚁群算法

改进的蚁群算法借鉴细菌的趋化能力，在保证群体特征前提下，追加蚂蚁个体的判断能力，使得信息素更新更为合理。

3．1 蚂蚁迁移点选择

将细菌植入蚂蚁进行基因改良，则有：

此时，细菌g位于蚂蚁a体内，F′为蚂蚁移动向量，由蚂蚁群体的信息素分布和蚂蚁自身的趋化策略共同决定。它与蚂蚁当前运动方向的夹角θ计算如下：

α、β分别表示群体和个体的控制权重。θτ为由信息素决定的蚂蚁移动转向角度。θF由障碍物和目标共同构成，对随机移动概率函数修正。

当蚁群中所有蚂蚁到达目标点后，选择当前最优路径，按式（2）更新信息素。这种改进不仅体现了蚂蚁群体特性，同时增强了蚂蚁个体障碍检测预警机制，保证了蚁群路径规划的实现。

3．2 叛逆蚂蚁策略

在信息素的引导下，蚂蚁移动的随机性被限制，路径节点的选择将更加单一，这种正反馈机制导致大量蚂蚁集中到某条特定路径上。然而该路径不一定是最优路径，从而使算法陷入局部最优。为了防止这种误导，引入叛逆蚂蚁。算法迭代过程中，根据蚁群规模设定某些蚂蚁为叛逆蚂蚁，当该蚂蚁发现某点某个方向上信息素特别集中时，抛弃该点，随即选择其他方向点移动。叛逆蚂蚁保证了路径的多样性，避免了局部最优路径，实现了算法收敛。

4 路径规划应用

4．1 蚂蚁机器人移动方向选取

变异蚂蚁在极小范围内可以感知周围环境，其转向具有随机性。而机器人可以通过自身高效传感器来感知并评价所处环境，其转向更有方向性，因此转向可以机器人为中心划分。假设机器人每次转角为π／4的倍数，逆时针为正方向，则转向示意图如图1所示。

图1 转向示意图

其中，θ表示蚂蚁机器人的转向角度，其值由式（4）确定。

（1）θτ的确定

因为蚂蚁机器人转向有8个，假设当前8个方向上的信息素含量为：

（2）θF的确定

若F为障碍物和目标共同决定的势场：

（6）式中：ω1、ω2表示蚂蚁机器人趋向目标和避障的权重。生物实验证实蚂蚁危险信号的感知能力很强，路径选择的安全性尤为重要，所以ω2会比ω1大很多。θg、θ0i为蚂蚁当前位置与目标点或障碍物点的夹角，（xg，yg）为目标点的坐标，（x0i，y0i）为第i个障碍物的中心点坐标，Fg为目标点对蚂蚁机器人的吸引力，保障了蚂蚁机器人的趋向性运动，F0为所有障碍物对蚂蚁机器人的排斥力之和，体现蚂蚁路径选择的安全性。δi为第i个障碍物的作用半径。则F与当前蚂蚁机器人的运动方向夹角即为θF。

4．2 路径规划实现步骤

（1）初始化。布置地图。设定路径的起点（xs，ys）和目标点（x0，y0），设置每一个障碍物的中心点（x0i，y0i）和作用半径δ。假定机器人的步长stepsize＝1，则障碍物作用半径可以被简化为机器人步长的整数倍。同时设定α、β、ω1、ω2的值。

（2）根据地图规模，确定蚂蚁种群规模m。初始时所有蚂蚁都位于起点，此时没有群体信息，各方向携带信息素均为初始值Q，于是在随机选择某一移动方向后，根据蚂蚁机器人的趋化能力对方向进行调整。当所有蚂蚁都到达目标点后，计算每只蚂蚁的路径长度，根据式（2）修改相应节点的信息素。

（3）将所有蚂蚁重新置于起始点，由式（4）决定下一次的移动方向，（5）式决定蚂蚁机器人的移动位置。另外，为保证路径的多样性，避免由于信息素过度集中而导致的算法不收敛，将种群m／5的蚂蚁设定为叛逆蚂蚁，这些蚂蚁机器人在选择下一移动方向时，（4）式中θτ将在去除S最大值的基础上计算。当所有蚂蚁都到达目标点后，计算每只蚂蚁的路径长度，根据最短路径按式（2）修改相应节点的信息素。若设定迭代没有完成，则重复本步骤。否则转（4）。

（4）算法结束后，计算当前最短路径，该路径即为最优路径。

5 仿真实验

5．1 实验参数设置

实验用Matlab编程，地图规模为100*100，蚂蚁机器人起点位于坐标（0，0），终点定为（100，100），初始障碍物如表1所示。设定α＝0．7、β＝0．3，以保证蚁群的群体优势，同时体现蚂蚁个体的趋化能力。为了保证路径的安全性，给定ω1＝0．2，ω2＝0．8，使得机器人避障能力高于对目标的趋向能力。蚂蚁种群规模m＝10，信息素初始值Q＝1，信息素消逝率初值ρ＝0．3，其值随着迭代次数递增，算法结束时由于每次实验迭代次数的不同略有差异，其平均值为0．6。10次实验中最优路径长度为151．04cm，图2为实验结果。

图2 路径规划结果

表1 障碍物信息

5．2 实验对比

根据文献［10］提供的数据，与其中各种算法在同样实验环境下进行对比实验，如表2所示。从表中可以看出，改进算法路径虽然不是最短的，但相对比较合理安全，因此算法还是可以信赖的。

表2 方法对比

6 结束语

针对蚁群算法特点，将细菌的趋化能力引入到蚂蚁个体中，弥补了以往蚂蚁算法只考虑群体特性的不足，不仅避免了蚂蚁个体觅食过程中的随机性，使得单个蚂蚁觅食和避障的能力极大改善，同时也为其他蚂蚁提前躲避障碍物给出了指示，使得蚂蚁个体具备了障碍检测预警能力，从而提高了整个蚁群的路径规划效率。而叛逆蚂蚁的加入，保障了蚁群路径选择的多样性，提高了路径规划效果。实验表明，在多障碍物环境中，该算法能有效地规划出合理路径。今后，在算法中参数的选择上应进行重点研究分析，避免经验选择的随机性。

［1］ Ramekin H E，Smith R L．Simulated Annealing for ConstrainedGlobalOptimization［J］．JofGlobal Optimization，1994，5（2）：101－124．

［2］ Chen L N，Aihara K，Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos［J］．Neural Networks，1995，8（6）：915－930．

［3］ 覃柯，孙茂相，孙昌志．动态环境下的基于改进人工势场的机器人运动规划［J］．沈阳工业大学学报，2003（5）：568－570．QIN Ke，SUN Mao－xiang，SUN Chang－zhi．Motion robot planning in dynamic environment based on improved artificial potential field method［J］．Journal of Shenyang University of Technology，2003（5）：568－570．

［4］ J Tu，S Yang．Genetic Algorithm Based Path Planning for a Mobile Robot［C］．／／Taiwan：Proceeding of IEEE Intelligent Conference on Robotics and Automation，2003：L1221－1226．

［5］ 张颖，吴成东，原宝龙．机器人路径规划方法综述［J］．控制工程，2003（5）：152－155．ZHANG Ying，WU Cheng－dong，YUAN Bao－long．Progress on Path Planning Research for Robot［J］．Control Engineering of China，2003（5）：152－155．

［6］ 杜宗宗，刘国栋．基于遗传模拟退火算法的移动机器人路径规划［J］．计算机仿真，2009，26（2）：118－121．DU Zong－zong，LIU Guo－dong．Path planning of Mobile Robot Based on Genetically Simulated Annealing Algorithm［J］．Computer Simulation，2009，26（2）：118－121．

［7］ 朱大奇，颜明重．移动机器人路径规划技术综述［J］．控制与决策，2010，25（7）：961－967．ZHU Da－qi，YAN Ming－zhong．Survey on technology of mobile robot path planning［J］．Control and Decision，2010，25（7）：961－967．

［8］ 周雅兰．细菌觅食优化算法的研究与应用［J］．计算机工程与应用，2010，46（20）：16－21．ZHOU Ya－lan．Research and application on bacteria foraging optimization algorithm［J］．Computer Engineering and Applications，2010，46（20）：16－21．

［9］ 李燕，牟伯中．细菌趋化性研究进展［J］．应用与环境生物学报，2006，12（1）：135－139．LI Yan，MU Bo－zhong．Progress chemotaxis of Bacteria［J］．ChineseJournalofApplied＆Environmental Biology，2006，12（1）：135－139．

［10］ 蒲兴成，赵红全，张毅．细菌趋化行为的移动机器人路径规划方法［J］．智能系统学报，2014，9（1）：1－7．PU Xingcheng，ZHAO Hongquan，ZHANG Yi．Mobile robot path planning research based on bacterial chemotaxis［J］．CAAI Transactions on Intelligent Systems，2014，9（1）：1－7．

An Improved Ant Colony Algorithm Based on Chemotaxis and Applications in Path Planning

Yu Hongbin1，2，Zhang Zhijun1，Su Pei1
（1．College of Computer and Information Engineering，Henan Normal University，Xinxiang 453007，China；2．Engineering Technology Research Center for Computing Intelligence＆Data Mining，Henan Province，Xinxiang 453007，China）

In order to solve the individual weakness of ant colony algorithm，an integrated algorithm is proposed based on bacterial chemotaxis．This improvement，combining tendency of bacteria，not only makes up the blindness for foraging itself，also makes the ant individuals possess the ability of obstacle detection warning，so as to improve the efficiency of path planning of the whole ant colony．In addition，by setting the rebellious ants，the diversity of the ant colony routing is guaranteed and the effect of the path planning is improved．The experimental results show that the algorithm can effectively solve the problem of robot path planning in many obstacles environment．

Chemotactic behavior；Ant colony algorithm；Path planning；Many obstacles；Obstacle detection；Rebellious ants

10．3969／j．issn．1002－2279．2015．04．012

TP18

A

1002－2279（2015）04－0045－04

河南省教育厅科学技术重点研究项目（14A520005）；河南师范大学青年科学基金资助项目（2013QK19）

于红斌（1979－），女，硕士研究生，讲师，主研方向：机器学习、智能算法。

2014－12－25