基于改进烟花算法的路径规划策略研究

朱宇 朱留存 罗俊琦 沙波

（1.扬州大学信息工程学院 江苏省扬州市 225009 2.北部湾大学先端科学技术研究院 广西壮族自治区钦州市 535000）

1 引言

路径规划[1]是指移动机器人或者移动主体在有障碍物的环境中寻找一条从初始地点到达目标地点的无碰撞路径。自移动机器人在20世纪60年代问世开始，作为移动机器人关键性技术[2]之一的路径规划也随之产生。

目前路径规划分为两大种类，一种是全局路径规划[3]，又称为静态路径规划，另一种是局部路径规划，又称为实时动态路径规划。局部路径规划注重的是移动机器人实时避障的性能，根据自身传感器采集到的局部环境进行实时动态路径规划，有非常好的灵活性，但由于缺乏更多的环境信息，所得到的路径一般是局部最优而非全局最优。全局路径规划则需要知道全局环境信息，通过建立环境地图模型，然后在全局地图上使用寻优搜索算法获取全局最优或者较优路径。局部路径规划的代表人工势场法[4]，该算法结构简单，方便实时控制，能节省大量运算时间，但在狭窄通道中会摆动，且目标点存在障碍物时，无法到达目标点。全局路径规划代表有粒子群算法(Particle swarm optimization)[4]，调整参数少，易于实现，收敛速度快，但对于离散优化问题，又容易陷入局部最优。蚁群算法(Ant colony optimization)[5]。模仿蚁群觅食的行为搜索路径，具有较强的鲁棒性和搜索较好解的能力，但容易陷入局部最优解，并且收敛次数较慢。遗传算法[6]，能充分发挥自身优势与其他算法融合，拥有优秀的自组织性和自学习性，实现简单，受外界影响小，但运行速度较慢，搜索效率较低，同样易于陷入最优解。烟花算法（Fireworks Algorithm）[7]，收敛速度快，易于实现，且具有爆发性、多样性和随机性等等，但运算量大导致运行时间稍长。

其中烟花算法由谭营教授等人于2010年发表，是根据烟花在夜空中爆炸的现象而提出的一种新型群智能优化算法，但由于出生较晚，对于求解不同类型的优化问题的能力还并不成熟，因此业界内对烟花算法的研究逐步深入和铺开，针对原始烟花算法的不足，进行了大量的改进，例如张颖[10]通过结合烟花算法和例子群算法优化无线网络拓扑结构，马创涛[11]运用烟花算法改进BP神经网络预测模型。而本文则是针对烟花算法在路径规划上的应用做出优化改进。

2 烟花算法原理

烟花算法[10]模拟烟花在夜空中爆炸的现象，将爆炸的一系列流程转换成数学模型。首先开始爆炸，然后依次利用爆炸算子、变异算子探索空间，再利用映射规则将超出范围的火花拉入范围内，最后应用选择策略选出下一代爆炸的烟花，直到达到终止条件。

2.1 爆炸强度

烟花种群中的每个烟花都会产生相应的爆炸火花种群，适应度值越好的烟花爆炸强度越大，爆炸火花的数量就越多，相反，爆炸强度越小，爆炸火花的数量就越少[11]，爆炸强度公式如下所示。

式中Si为第i 个烟花产生火花的数目，m 为限制火花生成的数目，Ymax为当前适应度最大的值，f(xi)为第i 个个体产生的适应度值，ε 是一个极小的常数，其目的是为了避免公式分母出现0 的情况，N 是指烟花的种群数目。

为了限制烟花产生火花的数目，防止烟花哑火或者产生预料之外爆炸，设置了火花数量的和爆炸范围的限制公式分别如式（2）和式（3）所示。

式（2）是火花数量的限制公式，其中Si是第i 个烟花产生的火花数量，ceil 是四舍五入向上取整的函数，a 和b 都是给定的常数。

式（3）是烟花爆炸范围的限制公式，其中AI为第i 个烟花的爆炸幅度，Ymin为当前最小的适应度值，A 为爆炸最大范围，其他参数同式（1）。

火花的移动规则是在确定的爆炸范围内，进行随机的位移操作，具体如式(4)所示：

2.2 火花变异

随机对烟花的若干个维度进行高斯变异，其公式如下：

其中N(1,1)是服从均值为1，方差为1 的高斯分布的随机数。

2.3 映射规则

不论是在火花变异和产生火花的过程中，注定会碰到越过地图范围的火花，因此设立了映射规则，公式如下：

2.4 下一代种群选择规则

通过欧式距离计算任意2 个烟花之间的距离，并将每一个烟花到其他烟花距离的总和计算出来，如式（7）所示：

其中d(xi,xi)是任意2 个烟花xi和xj之间的欧式距离R(xi)是烟花个体xi到其他烟花个体的距离总和，集合k 表示烟花，变异火花和爆炸火花的总和，是烟花初始种群的3 倍。

进行下一代种群选择时运用的是轮盘赌法的方式，每个个体被选中的概率P(xi)如下：

公式（8）表示的意义是距离其他路径越远的个体越容易被选中成为下一代，这种选择方式是烟花算法种群多样性的主要原因[12]。

3 烟花算法优化

3.1 连接规则优化

最初的烟花算法在连接规则上和遗传算法[13]相似，都是直连的，没有节点选择的环节。因此，本文为烟花算法添加节点连接环节。烟花通过一次爆炸产生n 个烟花，于是xi=(a1,a2,..aend)，其中xi为第i 次烟花爆炸，a1,a2…及aend为第i 次烟花爆炸的火花个数及位置，共计N 个火花。

公式（9）的目的是将火花an-1到an之间的节点通过轮盘赌法连接。其中allow 是火花an-1到an的所有可行节点，D（j,an）为节点j 到第n 个火花的欧式距离，nt是最短路径奖励机制[14]，它的目的是提高选择最短节点的概率，因为火花本身就是随机产生的，通过加强最短节点的连接概率能够大幅度减少火花连接的随机性，更加利于寻找最优路径。最终火花相互之间连接形成一条能够到达终点的路径，如图1所示。

图1：火花连接示意图

3.2 烟花爆炸及变异优化

原烟花算法中，从火花，变异火花以及爆炸火花中选择三分之一进行下一轮迭代，没有被选中的火花则被丢弃，极大的浪费了运算时间和存储空间，这也是烟花算法运行时间较长的原因之一。针对这一缺点，将火花变异和烟花爆炸进行结合：

式中：allow 是第Si个烟花中未进行爆炸的火花的集合，其目是先进行火花爆炸，再对剩下火花选择若干个进行高斯变异，然后统再一进行位移操作。

3.3 路径冗余优化

烟花算法作为自组织系统，通过爆炸产生若干个火花，然后通过节点选择步骤使得每个火花之间相连，由于节点选择方法为轮盘赌法，因此每个火花之间都不可避免存在着冗余节点问题，而冗余节点可分为3 种情况，分别如图2，图3 和图4所示。

图2：节点冗余示意图

图3：节点冗余示意图

图4：节点冗余示意图

通过预连接的方式，在一个火花与另一个火花预连接之后，按照图2、图3、图4 三种冗余情况执行冗余优化步骤，通过将冗余的节点加入禁忌表，重新进行一遍节点选择，以达到预期的结果。但是在前期烟花算法处于探索阶段，需要扩大搜索范围，直到中后期烟花算法才处于收敛迭代状态，为了避免算法过早的陷入收敛状态，因此给予该冗余优化步骤一个激活公式：

式（12）中，K 为总的迭代次数，m 是激活冗余优化方法的迭代次数，迭代的总次数越大，激活该冗余优化方法的时间就越晚。

3.4 种群选择优化

在所有的火花位移操作完成之后，开始进行下一代种群选择，原烟花算法会大概率选择距离其他个体较远的火花作为下一代种群。此种种群选择规则存在以下两个问题：第一，路径之间的距离难以用公式进行计算，第二，种群选择需要先计算每条路径与其他所有路径的距离总和然后再比较，算法运行花销较大。基于上述两种弊端，提出新的种群选择公式如下所示：

式（13）中f(xi)是一条路径的适应度值，K 是爆炸火花与烟花的合计，其目的是大概率选择适应度值较大的个体作为下一代种群，继续保持烟花种群的多样性。

3.5 优化算法的步骤

优化烟花算法原理步骤图如图5所示。

图5：优化烟花算法原理步骤图

步骤一：初始化烟花种群N 和各个参数；

步骤二：通过式（10）和式（11）连接烟花中的火花，并计算其适应度；

步骤三：通过式（1）和式（3）进行每一个烟花的爆炸强度和爆炸幅度的计算；

步骤四：通过式（6）进行火花越界处理并通过式（10）和式（11）计算爆炸和变异的火花的适应度值；

步骤五：通过式（9）将火花相互连接，形成完整的路径并根据式（12）确定是否需要进行1 冗余优化。

步骤六：通过式（13）选择出0.6*N 个数目的火花以及0.4*N个本次最优火花作为下一代种群

步骤七：不断执行步骤二到步骤六，直到满足终止条件为止。

4 仿真实验

4.1 实验环境建模

本文算法使用栅格地图法[16]，将障碍物按比例在栅格地图上建模，其中白色格子为可行区域，黑色格子代表着障碍物，为非可行区域，具体环境和栅格地图节点序号分别如图6 和公式（13）所示。

图6：20*20 栅格地图

公式（14）中D 为每个格子的序号，M 为栅格地图的维度，x和y 分别为栅格地图的横纵坐标。

4.2 实验参数设置

原烟花算法与改进的烟花算法共用参数，其中烟花迭代数目设置为50 次，种群数目为50，变异火花数目为3。

为了验证本论文算法的性能，选取了蚁群算法[17]以及遗传算法[18]作为对比，蚁群算法和遗传算法参数分别如下：蚁群迭代次数为50 次，蚂蚁个数为50，信息素系数α 为1.5，能见度因子β 为6，信息素挥发因子ρ 为0.9，信息素强度Q 为1。遗传算法迭代次数为50 次，种群数500，基因数10，交叉概率0.7，变异概率为0.06。

将原烟花算法，本文改进烟花算法，蚁群算法以及遗传算法在两种不同规模的地图中分别进行10 次仿真，各选取其中最好的一次仿真作为结果。

本文所有算法都是在mtlab2019b，windows10 系统，8G 内存,i5处理器中进行仿真实验的。

第一种仿真环境是在20*20 的栅格地图中进行的，其路线效果图和迭代图分别如图7，图8 以及表1所示。

图7：20*20 栅格地图路线效果图

图8：20*20 迭代曲线图对比

表1：20*20 路径规划数据表

第二种仿真环境对比是在30*30 的栅格地图中进行的，其路线效果图和迭代图分别如图9，图10 以及表2所示。

表2：30*30 路径规划数据对比图

图9：30*30 栅格地图路线效果图

图10：30*30 迭代曲线图对比

4.3 实验数据分析

结合表图7 和图8 以及表1 可以看出在20*20 的栅格地图中，优化过的烟花算法能够取得最优路径，并且优化过得烟花算法取得的最短路径较蚁群算法提升了7.5%，较原烟花算法提升了25%，较遗传算法提升了15.9%。其次优化过得烟花算法收敛次数为21 次，是四个算法中最早收敛的。

从以及图9，图10 以及表2 可以看出，在30*30 的栅格地图中，优化过的烟花算法最短路径长度为50.533，是四个算法中路径最短的，其路径长度较蚁群算法提升了11%，较原烟花算法提升了16.1%，较遗传算法提升了18%，且优化过得烟花算法经过9 次迭代即完成收敛，相较于其他3 个算法的收敛次数，其性能大幅度上升。

从以上两次对比实验中，可以发现原烟花算法虽然没有陷入局部最优解，但其搜索最优路径的性能比蚁群算法略差，其原因有一方面在于原烟花算法最初是寻找数值最优解，而非路径规划方面，所以其路径规划方面的应用时还并不是很成熟。因此，通过对烟花算法的优化，使得优化烟花算法不论是在20*20 的栅格地图中还是30*30 的栅格地图中，相比于原烟花算法都能取得更好的规划效率，获得的最终路径更短。

5 结语

通过对烟花算法的路径节点连接机制的完善，将爆炸火花和高斯变异进行结合，并对下一代种群选择的方式进行了修改，改进后烟花算法在不同规模的环境中在寻找最短路径方面了显著的提高，并且运算时间较原烟花算法也有了缩短。在多次试验中，也发现了火花的数目和地图复杂程度有着一定的关系，所以，下一步还会继续完善对烟花算法，寻找烟花算法各个因素之间的相互影响关系，并探索该算法在真实环境中的表现。