基于GIS的CA-PSO多出口场景疏散模型研究

杨 波，陈丹丹，夏 颖，余志涛

(中南民族大学 计算机科学学院，武汉430074)

基于GIS的CA-PSO多出口场景疏散模型研究

杨 波，陈丹丹，夏 颖，余志涛

(中南民族大学 计算机科学学院，武汉430074)

参考当前所处位置的人员密度以及所选出口的密度大小，融合元胞自动机与粒子群优化算法，建立了一个新的CA-PSO人员疏散模型模拟教学楼中学生的疏散过程．通过对同一疏散环境中教室的学生进行模拟疏散实验对比，结果表明：在元胞自动机模型基础上结合粒子群优化算法，模拟疏散过程的结果更加符合实际，疏散效率高．将其结合地理信息系统，模拟教学楼某楼层学生疏散行为，具有较好的实用性和通用性．

元胞自动机；粒子群优化算法；地理信息系统；多出口

人群聚集地方易发生公共安全事件，为了减少人员伤亡，降低财产损失，国内外学者利用先进的计算机技术模拟疏散过程，得出切实有效的指导措施，或者优化当前建筑格局[1]．采用网格模型[2]疏散环境，更易表现个体的行为．在此基础上引入元胞自动机[3]算法思想所建立的模型，是人员疏散问题研究的重要领域．

基于元胞自动机理论，崔喜红等人通过设置简单规则实现疏散过程中人员个体特性和从众行为[4]，在此理论基础上，赵宜宾等人提出多出口人员疏散模型[5]，通过引入目标方向密度概率、出口影响因子概率、移动方向校正因子，使模拟仿真结果更加合理，但其未考虑视野范围内优异个体对其下一步移动方向的指导作用．

疏散人员所表现出来的行为、应急心理、决策各不相同，并贯穿整个疏散移动过程，多智能体模型结合元胞自动机用于模拟个体行为，提高了模型对实践的指导意义[6]．

粒子群优化算法也是研究疏散问题的一个重要方向，Chen Y P等人[7,8]克服了原始的PSO算法中粒子移动的随意性与碰撞性，在寻找路径过程中采用冲突避免机制，躲避障碍物，使人群的移动路线更加光滑和自然．Tsai P C等人[9]通过寻找视野范围内可以追寻的最优个体，以此作为全局最优值，让疏散模拟情形更加符合实际疏散环境．但上述文献均未考虑疏散人员在紧急情况下的心理状态以及疏散出口人员密度问题．

结合地理信息系统(GIS)在改进的多智能体模型框架下模拟行人，并结合趋势地图使个体可以察觉到危险区域，从而避免人员伤亡[10]．上述情形缺少对多出口环境的模拟，以及原始算法在寻优的过程中，容易陷入局部最优值．文献[11-13]为了克服算法本身存在的缺陷，对原始算法加以改进，使其改进后的算法能更好地搜索到全局最优值．

本文在对元胞自动机与粒子群优化算法等相关模型研究的基础上，将二者优势相结合，应用于多出口人员疏散场景，利用粒子群算法更新人员方向、元胞自动机规则进行位置评价，从而使疏散模拟结果更加合理化，并将其应用于教学楼疏散场景．

1 CA-PSO人员疏散模型的建立

1.1 理论基础

粒子群优化算法可呈现人群疏散的特征，但模拟实际人员移动时仍存在诸多缺陷[9,10]．而采用元胞自动机的相关疏散模型，个体根据自身以及邻居状态更新规则实现在疏散场景中的方向性移动[4,5]．本文建立CA-PSO人员疏散模型将二者相结合，用元胞表示粒子即疏散人员，将区域中出口定义为最终目的地，实现对人群疏散过程的模拟．

1.2 CA-PSO人员疏散模型

1.2.1 模型设定

教学楼是人员密集的场所，易发生突发事件，研究人员如何快速、安全疏散，是面对紧急情况需要考虑的重要内容．本文采用ArcGIS技术对教室和教学楼进行场景建模，学生作为主要疏散人群，模拟突发状况发生时，教室以及教学楼整个楼层学生的疏散行为．

1)栅格化：利用ArcMap绘制地图进行疏散场景建模，并对地图中的空间区域进行栅格化操作，让其中的每个栅格设置符合0.4m×0.4m[14]元胞大小；

2)移动方向：采用CA中两种常用邻居中的Moore型，如图1所示，其包含8个可移动方向，在此模型中人员可以根据规则在这8个方向上移动，或是停留在原地；

图1 疏散人员可移动方向Fig.1 Possible moving direction of the evacuee

3)人员特性：学生处于相同年龄段，移动速度和心理行为相仿，故用同一种元胞进行代替；

4)时间步长：区域中所有元胞状态均按照规则同步更新，现规定单位时间步内，疏散个体只可移动一个方格位置或停留在原位置．

1.2.2 人员疏散过程

在实际疏散环境中，针对其中任意一个移动个体，只有当该人员离开具体疏散环境，即疏散成功．疏散过程中，疏散个体会从一个区域进入另一区域，此时该人员需要根据实时环境更新自身信息．在整个疏散过程中的每个疏散个体在单个时间步长的移动具体包括：首先，搜索当前所在视野范围内的障碍物和其他移动人员，进而得到其所处位置当前的局部最优位置以及全局最优位置；其次，根据目前掌握的信息，利用PSO算法思想确定其移动方向区间，并在此区间中寻找当前最优方向，确定下一步的移动位置；最后，判断该位置是否存在竞争，当不存在竞争，则更新当前个体位置，若存在且该个体竞争处于劣势，则利用冲突解决机制去寻找次优位置，直至找到新位置，详细步骤如图2.

图2 疏散过程Fig.2 Evacuation process

1.2.3 人员移动规则

在二维空间中考虑人员在疏散场景中的移动过程，结合元胞自动机自身的特性，故将区域中第i个人员的移动方向和所处位置设置为空间中的二维向量，分别为Di=[Di_x,Di_y]和Pi=[Pi_x,Pi_y]．疏散过程中的每个个体都保持着自身独有的信息，包括其具体位置、移动方向、视野中的最优信息、全局最优信息以及对当前所处位置的评价值．

(1) 更新位置规则.粒子群算法的更新规则针对速度进行更新，进而更新自身位置信息，而CA-PSO模型由速度更新规则转变为速度方向更新规则.速度方向更新[7]是结合人员当前所处位置的局部最优位置、该区域范围内全局最优位置，在其标准速度上进行修正，得到最终的移动方向．具体如下：

Di+1=wDi+C1R1(Pilocal-Pi)+C2R2(Pigobal-Pi)，

(1)

其中w为保持原方向的惯性权重，C1为局部学习因子，C2为全局学习因子，为了增加搜索的随机性，R1,R2是介于(0,1)之间的随机数，Pigobal是人员所处位置的全局最优位置，Pilocal是人员视野范围的局部最优位置．

根据当前人员移动方向，确定其视野范围，并在其视野范围内搜索优于自身的其他人员的位置信息，并将该位置作为局部最优位置．与此同时，在疏散场景区域范围内寻找最优的疏散个体信息．由人员当前所处位置信息、局部最优位置信息、全局最优位置信息共同作用，指导该人员单位时间步长的移动方向．

在已经确定人员所要移动的方向后，通过位置评价公式，计算评估在该移动方向上的位置以及与其相邻方向位置的优越性，选择其中最优的方向位置作为下一步的更新位置．

(2) 位置冲突解决机制.当人员获得下一步的位置时，基本粒子群算法未考虑人员碰撞，CA-PSO要克服上述缺陷，需对该位置是否存在竞争进行判断，最终落实下一步的具体位置．具体步骤包括：首先，针对该位置搜索其附近有无其他竞争者，若无，则为该人员下一步的实际位置；若有，将其自身的位置评价值与其他竞争者的评价值进行比较，若优于其他人员，则该位置可被其占有，否则需寻找视野范围内的次优位置．不断重复上述过程，直至全部视野中没有可移动的位置，则该人员在该时间步长中需停留在原地，等待视野中再次出现可移动位置．具体过程如图3所示.

图3 冲突解决方案Fig.3 The method of conflict resolution

在当前视野范围中不存在可移动位置时，该人员可将其视野范围逐步扩大，直至找到满足条件的位置．若不存在，则停留在原地．具体过程如图4所示，图4(a)中黑色小方块表示当前疏散个体所在的位置，方向8是其目前所选方向即下一个要更新的位置．若方向8所在的位置被其他人员优先占有，则需寻找次优方向．为了维持由粒子群算法更新的方向位置的优越性，则该个体需要在该方向的基础上分别向左向右扩大其视野范围，寻找下一可移动位置，如图4(b)所示．若仍未找到，则继续扩大范围向其邻域方向寻找，如图4(c)，直至该人员视野中的所有方向都搜索完．

图4 扩大视野范围Fig.4 Enlarge field of view

(3) 方向位置评价函数.不同于现实世界人群的移动，事实上，粒子群优化算法不关注每一步的移动步骤以及具体的移动过程．在真实疏散场景人员的移动过程中仍需要考虑诸多因素，比如静态障碍物，其他可移动的障碍物包括其他移动人员，以及实际移动的环境情况等．

赵宜宾等人研究的CA模型[5]是基于文献[4]中的模型，本文是在上述模型理论基础上引入粒子群优化算法，提出新的疏散模型进行模拟仿真．由于人员在疏散过程中会根据前进方向的人员密度、障碍物分布情况、出口处人员密度等因素智能调整自身行进方向，故对人员所在方向位置进行基于上述3个要素的评价，具体计算公式如下：

fitness=n(k)[ktemptPtempt(k)+kdensityPdensity(k)+Pexit(k)]wexit(k),

(2)

其中n(k)为调节系数，当该方向k位置存在时，其取值为1，否则为0，ktempt为方向k吸引力权重因子，Ptempt(k)为方向k吸引力概率密度，kdensity为方向k密度权重因子，Pdensity(k)为方向k密度概率，Pexit(k)为方向k出口影响因子概率，wexit(k)为方向k移动方向校正因子．

2 CA-PSO结果分析

2.1CA与CA-PSO仿真结果比较

在赵宜宾等人建立的基于CA多出口人员疏散模型[5]的基础上引入群体智能算法粒子群优化算法的CA-PSO模型．与原CA模型相比，新模型未对元胞所有邻居进行评判，而是利用粒子群优化算法思想结合当前元胞移动方向、视野范围中对其有吸引力位置以及当前区域中最优位置共同作用下，确定一个方向区间．只针对该区间中的方向进行评价，然后选取评价值最高的方向，作为下一步的移动方向．当下一步位置与其他移动人员产生竞争且处于劣势时，个体在原有视野范围的基础上逐步扩大搜索范围，寻找次优位置，若该位置仍不满足条件，则重复上述步骤继续寻找，或是停留在原地等待合适位置的出现．

在同一疏散环境[5]中，该模型与由CA建立的M0，M1模型进行模拟结果的比较，模型中采用元胞规则的重要参数设置和具体疏散环境参考赵宜宾等人的文献．图5显示的是相同时间步ts分别取3，10，20，30时的疏散过程，通过观察图5，以及与文献[5]中的图7进行对比，可以得出疏散个体向优势位置附近靠拢，从而加快疏散速度．

图5 疏散过程Fig.5 Evacuation process simulation

为了进一步说明模型间的差异，对上述疏散过程进行100次模拟，并与文献[5]表1中的统计数据进行对比，具体见表1.

表1 相同时间步长下，3个疏散模型未疏散人数对比Tab.1 Comparison of number of unevacuated occupants in three evacuation models in the same time step

表1给出相同的时间步长下，3个模型在疏散过程中未离开疏散区域的人员对比以及随时间步长增加的变化情况．通过观察分析上述实验数据，3个模型在疏散初期，疏散效率基本保持一致，此时间段内的人员正处于寻找可移动空间并向出口位置移动．但随着时间步的增加，由于当前位置信息，视野范围中优秀个体对其的引导作用，使其快速向较优的出口位置移动，缩短了疏散距离，故CA-PSO模型的疏散效率优于其它两个模型．

2.2 教学楼场景仿真

采用上述设定模型及ArcGIS技术，对教学楼某一楼层进行场景建模，该模型包括9间教室，2个走廊，2个楼梯，4个出口，其中楼梯分别对应着两个出口．在疏散过程中，个体位置会随着时间不停地移动，相应其坐标也在不断变化．进行仿真疏散模拟时，需对疏散场景进行初始化包括出口和障碍物等信息，以及初始化疏散人员速度和位置，并让这些个体均匀分散在疏散仿真场景中的各个区域，结果见图6．

本文将提出的CA-PSO模型应用到教学楼场景中，模拟人员疏散行为，具体过程如图7所示．图7(a)可以观察到教室中的人员首先会向对自身有利的出口聚集，接着图7(b)、图7(c)演示了其穿过走廊最终成功疏散的整个过程．图7体现了在疏散过程中所表现出的个体行为和社会行为，能够很好地展示紧急疏散过程中人群所表现出的一些复杂的社会行为，如排队、拥挤、聚集等．

图6 疏散场景初始化Fig.6 Initialization of evacuation scene model

图7 模拟教学楼场景疏散过程Fig.7 Simulation of the evacuation process in the teaching building

教学楼场景的仿真结果中，由于出口3和出口4位置相较于出口1和出口2位置远，不易被人员选择，故出口1、出口2易导致人员拥塞现象，易发生人员踩踏和碰撞事件．故在发生紧急情况下，可考虑引导人员向出口3、出口4进行疏散，加快人员撤离危险区域，保证人员安全．此外，CA-PSO模型具有通用性，不仅能应用于特定疏散场景，而且可根据实际情况推广至一般疏散场景.

3 结语

模拟疏散人员依据自身在整个疏散环境中所表现出的具体的、实际的疏散行为，本文建立的CA-PSO模型将元胞自动机更新规则与粒子群优化算法本身的优势相结合，充分考虑了出口人群的密度、当前位置人员的密度、个体自身所拥有的决策信息以及视野范围中优异个体信息对其的吸引作用等因素，得到该个体下一步移动方向位置．通过相同实验环境条件下的对比实验，发现本文提出的疏散模型能够更好地模拟真实情况，且将其应用于教学楼场景的疏散环境中，再现人员疏散过程中的成拱、排队等群体现象，且可以根据仿真结果制定疏散指导策略．

当然人员疏散过程涉及的因素众多，本文只考虑对疏散过程影响较明显的因素，同时，模型中的人员结构较为单一且疏散方向固定，而现实中疏散环境多元化，人员结构复杂，疏散速度、空间占据范围、移动方向等多样化．下一步，将在本文所建立模型的基础上，深入讨论上述问题，使该模型的适用范围更大．

[1] Gwynne S, Galea E R, Owen M, et al.A review of the methodologies used in the computer simulation of evacuation from the built environment[J].Building &Environment, 1999, 34(6): 741-749.

[2] Muramatsu M, Nagatani T.Jamming transition in two-dimensional pedestrian traffic[J].Physica A Statistical Mechanics &Its Applications, 2000, 275(1-2): 281-291.

[3] 赵道亮，刘英学.人员疏散的二维元胞自动机随机模型研究[J].安全与环境学报, 2009, 9(5): 179-182.

[4] 崔喜红，李 强，陈 晋，等.大型公共场所人员疏散模型研究——考虑个体特性和从众行为[J].自然灾害学报, 2005, 14(6): 133-140.

[5] 赵宜宾，黄 猛，张鹤翔.基于元胞自动机的多出口人员疏散模型的研究[J].系统工程学报, 2012, 27(4): 439-445.

[6] 刘全平，梁加红，李 猛，等.基于多智能体和元胞自动机人群疏散行为研究[J].计算机仿真, 2014, 31(1): 328-332.

[7] Lin Y Y, Chen Y P.Crowd control with swarm intelligence[C]//IEEE.2007 IEEE Congress on Evolutionary Computation.Piscataway: IEEE Congress on Evolutionary Computation, 2007: 3321-3328.

[8] Chen Y P, Lin Y Y.Controlling the movement of crowds in computer graphics by using the mechanism of particle swarm optimization[J].Applied Soft Computing, 2009, 9(3): 1170-1176.

[9] Tsai P C, Chen C M, Chen Y P.PSO-based evacuation simulation framework[C]//IEEE Computational Intelligence Society.2014 IEEE Congress on Evolutionary Computation (CEC).Beijing: IEEE Congress on Evolutionary Computation, 2014: 1944-1950.

[10] Bo Y, Cheng W, Hua H, et al.A multi-agent and PSO based simulation for human behavior in emergency evacuation[C]//IEEE.Ninth International Conference on Computational Intelligence and Security (2007).Harbin: IEEE Computer Society, 2007: 296-300.

[11] Khan S, Yang S, Wang L, et al.A modified particle swarm optimization algorithm for global optimizations of inverse problems[J].IEEE Transactions on Magnetics, 2016,52(3):1-4.

[12] Jamian J J, Abdullah M N, Mokhlis H.Global particle swarm optimization for high dimension numerical functions analysis[J].Journal of Applied Mathematics, 2014, 2014(2): 1-14.

[13] Li J, Zhang J, Jiang C, et al.Composite particle swarm optimizer with historical memory for function optimization[J].IEEE Transactions on Cybernetics, 2015, 45(10): 2350-2363.

[14] Burstedde C, Klauck K, Schadschneider A, et al.Simulation of pedestrian dynamics using a two-dimensional cellular automaton[J].Physica A Statistical Mechanics &Its Applications, 2001, 295(3): 507-525.

Research on CA-PSO Multi-Exit Scene Evacuation Model Based on GIS

YangBo,ChenDandan,XiaYing,YuZhitao

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

Considering the crowd density of the current position and the density of target outlet, combining cellular automaton with particle swarm optimization algorithm, we proposed a new evacuation model named CA-PSO to simulate the evacuation process of the students in teaching building.The comparison results showed that CA-PSO algorithm performed well and improved the efficiency of evacuation process simulation.It is more practical and general when applying the model combined with Geographic Information System to simulate the students′ evacuation in a certain floor of the teaching building.

cellular automaton；particle swarm optimization；GIS；multi-exit

2016-12-23

杨 波(1979-)，女，副教授，博士，研究方向：可视化与仿真，地理信息系统，E-mail: yangbo@mail.scuec.edu.cn

国家自然科学基金资助项目(71003038)；中南民族大学2016年研究生学术创新基金项目(2016sycxjj208)

TP391.9

A

1672-4321(2017)01-0107-06