基于元胞自动机模型的地铁人员疏散仿真研究∗

许爱军谢依馨

（广州铁路职业技术学院广州510430）

地铁环境相对封闭，通道复杂，发生火灾时容易造成群死群伤事件。根据疏散时人流宏观流动和个体行为，结合地铁建筑结构特征，提出基于元胞自动机建立地铁应急疏散模型，利用遗传算法淘汰适应度低下的网格节点，从而生成全局最优子图，计算最佳逃生路径。仿真实验证明，新模型和算法平均疏散路径长度最短，能很好地应用于地铁疏散预案和消防演练之中。

元胞自动机；遗传算法；地铁；疏散模型

Class NumberTP393

1 引言

地铁是城市重要交通工具，也是人流密集公共场所。但地铁建筑复杂，环境相对密闭，大多过往客流对站场环境不熟悉，一旦发生火灾事故极易引起群体恐慌，发生践踏事故，甚至造成重大人员伤亡［1］。加强地铁应急预案，提高发生事故时乘客疏散效率己成为城市公共安全领域研究的重点和热点。

疏散过程中受人员之间和人员与环境之间的相互影响和作用，高密度人群会出现聚集阻塞、自动队列、震荡和协作等现象［2～3］。为模拟疏散方式，业界提出元胞自动机、流体力学、社会力等仿生疏散模型，以此计算最佳逃生路径，提高人员逃生和救援效率。其中，流体力学模型为减少计算复杂度，不考虑流体质点之间的摩擦和碰撞导致的能量损失，将疏散人流看为无粘性的流体运动，在人流量较少时模拟精确，但当人流密度达到一定值时，该模型就会失效，并不适用于地铁密集人员疏散模拟［4］。社会力模型主要考虑疏散人群之间的社会属性，即人的宏观流动，忽略人的个体行为。如当火灾发生时烟气、高温和缺氧对个人造成生理和心理的影响，前者影响个人行进速度和可视范围，后者会因心理恐慌影响对最佳逃生路径的判断，模拟效果与真实地铁疏散情况差距较大［5］。元胞自动机模型将疏散空间划分为网格，处于网格中的每个单元叫做元胞。网格中的元胞通过相互作用动态演化，模拟人群个体行为和群体效应。元胞自动机模型能很好地阐释人群疏散过程中的出口动态，目前已广泛应用于公众场合中的人群流动和疏散建模［6～7］。

鉴于此，本文根据疏散时人流的宏观流动和个体行为，结合地铁建筑结构特征，提出基于元胞自动机建立地铁应急疏散模型，利用遗传算法淘汰适应度低下的网格节点，从而生成全局最优子图，计算最佳逃生路径。

2 元胞自动机的定义与特征

元胞自动机是指在具有离散和有限状态的元胞组成的元胞空间上，按照一定的局部规则，在离散的时间序列上演化的动力学系统［8～9］。元胞自动机模型由单个元胞、元胞状态、邻居元胞以及局部规则组成。

元胞自动机的定义为：定义均匀网格为G，元胞集合为J，其中J={0,1,2,…,i-1}，D为元胞空间维度，k为元胞在t时刻状态，状态集合为S。SD为状态集S的一个分布。元胞邻域集合为N，元胞邻居半径为r，局部变化规则F满足f''→f。则在模型中元胞状态变迁可以表示为不同时刻t下各个元胞状态组合的演化，表示为

元胞状态演化通过局部变化规则f函数实现，遍历网格内所有元胞，应用f演变函数，得出模型全局演化规则：

从以上定义可以看出，元胞自动机具有同质性（遵循相同的演化规则）、齐性（分布规则整齐）、时空局限性（下一时刻状态取决于上一时刻自身及其邻居元胞的状态）、状态离散有限（只能在有限的离散空间内取值）等特征。

3 基于元胞自动机的地铁火灾疏散模型

3.1疏散模型

在元胞自动机模型中，将地铁疏散通道和空间划分成0.3m×0.3m正方形元胞网格，每个网格仅能存在单个元胞个体，每个元胞个体分为被人占据和无人占据两种情况。网格节点之间疏散人员按照逃生出口顺序沿着网格从一个节点移动到另一节点，从而准确展现地铁建筑结构和障碍物位置，真实表现人群逃生路径信息。

设人员疏散方向概率Pm,n为个体选取相邻网格点（m，n）概率，则Pm,n可以表达式为

其中

其中，Hm,n是相邻网格点（m，n）被疏散人员占据情况，Qm,n表示相邻网格点（m，n）被障碍物占据情况，FΓ用于评价疏散人员个体对地铁环境熟悉度和恐慌度，Tm,n是安全出口位置对网格点（m，n）吸引度，其值为

式中（x，y）是安全出口坐标，疏散个体选择最优逃离路径为

定义L(xi,yi)为疏散人员i初始坐标，M(x,y)为疏散群体在选择最优路径时相遇的聚合坐标，疏散个体在M处汇聚后列队逃离最近逃生出口，则疏散人员选择的全局最优路径疏散的最少时间需满足d(x,y)最小值，即：

其中，Aim,n是疏散人员i对网格（m，n）的吸引度。

3.2火灾扩散衰减模型

定义火灾扩散和衰减过程为

其中，E是元胞自动机模型中某网格受火灾影响程度，A是火灾扩散系数，B是火灾衰减系数，ΔE是火灾格点与其他网格点之间距离。

4 疏散算法设计

疏散人员的最优逃生路径可以转变为求解单源多目的路径排列组合的最优算法问题。定义地铁共有k个目标逃生出口，则全局最优路径Y为

Y满足约束条件如下

则疏散人员平均逃离路径长度为

根据式（11）求解全局最优解。求解全局最优算法有蚁群算法、粒子群算法、遗传算法等。其中蚁群和粒子群算法都容易陷入局部最优现象导致算法提前收敛。遗传算法通过选择、交叉和变异三种遗传算子保持物种多样性，计算复杂，但能很好解决算法搜索停滞和提前收敛问题。

4.1适应度函数建立

对逃生出口节点进行编号，范围是1～p。矩阵pop表示染色体数量，popsize为矩阵pop行数，c为矩阵pop列数，矩阵中每行对应pop的每个染色体。Pn为逃生路径段［p1，p2，p3，…，pn］的累加长度，即逃生总路径长度，以此建立适应度评价函数为

其中，kru(v0)为平均逃生路径总长度，kru(x)为网格节点［x1，x2，x3…，xn］所确定的逃生最优路径。引入遗传算法目的在于判断每次生成的路径子图是否满足适应度条件，通过循环迭代淘汰元胞自动机模型中适应度低下网格节点，从而生成全局最优子图。

4.2遗传算子设计

定义Pc为单点交叉概率，其值越大，表示遗传算法中产生新个体速率越快，搜索速度也越大，从而加速解的收敛。交叉概率Pc为

4.3疏散算法的基本流程

step1：初始化种群数量和最大迭代次数；

step2：在相邻的元胞中选择一个个体作为父代；

step3：选择邻居元胞与中心元胞进行交叉和变异操作；

step4：判断算法是否收敛，否则返回step2元胞操作；

step5：根据适应度函数判断新生成的个体是否优于元胞，是则替换元胞，否则返回step2，以此淘汰适应度低下的网格节点；

step6：输出最佳逃生路径。

新算法流程见图1所示。

图1 新算法流程图

5 仿真测试

5.1测试环境

为验证本文所提方法的有效性，以广州地铁某站场为例进行仿真实验。实验选取标准地铁口站台换乘大厅，地铁疏散出口有10处，其中A～D为站台出入口，E～J为出入闸［10］，见图2所示。

图2 仿真实验拓扑图

5.2测试结果

在测试实验中，将地铁换乘站厅划分成元胞空间为1000*600网格，人员节点均匀分布于站厅各处，疏散速度为1m/s。在遗传算法中，初始群体大小pop为200，最大遗传代数500，初始化交叉概率Pc＝0.8，变异概率Pm＝0.01。图3是不同人群规模与疏散总距离之间的关系，图4是不同人群规模与疏散时间之间的关系。

图3 疏散人数对疏散距离的影响

在图3，由于人群列队行进，疏散人数对疏散距离影响不大，两者呈线性增长。在图4，当人数少于100时疏散时间随疏散人数匀速增长，当超过120人次时发生拥堵，180人次时严重拥堵，疏散时间消耗迅速增加。图5是不同疏散算法对疏散时间的影响。初期疏散人数少于120人次时，三种算法疏散时间相差不大，新算法略优。

随着疏散人数的增加，蚁群算法和粒子群算法在不同程度上陷入局部最优现象，算法提早收敛。新算法利用遗传迭代淘汰元胞自动机模型中适应度低下的网格节点，从而生成全局最优子图，疏散时间最短。

6 结语

本文提出了基于元胞自动机模型建立地铁应急疏散模型。模型利用遗传迭代淘汰元胞自动机模型中适应度低下的网格节点，从而生成全局最优子图。通过仿真，对不同人群规模与疏散总距离、疏散时间分别进行模拟，得出结果：1）疏散人数与疏散距离两者呈线性增长，两者之间的影响关系不大；2）当疏散人数达到站场容量某个定值时，疏散时间明显增加。因此，在地铁人流高峰时期，进行客流高峰管制对地铁站的秩序安全有重要作用。本文还分别对粒子群算法、蚁群算法和本文提高的新算法进行了对比分析，结果显示三种疏散算法在疏散时间方面，新算法略优，但在疏散效率方便，新算法具有明显优势，能很好地应用于地铁疏散预案和消防演练之中。

［1］吕春杉，翁文国，杨锐.基于运动模式和元胞自动机的火灾环境下人员疏散模型［J］.清华大学学报，2007，47（12）：72-76.

LU Chunshan，WENG Wenguo，YANG Rui.Fire evacua⁃tion model based on motor schema and cellular automaton［J］.Joumal of Tsinghua Univ（Sci&Tech），2007，47（12）：72-76.

［2］连培昆，李振龙，荣建，等.基于VISSIM微观交通仿真软件的导流岛机非冲突元胞自动机模型［J］.计算机应用，2016，36（6）：1745-1750.

LIAN Peikun，LI Zhenlong，RONG Jian，et al.Cellular au⁃tomaton model of vehicle-bicycle conflict at channelized islands based on VISSIM microscopic traffic simulation software［J］.Journal of Computer Applications，2016，36（6）：1745-1750.

［3］汪金辉，陆守香.建筑火灾中人员安全疏散的可靠概率分析模型［J］.中国科学技术大学学报，2006，36（1）：116-118.

WANG Jinhui，LU Shouxiang.Model of probabilistic risk assessment for evacuation under building fire［J］.Jounal of University of Science and Technology of china，2006，36（1）：116-118.

［4］于群，张敏，曹娜，等.基于模糊元胞自动机的电网故障演化模型［J］.计算机应用，2015，35（9）：2682-2686.

YU Qun，ZHANG Min，CAO Na，et al.Power grid fault evolution model based on fuzzy cellular automata［J］.Jour⁃nal of Computer Applications，2015，35（9）：2682-2686.

［5］魏娟，胡俊，张洪，等.一种元胞自动机与类电磁法相结合的行人流模型［J］.四川大学学报（自然科学版），2016，53（4）：753-758.

WEI Juan，HU Jun，ZHANG Hong，et al.A pedestrian eca⁃cuation model based on cellular auto maton and electro⁃magnetism mechanism［J］.Journal of Si Chuan University（Natural Science edition），2016，53（4）：753-758.

［6］李晶晶，纪庆革.基于遗传算法优化多出口疏散路径问题［J］.上海师范大学学报（自然科学版），2008，37（4）：383-389.

LI Jingjing，JI Qingge.Research on GA-based optimizin gmulti-exit evacuation path problem［J］.Journal of Shang hai NormalUniversity（Natural Sciences），2008，37（4）：383-389.

［7］曾平安，郑智捷.利用变值编码展现元胞自动机的4类经典分类模式［J］.计算机科学，2016，43（6A）：139-141.

ZENG Pingan ZHENG Zhijie.Using Variable Value Cod⁃ing to Show 4 Classical Classification Models of Cellular Automata［J］.Computer Science，2016，43（6A）：139-141.

［8］刘真余，芮小平，董承玮，等.元胞自动机地铁人员疏散模型仿真［J］.计算机工程与应用，2009，45（27）：203-205.

LIU Zhenyu，RUI Xiaoping，DOND Chengwei，et al.Simu⁃lation of urgent evacuation in subway station based on Cel-lular Automation［J］.Computer Engineering and Ap⁃plications，2009，45（27）：203-205.

［9］陆秋琴，杨少敏，黄光球.求解非线性方程组的元胞自动机方法及其全局收敛性证明［J］.计算机应用，2012，32（12）：3283-3286.

LU Qiuqin，YANG Shaomin，HUANG Guangqiu.Cellular automata method for solving nonlinear systems of equa⁃tions and its global convergence proof［J］.计算机应用，2012，32（12）：3283-3286.

［10］许爱军，苏境迎.基于自适应蚁群算法的地铁人员疏散模型［J］.微处理机，2016，37（01）：50-53.

XU Aijun，SU Jingying.Subway Personnel Evacuation Model Based on Adaptive Ant Colony Algorithm［J］.Mi⁃cro Processors，2016，37（1）：50-53.

Research on Subway Evacuation Simulation Based on Cellular Automata Model

XU AijunXIE Yixin
（Guangzhou Railway Polytechnic，Guangzhou510430）

Metro subway underground is too complex to cause fire.According to evacuation flow and individual behavior，com⁃bined with the structural features in subway，this paper put forward a subway emergency evacuation model based on cellular automa⁃ta，and use genetic algorithm to eliminate unsuitable grid nodes.Simulation results show that the new algorithm can evacuate more than 80%passengers in the shortest time，and has the shortest evacuation routing length，can be used in subway evacuation plans and fire drills.

cellular automata，genetic algorithm，metro，evacuation model

TP393

10.3969/j.issn.1672-9722.2017.05.033

2016年11月5日，

2016年12月26日

2016年度大学生科技创新培育专项资金（编号：pdjh2016b0687）；广东省科技计划项目（编号：2015A030401005）资助。

许爱军，男，教授，研究方向：数据管理系统与智能算法、虚拟现实技术。谢依馨，男，研究方向：虚拟现实技术。