﻿ 基于元胞鱼群算法的人员疏散模型
 计算机系统应用  2019, Vol. 28 Issue (5): 131-136 PDF

Pedestrian Evacuation Model Based on CA-IAFSA Algorithm
LIU Wen-Ning, WANG Jia-Wei, TANG Xue-Qin
School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China
Abstract: For the limitations of the Cellular Automata (CA) model and the original Artificial Fish Swarm Algorithm (AFSA) in describing the conventional evacuation behavior of the comprehensive transportation hub personnel, a kind of pedestrian evacuation model based on the CA-Improved AFSA (CA-IAFSA) is proposed with considering the difference of walking speed and the difference of view between individuals. As the queuing mechanism and the export (entrance) selection behavior, the guiding behavior, and the memory function are added to the original AFSA. The top layer adopts the IAFSA for mobile location updating, and the bottom layer uses the CA model to solve moving position conflicts. Experiments show that the model can truly reflect the evacuation process of people transferring vehicles in an integrated transportation hub. Under the same environment, compared with the original AFSA, the proposed model realizes the orderly movement of individuals according to guidance, avoiding falling into local optimum. Compared with the CA model, it is better in terms of reflecting the individual's herd, obstacle avoidance, and export (entrance) selection behavior, thus effectively reduces the time complexity.
Key words: integrated transportation hub     conventional evacuation     evacuation behavior     Cellular Automaton (CA)     Artificial Fish Swarm Algorithm (AFSA)

1 相关研究

CA模型是把空间和时间按照一定间距离散化, 系统物理量只取有限个状态的物理系统简化模型[1]. 它具有四个基本组成部分: 元胞、状态、邻域和转换规则. 基于CA的疏散模型侧重于研究应急情况下的人员疏散过程[46], 关注于人员特性或者环境对疏散效率造成的影响[710], 忽略个体在疏散过程中的行为表现和相互影响.

AFSA算法最早是在2002年被提出的[11], 该算法使用人工鱼的四种基本行为: 聚群行为、追尾行为、觅食行为、随机行为来实现变量在变量空间中寻优的过程[12]. 该算法在解决配电网重构等一系列连续性优化问题取得了较好的效果, 但在解决离散型优化问题上仍具有一定的局限性[13].

2 基于元胞鱼群算法的疏散模型

2.1 模型假设

(1)人员在移动过程中, 不考虑碰撞与挤压;

(2)换乘客流全部来源于火车到站客流, 其乘车意向假设已知. 人员在移动过程中不会更改乘车意向.

2.2 个体抽象

 $p = \{ X,O,{v_0},w,M,Q\}$ (1)

2.3 行为抽象

(1)出(入)口选择行为:

 $X_i^{t + 1} = X_i^t + \frac{{{e_O} - X_i^t}}{{||{e_O} - X_i^t||}} \times v(t)$ (2)
 ${e_O} = \arg \min T({E_k})$ (3)
 $T = \sum\limits_{j = 1}^n {t(j) + \frac{{d({E_k},{X_i}^t)}}{{{v_0}}}}$ (4)

(2)导向行为: 当在视野可见范围内, 没有目标出口, 存在引导指示时, 选择距离最近的引导指示 $l$ .

$l \notin M$ :

 $M = \{ {l_1},{l_2},\cdots,{l_k},l\}$ (5)

$d(st,X_i^t) > \eta$ :

 $X_i^{^{{\rm{t}} + {\rm{1}}}} = X_i^t + \frac{{st - X_i^t}}{{||st - X_i^t||}} \times v(t)$ (6)

$d(st,X_i^t) \leqslant \eta$ :

 $X_i^{t + 1} = X_i^t + \frac{{en - st}}{{||en - st||}} \times v(t)$ (7)

$l \in M$ :

 $X_i^{t + 1} = \frac{{{l_k}(en) - {l_k}(st)}}{{||{l_k}(en) - {l_k}(st)||}} \times v(t)$ (8)

${p_i}$ 视野可见范围内即无出口又无引导指示时, 则选择从众行为、跟随行为、探索行为中最优的一种行为执行.

(3)从众行为: ${p_i}$ 搜索视野可见范围内具有相同意向的伙伴, 计算其中心位置 ${X_c}$ , 若 $Y({X_c})$ 优于 $Y(X_i^t)$ , 将 $S\_X_i^{t + 1}$ 作为 ${p_i}$ 下一个时间步的待选位置.

 $S\_X_i^{t + 1} = X_i^t + \frac{{{X_c} - X_i^t}}{{||{X_c} - X_i^t||}} \times v(t)$ (9)

(4)跟随行为: ${p_i}$ 搜索视野可见范围内具有相同乘车意向的伙伴 ${p_j}$ , 若 $Y({X_j})$ 优于 $Y(X_i^t)$ , 将 $F\_X_i^{t + 1}$ 作为 ${p_i}$ 下一个时间步的待选位置.

 $F\_X_i^{t + 1} = X_i^t + \frac{{{X_j} - X_i^t}}{{||{X_j} - X_i^t||}} \times v(t)$ (10)

(5)探索行为: 个体在视野范围内随机而不重复的任选一个位置 ${X_r}$ , 若 $Y({X_r})$ 优于 $Y({X_i})$ , 则将 $P\_X_i^{t + 1}$ 作为 ${p_i}$ 下一个时间步的待选位置.

 $P\_X_i^{t + 1} = X_i^t + \frac{{{X_r} - X_i^t}}{{||{X_r} - X_i^t||}} \times v(t)$ (11)

${p_i}$ 在尝试了 $try\_num$ 次后, 仍没找到较优的位置, 则停留在原地.

(6)随机行为: 当 ${p_i}$ 在尝试了以上五种行为后, 仍停留在原地, 说明陷入了局部最优, 此时, 随意选择一个可行的方向进行移动.

2.4 排队机制的实现

${p_i}$ $t$ 时刻确定相应的出(入)口 ${e_O}$ , 且 $d({p_i},{e_O})$ $< \xi$ ( $\xi$ 表示距离阀值), ${p_i}$ 进入到 ${e_O}$ 当前的排队队列中, ${p_i}$ 停止移动, 排队结束后, 则恢复运动.

 $Q = ({e_O},{t_{}},{t_2})$ (12)
 ${t_2} = t + \sum\limits_{j = 1}^n {t(j)}$ (13)
2.5 位置冲突的解决

(1)将 ${X_n}$ 作为中心元胞, 使用Moore型邻域, 当 ${X_n}$ $X_i^t$ 之间既没有障碍物, ${X_n}$ 也没有被其他个体占据, 优先选择 ${X_n}$ .

(2)当发生冲突时, 遍历 ${X_n}$ 周围满足条件的邻域元胞 $N({X_n})$ , 分别计算未被其他个体占据且与 ${X_n}$ 之间不存在障碍物的元胞与 $X_i^t$ 的欧式距离, 随机选择一个元胞作为下一个时间步的目标移动位置.

(3) ${X_n}$ 周围没有满足条件的邻域元胞时, 停留在原地.

 图 1 CA模型解决位置冲突

3 实验及结果分析 3.1 环境设置

(1)环境区域为 ${\rm{100}}\;{\rm{m}} \times 100\;{\rm{m}}$ , 元胞边长为 $0.2\;{\rm{m}}$ , 设置火车站的范围为 $x \in [0\;{\rm{m}},100\;{\rm{m}}]$ , $y \in [0\;{\rm{m}},20\;{\rm{m}}]$ . 各交通方式的出/入口参数设置如表1所示.

(2)这里参考文献[15], 设置个体占地面积 ${\rm{0}}{\rm{.4\;{\rm{m}}}} \times$ 0.4 m, 初始速度服从正态分布 $N({\rm{1}}{\rm{.34,0}}{\rm{.2}}{{\rm{6}}^{\rm{2}}})$ , (单位: m/s)时间变化步长为1s.

(3) $\omega = {\rm{0}}{\rm{.01}}$ , $\eta = 2$ , $\xi = 2v$ .

3.2 算法参数分析

(1)调试 $try\_num$ 参数值: 设置 $w$ 随机分布在 $[20,30]$ 范围内. $try\_num$ 变化步长为5, 分析 $try\_num =$ 5, 10, …, 50时对于疏散效果的. 实验结果如图2所示.

 图 2 参数 $try\_num$ 对疏散效果的影响

(2)调试 $w$ 参数值: 基于实验(1), 设置 $try\_num = 20$ , 设置 $w$ 变化步长为5, 分析 $w$ 分布[5,10], [10,15], …, [45,50]范围时对于疏散效果的影响. 实验结果如图3所示.

 图 3 参数 $w$ 对疏散效果的影响

3.3 实验及对比分析

 图 4 三种模型的模拟效果

 图 5 两种模型的火车出口排队人数变化趋势

4 结论与展望

 [1] Bakar NAA, Majid MA, Ismail KA. An overview of crowd evacuation simulation. Advanced Science Letters, 2017, 23(11): 11428-11431. DOI:10.1166/asl.2017.10298 [2] Zong XL, Jiang YL, Wang CZ. Evacuation behaviors and link selection strategy based on artificial fish swarm algorithm. Proceedings of the 7th International Conference on Cloud Computing and Big Data. Macau, China. 2016. 279–283. [3] Lu DJ, Zhang GJ, Liu YL, et al. AFSA based path planning method for crowd evacuation. Journal of Computational Information Systems, 2014, 11(11): 3815-3823. [4] 张鑫龙, 陈秀万, 李怀瑜, 等. 一种改进元胞自动机的人员疏散模型. 武汉大学学报•信息科学版, 2017, 42(9): 1330-1336. [5] 杨波, 陈丹丹, 夏颖, 等. 基于GIS的CA-PSO多出口场景疏散模型研究. 中南民族大学学报(自然科学版), 2017, 36(1): 107-112. [6] 袁野, 田中旭. 隧道火灾疏散模型实时仿真算法的实现. 计算机工程与应用, 2017, 53(23): 208-211. DOI:10.3778/j.issn.1002-8331.1606-0083 [7] 李世威, 王建强, 刘应东. 初始分布非均匀的行人流疏散仿真研究. 计算机应用研究, 2017, 34(3): 702-705. DOI:10.3969/j.issn.1001-3695.2017.03.014 [8] Fu ZJ, Zhou XD, Zhu KJ, et al. A floor field cellular automaton for crowd evacuation considering different walking abilities. Physica A: Statistical Mechanics and Its Applications, 2015, 420: 294-303. DOI:10.1016/j.physa.2014.11.006 [9] 蒋雪玲, 潘颖. 大规模聚集人群的疏散仿真模型研究. 计算机仿真, 2015, 32(6): 398-402, 415. DOI:10.3969/j.issn.1006-9348.2015.06.088 [10] Zhong W, Tu R, Yang JP, et al. Simulation of evacuation process in a supermarket with cellular automata. Procedia Engineering, 2013, 52: 687-692. DOI:10.1016/j.proeng.2013.02.207 [11] 李晓磊, 邵之江, 钱积新. 一种基于动物自治体的寻优模式: 鱼群算法. 系统工程理论与实践, 2002, 22(11): 32-38. DOI:10.3321/j.issn:1000-6788.2002.11.007 [12] Neshat M, Adeli A, Sepidnam G, et al. A review of artificial fish swarm optimization methods and applications. International Journal on Smart Sensing and Intelligent Systems, 2017, 5(1): 107-148. [13] Neshat M, Sepidnam G, Sargolzaei M, et al. Artificial fish swarm algorithm: A survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artificial Intelligence Review, 2014, 42(4): 965-997. DOI:10.1007/s10462-012-9342-2 [14] 柳毅, 沈勤. 带时间窗可回程取货车辆路径问题的元胞鱼群算法. 系统管理学报, 2011, 20(6): 739-743. [15] 杨立中. 建筑内人员运动规律与疏散动力学. 北京: 科学出版社, 2012.