刘相旭，张永刚

(安徽理工大学 电气与信息工程学院，安徽 淮南 232001)

0 引言

路径规划技术[1]是指在满足所有约束条件下，在有障碍物的环境中寻找到一条从起点到终点的最优或次优、安全、无碰撞的路径。对于路径规划理论，国内外学者进行了大量的研究，提出了许多算法，如智能仿生算法蚁群算法[2]、粒子群算法[3]、遗传算法[4]等，还有其他类型的算法，如A*算法[5]、RRT算法[6]、人工势场法[7]等。蚁群算法具有较强的鲁棒性和搜索能力，但易陷入局部最优，AJEIL等[8]提出老化蚁群算法，由路径长度决定信息素常量大小，提高算法效率；遗传算法的全局搜索能力较强但收敛较慢，HAO等[9]将种群分成若干个小种群，用种群间的迁移取代了选择机制，同时改进了交叉变异算子，使其适用各种模式的地图。

单一算法存在各种问题，针对其缺点进行优化能有效提高路径搜索效率，但仍无法满足实际需求，于是学者们将单个算法与其它算法相互融合来提高算法的性能，如DAI等[10]将A*算法与蚁群算法启发函数结合提出弯曲抑制算子，加快算法收敛性；SHI等[11]将遗传算法与蚁群算法融合，改进路径评价标准。

针对蚁群算法搜索易陷入局部最优问题，改进启发式函数，自适应调整挥发因子，利用A*算法提出回溯策略优化死锁问题，提高搜索效率；针对遗传算法收敛慢、转弯多问题，改进遗传算法的种群生成方式，提出通信机制交叉，调整适应度函数和交叉变异因子；针对传统融合算法收敛较慢的问题，将优化蚁群算法得出的次优解引入遗传算法优化后的种群中，得到改进的融合算法来优化路径。

1 环境建模

路径地图采用栅格法进行环境建模，将工作环境分为N×N网格。对处于环境中的障碍物进行膨化处理，该栅格只要被障碍物所触及，就视为障碍物。地图栅格以左下角为起点，右上角为终点。自由区域为白色栅格，可自由通行；障碍区域为黑色栅格，无法通行。为便于计算，将智能车辆视为质点，可在自由区域的栅格中心连线之间移动。网格坐标可表示为：

x=mod(i，n)+1

y=fix(i/n)+1

(1)

式中：mod为取余运算，fix为取整函数，i为当前栅格的序列数，n为栅格的行数和列数。

2 改进蚁群和遗传算法

2.1 传统蚁群算法

蚁群算法是模拟自然界蚂蚁利用信息素探索路径的行为，蚂蚁在探索路径时会分泌信息素，较短的路径上留下的信息素浓度较高，蚂蚁会选择信息素浓度较高的路径，该路径上分泌的信息素浓度持续增加，由此形成了正反馈。蚁群算法的两个关键因素为路径选择和信息素更新。蚂蚁根据路径上信息素浓度和距离启发函数来搜索路径，蚂蚁k在t时刻选择下一点的概率

(2)

式中：α、β为信息素和距离启发因子；allowedk为下一步可选择的路径点集合；τij为路径上信息素浓度；ηij为距离启发函数，ηij(t)=1/dij。

蚂蚁在搜索路径时会留下信息素，同时信息素根据挥发因子进行挥发，当所有蚂蚁走完路径时，算法进行迭代由公式(3)～(5)更新路径上的信息素含量：

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

(3)

(4)

(5)

式中：ρ为信息素挥发因子，τij(t)为蚂蚁在本次搜索路径中增加的信息素浓度，Q为信息素常量，Lk为路径的长度。

2.2 改进蚁群算法

针对蚁群算法易陷入局部最优及收敛差的问题进行改进。

2.2.1 改进距离启发函数

传统距离启发函数在搜索中存在搜索效率和寻优能力不足的问题，改进方法是在距离启发函数中加入对目的点的引导作用，增加搜索的目的性，有助于跳出局部最优解。新的公式

(6)

式中：dij为当前点i到下一可行点j的距离，die为当前点i到终点的距离，dje为下一可行点j到终点的距离。

2.2.2 结合A*算法的回溯策略优化死锁问题

蚁群算法在搜索过程中存在蚂蚁走入死胡同的情况即死锁问题，该路径作废且影响算法搜索效率，针对该问题结合A*算法提出回溯策略。

当出现死锁时，由死锁点向前回溯至起点找出所有走过的点并组成集合，由A*算法找出路径点集合中到终点代价最小的点，回溯至代价最小点继续搜索。若蚂蚁在单次路径搜索中触发2次以上回溯策略时，则令路径无效，由下只蚂蚁进行搜索。A*算法公式为：

f(n)=g(n)+h(n)，

(7)

式中：g(n)为实际代价指当前点到下一点的距离，h(n)为估计代价指下一点到终点的距离。

在其他条件相同时针对死锁问题进行无死锁改进，回退策略(回退一格搜索)和融合A*算法的回溯策略进行仿真试验，结果如图1所示，回溯策略能在算法前期保证蚂蚁数量较多，提高搜索效率。

图1 有效蚂蚁数量对比图

2.2.3 调整自适应挥发因子

挥发因子固定导致路径上信息素分布不均，影响蚂蚁寻优效率。改进的自适应改进挥发因子

(8)

式中：T为蚁群算法的总迭代次数，t为算法当前的迭代次数，ρmin为挥发因子最小值。

算法初期，挥发因子较大使得蚂蚁全局搜索能力提高，此时信息素浓度对蚂蚁的引导作用较弱，蚁群可以搜寻更多的路径；但随着迭代次数增加，挥发因子逐渐减小，负反馈减弱，路径上信息素浓度提高，浓度对于蚂蚁的引导作用加强，蚂蚁会集中于浓度较大的路径上。

改进的蚁群算法在搜索能力上有一定的增强，不易陷入局部最优。但引入自适应挥发因子后，挥发因子随着迭代增加由大变小，在算法后期较短路径上的信息素浓度会过大，导致蚂蚁集中于这些路径上，而最短路径可能会出现没有蚂蚁走过的情况，该路径上浓度较低，致使改进的蚁群算法得到了一条次优解。

2.3 传统遗传算法

遗传算法将函数的解(路径)视为种群中的个体，通过随机方式生成初始种群，每一个个体以实数编码，视为基因，用于选择、交叉、变异进行逐步寻优。算法中将单一路径视为个体，路径组成部分视为基因。

种群生成模式为在路径的每一行中随机选择一点，判断是否连续，不连续采用平均值法插入一点，然后依次组成连续路径；选择操作结合适应度函数进行选择，适应度较高个体保留概率越高；交叉模式为在两个个体中选出某一相同位置后交换其余部分；变异操作为随机选择个体中的2点重新组成新的路径片段。

2.4 改进遗传算法

算法生出的初始种群适应度较小，前期搜索效率较低，固定交叉变异因子在中后期影响算法的寻优能力，针对这些问题进行改进。

2.4.1 改进初始种群生成

传统种群生成模式得出的路径过长，前期搜索效率较低，改进后的生成方式为：采用邻接矩阵的形式建立所有自由栅格点的下一步可走点集合，由起始点开始选出下一步可走点集合，分别计算终点坐标减去当前点i坐标的数值n1，可选点集合中的坐标到当前点i坐标的数值n2；结合反余弦函数计算n1、n2的内积与n1、n2范数之积，得出当前点到每一可走点的概率，采用轮盘赌法选出下一步的点，由此重复直至得到完整的路径。

采用改进的初始种群生成可有效降低单一个体(路径)的冗余部分，提高了个体的适应度，加快了算法的收敛。

2.4.2 改进适应度函数

适应度决定个体适应能力的大小，适应度较高的个体更易生存，反之更易淘汰。传统适应度函数仅由路径长度组成，与实际情况不相符，车辆在路径规划中通过转弯躲避障碍物，转弯角度不同，能量损耗也不同。改进的适应度函数集合长度因子、能耗因子、安全因子三部分共同组成：

fit=a×fit1+b×fit2+c×fit3，

(9)

2.4.3 改进交叉模式及交叉变异因子

提出一种基于通信机制的交叉模式：选出两个个体，并找出两个个体中所有相同的部分，建立集合C；从集合C中依次取出连续的两个元素如Ci与Ci-1或Ci与Ci+1，将两点返回原先个体中得出路径片段S1和S2；计算S1和S2的路径片段长度，选择长度片段较短的一方，依次组成一条完整的路径；判断得出的新路径与父辈个体是否相同，若不相同，则另一新路径为父辈适应度较大的一方，若相同，则采用父辈的两个个体。改进的交叉模式能将优秀的路径片段集中于单个个体中，能有效提高算法的收敛速度。

传统算法的交叉与变异概率为固定值，对交叉来说，概率越大，适应度较高的个体被破坏的几率会增加；概率较小，算法的搜索速度会减慢。对变异来说，概率较小，算法跳出局部最优的能力变差；概率较大，可能会破坏较优解。改进后的自适应概率

(10)

(11)

式中：T为总迭代次数，t为当前的迭代次数，Pm为变异因子的最大值。随着迭代次数的增加，Pc由大变小，Pm由小变大。Pc在前期较大易于搜索较优解，在中后期减小使较优解不易被破坏，Pm在前期较小不易破坏较优解，在中后期易于让个体跳出局部最优。

3 融合算法的改进

3.1 加入剪枝优化算子和删除算子

针对遗传初始种群个体出现局部绕路的情况，采用剪枝优化算子来进行优化，步骤如下：在当前路径上初始化一条新路径，设i为个体的起点，并将i放入新路径中；定义j为个体的终点，并判断j是否为i的相邻节点，若不是，则j沿着路径向前回溯一点并继续判定，若是，则令i=j，将新的i放入新路径中，j回到终点重新判定；当i为原路径终点时，优化结束，输出新路径。

融合算法结束后采用删除算子对路径进行优化。针对路径的转折点进行判定，若移去该点后仍为可行路径则进行移除，同时保证新路径的转折点少于原路径。该优化是在保证转折点不增加的同时尽可能优化现有路径。

3.2 算法融合

蚁群优化算法搜索能力得到提升，但自适应挥发因子随着迭代次数增加而减少，在相对较短的路径上信息素积累较多，导致蚂蚁搜索最优路径的概率减少，算法最终得到次优解。传统的蚁群与遗传算法融合方式为：遗传算法得出路径后交由蚁群算法进行初始信息素的铺设，之后进行路径搜索，但算法在遗传阶段的种群多样性下降较快，影响融合算法搜索效率。

针对该问题提出改进融合算法：将蚁群优化算法得出的次优解加入到遗传算法优化后的种群中，形成新种群；新种群的筛选采用精英保留策略(保留适应度前50%的个体)，后续采用通信和传统交叉共同作用的模式、精英保留策略及自适应变异优化种群直至算法结束；最后利用删除算子优化最终解。通过这一过程得到了改进融合算法，改进融合算法流程图如图2所示。其中用于通信交叉的个体为总个体的40%，传统交叉为总个体的60%。

图2 融合算法流程图

4 仿真试验对比

将改进融合算法(ant colony&a* and backtracking genetic fusion algorithm，A*ACO-BGA)与遗传算法(genetic algorithm，GA)、传统融合算法(genetic and ant colony fusion algorithm，GA-ACO)和文献[11]算法(improved ant colony and genetic fusion algorithm，IACO-GA)在MATLAB软件下进行仿真对比，分别在20×20的简单(障碍物占比少)和复杂(障碍物占比多)地图中进行测试，每种地图进行20次仿真试验，取一组结果进行比较。蚁群和遗传算法参数如表1所示。

表1 蚁群与遗传算法参数

4.1 简单环境下仿真对比

4种算法在20×20的简单环境中输出路径如图3所示，遗传算法经16次转弯到达终点，传统混合算法经11次转弯到达终点，IACO-GA算法和改进融合算法路径重合经2次转弯后到达终点，能耗有所降低。

图3 简单地图四种算法路径对比

从图4可看出，4种算法分别在28、19、13和11次迭代后得到长度31.80、30.97、30.97和30.97的最优路径。

图4 简单地图四种算法迭代对比

20次试验结果见表2，IACO-GA算法和改进融合算法搜索到的路径较优，转弯次数较少。与遗传算法和传统混合算法相比，在迭代次数上减少约70%和57%；转弯次数减少约84%和75%。与IACO-GA算法相比转弯次数无明显波动但迭代次数减少36%。改进融合算法在简单地图中对比遗传算法和传统混合算法在收敛速度和能耗上有着一定的优势，对比IACO-GA算法，在得到最优路径的同时，收敛速度有所增加。

表2 简单栅格四种算法迭代数据总结

4.2 复杂环境下仿真对比

在复杂地图中再次进行仿真试验，参数与简单地图相同，路径规划如图5所示。由图5可知遗传算法经16次转弯后到达终点，能耗较高；传统融合算法经9次转弯到达终点；IACO-GA算法经11次转弯到达终点；改进融合算法得到路径相对平滑且转弯次数较少，有8次转弯。

图5 复杂地图四种算法路径对比

从图6可看出，4种算法分别在42、30、11、9次迭代后搜索到最优路径且路径长度分别为34.97、32.38、32.14、31.20。改进算法能搜索到转弯次数较少，路径较优且收敛较快的路径。

20次试验结果见表3，障碍物的增加使得传统算法在寻路过程中可走路线减少，收敛较慢。改进融合算法相较于遗传算法，传统融合算法和IACO-GA算法的迭代次数减少约80%，70%和38%，转弯次数减少约43%、18%和19%。

表3 复杂地图四种算法迭代数据总结

从表2、3可看出，在简单和复杂地图中相较于其余3种算法，改进融合算法在收敛速度上有着一定的优势，且输出路径较优，转弯次数减少，可有效降低能耗，有着更好的路径规划能力。

5 结论

针对传统融合算法存在收敛慢、转弯多的问题提出了一种改进的融合算法，并进行了仿真验证。将优化蚁群算法得出的次优解加入遗传算法优化后的种群中，通过精英策略，通信机制交叉和传统交叉相结合的模式来搜索路径。改进的融合算法解决了传统融合算法转弯次数多、路径不平滑的问题，通过仿真验证可以看出，在简单和复杂地图中改进后的融合算法能搜索到路径更短、能耗更低的路径，对比传统融合算法在收敛速度和搜索效率上有着一定的优势。