文化算法与微粒群算法结合的人群疏散仿真方法及系统

摘要

本发明公开了一种文化算法与微粒群算法结合的人群疏散仿真方法及系统，该方法包括构建疏散场景三维模型，查找疏散场景的所有出口；将待疏散人群存储至种群空间并进行分组，筛选各组中最接近出口位置的个体作为各群组的引领个体并存储至信念空间；利用文化算法来构建用于关联信念空间与种群空间的导航；将引领个体当前位置传给导航，由导航规划出引领个体当前位置到达相应出口的最短路径并计算出引领个体的下一位置，传递给引领个体；将导航给出的下一位置作为目标，执行跟随引领个体的微粒群算法，并把移动后引领个体的位置反馈给导航：若引领个体到达相应出口，则重新筛选各群组的引领个体并存储至信念空间，直至各群组中无个体。

说明书

技术领域

本发明属于人群疏散计算仿真领域，尤其涉及一种文化算法与微粒群算法结合的人群疏散仿真方法及系统。

背景技术

近年来，随着社会经济的高速发展，各种聚集了大量人群的大型公共活动不断增多，这其中的安全问题引起了越来越多的关注。突发事件下的人群疏散运动是一个非常复杂的过程。组织人员进行疏散实验，虽然针对性强，获得的信息量大，但是实验费用和人员安全问题是不可回避的，所以计算机仿真模拟成为研究突发事件下人群疏散的最主要方法。

文化算法是由Reynolds于1994年提出的一个新的进化计算框架，由群体空间和信念空间两大部分组成，其重要思想就在于从进化的种群中获取待解决问题的经验知识，并反馈这些经验知识来指导搜索过程，从而提高搜索效率。

微粒群优化算法源于1987年Reynolds对鸟群社会系统boids(类鸟群)的仿真研究。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：

(1)避免与相邻的鸟发生碰撞冲突；

(2)尽量与自己周围的鸟在速度上保持协调和一致；

(3)尽量试图向自己所认为的群体中靠近。

仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。

常用的人群疏散仿真模型有宏观模型和微观模型，宏观模型把疏散人群作为为一个整体对待，疏散速度快，但是不能真实地对人群疏散运动仿真。微观模型要为每个疏散个体都作全局运动规划，计算开销太大，由于疏散人群数量大，每个个体计算路径导致的速度又过慢，这种微观模型往往只能用于处理较小规模的群体，并且在实时计算环境中很难应用。

发明内容

为了解决现有技术的缺点，本发明提供一种文化算法与微粒群算法结合的人群疏散仿真方法及系统。本发明结合宏观模型和微观模型的优点，弥补两种模型在仿真大规模人群疏散时的不足，在疏散场景的导航的引导下分组疏散，能够有效提高公共场所中通道的利用率以及危机情况下的人员安全性，有利于设计疏散预案，为真实的疏散演练提供帮助。

为实现上述目的，本发明采用以下技术方案：

一种文化算法与微粒群算法结合的人群疏散仿真方法，包括：

步骤(1)：获取疏散场景参数，构建疏散场景三维模型；在疏散场景三维模型中，查找疏散场景的所有出口；

步骤(2)：将疏散场景中的待疏散人群存储至种群空间，根据个体间关系和距离出口的位置将待疏散人群划分成若干个群组，筛选各组中最接近出口位置的个体作为各群组的引领个体并存储至信念空间；

步骤(3)：利用文化算法来构建用于关联信念空间与种群空间的导航，其中，导航的数量与群组数量一致，且导航与引领个体一一对应；

步骤(4)：将引领个体当前位置传给导航，由导航规划出引领个体当前位置到达相应出口的最短路径并计算出引领个体的下一位置，还通过文化算法的交互机制将引领个体的下一位置传递给引领个体；

步骤(5)：将导航给出的下一位置作为目标，执行跟随引领个体的微粒群算法，并把移动后引领个体的位置反馈给导航：若引领个体到达相应出口，则重新筛选各群组的引领个体并存储至信念空间，返回步骤(4)，直至各群组中无个体，结束人群疏散仿真。

本发明将文化算法与微粒群算法结合，利用文化算法的框架建立对信念空间与群体空间的关联与交互。其中，信息空间由导航和知识库组成，具有到达出口最短路径，各出口的拥塞度等知识。这样建立了疏散人群与导航、知识库之间的有机联系，避免了疏散人群盲目的移动。

在每个出口处配置一个用于统计从相应出口疏散的个体数量的计数器。

若引领个体到达相应出口，则相应出口处的计数器加1。

导航还根据出口处的计数器的数值，得到出口的拥挤度；其中，拥堵度等于正常情况下通过相应出口的预设个数与出口相匹配的群组内个体总数的比值。

所述步骤(4)中，导航规划出引领个体当前位置到达相应出口的最短路径的过程为：

将引领个体的当前位置作为起始点，相应出口作为目标点，将起始点到达目标点的距离乘以第一权值系数，得到加权的距离；

将相应出口的拥挤度乘以第二权值系数，得到加权的人群流量；

以加权的距离+加权的人群流量作为花费值，采用D*Lite算法动态获取当前位置到相应出口的最短路径。

本发明利用文化算法作为框架建立导航与引领者及带领的群组之间的连接，交流传递信息，根据群组中最接近出口的位置的个体及出口的拥堵情况，动态确定下一步移动目标，利用改进的微粒群算法实现群组中个体跟随目标的移动。因为大部分的计算针对群组而非个体，计算量大大减少，可以实时地模拟规模较大的群体，为疏散演练提供帮助。

在最短路径上选取下一个位置作为相应组的目标。

一种文化算法与微粒群算法结合的人群疏散仿真系统，包括：

模型构建模块，其被配置为获取疏散场景参数，构建疏散场景三维模型；在疏散场景三维模型中，查找疏散场景的所有出口；

引领个体筛选模块，其被配置为将疏散场景中的待疏散人群存储至种群空间，根据个体间关系和距离出口的位置将待疏散人群划分成若干个群组，筛选各群组中最接近出口位置的个体作为各群组的引领个体并存储至信念空间；

导航构建模块，其被配置为利用文化算法来构建用于关联信念空间与种群空间的导航，其中，导航的数量与群组数量一致，且导航与引领个体一一对应；

路径规划模块，其被配置为将引领个体当前位置传给导航，导航规划出引领个体当前位置到达相应出口的最短路径并计算出引领个体的下一位置，还通过文化算法的交互机制将引领个体的下一位置传递给引领个体；

路径执行模块，其被配置为将导航给出的下一位置作为目标，执行跟随引领个体的微粒群算法，并把移动后引领个体的位置反馈给导航：若引领个体到达相应出口，则重新筛选各群组的引领个体并存储至信念空间，直至各群组中无个体，结束人群疏散仿真。

该系统还包括计数器，其配置在每个出口处，用于统计从相应出口疏散的个体数量。

导航还配置为根据出口处的计数器的数值，得到出口的拥挤度；其中，拥堵度等于正常情况下通过相应出口的预设个数与出口相匹配的群组内个体总数的比值。

所述路径规划模块还包括：

加权的距离计算模块，其被配置为将引领个体的当前位置作为起始点，相应出口作为目标点，将起始点到达目标点的距离乘以第一权值系数，得到加权的距离；

加权的人群流量计算模块，其被配置为将相应出口的拥挤度乘以第二权值系数，得到加权的人群流量；

最短路径计算模块，其被配置为以加权的距离+加权的人群流量作为花费值，采用D*Lite算法动态获取当前位置到相应出口的最短路径。

本发明的有益效果为：

(1)本发明将文化算法与微粒群算法结合，利用文化算法的框架建立对信念空间与群体空间的关联与交互。信息空间由导航和知识库组成，具有到达出口最短路径，各出口的拥塞度等知识。这样，建立了疏散人群与导航、知识库之间的有机联系，避免了疏散人群盲目的移动。

(2)本发明借鉴了微粒群算法模拟鸟群飞行的规则，可以有效的实现群组移动，大大提高运行效率。人群疏散仿真时，只需要通过导航为每个组的引领个体规划路径，组内其他成员执行微粒群算法在引领个体的引导下移动。这就解决了大规模人群疏散计算机仿真系统为每个个体计算路径导致的速度过慢的问题。

(3)本发明结合宏观模型和微观模型的优点，建立一种混合模型，弥补两种模型在仿真大规模人群疏散时的不足，并采用该模型实现人群疏散仿真；在熟悉场景的导航的引导下分组疏散，能够有效提高公共场所中通道的利用率以及危机情况下的人员安全性，有利于设计疏散预案，为真实的疏散演练提供帮助。

(4)本发明的该方法将待疏散人群分为群组，群组内选出疏散引导者，引导者通过导航与知识库交互，获取快速到达出口的知识。利用文化算法作为框架建立导航与引领者及带领的群组之间的连接，交流传递信息，根据群组中最接近出口的位置的个体及出口的拥堵情况，动态确定下一步移动目标，利用改进的微粒群算法实现群组中个体跟随目标的移动。因为大部分的计算针对群组而非个体，计算量大大减少，可以实时地模拟规模较大的群体，为疏散演练提供帮助。

附图说明

图1是本发明的文化算法与微粒群算法结合的人群疏散仿真方法流程示意图；

图2是本发明的文化算法与微粒群算法结合的人群疏散仿真系统结构示意图；

图3是本发明的路径规划模块结构示意图；

图4是在利用文化算法来构建用于关联信念空间与种群空间的导航的示意图；

图5是一个初始化后的人群随机分布的情况；

图6是各群组在引领个体的带领下向出口移动的状况；

图7是各群组在引领个体的带领下接近出口状况。

具体实施方式

下面结合附图与实施例对本发明做进一步说明：

图1是本发明的文化算法与微粒群算法结合的人群疏散仿真方法流程示意图，如图所示的文化算法与微粒群算法结合的人群疏散仿真方法，至少包括以下五个步骤：

步骤(1)：获取疏散场景参数，构建疏散场景三维模型；在疏散场景三维模型中，查找疏散场景的所有出口。

在具体实施过程中，疏散场景参数包括疏散场景形状以及建筑结构信息。在本实施例中，通过疏散场景形状以及建筑结构信息进行提取疏散场景的特征，进而得到疏散场景的三维模型。

根据疏散场景的出口特征，在疏散场景三维模型中能够查询到疏散场景的所有出口。

步骤(2)：将疏散场景中的待疏散人群存储至种群空间，根据个体间关系和距离出口的位置将待疏散人群划分成若干个群组，筛选各组中最接近出口位置的个体作为各群组的引领个体并存储至信念空间。

以人群数据集P＝{p_i,i＝1,2,…,N}为例：

其中，p_i＝(p_i1,p_i2,…,p_im)表示数据集中第i个个体，p_ij表示第i个个体的第j个属性。

人群个体间的关系为：

对于两个个体p_l和p_m，关系值表示两个个体之间的紧密程度，取值为0到1，用rel(p_l，p_m)表示。

如果两个个体无关系，则关系值为0，如果是母子或恋人关系，则关系值趋近于1。为了反映紧急疏散时，查找导游或者一个团体的领导者，把旅游团队中的每个人与导游都建立关系，并且关系为1，同样的道理，每个集体的个体与领队之间，也都建立关系，并且关系值为1。待疏散人群数据集的个体之间的关系取值范围为：

步骤(3)：利用文化算法来构建用于关联信念空间与种群空间的导航，其中，导航的数量与群组数量一致，且导航与引领个体一一对应。

步骤(4)：将引领个体当前位置传给导航，由导航规划出引领个体当前位置到达相应出口的最短路径并计算出引领个体的下一位置，还通过文化算法的交互机制将引领个体的下一位置传递给引领个体。

在每个出口处配置一个用于统计从相应出口疏散的个体数量的计数器。

若引领个体到达相应出口，则相应出口处的计数器加1。

导航还根据出口处的计数器的数值，得到出口的拥挤度；其中，拥堵度等于正常情况下通过相应出口的预设个数与出口相匹配的群组内个体总数的比值。

在步骤(4)的导航规划出引领个体当前位置到达相应出口的最短路径的具体实施过程中：

将引领个体的当前位置作为起始点，相应出口作为目标点，将起始点到达目标点的距离乘以第一权值系数，得到加权的距离；

将相应出口的拥挤度乘以第二权值系数，得到加权的人群流量；

以加权的距离+加权的人群流量作为花费值，采用D*Lite算法动态获取当前位置到相应出口的最短路径。

优选地，第一权值系数和第二权值系数的取值均为0.5。

本发明利用文化算法作为框架建立导航与引领者及带领的群组之间的连接，交流传递信息，根据群组中最接近出口的位置的个体及出口的拥堵情况，动态确定下一步移动目标，利用改进的微粒群算法实现群组中个体跟随目标的移动。因为大部分的计算针对群组而非个体，计算量大大减少，可以实时地模拟规模较大的群体，为疏散演练提供帮助。

本实施例中，在最短路径上选取下一个位置作为相应组的目标。

步骤(5)：将导航给出的下一位置作为目标，执行跟随引领个体的微粒群算法，并把移动后引领个体的位置反馈给导航：

若引领个体到达相应出口，则重新筛选各群组的引领个体并存储至信念空间，返回步骤(4)，直至各群组中无个体，结束人群疏散仿真。

在步骤(5)的具体实施过程中，跟随引领个体的微粒群算法如下：

(1)设置参数：设置跟随微粒种群规模为组中个体数-1，引领微粒的目标位置为对应的导航给出的下一个位置，微粒群的运动空间范围为场景限制的区间范围，微粒运动速度的最大值，加速常数c₁、c₂；

(2)对于每一个微粒

本发明将文化算法与微粒群算法结合，利用文化算法的框架建立对信念空间与群体空间的关联与交互。其中，信息空间由导航和知识库组成，具有到达出口最短路径，各出口的拥塞度等知识。这样建立了疏散人群与导航、知识库之间的有机联系，避免了疏散人群盲目的移动。

本发明的该方法将待疏散人群分为群组，群组内选出疏散引导者，引导者通过导航与知识库交互，获取快速到达出口的知识。利用文化算法作为框架建立导航与引领者及带领的群组之间的连接，交流传递信息，根据群组中最接近出口的位置的个体及出口的拥堵情况，动态确定下一步移动目标，利用改进的微粒群算法实现群组中个体跟随目标的移动。因为大部分的计算针对群组而非个体，计算量大大减少，可以实时地模拟规模较大的群体，为疏散演练提供帮助。

图2是本发明的文化算法与微粒群算法结合的人群疏散仿真系统结构示意图，如图所示的文化算法与微粒群算法结合的人群疏散仿真系统，包括模型构建模块、引领个体筛选模块、导航构建模块、路径规划模块和路径执行模块这五个模块。

其中：

(1)模型构建模块，其被配置为获取疏散场景参数，构建疏散场景三维模型；在疏散场景三维模型中，查找疏散场景的所有出口。

(2)引领个体筛选模块，其被配置为将疏散场景中的待疏散人群存储至种群空间，根据个体间关系和距离出口的位置将待疏散人群划分成若干个群组，筛选各群组中最接近出口位置的个体作为各群组的引领个体并存储至信念空间。

(3)导航构建模块，其被配置为利用文化算法来构建用于关联信念空间与种群空间的导航，其中，导航的数量与群组数量一致，且导航与引领个体一一对应。

(4)路径规划模块，其被配置为将引领个体当前位置传给导航，导航规划出引领个体当前位置到达相应出口的最短路径并计算出引领个体的下一位置，还通过文化算法的交互机制将引领个体的下一位置传递给引领个体。

图3是本实施例的路径规划模块结构示意图，如图所示的路径规划模块包括：

加权的距离计算模块，其被配置为将引领个体的当前位置作为起始点，相应出口作为目标点，将起始点到达目标点的距离乘以第一权值系数，得到加权的距离；

加权的人群流量计算模块，其被配置为将相应出口的拥挤度乘以第二权值系数，得到加权的人群流量；

最短路径计算模块，其被配置为以加权的距离+加权的人群流量作为花费值，采用D*Lite算法动态获取当前位置到相应出口的最短路径。

(5)路径执行模块，其被配置为将导航给出的下一位置作为目标，执行跟随引领个体的微粒群算法，并把移动后引领个体的位置反馈给导航：若引领个体到达相应出口，则重新筛选各群组的引领个体并存储至信念空间，直至各群组中无个体，结束人群疏散仿真。

该系统还包括计数器，其配置在每个出口处，用于统计从相应出口疏散的个体数量。

导航还配置为根据出口处的计数器的数值，得到出口的拥挤度；其中，拥堵度等于正常情况下通过相应出口的预设个数与出口相匹配的群组内个体总数的比值。

本发明将文化算法与微粒群算法结合，利用文化算法的框架建立对信念空间与群体空间的关联与交互。信息空间由导航和知识库组成，具有到达出口最短路径，各出口的拥塞度等知识。这样，建立了疏散人群与导航、知识库之间的有机联系，避免了疏散人群盲目的移动；

本发明借鉴了微粒群算法模拟鸟群飞行的规则，可以有效的实现群组移动，大大提高运行效率。人群疏散仿真时，只需要通过导航为每个组的引领个体规划路径，组内其他成员执行微粒群算法在引领个体的引导下移动。这就解决了大规模人群疏散计算机仿真系统为每个个体计算路径导致的速度过慢的问题。

本发明结合宏观模型和微观模型的优点，建立一种混合模型，弥补两种模型在仿真大规模人群疏散时的不足，并采用该模型实现人群疏散仿真；在熟悉场景的导航的引导下分组疏散，能够有效提高公共场所中通道的利用率以及危机情况下的人员安全性，有利于设计疏散预案，为真实的疏散演练提供帮助。

下面提供一个仿真实施例：

由300个人在300×250的平面区域上进行计算机人群疏散仿真，如图4-图7所示。图4是在利用文化算法来构建用于关联信念空间与种群空间的导航的示意图；图5是一个初始化后的人群随机分布的情况；图6是各群组在引领个体的带领下向出口移动的状况；图7是各群组在引领个体的带领下接近出口状况。由图6和图7可以看出，各组根据离各出口的最短距离及拥堵状况有引导的疏散，较好的避免了在出口处由于拥堵形成的拱形。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。