摘要：快速有效的应急疏散是保障火灾现场被困人员逃生和救援人员撤离的重要环节，合理的火场路径规划能有效地帮助火场被困人员实现安全逃生。本文针对火灾现场的疏散路径规划问题，提出了基于聚类融合交叉粒子群算法的疏散路径规划分析模型。基于聚类融合交叉粒子群算法，在不同栅格大小和复杂地形条件下，聚类融合交叉粒子群算法通过增强粒子的探索能力增加了粒子多样性，快速有效地规划出相应的最优疏散路径，使人员在火场紧急情况下安全快速地到达出口，提高疏散效率，减少人员伤亡。仿真结果验证该算法的可行性和有效性。

关键词：消防；粒子群算法； 路径规划； 适应度

1引言

    近年来，随着经济社会迅速发展,幼小活动场所或少儿教育机构大量出现，这些地方聚集大量儿童，场所内部部局复杂、功能多样、空间大、可燃物多，一旦发生火灾造成的人员伤亡、经济损失和社会影响将极为严重。尤其在多障碍物的幼小活动场所，由于场所障碍物不规则，人员年龄小、消防安全常识欠缺，所以一旦发生火灾，逃生极为困难。粒子群算法（PSO）是模拟鸟类飞行的一种优化算法，根据粒子群算法对建筑空间进行网格模型划分，定义和描述建筑空间各网格的静态属性，利用粒子群算法寻找最优路径是可行的一种方法。

    本文尝试将聚类算法和遗传算子加入到粒子群算法中，以此来实现在稀疏仿真地图中的路径寻优。引入基于划分的聚类方法中的Kmeans算法，根据粒子的适应度进行聚类，把粒子划分为若干个粒子子群，便于粒子在保存群体极值时，更多数目的适应度较好粒子信息传递到下一代粒子中，有效提高了算法的寻优速度。对每个子群采用一定规则的交叉和变异算子，从而提高粒子群算法的种群多样性。在每个子区内更新粒子速度和位置时，随着代数的增加改变惯性权重和加速系数，避免了早熟的现象。最后通过仿真验证了该算法的有效性，实验结果表明，算法加快了收敛速度，防止局部最优的问题产生，使火场被困人员在复杂的环境中，能快速找到最满意的路径。

2聚类融合混合粒子群算法

2.1聚类分析

    为了加强粒子之间信息交流，使粒子群算法收敛性好，将初始种群中的粒子根据聚类方法中的Kmeans算法分为若干个子种群，由每个子种群的最优粒子以及个体最优粒子的速度和位置信息指导下一代粒子更新进行速度和位置值。这样处理方式加强粒子的信息交换，从之前只有两个极值保留下来到现在有若干个极值保存下来，增加了粒子的多样性和信息传递，进而避免了局部最优的情况发生，利用粒子之间在迭代过程中的信息更新，加快收敛速度。

 每个粒子至今为止搜索到的最优位置P1(1)(i=1,2,...,N)每个聚类区C1(i=1,2,...,K)粒子至今为止搜索到的最优位置q1(i=1,2,...,K)

 2.2 加入交叉变异控制算子

 将遗传算子加入到粒子群优化过程中，已有很多研究成果。李红亚学者对研究成果进行了细致的分类和研究，无论是哪一种融合，遗传算子都能起到解决粒子群陷入局部最优值出现早熟、种群多样性差、搜索范围小等缺点，使得两种算法在性能上克服局限，再实现优势互补^[7]。本文将交叉算子和变异算子加入到粒子群算法路径规划过程中，在迭代过程中，对适应度进行排序，令前x%的粒子直接遗传到下一代，后（100-X）%的粒子进行交叉变异操作，通过变换X的值，调整算法的延展性。

 将粒子与父代中同一聚类的群体极值进行交叉操作，使交叉后的粒子具有群体极值的优势；对适应度相对不好的粒子进行变异操作，使变异后的粒子能够保持多样性，跳出局部最优。

2.3自适应调整加速系数和惯性权重

粒子群迭代过程中，早期希望粒子有较强的自我学习能力，较低的社会学习能力，这样保持粒子的多样性，在晚期希望粒子有较低的自我学习能力，较强的社会学习能力，这样使粒子能收敛于全局最优。为此，对传统的粒子群加速系数进行改进，具体为：

    其中，C1max和C1min为加速系数C1的上下限。C2max和C2min为加速系数C2的上下限。tmax是迭代的最大次数。t是当前迭代次数。

2.4 适应度函数的选择

在设计路径时，要综合考虑路径的长短和是否成功避开障碍物，所以本文选择的适应度函数如下：

   其中N表示路径段数，n记录了与障碍物相交的路径段数目，D表示路径的长度。

   （xs，ys），（xf，yf）分别代表路径起始点与终点坐标。此设计将两个因素综合在一个函数中，实现了量化的统一。路径长度越小，与障碍相交次数越少，则适应度函数值越大。

2.5 具体步骤

1) 初始化参数。设置所需规划地图信息、起始点、终止、改进算法的各种参数、粒子群的规模（N）、初始速度、聚类数目(k），交叉及变异概率。

2) 计算适应度值。根据公式（4）及（5）更新每个粒子的适应度值。

3) Kmeans算法对粒子分区。对N只粒子的适应度值进行排序，根据适应度排序结果运用Kmeans算法分析把粒子分为k个聚类区，即W1(i=1,2,...,K)。

4) 对个体极值和群体极值进行更新。对分区后的粒子更新适应度值，个体极值为当前粒子迄今为止搜索到的最优位置P1(1)(i=1,2,...,K)，即适应度最大时候粒子所在位置，个体极值对于每个粒子是唯一的，一共有N个。群体极值为每个聚类区W1(i=1,2,...,K）中的所有粒子迄今为止历史搜索到的适应度值最大的位置q1W1(i=1,2,...,K）群体极值一共有K个。

5) 速度和位置的更新。使用公式（3）更新自适应学习因子C1(j=1,2,...,K）。

6) 若迭代次数达到设定值则停止程序运行，输出全局最优解，否则循环(4) (5)。

3 结果分析

 在Inte(R) Core(TM) i5-4200U CPU，1.60GHz，4GB内存，MATLAB R2014a环境下对算法进行仿真实验。为了验证本文采用的对适应度Kmeans聚类分析方法和交叉、变异算子的有效性，在相同运行环境下分别用传统粒子群算法、具有交叉、变异算子的粒子群算法和聚类融合交叉粒子群算法进行了对比模拟仿真实验。

 图3至图8分别给出了采用传统粒子群算法、带有交叉、变异算子的粒子群算法和本文聚类融合交叉粒子群算法的最优路径图。从图中容易看出，传统粒子群优化算法在相同迭代次数下走出的路径效果最差，虽然找出一条不和障碍物重叠的路线，但是粒子路线跳跃起伏较大，带来的耗能随之增大，明显是一条局部最优路径。图4和图7是在传统粒子群中加入交叉、变异算子后的结果，可以看出减少了一些冗余路线，效果虽然有所改进，但是耗费时间长，一些区域还存在可以优化的可能性。而在交叉粒子群基础上加入Kmeans聚类分析的本文改进算法（图5，图8）得到的最优路径精度相对较高，在相同运行代数下，路径长度明显最短，路线较为顺滑，相对而言降低了拐点数和无效路径段，实际过程中可以达到节省被困人员体能消耗、缩短疏散时间的效果。

 为了更直观看出加入聚类算法的优势，本文对交叉粒子群算法和聚类融合交叉粒子群算法收敛情况进行比较，结果如图9所示（粒子数为3000，迭代次数为10000，聚类数为10）。

 对比结果可以看出，粒子群算法加入交叉、变异算子可以改变传统粒子群的最大的缺陷，即容易陷入早熟现象，增加种群多样性，但是计算量会随之加大，收敛代数也会成指数上升，针对这个缺陷，加入Kmeans聚类分析算法，能够使收敛代数稳定下降，加快收敛速度，使得总计算时间也大大缩短，对于智能路径寻优有很好的效果。

4 结论

本文提出基于聚类融合交叉粒子群算法的路径规划方案，通过引入聚类分析的思想和遗传算法中的交叉、变异算子到传统粒子群算法中，避免了粒子群算法在复杂环境下容易出现停滞现象。通过对比仿真实验可以看出，选择适合复杂地图模型的聚类数目，在增加粒子多样性的同时，可以加快收敛速度，搜索出的路径明显优于传统粒子群算法和交叉粒子群算法。通过模拟在幼儿活动场所内发生火灾后，利用基于聚类融合交叉粒子群算法规划火场逃生路径是安全可行的，该算法既能保证避开障碍物，也可以实时动态避开危险区域，并且在此前提下迅速规划出最短的逃生路线。

参考文献

[1]Kubota K , Inoue K , Hashimoto R , et al. Development and Investigation of Efficient GA/PSO-Hybrid Algorithm Applicable to Real-World Design Optimization. Eleventh Conference on Congress on Evolutionary Computation. IEEE Press, 2009.

[2] A. Mohammadi, and M. Jazaeri. A Hybrid Particle Swarm Optimization-Genetic Algorithm for Optimal Location of SVC Devices in Power System Planning. In Proceedings of the 42nd International Universities Power Engineering Conference, pp. 1175 – 1181, 2007.

[3] A. A. A. Esmin, G. Lambert-Torres, and G. B. Alvarenga. Hybrid Evolutionary Algorithm Based on PSO and GA mutation. In Proceedings of the 6th International Conference on Hybrid Intelligent Systems, 2006.

[4] 张勇，陈玲，徐小龙，等.基于PSO-GA混合算法时间优化的旅行商问题研究[J].计算机应用研究，2015，32（12）：3613-3617.

[5]冯辉, 刘梦佳, 徐海祥. 基于AHPSO算法的无人艇多目标路径规划[J]. 华中科技大学学报(自然科学版), 2018(6).

[6]高鹰, 谢胜利, 许若宁. 基于聚类的多子群粒子群优化算法[J]. 计算机应用研究, 2006, 23(4):40-41.

[7]李红亚, 彭昱忠, 邓楚燕. GA与PSO的混合研究综述[J]. 计算机工程与应用, 2018(2):20-28.

[8] YU H, LI X. Fast path planning of robot based on grid method [J]. Microelectronics and Computer，2005，22（6）：98－100．（于红斌 李孝安．基于栅格法的机器人快速路径规划［J］．微电子学与计算机，2005,22（6）：98－100.）