一种基于势能驱动元胞蚁群算法的室内疏散仿真优化方法

技术领域

本发明属于智能系统建模及优化领域，具体的为一种基于势能驱动元胞蚁群算法的室内 疏散仿真优化方法。

背景技术

疏散问题可以根据疏散场景抽象成为一个复杂的大规模动态网络，最简单直接的方法是 利用传统的最短路径算法求解，但是这种算法适用于小规模静态路网的路径寻优，而对于大 规模动态网络，当网络规模增大时，算法的复杂度就会迅速增加，这种传统的最短路径算法 的运算能力缺陷导致无法满足系统的需求。由于智能算法计算时间不会随着网络规模的增大 而明显增加，相对传统的最短路径算法而言，更加适合解决建筑物人员疏散这种大规模网络 的路径搜索问题。

蚁群优化算法(Ant Colony Optimization:ACO)是Colorni和Dorigo等在20世纪90年 代初提出的一种新型分布式智能仿生类算法，它模拟和借鉴了现实世界中蚂蚁种群的觅食行 为特征。蚂蚁在运动时会在通过的路径上释放一种特殊的分泌物──信息素来寻找路径。当 它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径有关的 信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候， 选择信息量较大的路径概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量 越来越大，而其他路径上的信息量却会随时间的流逝消减，最终整个蚁群会找出最优路径。 该方法具有可并行性、寻优能力强、适应性强和易于其他算法结合等优点，但也存在一定缺 陷，如搜索时间长、对复杂问题的描述能力不强和容易出现搜索停滞等等。

人工势能场(Artificial Potential Field:APF)是一种模拟电势场分布的规划方法, 其概念首先由Khatib提出，并成功应用于机械臂避碰。人工势能场的思想借鉴了“物体运 动一般由势能较高的位置向势能较低的位置运动”这一物理规律，根据人员对建筑物内部及 出口的熟悉程度、障碍物的分布、离出口的距离、火灾等外界因素的影响等初始化网格势能。 其特点是规划速度快，能够保证路径的安全，但由于势函数存在引力和斥力相等的局部极小 点，会使算法停滞而无法抵达目标位置，又由于没有代价函数对航迹优劣进行衡量而不能保 证路径的最优。

人工势能场的物理特性与紧急情况下人员的运动规律非常相近，而蚁群算法所表现出的 自组织性、群体性也非常适合应急疏散问题建模，蚂蚁在觅食过程中通过释放信息素来进行 交流和消息互通，以帮助同伴更快地找到食物，这与人在疏散过程中的相互协作具有很大的 相似性。用蚂蚁代表疏散中的个体，蚂蚁可以通过势能值的负梯度方向找到通往安全出口的 路径，能够加快疏散进程，同时优化结果克服了人工势能场的局部极小问题。

发明内容

为了克服现有技术的不足，本发明提出了一种基于势能驱动元胞蚁群算法的室内疏散仿 真优化方法，一方面利用势能场的物理特性和蚁群算法的自组织性、正反馈机制从微观上模 拟了人员的运动规律，另一方面在仿真的同时完成了人员疏散路径的优化，解决了人工势能 场的局部极小问题，提高了疏散效率。

本发明的技术方案是，一种基于势能驱动元胞蚁群算法的室内疏散仿真优化方法，包括 如下步骤：

步骤1.建立二维元胞自动机的建筑物疏散模型；

二维元胞自动机C定义为以下四元组：

C＝(D₂,S,N,f)

其中，D₂为二维元胞空间，S是有限状态机集合，对于位于格位r上的元胞在t时刻的 状态可以表示为：

S＝{S₁(r,t),S₂(r,t),…,S_z(r,t)}

式中S_z(r,t)表示格位r上的元胞在t时间的第z个状态；N为以r为中心元胞的邻域， N＝{N₁,N₂,…,N_n}是D₂的有限的序列子集，n为格位r上的元胞的邻居元胞个数，f为中心 元胞r与邻居间的移动规则；

步骤2.设置模型参数；包括蚁群算法相关参数和势能场增益系数，疏散人员个数m、蚁 群算法的信息素和启发式信息重要程度α和β，信息素挥发系数q，势能场增益系数ξ₁和ξ₂， 信息素强度初始值Q，算法的最大迭代次数T；

步骤3.初始化疏散场景；根据建筑物内布局对二维元胞空间进行疏散场景模拟，随机设 置障碍物的位置和大小，根据建筑物真实场景标注出口元胞位置，随机设置疏散人员在疏散 开始时所处元胞位置，根据每个元胞是被障碍物、人员占据还是空闲设置其初始状态，初始 化元胞之间路径上的信息素强度为步骤2设置的Q，将所有人员状态标注为人“未疏散”；

步骤4.计算场景的人工势能场；

根据步骤3人员在元胞中的分布，按以下公式计算每个元胞的总势能：

$U_{\mathrm{att}}\left(i\right)=\frac{1}{2}{\xi }_1{\rho }_g^2\left(i\right)---\left(1\right)$

$U_{\mathrm{rep}}\left(i\right)=\left(\begin{array}{cc}\frac{1}{2}{\xi }_2{(\frac{1}{\rho \left(i\right)}-\frac{1}{{\rho }_0})}^2,& \rho \left(i\right)\le {\rho }_0\\ 0,& \rho \left(i\right)>{\rho }_0\end{array}\right)---\left(2\right)$

式中U_att(i)和U_rep(i)分别是元胞i处的引力势能和斥力势能，ρ_g(i)为元胞i到目标元胞i_g的欧式距离，ξ₁,ξ₂是相应的势能场增益系数,ρ(i)是人员k与障碍物之间的最近距离,ρ₀为障 碍物对人产生影响的最大距离；

人员在元胞i处受到的引力和斥力分别是相应势能的负梯度:

$\overline{F_{\mathrm{att}}}\left(i\right)=-\mathrm{grad}\left[U_{\mathrm{att}}\left(i\right)\right]={\xi }_1{\rho }_g\left(i\right)---\left(3\right)$

$\overline{F_{\mathrm{rep}}}\left(i\right)=-\mathrm{grad}\left[U_{\mathrm{rep}}\left(i\right)\right]=\left(\begin{array}{cc}\frac{{\xi }_2}{{\rho }^2\left(i\right)}(\frac{1}{\rho \left(i\right)}-\frac{1}{{\rho }_0})▿\rho \left(i\right),& \rho \left(i\right)\le {\rho }_0\\ 0,& \rho \left(i\right)>{\rho }_0\end{array}\right)---\left(4\right)$

其中，-grad[U_att(i)]和-grad[U_rep(i)]分别表示元胞i点处吸引力势能的负梯度和排斥力势 能的负梯度，ξ₁,ξ₂是相应的势能场增益系数,ρ_g(i)为元胞i到目标元胞i_g的欧式距离，▽ρ(i) 表示障碍物指向元胞i的单位向量；

因此，综合因素对人员在元胞i处产生的总势能可以表示为：

U_i＝ΣU_att(i)+ΣU_rep(i)     (5)

人员在引力和斥力的综合作用下，沿着势场力方向移动。人工势能场的引入能够有效模 拟人员疏散中的驱动力，使人员避开已知的障碍物，并到达出口位置。

步骤5.根据步骤4得到的人员在当前可移动元胞的总势能值，计算可移动路径上的启发 式信息；

在t时刻，人员由元胞i移动到元胞j上，利用人工势能场对出口和障碍物的感知能力， 对蚁群算法的启发信息η_ij(t)进行改进，即启发式信息由势能和人员距出口的距离共同决定， 引导人员避开障碍物并快速靠近出口，其公式为：

${\eta }_{\mathrm{ij}}\left(t\right)=\frac{1}{\min \left\{d_{j,\mathrm{exits}}\right|j\in J_i\}\times U_i}---\left(6\right)$

其中，η_ij(t)为元胞i与元胞j之间路径上的启发式信息，d_j,exits是元胞j到 出口的距离，min{d_j,exits|j∈J_i}表示元胞j距离出口的最短欧式距离，J_i是元胞 i附近的邻居集合，U_i为步骤4得到的元胞i的总势能值；

步骤6.设置迭代计数器NC＝1；

步骤7.从所有疏散人员中随机选择一名人员作为第一个开始疏散，设k＝1；

步骤8.判断第k个人员的当前状态是否为“已疏散”状态，若是则执行步骤15，否则执 行下一步；

步骤9.根据第k个人员所在的元胞，得到其邻居元胞的集合；

步骤10.根据步骤9得到的邻居元胞集合，判断其当前时刻的状态，邻居元胞为空闲可 移动点或是被占位不可移动点，根据邻居元胞状态和禁忌规则判断第k个人员可移动的元胞 邻居集；

步骤11.根据步骤10得到的可移动元胞邻居集，判断第k个人员是否有可移动的元胞， 若有，执行下一步；若没有则在这一时刻停留在当前元胞位置，执行步骤15；

步骤12.根据当前时刻的第k个人员所处元胞与邻居元胞路径上的信息素强度和步骤5 得到的启发式信息，计算第k个人员选择邻居可移动元胞的概率；

在t时刻，第k个人员由元胞i转移到元胞j的状态转移概率公式如下所示：

式中,是人员k由元胞i转移到元胞j的转移概率，τ_ij(t)是元胞i与元胞j之间路 径上的信息素强度，η_ij(t)是元胞i与元胞j之间路径上的启发式信息，α和β是常量参数， 用来表示信息素和启发信息的重要程度，J_i表示元胞i附近的邻居集合；代表元胞i到所有邻居元胞的启发式信息和信息素乘机的累加和；

步骤13.根据步骤12得到的转移概率得出第k个人员的转移概率最大的邻居元胞，将第 k个人员移动到此元胞处，更新该元胞的状态，将该元胞加入该人员的疏散路径；

步骤14.根据步骤13得到的第k个人员的最新移动到的元胞，判断人员k是否达到出口， 若已到达，则标记该人员为“已疏散”状态，否则标记该人员为“未疏散”状态；

步骤15.疏散人员计数加1，即k＝k+1，对下一个人员进行可移动元胞搜索；

步骤16.如果k≤m，则说明还未遍历所有疏散人员，返回到步骤8，否则表明所有人员 完成了一个时间步的搜索，执行下一步；

步骤17.判断所有人员的当前状态是否都为“已疏散”状态，若是则表明所有人员完成 了从初始元胞到出口的路径搜索，即本轮疏散模拟迭代完成，执行下一步，否则返回步骤7；

步骤18.根据步骤13得到的每一个人员从其初始元胞到出口的疏散路径，按照公式 (8)-(10)来更新每个人员疏散路径上元胞之间的信息素强度：

τ_ij(t+Δt)＝(1-q)×τ_ij(t)+Δτ_ij(t+Δt)     (8)

$\Delta {\tau }_{\mathrm{ij}}(t+\mathrm{\Delta t})=\underset{k=1}{\overset{m}{\Sigma }}{\tau }_{\mathrm{ij}}^k(t+\mathrm{\Delta t})---\left(9\right)$

${\tau }_{\mathrm{ij}}^k(t+\mathrm{\Delta t})=\left(\begin{array}{c}\frac{Q}{L_k},\mathrm{edge}(i,j)\in {\mathrm{path}}_k\\ 0,\mathrm{otherwise}\end{array}\right)---\left(10\right)$

其中，τ_ij(t)表示t时刻元胞i与元胞j之间路径上的信息素强度函数，Q为常数，是步骤 2设置的信息素强度初始值，L_k为k个人员第在本次循环中所走的路径长度，edge(i,j)代表 元胞i与元胞j之间的路径，path_k是人员k经过的路径；q为步骤2设置的信息素强度挥发 系数；当元胞之间路径上的信息素强度越大，人员选择这条路径的概率就会越大。由于这种 正反馈机制,疏散人员最终会被吸引到最短疏散路线上；

步骤19.迭代计数器NC加1，即NC＝NC+1；

步骤20.当NC≤T，每一个人员返回步骤3设置的人员各自的初始元胞，重复步骤7-19， 直到NC＞T，迭代结束，执行下一步；

步骤21.输出最优疏散路径和疏散时间,演示最优疏散方案。

优选的，所述的步骤1中以f为中心元胞r与邻居间的移动规则采用Moore型邻居定义， 以中心元胞的上、下、左、右、左上、左下、右上、右下这八个方向上的元胞为其邻居,此时 邻居半径同样为r＝l,行人可以在同一时间向这八个方向移动到达邻近空闲元胞。

优选的，所述的步骤9中得到其邻居元胞的位置集合为第k个人员所在位置的上，下， 左，右，左上，左下，右上，右下8个方向的元胞。

优选的，本方法的参数设置为：蚁群算法参数α＝1，β＝2，ρ＝0.5，Q＝1，最大循环 次数T＝100；势能场增益系数ξ₁＝2,ξ₂＝1。

优选的，所述的步骤10中的禁忌规则为：

(1)一个元胞只能容纳一个人员；

(2)在建筑物的人员可以向空闲元胞和出口移动，从出口的元胞不能向建筑物内的元 胞移动；

(3)若多个人员同时竞争同一个空闲元胞,随机选择一人进入，其他人重新选择路径， 直到所有人员在网格上找到自己下一时刻唯一目标为止；

(4)当人员不能选择当前最优站位时,则在不考虑出口方向情况写选择一个次优元胞 作为站位；

(5)人员选择元胞不能是自己上一步所在的元胞，除非周围其他的元胞都不可被访问。

本发明与现有的技术相比具有以下优点：

1、本发明采用元胞来划分疏散场景，能够更好地从微观上模拟人员疏散过程。

2、本发明采用人工势能场的思想，利用势能负梯度方向来完成路径规划，人员在出口产生的 吸引力和障碍物产生的排斥力的综合作用下，沿着势能下降的方向移动，更加符合疏散真实 过程。

3、本发明在势能场的基础上引入蚁群算法，利用势能知道蚂蚁的搜索路径，能够更快完成疏 散路径寻优，提高疏散效率。

4、本发明相对于其他优化算法，拥有更好的收敛速度和收敛效果。

附图说明

图1是本发明的实验流程图；

图2是本发明的500人疏散过程效果图；

图3是本发明的500人路径的算法迭代关系图；

图4是本发明的不同人数的疏散路径长度图。

具体实施方式

1、建立二维元胞自动机的建筑物疏散模型：

元胞自动机可以定义为一个四元组：

C＝(D₂,S,N,f)

其中D₂为2维元胞空间；S是有限状态机集合，对于位于格位r上的元胞在t时刻的状 态可以表示为：

S＝{S₁(r,t),S₂(r,t),…,S_k(r,t)}

式中S_k(r,t)表示格位r上的元胞在t时间的第k个状态；N为以r为中心元胞的邻域， N＝{N₁,N₂,…,N_n}是D₂的有限的序列子集。

f为中心元胞r与邻居间的移动规则，这里采用Moore型邻居定义，即中心元胞的上、 下、左、右、左上、左下、右上、右下这八个方向上的元胞为其邻居,此时邻居半径同样为 r＝l,此邻居模型通常也被称之为八邻域。行人可以在同一时间向这八个方向移动。根据演化 规则，即一个元胞下一时刻的状态取决于这一时刻本身状态和它的邻居元胞的状态，初始时 刻所有元胞状态各不相同，每个元胞在t+1时刻的状态值是由t时刻自身状态和邻居状态组 合共同来确定的。

用元胞自动机来模拟室内人群疏散过程，就是用计算机技术去模拟具体某一个场景下的 人群运动，在此模型下可以将教学楼的平面空间划分成大小相等的网格，这样每个网格就对 应现实场景中的一小部分，各个元胞具有不同的状态和属性。在教学楼疏散中，每一层可以 视为一个二维平面，适合建立二维的元胞自动机模型，即把环境空间分割为许多规则的方形 网格，每个网格代表一个元胞。将建筑物进行网格划分，分为能容纳一个人的大小相等的网 格，生成二维元胞空间。每个元胞对应0.5m×0.5m的空间是人流中典型的人员空间分配。在 任一时刻，元胞的状态为被障碍物占据、被行人占据或者空闲，每个元胞只能容纳一个疏散 个体，并且每个个体可以在单位时间内向上，下，左，右，左上，左下，右上，右下8个方 向中的一个方向移动，在一个时间内可以到达邻近空闲元胞。

2、设置模型参数和初始化疏散场景模型的参数包括蚁群算法相关参数和势能场增益系 数，疏散场景的设置包括障碍物的位置和大小设置，人员初始分布设置，初始化包括元胞和 人员状态初始化以及蚁群算法中信息素的初始化。

3、引入人工势能场对疏散场景进行描述：

将疏散场景中的人员、障碍物放置在网格中，标注出口元胞。场景中的出口产生引力场， 墙壁、桌椅等障碍物产生斥力场。人员在引力和斥力的综合作用下，沿着势场力方向移动。 人工势能场能够有效模拟人员疏散中的驱动力，使人员避开已知的障碍物，并到达出口位置。

4、势能驱动的启发式信息：为使人员疏散过程具有智能性和启发性，元胞之间的移动路 径具有启发式信息，其大小由元胞节点的势能和相对于出口的距离共同决定，从而引导行人 避开障碍去并快速靠近出口。

5、利用带有势能信息启发的蚁群算法进行人员疏散优化：

蚁群算法是M.Dorigo受到自然界中真实蚂蚁集体行为的启发提出的。蚁群之间利用信息 素交流以及正反馈机制能够很快找到食物和蚁巢最短路径。所谓的正反馈是指一条路径上经 过的蚂蚁数量越多，留下的信息素就会越多，蚂蚁选择某条路径的概率会随着之前蚂蚁选择 该条路径的增多而增大。

在利用蚁群算法进行疏散优化时，疏散过程中的人员代表蚁群算法中的蚂蚁，人员根据 当前邻居元胞的状态判断能够移动的元胞位置，从这些可选的元胞中按照概率选择一个元胞 作为下一个时刻的位置，同时在该路径上释放一定量的信息素，其他人员在选择路径的时候 一方面受到势能驱动启发式信息的引导，另一方面能够感受到其他人员在该路径上释放的信 息素浓度，从而在个人判断和环境感知上做出综合决策。当所有人员到达出口，完成一次疏 散过程，演化若干次后，比较得到的疏散结果，从而得出最优疏散方案。

图1和图2是本发明的系统架构图和实验流程图的主要步骤，从图中可以看出其具体实 现过程如下：

步骤1.建立二维元胞自动机的建筑物疏散模型；

二维元胞自动机C可以定义为以下四元组：

C＝(D₂,S,N,f)

其中，D₂为2维元胞空间；S是有限状态机集合，对于位于格位r上的元胞在t时刻的 状态可以表示为：

S＝{S₁(r,t),S₂(r,t),…,S_z(r,t)}

式中S_z(r,t)表示格位r上的元胞在t时间的第z个状态；N为以r为中心元胞的邻域， N＝{N₁,N₂,…,N_n}是D₂的有限的序列子集，n为格位r上的元胞的邻居元胞个数。

f为中心元胞r与邻居间的移动规则，这里采用Moore型邻居定义，即中心元胞的上、 下、左、右、左上、左下、右上、右下这八个方向上的元胞为其邻居,此时邻居半径同样为 r＝l,此邻居模型通常也被称之为八邻域。行人可以在同一时间向这八个方向移动到达邻近空 闲元胞。

用元胞自动机来模拟室内人群疏散过程，就是用计算机技术去模拟具体某一个场景下的 人群运动，在此模型下可以将建筑物的平面空间划分成0.5m×0.5m大小相等的网格，每个网 格仅能容纳一个疏散个体，这样每个网格就对应现实场景中的一小部分，各个元胞具有不同 的状态和属性。在建筑物疏散中，每一层可以视为一个二维平面，适合建立二维的元胞自动 机模型，即把环境空间分割为许多规则的方形网格，每个网格代表一个元胞。在任一时刻， 元胞有三种可能的状态：被障碍物占据，被行人占据以及空闲。

步骤2.设置模型参数；

设置模型参数，包括蚁群算法相关参数和势能场增益系数，疏散人员个数m、蚁群算法 的信息素和启发式信息重要程度α和β，信息素挥发系数q，势能场增益系数ξ₁和ξ₂，信息 素强度初始值Q，算法的最大迭代次数T。

步骤3.初始化疏散场景；

根据建筑物内布局对二维元胞空间进行疏散场景模拟，随机设置障碍物的位置和大小(即 其所占元胞的数目)，根据建筑物真实场景标注出口元胞位置，疏散人员在疏散开始时所处 元胞位置是随机设置的，根据每个元胞是被障碍物、人员占据还是空闲设置其初始状态，初 始化元胞之间路径上的信息素强度为步骤2设置的Q，将所有人员状态标注为人“未疏散”。

步骤4.计算场景的人工势能场；

人工势能场是由Khatib提出的用于描述行人运动空间的特征结构，利用势场负梯度方向 来完成路径规划。区域内的出口产生引力场，墙壁、桌椅等障碍物产生斥力场。人员在引力 和斥力的综合作用下，沿着势场力方向移动。人工势能场能够有效模拟人员疏散中的驱动力， 使人员避开已知的障碍物，并到达出口位置。

根据步骤3人员在元胞中的分布，按以下公式计算每个元胞的总势能：

$U_{\mathrm{att}}\left(i\right)=\frac{1}{2}{\xi }_1{\rho }_g^2\left(i\right)---\left(1\right)$

$U_{\mathrm{rep}}\left(i\right)=\left(\begin{array}{cc}\frac{1}{2}{\xi }_2{(\frac{1}{\rho \left(i\right)}-\frac{1}{{\rho }_0})}^2,& \rho \left(i\right)\le {\rho }_0\\ 0,& \rho \left(i\right)>{\rho }_0\end{array}\right)---\left(2\right)$

式中U_att(i)和U_rep(i)分别是元胞i处的引力势能和斥力势能，ρ_g(i)为元胞i到目标元胞i_g的欧式距离，ξ₁,ξ₂是相应的势能场增益系数,ρ(i)是人员k与障碍物之间的最近距离,ρ₀为障 碍物对人产生影响的最大距离。

人员在元胞i处受到的引力和斥力分别是相应势能的负梯度:

$\overline{F_{\mathrm{att}}}\left(i\right)=-\mathrm{grad}\left[U_{\mathrm{att}}\left(i\right)\right]={\xi }_1{\rho }_g\left(i\right)---\left(3\right)$

$\overline{F_{\mathrm{rep}}}\left(i\right)=-\mathrm{grad}\left[U_{\mathrm{rep}}\left(i\right)\right]=\left(\begin{array}{cc}\frac{{\xi }_2}{{\rho }^2\left(i\right)}(\frac{1}{\rho \left(i\right)}-\frac{1}{{\rho }_0})▿\rho \left(i\right),& \rho \left(i\right)\le {\rho }_0\\ 0,& \rho \left(i\right)>{\rho }_0\end{array}\right)---\left(4\right)$

其中，-grad[U_att(i)]和-grad[U_rep(i)]分别表示元胞i点处吸引力势能的负梯度和排斥 力势能的负梯度，ξ₁,ξ₂是相应的势能场增益系数,ρ_g(i)为元胞i到目标元胞i_g的欧式 距离，▽ρ(i)表示障碍物指向元胞i的单位向量。

因此，综合因素对人员在元胞i处产生的总势能可以表示为：

U_i＝ΣU_att(i)+ΣU_rep(i)     (5)

步骤5.根据步骤4得到的人员在当前可移动元胞的总势能值，计算可移动路径上的启发 式信息；

在t时刻，人员由元胞i移动到元胞j上，利用人工势能场对出口和障碍物的感知能力， 对蚁群算法的启发信息η_ij(t)进行改进，引导人员寻找路径，其公式为式(6)：

${\eta }_{\mathrm{ij}}\left(t\right)=\frac{1}{\min \left\{d_{j,\mathrm{exits}}\right|j\in J_i\}\times U_i}---\left(6\right)$

其中，η_ij(t)为元胞i与元胞j之间路径上的启发式信息，d_j,exits是元胞j到出口的距离， min{d_j,exits|j∈J_i}表示元胞j距离出口的最短欧式距离，J_i是元胞i附近的邻居集合，U_i为 步骤4得到的元胞i的总势能值。

步骤6.设置迭代计数器NC＝1；

步骤7.从所有疏散人员中随机选择一名人员作为第一个开始疏散，设k＝1；

步骤8.判断第k个人员的当前状态是否为“已疏散”状态，若是则执行步骤15，否则执 行下一步；

步骤9.根据第k个人员所在的元胞，得到其邻居元胞的集合，即第k个人员所在位置的 上，下，左，右，左上，左下，右上，右下8个方向的元胞。

步骤10.根据步骤9得到的邻居元胞，判断其当前时刻的状态，即邻居元胞为空闲可移 动点或是被占位不可移动点，根据邻居元胞状态和以下禁忌规则判断第k个人员可移动的元 胞邻居集；

在元胞移动规则基础上模型的禁忌规则为：

(1)一个元胞只能容纳一个人员。

(2)在建筑物的人员可以向空闲元胞和出口移动，从出口的元胞不能向建筑物内的元 胞移动。

(3)若多个人员同时竞争同一个空闲元胞,随机选择一人进入，其他人重新选择路径， 直到所有人员在网格上找到自己下一时刻唯一目标为止。

(4)当人员不能选择当前最优站位时,则在不考虑出口方向情况写选择一个次优元胞 作为站位

(5)人员选择元胞不能是自己上一步所在的元胞，除非周围其他的元胞都不可被访问。

步骤11.根据步骤10得到的可移动元胞邻居集，判断第k个人员是否有可移动的元胞， 若有，执行下一步；若没有则在这一时刻停留在当前元胞位置，执行步骤15；

步骤12.根据当前时刻的第k个人员所处元胞与邻居元胞路径上的信息素强度(NC＝1 时，信息素强度值为步骤3设置的初始信息素强度Q，NC不为1时，为步骤18所计算得到 的信息素强度)和步骤5得到的启发式信息，计算第k个人员选择邻居可移动元胞的概率；

在t时刻，第k个人员由元胞i转移到元胞j的状态转移概率公式如下所示：

式中,是人员k由元胞i转移到元胞j的转移概率，τ_ij(t)是元胞i与元胞j之间路 径上的信息素强度，η_ij(t)是元胞i与元胞j之间路径上的启发式信息，α和β是常量参数， 用来表示信息素和启发信息的重要程度，J_i表示元胞i附近的邻居集合，与公式(6)中的J_i相同。代表元胞i到所有邻居元胞的启发式信息和信息素乘机的累加和。

步骤13.根据步骤12得到的转移概率得出第k个人员的转移概率最大的邻居元胞，将第 k个人员移动到此元胞处，更新该元胞的状态，将该元胞加入该人员的疏散路径；

步骤14.根据步骤13得到的第k个人员的最新移动到的元胞，判断人员k是否达到出口， 若已达，则标记该人员为“已疏散”状态，否则标记该人员为“未疏散”状态；

步骤15.疏散人员计数加1，即k＝k+1，对下一个人员进行可移动元胞搜索；

步骤16.如果k≤m，则说明还未遍历所有疏散人员，返回到步骤8，否则表明所有人员 完成了一个时间步的搜索，执行下一步；

步骤17.判断所有人员的当前状态是否都为“已疏散”状态，若是则表明所有人员完成 了从初始元胞到出口的路径搜索，即本轮疏散模拟(迭代)完成，执行下一步，否则返回步 骤7；

步骤18.根据步骤13得到的每一个人员从其初始元胞到出口的疏散路径，更新每个人员 的疏散路径上元胞之间的信息素强度；当所有人员完成一次从初始位置到出口的搜索后按公 式(8)-(10)来更新信息素。

τ_ij(t+Δt)＝(1-q)×τ_ij(t)+Δτ_ij(t+Δt)     (8)

$\Delta {\tau }_{\mathrm{ij}}(t+\mathrm{\Delta t})=\underset{k=1}{\overset{m}{\Sigma }}{\tau }_{\mathrm{ij}}^k(t+\mathrm{\Delta t})---\left(9\right)$

${\tau }_{\mathrm{ij}}^k(t+\mathrm{\Delta t})=\left(\begin{array}{c}\frac{Q}{L_k},\mathrm{edge}(i,j)\in {\mathrm{path}}_k\\ 0,\mathrm{otherwise}\end{array}\right)---\left(10\right)$

其中，τ_ij(t)表示t时刻元胞i与元胞j之间路径上的信息素强度函数，Q为常数(即步骤 2设置的信息素强度初始值)，L_k为k个人员第在本次循环中所走的路径长度，edge(i,j)代表 元胞i与元胞j之间的路径，path_k是人员k经过的路径。q为步骤2设置的信息素强度挥发 系数，路径上的信息素随着时间的推移会挥发掉，所以当前时刻元胞i与元胞j之间路径上 的信息素即为此路径上经过挥发以后剩下的信息素((1-q)×τ_ij(t))加上时间增量期间所有经 过该元胞的人员新撒下的信息素(Δτ_ij(t+Δt))之和。

因此，路径上的信息素强度越大，路径之间的距离越短，那么人员k选择这条路径的概 率就会越大。由于这种正反馈机制,所有人员会被吸引到最短的路线上。

步骤19.迭代计数器NC加1，即NC＝NC+1；

步骤20.当NC≤T，每一个人员返回步骤3设置的人员各自的初始元胞，重复步骤7-19， 直到NC＞T，迭代结束，执行下一步；

步骤21.输出最优疏散路径和疏散时间,演示最优疏散方案。

为了验证本发明的有效性，我们将本发明与基本蚁群算法进行了仿真比较，在仿真实验 过程中，选取真实教学楼场景进行仿真试验。本发明的参数设置为：蚁群算法参数 α＝1,β＝2,ρ＝0.5,Q＝1，最大迭代次数T＝100。势能场增益系数ξ₁＝2,ξ₂＝1。

图3是本发明的优化结果(疏散路径总长度)与迭代次数的关系图，从图中可以看出， 随着迭代次数的增加，疏散路径总长度明显下降，说明本发明能够有效优化疏散路径长度， 当迭代次数达到50代之后，疏散路径总长度变化不明显，表明本发明的优化方法是收敛的， 且在50代左右达到最优。图4是本发明和对比方法的迭代收敛图，从图中可以得出，本发明 的收敛速度明显更快。

表1列出了本发明和对比方法对不同疏散人数的实验结果。可以看出对于不同疏散人数， 通过势能场蚁群算法得出的平均路径和最优路径都能找到更好的解，而且输出路径较为稳定。

表1 本发明与基本蚁群算法对不同疏散人数的实验结果