基于改进遗传算法的消防疏散标识布局优化.pdf

2097-3012(2023)02-0268-07 Journal of Spatio-temporal Information 时空信息学报 收稿日期:2021-12-08；修订日期:2023-05-16 基金项目:四川省科技计划项目（2022YFS0533，2020JDTD0003）作者简介:周曈，研究方向为虚拟地理环境。E-mail: 基于改进遗传算法的消防疏散标识布局优化 周曈1，朱军1，李维炼1，付林1，柴金川2 1.西南交通大学 地球科学与环境工程学院，成都 611756；2.中国铁道科学研究院集团有限公司 国家铁道试验中心，北京 100015 摘 要：消防疏散标识布局对火灾疏散逃生有重要意义，但现有的布局方法存在因布设者经验差异大，地方标准的不同导致标识引导效能差的问题。本文提出了标识引导效能计算思路，构建疏散标识布设优化模型，研究基于自定义算子的改进遗传算法，实现了改进遗传算法的消防疏散标识布局优化方法；并以地铁站台为例开展了实验模拟。结果表明，本文方法能够明显提高消防疏散标识引导效能。这可为室内消防疏散逃生下的标识布设提供科学依据。关键词：消防疏散标识；布局优化；改进的遗传算法；自定义算子；并行化加速 引用格式：周曈,朱军,李维炼,付林,柴金川.2023.基于改进遗传算法的消防疏散标识布局优化.时空信息学报,30(2):268-274 Zhou T,Zhu J,Li W L,Fu L,Chai J C.2023.Optimizing fire evacuation sign layout optimization using improved genetic algorithm.Journal of Spatio-temporal Information,30(2):268-274,doi:10.20117/j.jsti.202302014 1 引 言 由于火灾具有不确定性、复杂性和快速性，往往会造成严重的生命财产损失（唐俊等，2019）。现有的构建博弈疏散模型可以证明，火灾疏散时合理的疏散标识可以显著提高人员的疏散效率（马晓辉等，2019；万展志等，2020），在火灾疏散过程中尤为重要，设置合理有效的地面疏散标识是减少人员伤亡的重要手段之一（高坤，2020）。尽管疏散标识在火灾应急疏散中起到重要作用，但现有的疏散标识布设是按照相关标准和规范，根据经验布设，往往会造成标识信息单一、指向混乱。标识可视性降低、标识引导效用差，使得现有的标识布局存在着不能准确指出正确的逃生路径的弊端（胡志方和万斌，2017；徐慧智等，2019；Ma 等，2019），会导致不能及时为乘客提供正确信息，延误逃生，造成更大规模的伤亡（高坤，2020）。传统的遗传算法具有计算简单、通用性强、鲁棒性较高等优点，被广泛应用于包括标识布局优化在内的诸多领域内（ozowicka，2021；Wan 等，2021）。其不足之处在于后期收敛慢导致整体执行时间长，还有可能错过全局最优解（何启嘉等，2021；杜航等，2021）。部分研究致力于优化该算法：Chen 等（2019）在遗传算法的基础上结合了模拟退火算法，将其应用在大型铁路综合客运枢纽公共换乘区引导标志设置中；Li 等（2022）将遗传算法与路由交换算法融合，实现了考虑流量平衡的人群疏散动态符号引导优化。但这些算法仍然存在着局部收敛能力不足，求解速度较慢、可能丢失最优解、在遗传算法的运行过程中，个体适应度的评价计算，往往占据了较长时间的问题（余雷等，2019）。针对以上问题，本文基于改进遗传算法探究了一种消防疏散标识布局的优化方法。其提出了基于标识引导效能的计算思路，以标识引导效能最大化为目的，建立了疏散标识布设优化模型；通过基于用户自定义算子和并行化加速个体适应度计算，改进传统遗传算法存在的速度慢、可能丢失最优解问题，试图实现模型的快速求解，并以地铁站为例进行了实验模拟。周曈 等：基于改进遗传算法的消防疏散标识布局优化 269 2 研究方法 2.1 总体研究路线 本文以标识投影到视网膜上的有效成像面积为标准，提出消防疏散标识布局下的引导效能计算思路。首先，根据标识引导的约束条件，构建基于标识引导效能的消防疏散标识优化模型；然后，通过自定义算子和并行化计算，改进遗传算法用于求解优化模型；最后，通过原型系统研发和模拟实验分析，论证本文方法的有效性与适用性（图 1）。图 1 研究技术路线 Fig.1 Research technological roadmap 2.2 基于标识引导效能的消防疏散标识优化模型 2.2.1 标识引导效能计算 本文定义标识引导效能的大小为标识投影到视网膜上的有效成像面积，为了确定该面积，采用了进一步简化的标准眼模型（Ai 和 Tsai，2012；吴爽，2017），将标识可视面积转换为视网膜面积。在该模型中，视网膜的成像机制被简化成简单的几何模型（图 2）。图 2 视网膜成像的等效模型示意图（吴爽，2017）Fig.2 Schematic diagram of the equivalent model for retinal imaging 在该视网膜成像模型的基础上，可以推导标识的引导效能 ij的大小，如图 2 所示。设当前位置为i 处，标识所在位置为 j 处，视距即当前位置 i 处到标识所在位置 j 处的距离为 Dij；瞳内间距 DT，标识可视面积 S1，视网膜成像面积 S2，根据相似三角形的性质可以得出：2T122ijDSSD （1）又因为标识的引导效能 ij同视网膜成像面积S2成正比，设为常数 K，则可以得到：0minmax22T10,/,ijijijijijijDDDDKD SD其他 （2）式中，当视距 DijDijmin时，标识始终能够发挥引导效用，此时标识引导效能始终为最大值0；当视距 DijDijmax时，标识始终不能发挥引导作用，此时标识引导效能始终为 0。由于场景和标识的差异270 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)性，在实际的模型建立中 Dijmin和 Dijmax这两个阈值的取值往往需要根据场景特征和标识特点确定。绘制标识引导效能函数，如图 3 所示。图 3 标识引导效能函数 Fig.3 Marker-guided performance function 2.2.2 消防疏散标识优化模型构建 将室内场景定义为引导服务的需求空间 V，为了方便建立模型，将需求空间离散为一系列元胞组成的集合。每一个元胞都是需求空间网络中的顶点，且每一个顶点 kV，都是消防疏散标识的潜在布设点，同时也是消防疏散标识引导范围内的需求点。将区域内现有的障碍物所在位置设为禁忌区域A，则剩下的区域均为符合可行性的标识选址区域B，且有 AV，BV，AB=V。定义标识引导需求点 i（i=1，2，3，n），疏散标识 j（j=1，2，3，m），n 为场景内所有的需求点的数量，m 为疏散标识的数量。消防疏散标识布局的目标是使得m个标识对场景内共计n个引导需求点提供的引导效能 最大，通过式（2）将标识引导效能 最大为目标函数，可以构建消防疏散标识布局模型如下：11maxmax1s.t.0,1nmijijiiiAiB且 （3）式中，i为在标识选址空间约束下，i处是否需要被引导的决策变量，由于在密闭的疏散空间中，每一处都可能存在需要被引导的逃生人员，所以i始终为1；i为在标识选址空间约束下，标识引导需求点i处是否放置标识的决策变量，在i处放置标记时i=1，否则i=0。2.3 基于改进遗传算法的优化模型求解 为了实现上述消防疏散标识优化模型的求解，本文提出了基于改进遗传算法的优化模型求解方法。联合自定义算子和并行计算，实现了优化模型的求解。2.3.1 基于自定义算子的改进遗传算法（1）编码。在本算法中，个体指每个标识布局，而染色体指每个标识的不同坐标，本文选取的编码方式为实数编码（real-number encoding），直接以原始数据表示染色体即可。相比于传统的二进制编码，该编码方式不需要将原始数据转换为二进制数，避免了频繁的编码和解码操作，降低了算法的计算量和额外最优解（刘振鹏等，2019；王雪峰，2019）。具体编码设定为（sign_x0，sign_x1，sign_xn，sign_y0，sign_y1，sign_yn），分别代表第1个、第2个第n+1个标识的x、y坐标。将算法得到的各坐标映射到场所布局，即为对应的消防疏散布局。（2）适应度计算。在遗传算法中，用适应度来评估个体的优越程度，适应度越大，越容易遗传到下一代。本文求解的优化模型目标是求引导效能的最大值，可以设适应度函数Fit为 Fit=max （4）式中，目标函数的具体求解参考式（3）。按这个方法对步骤（1）中编码得到的不同个体进行适应度计算，即可得到种群G，并设定总的迭代次数g、迭代计数器t=0，进入迭代计算直到步骤（6）。（3）个体选择计算。是指在每个遗传算法的循环环节的开始，利用选择算子从当前种群中选出适当的个体作为双亲，从而用于后续的产生下一代个体。该选择的概率基于适应度高低，个体适应度越高，被选择的概率也就越高。本文使用的选择算子为锦标赛选择（tournament selection），在此算子中，从总体中随机选择多个个体，个体间相互比较适应度，最高者获胜被选择，进入下一代个体（Kl和Yzge，2019a，2019b）。本方法中使用了AF共6个个体，具有不同的适应度值，随机选择了3个个体后即标识引导效能最高，假设C个体适应度最高，则视为获胜，进入子代，产生种群G1。锦标赛 周曈 等：基于改进遗传算法的消防疏散标识布局优化 271 算子不需要适应度函数的实际值，只需要比较多个个体间哪个更好即可，能够简单快速地完成选择操作，提高了算法速度。（4）染色体重组计算。染色体重组计算是指重新组合双亲的遗传信息，从而产生后代。相比于传统遗传算法中常见的单点交叉方法（1-point crossover），本文选用了双点交叉法（2-point crossover），在交叉过程中选取两个交叉点，进行基因的交叉（Mirjalili，2019；Katoch等，2021）。假设第一个交叉点位于第二个基因后，第二个交叉点位于第五个基因后，则重组计算是指将两个交叉点之间的片段进行互换。将种群G1进行染色体重组计算，可以得到种群G2。（5）染色体变异计算。通过引入变异操作跳出局部最优解，得到新的解集。相比于传统的遗传算法采用的单点变异方法，本文采用交换式变异（swap mutation）方法，随机选择两个长度相同的基因序列，具有更强的变异能力，并能保留大多数的相邻信息，具有更强的跳出局部最优解，从而搜索全局最优解的能力。利用该变异方式对种群S2进行操作，可以得到种群G3。（6）判断。将步骤（5）中得到的种群G3设为G，使得迭代计数器t的值加1，并判断迭代计数器t是否等于步骤（2）中定义的迭代次数g，若不满足，则回到步骤（2）；若满足，则停止迭代，输出最终结果。通过选择、重组、变异操作中的自定义算子，增强了算法跳出局部最优解的能力，提升了算法的计算效率，降低了算法的运行时间。2.3.2 基于线程池的算法并行化加速 针对遗传算法的运行过程中，适应度评价计算耗时久的问题（刘嵩，2006），通过在该环节引入并行化加速方法，提升算法的运行效率。传统的多线程方案将创建进程转化为创建线程，降低了程序运行时间。但在多线程处理过程中，如果任务简单、运行时间短，会导致程序频繁地启动、运行和销毁线程，造成了程序运行时间延长。为此，本文采用基于线程池的多线程技术，线程被预先创建并放入线程池中。相比于运行后就销毁线程的方法，线程池技术进行了重用线程，在运行完当前任务后，继续执行线程池中的下一个任务，如图4所示。这避免了多次创建和销毁线程，节省了相关时间，提升了算法运行效率，带来了更好的性能和系统稳定性。图 4 基于线程池的多线程技术 Fig.4 Multi-threading technologies based on thread pools 3 模拟实验分析 地铁是建于地下的大容量轨道交通系统。由于运营环境的特定性等因素，一旦突发火灾事故，乘客紧急逃生极其困难，群死群伤的可能性极大，如2003年2月18日韩国大邱市地铁火灾，造成近200人死亡、140余人受伤。为了在地铁站台内设置合理有效的地面疏散标识，从而减少人员伤亡，本文选择地铁站台开展模拟实验。3.1 模型建立 为了消除用户现有的认知记忆对于实验的干扰，通过考察国内典型的地铁站布局，建立一个具有主要地铁站台特点的虚拟场景，其中，站台长度为42.5 m，宽度为7.5 m（图5）。图 5 地铁站台俯视图（单位：m）Fig.5 Top view of the metro platform(Unit:m)该场景设立了两个扶梯出口，主要障碍物为座椅和柱子，其中座椅两处，而每处往往是8个座椅连在一起的情况，因此，可以对座椅进行简化处理，将相连的8个座椅简化为一个长方体障碍物，简化后的每处座椅长3 m、宽0.6 m。柱子14个，每个柱子的占地面积为0.5 m0.5 m。其中，忽略柱子上广告和光效应的影响，将柱子简272 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)化成没有修饰的长方体。根据障碍物的位置设定禁忌区域，将剩余区域设为可行性区域。采用交通枢纽分级导向标识布设方法，提出远视距定义，将可见性阈值Dijmax设为50 m，超出此距离的标识视为超出视距范围无法起到引导作用（李宁川，2017；林建新，2017；韩玉琦，2019）。由于地铁站台存在面积小、乘客多、站台拥挤的风险，需要减小标识间的布设距离，从而提高标识的覆盖密度以提高引导效能。根据地铁站域空间标识系统研究中提出的近距离资讯类标识牌体视距，将地铁站台的疏散引导标识设为2.5 m（汤雅莉，2014）。瞳内间距DT的取值，则依靠进一步简化的标准眼模型中的定义设为22.78 mm。标识大小，则采用地铁环境下紧急事件中地埋式标识的外径大小80 mm，计算得到圆形的标识大小S1为0.02 m2，并根据场景条件设定模型参数（表1）。表 1 模型参数设定 Tab.1 Model parameters Dijmin/m Dijmax/m DT/m S1/m2 站台长度/m 站台宽度/m 参数数值 2.5 50 0.02278 0.02 42.5 7.5 3.2 结果分析 实验选用的电脑为Lenovo ThinkBook14p，CPU是AMD Ryzen5 5600H，内存16 GB，显卡为CPU自带的AMD Radeon（TM）Graphics 集显，硬盘为1 TB SSD。根据前文提出的模型求解方法，设定标识迭代次数为30次，遗传算法中各染色体的上下界分别为（42.5，0）、（7.5，0）。设定标识总个数为m=10个。为了便于计算，设KT2S1为此场景下的引导效能标准量，记为1，计算得到优化前的标识引导效能值为74.603。优化前的标识布局是依据经验设定的，优化后的标识布局是由程序计算得到，如图6所示。与优化前相比，标识覆盖上更具有规律性，分布上更加均匀，能够覆盖的区域较广。图 6 优化前、后的标识布局（单位：m）Fig.6 Sign layout before and after optimization(Unit:m)经过22次迭代后，算法的迭代结果趋于稳定，最后获得的标识引导效能值为80.241，优化后结果相对于优化前增加了7.56%，如图7、图8所示。证明本文方法能够有效进行消防疏散标识布局的优化。图 7 遗传算法变化 Fig.7 Variation in genetic algorithm 图 8 遗传算法寻优轨迹 Fig.8 Genetic algorithm optimization trajectory 为了验证标识引导效能确实得到了提升，通过绘制优化前、后的标识引导范围覆盖图来进行对比。约定标识的覆盖近、中、远距离分别为1 m、3 m、5 m，绘制标识引导范围覆盖，如图9所示。优化前标识的布局较为集中，部分区域存在着标识分布稀疏的问题，优化后标识的布局更为分散，在各区域都有标识提供引导服务。由表2可知，在近距离上，新的疏散标识布局比旧的疏散标识布局，提升了0.13%；在中距离上，新的疏散标识比旧的疏散标识布局提升了18.40%；结合图9（a），在远距离上优化前的结果明显存在着白色区域，这代表着旧的疏散标识布局存在着不能覆盖的问题，使得部分区域的旅客不能被引导，而新布局则几乎完全覆盖了整个站台区域，可以为每一处旅客提供引导服务。以100代为例，将该模型分别用模拟退火算法、遗传算法，以及本文方法进行求解，并对运行时间进行计时，得到耗时和求解结果，如表3所示。本文方法较改进前提升了97.52 s，较其他算法也有明显的速度提升，提升了程序的运行效率。在求解结果上也能够得到较高的目标函数水平。周曈 等：基于改进遗传算法的消防疏散标识布局优化 273 图 9 优化前（a）、后（b）的标识引导范围覆盖（单位：m）Fig.9 Coverage range of sign guidance before(a)and after(b)optimization(Unit:m)表 2 优化前、后覆盖率对比 Tab.2 Coverage range comparison before and after optimization%优化 近距离 中距离 远距离 未覆盖 前 9.65 59.18 95.85 4.15 后 9.66 70.07 99.96 0.04 表 3 不同算法效率对比 Tab.3 Efficiency comparison of different algorithms 模拟退火算法 遗传算法 本文方法 100 代耗时/s 2860.31 2775.72 2678.20 效能求解结果 76.093 78.512 80.241 4 结 论 本文针对消防疏散标识引导效能差的问题，进行了基于改进遗传算法的消防疏散标识布局优化研究。提出了一种标识引导效能计算思路，通过引入自定义算子改进遗传算法，实现了消防疏散标识布设优化模拟的加速求解；还在个体适应度评价环节，引入基于线程池的多线程技术，实现了多个个体的适应度评价并行化检测，降低了运行时间，实现了更加高效的模型求解；选取了地铁站台进行模拟实验以验证本文方法的适用性。结果表明，本文方法能够明显提升标识布设效率和布局引导效能，可实现快速准确地获取引导效能好的消防疏散标识布局。后续将结合布局中障碍物的分布等情况，研究实际布设的可行性，并结合协同引导理论，研究多标识情况下的引导效能计算。参考文献 杜航,张涛,陈岩,赵银明.2021.基于遗传算法的BP神经网络预测石油单井产量.成都大学学报(自然科学版),40(1):57-61,70 高坤.2020.地铁虚拟火灾逃生能力测评及影响因素实验研究.硕士学位论文.郑州:郑州大学 韩玉琦.2019.基于乘客行为和信息需求的地铁导向标识系统优化.硕士学位论文.西安:长安大学 何启嘉,王启明,雷政.2021.基于改进遗传算法的 FAST 促动器油缸装配机器人运动学.科学技术与工程,21(19):8072-8078 胡志方,万斌.2017.城市轨道交通区间智能应急照明及疏散指示系统方案研究.公路,62(7):353-357 李宁川.2017.地铁站乘客引导标识优化设置研究.硕士学位论文.成都:西南交通大学 林建新.2017.基于乘客视觉感知行为的综合客运交通枢纽分级导向标识布设方法研究.博士学位论文.北京:北京交通大学 刘嵩.2006.改进的并行遗传算法应用研究.硕士学位论文.大连:大连交通大学 刘振鹏,王雪峰,薛雷,张彬,张寿华.2019.实数编码遗传算法的改进及并行化实现.河北大学学报(自然科学版),39(1):86-92 马晓辉,周洁萍,龚建华,黄琳,李文航,邹宇玲.2019.面向室内应急疏散标识的 VR 眼动感知实验与布局评估.地球信息科学学报,21(8):1170-1182 汤雅莉.2014.地铁站域空间标识系统的地域性体系研究.博士学位论文.西安:西安建筑科技大学 唐俊,朱军,李维炼,佘平.2019.基于虚拟地理环境的室内火灾真实感可视化.地理信息世界,26(3):72-76 万展志,周铁军,罗能.2020.基于可视性的会展建筑展厅应急疏散标识布局研究综述.建筑科学,36(8):160-168 王雪峰.2019.用于函数优化问题的实数编码遗传算法的改进及并行化实现.硕士学位论文.保定:河北大学 吴爽.2017.基于激光扫描点云的交通标志牌可见性评估研究.硕士学位论文.厦门:厦门大学 徐慧智,赵小红,武腾飞.2019.考虑乘客流量和节点重要度的地铁站信息查询台优化布置.交通运输系统工程与信息,19(6):68-76 余雷,马生涛,杨杰,康缘.2019.基于改进遗传算法的 VMS 选址274 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)研究与分析.计算机应用研究,36(1):91-93,98 Ai C B,Tsai Y.2012.Critical assessment of automatic traffic sign detection using three-dimensional LiDAR point cloud data/Transportation Research Board 91st Annual Meeting,12:3214 Chen J L,Guo X C,Liu S S,Yang M.2019.Research on the setting of guide signs in the public transfer zone of large-scale railway integrated passenger transportation hubs/19th COTA International Conference of Transportation Professionals,19:6311-6323 Katoch S,Chauhan S S,Kumar V.2021.A review on genetic algorithm:Past,present,and future.Multimedia Tools and Applications,80(5):8091-8126 Kl H,Yzge U.2019a.Improved antlion optimization algorithm via tournament selection and its application to parallel machine scheduling.Computers&Industrial Engineering,132:166-186 Kl H,Yzge U.2019b.Tournament selection based antlion optimization algorithm for solving quadratic assignment problem.International Journal Engineering Science and Technology,22(2):673-691 Li M H,Xu C Y,Xu Y,Ma L,Wei Y.2022.Dynamic sign guidance optimization for crowd evacuation considering flow equilibrium.Journal of Advanced Transportation,2022:1-19 ozowicka D.2021.The design of the arrangement of evacuation routes on a passenger ship using the method of genetic algorithms.Plos One,16(8):e0255993 Ma P J,Jiang Y Q,Zhu J F,Chen B K.2019.The effect of escape signs on the pedestrians evacuation.Physica A:Statistical Mechanics and Its Applications,534:121133 Mirjalili S.2019.Genetic Algorithm.Cham:Springer International Publishing Wan Z Z,Zhou T J,Tang Z L,Pan Y,Zhang L F.2021.Smart design for evacuation signage layout for exhibition halls in exhibition buildings based on visibility.ISPRS International Journal of Geo-Information,10(12):806 Optimizing fire evacuation sign layout optimization using improved genetic algorithm ZHOU Tong1,ZHU Jun1,LI Weilian,FU Lin1,CHAI Jinchuan2 1.Faculty of Geosciences and Environmental Engineering,Southwest Jiaotong University,Chengdu 611756,China;2.National Railway Track Test Center,China Academy of Railway Sciences Group Co.,Ltd.,Beijing 100015,China Abstract:The layout of fire evacuation signage plays a crucial role in ensuring effective evacuation and escape during fire incidents.However,existing layout methods suffer from issues such as significant variations in designer experience and discrepancies in local standards,resulting in poor effectiveness of the signage guidance.To address these challenges,this study proposes a calculation approach to assess the effectiveness of signage guidance,develops an optimization model for the layout of evacuation signage,and investigates an improved genetic algorithm based on customized operators.The proposed method is applied to optimize the layout of fire evacuation signage in subway platforms,and experimental simulations are conducted.The results demonstrate that the proposed approach significantly enhances the effectiveness of fire evacuation signage guidance,providing a scientific basis for indoor fire evacuation signage layout.Key words:fire evacuation signs;layout optimization;improved genetic algorithms;customized operators;parallelization acceleration Supported by Sichuan Science and Technology Program(2022YFS0533,2020JDTD0003)