虞馥泽，潘大志,2

(1.西华师范大学 数学与信息学院，四川 南充 637009；2.西华师范大学 计算方法与应用研究所，四川 南充 637009)

0 引 言

路径规划是指在有障碍物的环境中，依据一些标准搜索一条由起点到目标点的安全无碰撞路径。常用路径规划算法大致可分为：传统算法、图形学法、智能仿生学法及其他算法。传统算法有人工势场法[1]、模糊控制算法[2]等。图形学法有C空间法[3]、栅格法[4]等。智能仿生学算法有模拟退火算法[5]、蚁群算法[6]、粒子群算法[7]、遗传算法[8]等。

蚁群算法是Marco Dorigo受蚂蚁觅食启发，于1992年提出的一种仿生算法[9]。为解决蚁群算法在路径规划上的不足，研究人员提出了对它的各种改进。牛龙辉等[10]提出的一种自适应蚁群算法，引入自适应信息素挥发系数，能较好地提高算法收敛速度，但是对于路径平滑性的改进不够；胡春阳等[11]利用头尾搜索机制以及遗传算法对改进后的蚁群算法进行参数优化、引入奖惩因子以及多指标适应度函数，对避免局部最优和收敛速度方面有很大改进；甄然等[12]提出的自适应多态融合蚁群策略，在多态蚁群算法的基础上，引入自适应并行规则和伪随机规则，以提高算法全局寻优能力；赵静等[13]通过改进启发函数和信息素挥发因子以提升其全局搜寻能力；韩颜等[14]是根据粒子群算法最优解调整路径上初始信息素分布，解决蚁群算法中初始信息素缺乏的问题，并且利用简化操作优化路径，优化后的路径距离短且相对平滑，但是对于局部路径平滑性的改进依旧不足。赵开新等[15]提出将遗传算法与蚁群算法相结合，利用遗传算法得到的较优个体设置蚁群的初始信息素，在蚁群算法更新全局最优中，将当前最优与全局最优路径通过交叉操作，更新当前最优，进而更新全局最优。

对静态全局环境下求解路径的规划方法做出改进，提高算法的路径规划能力，是该文的研究目的。通过对两种智能仿生算法进行分析，将遗传算法及蚁群算法融合求解路径规划，利用遗传算法得到的较优路径，来设置蚁群算法所需的初始信息素，引导蚁群算法进一步寻优，最终得到全局最优。

1 环境建模

进行路径规划之前先建立环境地图，该文采用栅格法建立移动机器人的行走环境模型。将机器人处理为质点，行走空间为二维空间，障碍物的大小、位置已知。

如图1以4×4的栅格矩阵为例，map表示栅格环境矩阵，可行区域为白色，即map(i,j)=0；禁行区域为黑色，即map(i,j)=1。从左上角到右下角、从左到右、从上往下对栅格编号，依次为{1,2,…,16}。

图1 栅格矩阵及栅格地图

在环境模型中，每个栅格均与二维空间中的一个坐标(x,y)相对应。如图1所示，栅格1对应坐标(0.5,3.5)、栅格2对应坐标(1.5,3.5)，以此类推，利用式(1)、(2)可将栅格序号转化为对应坐标。

(1)

(2)

其中，N、M分别是栅格环境矩阵的行数、列数，index为栅格序号。

2 遗传算法

2.1 染色体编码

栅格序号形式简单，易于遗传操作，故采用栅格序号对染色体进行编码。P={p1,p2,…,pn}表示一条路径，其中pi(i=1,2,…,n)为路径上第i个节点的栅格序号，p1、pn分别为起止栅格序号。

2.2 适应度函数及选择策略

由于在生物遗传进化过程中，适应度较高的个体遗传到下一代的概率较大，反之则较小。故该文将适应度函数设定为机器人从起点到终点所经历的路径长度的倒数。

采用轮盘赌的方式选择出下一代个体，确保部分非最优的个体进入下一代，有效地避免算法陷入局部最优。

2.3 交叉策略

采用单点交叉，具体过程为：先找出两父代个体中除去起止点外所有相同的点构成集合I，若I非空，则随机选择其中的一个基因，在父代中将其之后的路径进行交叉；反之则不交叉。

例如，父代个体分别为{1,8,11,14,17,19,21,22,26,30}、{1,6,8,9,13,14,18,19,28,30}，I={8,14,19}，产生一个随机正整数R=2，则交换路径节点I(R)后面的路径，得到子代{1,8,11,14,18,19,28,30}和{1,6,8,9,13,14,17,19,21,22,26,30}。

2.4 变异策略

随机选取父代个体中除起点和终点以外的两个不相邻栅格，删去这两个栅格之间的路径，再分别以这两个栅格为起止点，使用路径初始化方法对这两个栅格进行连续化操作。若无法产生新的连续路径，则重新选择两个不相邻栅格执行连续化操作。

例如，对于父代{1,8,11,14,17,19,21,22,26,30}，随机选两个栅格11和22，若连续化操作得到{11,13,16,17,18,21,22}，则得到新个体{1,8,11,13,16,17,18,21,22,26,30}。

3 蚁群算法

蚁群算法是一种仿生算法，在路径规划中的应用主要分为觅食规则、行走规则及信息素规则。觅食规则要求建立禁忌表，规定蚂蚁可行位置；行走规则要求蚂蚁k在当前节点i转移到下一节点j的转移概率由信息素浓度和启发式函数决定，即式(3)决定。

(3)

(4)

其中，dj, end为栅格j距目标栅格的欧氏距离[16]。

3.1 信息素规则

初始信息素产生规则。针对初始信息素匮乏的问题，采用遗传算法寻找初始较优路径集合，按照适应度排序，选取前50%的较优个体，不考虑信息素的挥发，只考虑对走过的路径进行信息素增加，根据式(5)、(6)得到蚁群算法所需的初始信息素。

(5)

(6)

其中，ganum为种群规模，Q为常数，Lm为个体m所走路径长。

信息素更新规则。随着时间的推移，蚂蚁在运动中留下信息素的同时，路径上已存的信息素按照一定比例丢失。蚁群完成一次循环后，各路径上的信息素按式(7)～式(9)更新。

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(7)

(8)

(9)

其中，ρ∈(0,1)为信息素挥发因子，antnum为蚂蚁数，Q为常数，Lk为蚂蚁k所走路径长。

3.2 简化操作

为进一步优化路径及其长度，加入简化操作。图2给出了简化操作示意图。从起点开始遍历，与当前点不相邻的点相连接，得到的路径不经过障碍物，则删去冗余节点并重新计算适应度。

图2 简化路径示意图

4 遗传-蚁群算法设计

利用遗传算法对蚁群算法的信息素进行优化，解决蚁群算法初始信息素缺乏的问题，以此来提高算法精度。具体做法是利用遗传算法得到的较优解，计算得到蚁群算法所需的初始信息素，再用蚁群算法求解最优路径。遗传-蚁群算法流程如图3所示。

图3 遗传-蚁群算法流程

遗传-蚁群算法步骤：

步骤1：初始化遗传算法参数；初始化染色体；保留当前全局最优。

步骤2：选择、交叉、变异操作；更新全局最优。

步骤3：利用截断选择，根据式(5)、(6)更新信息素。

步骤4：若是达到最大迭代次数，或当前全局最优与前若干次全局最优相同，则停止迭代，输出次优解；否则返回步骤2。

步骤5：蚁群参数初始化。

步骤6：利用式(2)移动蚂蚁；计算路径长度；利用式(7)～式(9)更新信息素。

步骤7：更新全局最优，简化路径。

步骤8：若达到最大迭代次数，则输出最优值。否则返回步骤6。

5 仿真结果分析

为验证遗传-蚁群算法的性能，构建地图模型进行仿真对比实验。遗传算法参数：ganum=30、pc=0.8、pm=0.2、Q=1；蚁群算法参数：antnum=50、α=5、β=2.5、Q=1、ρ=0.01。为了增加对比性，分析文中算法的有效性，分别做了以下两组对比实验。

实验一采用文献[11]的30×30栅格地图。由图4知，各个算法均可找到一条由起点抵达终点的路径，基本蚁群算法(如图4(a))、文献[11]算法(如图4(b))、文献[13]算法(如图4(c))及文献[15]算法(如图4(d))的最优路径长分别为56.769 6、44.526 9、42.183 8、45.526 9，文中算法(如图4(e))的最优路径长为41.471 2，效果最好。图4(f)所示为算法每次迭代的最优路径，可知文中算法收敛速度更快且最优路径更短。为验证文中算法的优越性，采用最优路径长、运行若干次的平均最优路径长、最佳迭代次数作为对比算法相关指标，其详细数据如表1所示。综合对比易知，文中算法在提高全局搜索能力以及收敛速度方面有很大改进。

(a)传统蚁群算法

(b)文献[11]算法

(c)文献[13]算法

(d)文献[15]算法

(e)文中算法

(f)迭代图

表1 实验一算法指标

实验二采用40×40栅格地图。各算法找到的最优路径如图6，传统蚁群算路径长为67.497 5，文献[11]算法路径长为64.426 4，文献[13]算法路径长为61.012 2，文献[15]算法路径长为65.598 0，文中算法最优路径长为58.110 5。将算法指标记入表2，同时如图5(f)最优路径迭代可知，在复杂环境下，文中算法相比于其他算法仍具有较好的全局搜索能力。

(a)传统蚁群算法

(b)文献[11]算法

(c)文献[13]算法

(d)文献[15]算法

(e)文中算法

(f)迭代图

表2 实验二算法指标

实验结果表明：提出的遗传-蚁群算法相比于其他算法具有全局搜索能力强且收敛速度快的优点，能快速、准确、高效地实现机器人的路径规划。

6 结束语

针对蚁群算法在静态环境下的机器人路径规划中存在的初始信息素缺乏、易陷入局部最优、搜索效率低等缺陷，提出了将遗传算法和蚁群算法融合的方案。相对于传统蚁群算法按照经验设定初始信息素的方式，该文采取对遗传算法每次迭代得到的种群按照适应度降序排列，选取种群前50%的较优个体，根据初始信息素产生规则得到蚁群算法所需的初始信息素；由于混合算法涉及到算法之间的转换时间问题，文中设计相应的控制策略来控制遗传算法向蚁群算法转换的时机；为使规划路径更平滑且距离更短，对蚁群算法得到的全局最优路径采取简化操作。在栅格环境下对机器人路径规划进行仿真实验，结果表明，该算法具有全局搜索能力强、收敛速度快的优点，在路径规划上是可行且有效的。