熵修正的混合人工蜂群-蝙蝠算法人群疏散模型

2021-12-13郁彤彤陈晓薇

哈尔滨工业大学学报 2021年12期

郁彤彤，王坚，陈晓薇

(同济大学 CIMS研究中心，上海 201804)

发生突发事件时，能否高效安全疏散直接关系到公众生命财产安全，是对安保能力的巨大挑战。因此，研究人群的安全有序疏散，建立合理安全快速的疏散模型并利用计算机进行模拟仿真，是国内外一直以来的重要研究课题。目前人群疏散模型主要分为微观模型[1-2]、介观模型[3]和宏观模型[4]。由于微观疏散模型以个体建模为出发点，能够对复杂动态疏散环境中个体间的微观相互作用进行描述，在目前研究中更为广泛。

相比社会力、元胞自动机等微观模型，群智能疏散模型由于模型简单、运算速度快、且能够较真实的模拟行人运动等优点，为越来越多学者关注。Aymaz等[5]针对火灾疏散场景，采用PSO算法对疏散路径进行了优化；王超等[6]基于静态地面场模型和粒子群优化模型，构建了地面场PSO(FF-PSO)人群疏散模型，可用于高密度人群的拥挤管理和快速疏散问题；Yamamoto等[7]使用蚁群算法对东京市中心的疏散路线安全性进行了量化评估；Yan等[8]构建了一种基于ACO算法的实时消防疏散系统(RFES-ACO)，公众可以使用移动Web3D设备顺畅地实时体验火灾疏散演练。

然而这些模型大多只考虑了粒子群算法、蚁群算法等单一的经典算法，不足以描述复杂的群体疏散行为，且应用新型群智能算法进行人群疏散建模的研究较少。由于生物群体动力学与人群疏散动力学具有一定的相似性[9]，许多新型群智能算法十分适合描述疏散中的不同场景。如，萤火虫算法适合描述疏散中的从众心理与行为；人工鱼群算法适合描述团体逃生、小群体聚集行为；人工蜂群算法适合描述引导行为；蝙蝠算法适合描述亲情行为、对出口有感知力的人群(如引导者)行为等。因此，本文在构建人群疏散模型时，将人群分类，并尝试综合使用多种群智能算法对各类人群进行建模，以使模型更加符合实际。

除此以外，疏散过程中的恐慌情绪会导致一系列混乱无序的非适应性行为，增加踩踏等事故发生的可能，同时人群也会自发产生小群体聚集等自组织行为，对疏散起到积极的作用。因此，疏散人群的混乱与有序程度会对人群疏散的效率、安全性等产生重要影响，然而现有模型较少考虑这一因素，也较少将定量表征混乱程度的疏散熵[10]用于构建人群疏散模型。因此本文在人群疏散模型中引入描述人群混乱程度的疏散熵模型，使模型更加贴合实际，更具实际指导意义。

1 相关方法

1.1 蝙蝠算法

蝙蝠算法是一种高效的生物启发式优化算法，其模拟了蝙蝠利用回声定位来捕食猎物的行为[11]。主要包括位置更新、局部搜索和脉冲频率与响度更新3个步骤。

1.1.1 位置更新

蝙蝠算法通过调整频率、追寻全局最优蝙蝠来控制速度与位置的更新，公式如下：

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

式中：fi为蝙蝠i的脉冲频率；fmin、fmax分别为频率最小、最大值，且为常数；β为值在[0,1]之间的随机函数；xi为蝙蝠i的位置；vi为蝙蝠i的速度；x*为整个空间具有最佳适应度的蝙蝠所在的位置。

1.1.2 局部搜索

若脉冲发射率较低，则在全局最优蝙蝠附近进行随机搜索，公式为

(4)

式中∈为值在[-1,1]之间的随机数，At为t时刻所有蝙蝠的响度平均值。

1.1.3 脉冲频率与响度更新

蝙蝠在寻找猎物初期，脉冲发射率低、响度高，便于广泛寻找。当感知到猎物后会提高脉冲发射率，降低响度，由广泛搜索慢慢转向向着目标前进。故随着向最优解的靠近，脉冲发射率与响度按如下公式更新：

(5)

(6)

1.2 疏散熵

疏散熵由魏心泉等[10]在2015年提出，用于定量刻画人群运动的混乱与有序程度。首先将疏散空间离散化成均匀网格，将每个离散网格里人群的速度方向和大小分别离散化成等间距的8个区间，得到群体速度方向和大小的离散化如图1所示，其中Vmax为疏散个体前进的最大速度。

图1 速度方向与大小的离散化

然后通过统计每个区间上的疏散个体总数计算疏散熵值。每个离散网格内群体运动速度方向熵值En1、速度大小熵值En2和总疏散熵值En计算公式为：

(7)

(8)

En=α1En1+α2En2

(9)

式中：N为每个离散化网格中个体的总数，ni为第i个速度方向区间上个体的总数，mj为第j个速度大小区间上个体的总数，αi为权重系数，一般设定α1=α2=0.5。

最后根据疏散熵的大小，将每一个离散网格的疏散熵值映射到疏散场景中，即可得到整个场景的疏散熵图，整个求解过程如图2所示。

图2 整个空间疏散熵图的求解过程

2 模型构建

目前疏散模型大多将人群视为无差别的个体，但实际上人群疏散是一个由不同行人组成的复杂系统。通过对真实疏散视频中的行人行为进行研究发现，人群疏散过程中会形成自组织群组，普遍存在群组引导者、群组成员和离散人员3类人群[12-13]。因此为了使疏散过程更加符合实际，本文在构建疏散模型时将人群分为群组引导者、群组成员和离散人员。

2.1 群组划分

本文采用DBSCAN(density-based spatial clustering of applications with noise)算法达到群组划分目的。具体步骤如下：随机选择一个没有被访问过的个体，将所有在距离ε内的个体都视为邻居点。若邻居点不大于minpoints，则该个体标记为离散人员，否则将该点及邻居点，以及邻居点的邻居点，即所有在ε临域内的个体聚集为一个新群组。不断重复该过程，直到所有个体都被访问，即每个个体都被标记为属于一个群组或为离散人员。

2.2 位置更新模型

在每个群体内部群组引导者一般始终在群组的前方引导其他人，因此基于人工蜂群算法，将适应度高的前百分比例per疏散个体确定为群组引导者、剩下的为群组成员。到目前为止，疏散环境中的人群被分为了群组引导者、群组成员和离散人员。

2.2.1 群组引导者位置与速度更新

群组引导者是指对疏散环境较为熟悉，对出口有较强感知，能够快速向出口疏散的人员。蝙蝠算法模拟了蝙蝠通过回声定位感知并捕食猎物的能力，十分适合模拟对出口感知力较强的引导者行为。因此群组引导者的位置更新机制基于蝙蝠算法，包含位置更新、局部搜索、脉冲发射率与响度更新3个步骤，并针对蝙蝠算法中不适用于人群疏散建模的部分进行改进，使模型更加合理。

1)位置更新。由于人每一步的前进距离是有限的，故将疏散个体的速度分为速度大小Si和速度方向Di=[Dix,Diy]T两部分，位置更新公式如下：

(10)

(11)

(12)

(13)

式中s-Di为个体i的搜索方向。

3)脉冲发射率与响度更新。脉冲发射率与响度的更新公式同式(5)、(6)，表示疏散个体正向着出口坚定快速的前进。

2.2.2 群组成员位置与速度更新

群组成员对出口感知力弱，易受周围人影响，在疏散过程中倾向跟随他人一起疏散。人工蜂群算法基于蜂群采蜜行为，核心是分工与合作，观察蜂受引领蜂指引得到蜜源信息进行采蜜[14]，与人群疏散中群组成员跟随群组引导者疏散类似，因此群组成员基于人工蜂群算法进行位置更新。

群组成员基于轮盘赌算法选择引导者进行跟随，引导者适应度越高被选择的概率越大，选择概率公式为

(14)

式中：pc,i为群体c中群组引导者i被选择的概率，fitc,i为群体c中群组引导者i的适应度，n为群体c中群组引导者的数量。

进而，群组成员跟随选择的群组引导者进行位置更新，公式为：

(15)

(16)

2.2.3 离散人员位置与速度更新

离散人员对出口感知力弱于群组引导者，不能马上定位出出口位置，且距离群组有一定距离，需要依靠自身搜索出口进行疏散。故基于粒子群算法进行速度与位置更新[15]，公式如下：

(17)

(18)

2.3 疏散熵修正模型

疏散熵修正是指在得到的预计更新位置的基础上，考虑混乱程度对疏散的影响，对群组引导者的位置进行修正，主要步骤如下。

1)判断是否进行修正。是否进行疏散熵修正取决于疏散熵修正阈值。判断个体相邻的8个区域的疏散熵值是否都小于疏散熵修正阈值，若存在大于阈值的区域，则进行疏散熵修正，否则不进行修正。当个体周围疏散熵值都较低时，表示周围疏散环境较为稳定，不需要引导个体朝相对稳定的区域前进。

2)确定修正方向。若进行疏散熵修正，则选择视野内疏散熵值最低的区域为修正方向。根据个体速度方向确定视野内的5个相邻区域，选择其中疏散熵值最低的区域为修正方向，若存在两个及以上熵值同为最低的区域，则选择速度夹角最小的区域。

如图3所示，黑色箭头为预计更新方向，蓝色虚线箭头为修正方向，1-5为视野内的5个相邻区域。图3(a)为个体选择视野内熵值最低的区域为修正方向，图3(b)为当存在多个熵值最低区域时，选择夹角最小的区域为修正方向，图3(c)为当个体相邻区域熵值均小于疏散熵修正阈值时，不进行方向修正。

图3 方向修正

3)确定修正参数。确定修正方向后，按照以下公式进行速度与位置的修正：

(19)

(20)

式中：e-Di为个体i进行疏散熵修正后的速度方向，e-xi为个体i进行疏散熵修正后的位置，c-Di为修正方向；ce为修正参数，表示参考修正方向的权重，根据是否看见出口确定，若个体不能看见出口，会倾向选择稳定的区域进行疏散，此时ce=2，若个体看见出口，则会倾向于向着出口前进，此时ce=0。

2.4 避障机制

在得到疏散个体下一步的位置以后，需要判断新位置是否可达，即新位置上是否存在静态障碍物和其他疏散个体。若新位置存在障碍物，则需要进行避障。本文利用代价值确定下一步可接受的概率，当可接受概率为0时，即新位置不可接受，则采取避障措施[15]。

避障机制采用周边搜索的方式。具体规则为：若新位置不可接受，则选择下一步方向偏差-10°～10°的随机角度为新方向，若此方向对应的位置仍不可接受，则再扩大10°，选择下一步方向偏差-20°～20°的随机角度为新方向……依次类推，直到下一步位置可达。

熵修正的混合人工蜂群-蝙蝠算法人群疏散模型流程如图4所示。

图4 熵修正的混合人工蜂群-蝙蝠算法人群疏散模型流程图

3 仿真与分析

3.1 疏散环境与参数设定

疏散场景设定为40 m×40 m的单出口二维矩形区域，四周灰色部分为墙壁，红色矩形为出口，并随机放置了一些深灰色矩形和圆形障碍物，设定疏散人数为80人。参数的设定见表1。

表1 参数取值

3.2 群组疏散仿真效果

首先，不引入疏散熵修正模型，将本模型与文献[15]中的PSO疏散模型(即所有个体为离散个体)进行对比，验证群组疏散效果。将两个模型的初始位置设为相同，分别试验了200组取平均值，以减轻初始位置及群组分布随机性的影响，得到表2。

表2 200组实验结果对比

由表2可以看到，本模型的每个个体的平均疏散时间和疏散完成时间均小于PSO疏散模型，其中每个个体平均疏散时间减少5.3%，疏散完成时间减少7.76%。这说明相比每个个体单独疏散，以合适的群组形式疏散可以提高疏散效率。

图5为仿真过程图，对比了PSO疏散模型和本模型的疏散过程。文献[14]通过对真实疏散视频中的行人行为进行研究，归纳了疏散过程中自组织群组的形状特点：疏散群组多呈现队列行或排行，群组内部有一定程度的弯曲且相对紧密。

如图5可以看到，在疏散初期，相比PSO疏散模型，本模型出现了明显的疏散群组，群组内部较为紧密；在疏散中期，本模型中的疏散群组呈现队列形状，群组后方的个体跟随群组前方的引导者向出口前进，且群组内部有一定程度的弯曲，符合真实群组的疏散形状；在疏散后期，由于人群在出口处聚集，群组被一定程度的冲散，但相比PSO疏散模型，人群更为紧密。两个模型都复现了“出口拱形”现象，本模型中的疏散群组也符合真实群组的疏散形状，证明了模型的有效性。

图5 PSO疏散模型和本模型疏散过程对比

图6为疏散空间中不同种类人群的变化趋势。可以看到，群组个体的下降速度快于离散个体。在群组个体多于离散个体的初始条件下，出现了离散个体晚于群组个体疏散出去的情况。这说明在疏散过程中，群组成员在引导者的带领下能迅速向出口处疏散，避免了寻找出口等造成的时间浪费，能一定程度上提高疏散效率。

图6 疏散空间中不同种类人群的变化趋势

3.3 疏散熵修正仿真效果

3.3.1 疏散熵修正阈值对疏散时间的影响

在相同设定下改变疏散熵修正阈值仿真50遍取平均值得到图7。由图7可以观察出，整体上随着疏散熵修正阈值的增大，疏散完成时间和每个个体平均疏散时间呈先减小后增大的趋势，当疏散熵修正阈值为0.4时，疏散完成时间和每个个体平均疏散时间最小。

图7 疏散熵修正阈值与疏散时间的关系

分析可知，当疏散熵修正阈值较小时，个体在前进时过多考虑疏散混乱程度的影响，即使前方不是特别混乱也会朝向混乱程度更低的方向前进，延长了疏散路线进而增加了疏散时间；随着疏散熵修正阈值的提高，个体只有在前方特别混乱时才会进行速度修正，以避开混乱区域尽快到达出口；当疏散熵修正阈值较大时，个体基本不进行速度修正，即使前方混乱也会向其前进，进一步加剧了混乱程度，导致了疏散时间的增加。下面的仿真将疏散熵修正阈值设定为0.4。

3.3.2 引入疏散熵对疏散过程的影响

图8对比了有无疏散熵修正对疏散过程的影响。疏散初期，两个模型的差别不大，疏散个体的分布都较为分散，每个网格的疏散熵值较低，此时基本不进行疏散熵修正。疏散中后期，疏散熵修正的作用明显起来，无疏散熵修正的模型，人群尤其是群组倾向于选择图8(b)中的红色箭头对应的路径进行疏散，导致这条路变得拥挤；引入疏散熵修正后，后面的绿色和蓝色群组中的引导者引导各自群组成员，向图8(e)中的红色箭头对应的路径疏散，有效避免了混乱拥挤，提高了疏散效率，也增加了疏散安全性，一定程度上避免了因拥堵造成的二次伤害。

图8 疏散熵修正对疏散过程的影响

图9(a)为疏散时间与总疏散熵值的关系，反映整体混乱程度的变化趋势，图9(b)为疏散时间与个体分布网格平均疏散熵值的关系，反映局部混乱程度的变化趋势。下面分别分析总疏散熵值的变化趋势、个体分布网格平均疏散熵值的变化趋势、以及疏散熵修正对两者的影响。

图9 疏散熵修正对疏散混乱程度的影响

总疏散熵值在疏散前期迅速升高，中期在较高值处波动，后期逐渐降低。这是因为疏散前期群组成员迅速向各自的引导者靠近，运动方向不一致导致整体的混乱程度迅速上升；疏散中期人群逐渐聚集到出口附近，个体与个体、个体与障碍物相互作用，混乱程度较高；疏散后期随着人数的减少总熵值逐渐降低。

个体分布网格的平均疏散熵值在疏散前期上升缓慢，中期持续波动并略微升高，后期剧烈波动下降。这是因为疏散前期人群整体分散，局部混乱程度较低；随着人群的聚集，局部混乱程度升高；疏散后期人数较少且分布集中，局部混乱程度的变化变得敏感，波动剧烈。

结合两图来看，疏散前期，由于疏散熵修正未发挥作用，曲线高度重合；疏散中期，相比未引入疏散熵修正的模型，引入疏散熵修正的模型降低了混乱程度，局部混乱程度降低的更为明显，这是因为经过速度修正后，疏散个体的分布更加均匀化，减轻了局部的拥堵混乱程度；疏散后期，引入疏散熵修正的模型剩余个体更少，整体混乱程度和局部混乱程度均低于未引入疏散熵修正的模型。