元胞自动机模型(Cellular Automaton, CA)作为一种实现规则简单, 可以将复杂系统简单化的模型, 是目前应用最广泛的疏散模型之一^[1]. 然而, 其简单的实现规则也导致了其在描述疏散个体行为上具有一定的局限性, 而且当元胞的邻域为扩展Moore邻域时, 会花费较多的时间用于搜索可行领域元胞.

人工鱼群算法(Artificial Fish Swarm Algorithm, AFSA)作为一种较为新型的群集智能算法, 其利用群体之间信息交互来实现全局寻优的思想, 为微观疏散模型的研究提供了一种新的思路. Lu DJ等人^[2,3]使用人工鱼群算法来描述应急疏散时个体在路网中寻找疏散出口的过程.

不同于应急疏散, 在综合交通枢纽常规疏散的过程中, 人员的行为表现更为丰富, 具有排队等待、逗留、从众、跟随、随机探索、出(入)口选择行为、导向行为等, 使用单一的CA模型或者原始的AFSA算法都是难以完全刻画这些行为的. 因此, 本文改进原始AFSA算法, 结合CA模型, 提出一种基于元胞鱼群算法(CA-IAFSA)的人员疏散模型, 在刻画人员多样行为的同时, 降低模型的时间复杂度.

1 相关研究

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

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

目前, 将AFSA算法和CA结合起来进行研究的文献较少. 柳毅^[14]在研究带时间窗可回程取货车辆路径问题数据模型的基础上, 将AFSA算法和CA结合设计了元胞鱼群算法. 将二者结合起来, 一方面可以提高AFSA算法对离散型优化问题的处理能力, 另一方面可以使用AFSA算法中人工鱼的搜索规则来替代CA模型中的元胞状态转换规则, 从而降低模型的时间复杂度.

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

将综合交通枢纽内需要换乘的人员看成是人工鱼, 按照乘车意向划分为多个种群, 上层采用改进的AFSA算法, 底层采用CA框架, 将搜索空间离散化, 在每轮迭代过后, 利用CA模型的邻域模型和状态转换规则, 解决位置冲突.

2.1 模型假设

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

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

2.2 个体抽象

考虑个体的速度差异、视野差异, 个体表示为:

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

(1)

其中, X代表个体 $p$ 的位置; $O$ 表示乘车意向; ${v_0}$ 是初始速度; $v(t) = {v_0} \times {e^{ - \omega \times (\rho (t) - 1)}}$ , $\rho (t)$ 是 $t$ 时刻周围人群密度(单位: 人/m²); $w$ 为视野范围; M是一张记忆表, $M = ({l_1}{\rm{,}}{l_2}{\rm{,}}\cdots{\rm{,}}{l_k}{\rm{)}}$ , 用于记录个体 $p$ 记忆中的引导指示, 防止陷入局部最优, $l = (st,en)$ , $l$ 表示引导指示的方向矢量, $st$ 表示起始坐标, $en$ 表示终点坐标; $Q = (exit,{t_1},{t_2})$ , 保存个体 $p$ 当前的排队信息, $exit$ 表示 $p$ 正在出口(乘车点) $exit$ 处排队, ${t_1}$ 表示到达 $exit$ 的时刻, ${t_2}$ 表示离开 $exit$ 的时刻.

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)

其中, $X_i^t$ 表示个体 ${p_i}$ 在 $t$ 时刻的位置; ${E_k}$ 表示视野范围内可见的第 $k$ 个出(入)口; $n$ 表示当前时刻正在出口 ${E_k}$ 处排队等待的人数; $t(j)$ 表示队列中第 $j$ 个个体的所需服务时间; $d({E_k},X_i^t)$ 表示 $X_i^t$ 与 ${E_k}$ 之间的欧式距离.

(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)

其中, $\eta $ 是一个自定义参数, 表示疏散引导指示的作用范围.

若 $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}$ 在尝试了以上五种行为后, 仍停留在原地, 说明陷入了局部最优, 此时, 随意选择一个可行的方向进行移动.

完成一轮迭代后, 最终确定下一时间步的移动位置 ${X_n}$ .

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 位置冲突的解决

当个体确定了下一个时间步的移动位置 ${X_n}$ 时, 底层使用CA模型的并行更新策略来解决位置冲突. 冲突解决规则如下:

(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}$ 周围没有满足条件的邻域元胞时, 停留在原地.

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

在MATLAB上搭建2D模拟环境, 进行实验. 疏散环境设置如下:

(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 算法参数分析

采用控制变量法依次测试人工鱼的探索尝试次数 $try\_num$ 及视野范围 $w$ 对于疏散效果的影响. 设置人数为500, 换乘其他四种交通方式的人数各占25%.

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

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

从图2可知, 当设定人工鱼的视野范围 $ w \in$ $ [20,30]$ 时, $try\_num{\rm{ = }}$ 20时, 平均疏散时间与平均实验时间最短, 而当 $try\_num$ 大于35时, 平均疏散时间基本变化不大, 平均实验时间却在上下波动变化. 因此, 这里设置 $try\_num{\rm{ = }}$ 20.

从图3中可知, 当设定人工鱼的探索尝试次数 $try\_num{\rm{ = }}$ 20时, $w \in [20,25]$ 时, 平均疏散时间和平均实验时间最少, $w$ 的分布范围大于30时, 其对应的平均疏散时间和平均实验时间基本上变化不大. 因此这里设置 $w$ 的分布范围为 $[20,25]$ .

3.3 实验及对比分析

设置人数为500, 换乘其他4种交通方式的人数各占25%. 对比三种模型: ① ICA模型: 在CA模型中, 加入导向行为、排队行为和出口选择机制; ② CA-AFSA: 将CA模型和原始AFSA模型结合, 加入排队行为和出口选择机制, 不加导向行为; ③ 本文提出的CA-IAFSA模型. (注: 由于完整截取的图片较大, 图4中的(c)和(d)只截取了部分效果图.)

对比图4中的(a)和(b)可以发现, 模型①中, 位于火车站内的绝大数个体“绝对理性地”选择了距离出口最近的位置, 紧贴靠近出口的障碍物进行移动, 且趋向于在出口处形成“拱形”. 而在模型③的模拟效果图中, 人群是从远离出口的初始位置以聚集的趋势逐渐向三个出口靠近, 有效地避免了“紧贴墙壁行走”. 模型③相比模型①更好地体现了“从众”和“避障”行为.

对比图4中的(c)和(d), 相比模型②, 加入“导向行为”的模型③克服了根据“最短路径原则”移动而陷入局部最优, 原地徘徊而无法继续疏散的缺陷, 实现了人群自发有序地向着目的换乘点移动, 很好地体现了人员疏散的“导向”行为.

对比图5中的(a), (b), 对于距离较近的三个火车出口, 模型③相比模型①, 实现了资源的均衡利用, 比较符合实际情况下人员的“出口选择”行为.

为了进一步验证CA-IAFSA模型的在疏散模拟时间性能上的提升, 分别将人数设置为300人, 500人, 1000人, 在同等条件下, 使用ICA模型和CA-IAFSA模型进行10次模拟实验取均值, 结果如表2所示.

由表2可以看出, 在同一实验条件下, 模型③与模型①相比, 平均疏散时间在一定程度上有所降低, 在实验时间花费上至少降低了59%. 原因是: 前者采用扩展型摩尔型邻域, 遍历邻域元胞获得下一个移动位置时花费了大量的时间. 后者采用AFSA算法中人工鱼的搜索规则来替代CA模型中的元胞状态转换规则, 避免了盲目搜索, 同时, 在一定程度上避免了“快即是慢”现象的发生, 防止人群由于“最短路径原则”产生过度拥挤, 从而提升疏散性能.

4 结论与展望

本文提出的CA-IAFSA模型, 针对综合交通枢纽的常规疏散, 考虑个体之间的速度差异、视野差异, 将导向行为和排队机制加入原始AFSA算法中, 融合CA模型构建人员常规疏散模型. 实验结果证明, CA-IAFSA模型, 可真实的反映人员在综合交通枢纽内进行换乘时的疏散过程. 克服了原始AFSA在存在障碍物的疏散环境中, 易陷入局部最优的缺陷, 在刻画人员的导向行为、避障行为、排队行为、出(入)口选择行为上具有较好的模拟效果, 相比ICA模型, CA-IAFSA模型在一定程度上减少了疏散时间, 在时间复杂度上至少降低了59%. 在今后的研究中, 会根据实际情况, 进一步对模型参数进行调整, 为特定综合交通枢纽场景中的人员常规疏散提供决策辅助.