基于量子蚁群算法的建筑消防疏散路径规划

王 钾，王慧琴，冯路佳，

(西安建筑科技大学 信息与控制工程学院， 西安 710054)

0 引言

在消防应急疏散研究领域中，路径规划一直是研究的重中之重。在火灾事故发生时，在短时间内对撤离人员进行安全高效的疏散和转移是现代城市消防救援的关键问题[1]。路径优化在疏散中起着重要作用，并且是影响和衡量疏散计划是否可行的标准。目前，国内外学者在路径疏散规划方面已经进行了大量的研究，并提出了相应的解决方案。常用的路径规划方法有可视图法[2]、栅格法[3]、人工势场法[4]以及包括人工神经网络算法[5]、遗传算法[6]、蚁群算法[7]、粒子群算法[8]等一些智能算法。

蚁群算法作为最具代表性的群体智能算法之一，具有正反馈、鲁棒性、分布式计算以及容易同其他算法相结合的特点，在解决路径规划问题上取得了很好的效果。并且，疏散人群在撤离过程中的群体归属，自组织等运动特征与蚁群系统有许多共同之处。但是蚁群算法在解决大规模路径规划问题时存在容易陷入局部最优，收敛速度过慢等问题，为了克服这些问题，很多专家学者对其进行了改进优化，文献[8]许凯波等人使用了一种改进信息素二次更新与局部优化策略，增强了搜索能力，多样性更好，但收敛问题却有待提高；文献[9]利用全局信息素和局部更新相结合的方法，动态调配当前最优路径的信息素，从而使算法跳出局部最优，避免停滞。文献[10]张立毅等人将蚁群与细菌觅食算法融合来改进蚁群算法易死锁和收敛速度慢的不足。

在现有文献的基础上，采用一种融合量子进化算法[11]的改进蚁群算法：量子蚁群算法(Quantum ant colony algorithm，QACA)，集成了蚁群算法和量子进化算法的特性，其群体大小可自由调控，收敛速度快，具有较强的全局寻优能力和丰富的群体多样性。

1 相关研究

1.1 疏散网络简述

在建筑消防应急疏散问题上，疏散计划的目的是选择一条最短安全路径，以最大限度的减少撤离人员从危险区域到安全地点的所需的总时间。通过建立一个疏散网络来模拟现实建筑体内部情况。将建筑内部空间信息抽象为由节点集和疏散通道集合共同组成网络数学模型[12]，节点用于描述房间、走廊、楼梯和大厅等位置信息，疏散通道表示节点之间的链路通道,采用图网中的节点和弧段来模拟撤离人员的流动情况。如图1所示。

图1 应急疏散网络拓扑图

则路径优化问题可描述为：

(1)

(2)

(3)

(4)

(5)

则：

(6)

对于上述路径问题，采用加权理想点法[13]用于处理多目标问题。其最优解可以通过求解下式单目标优化问题得到，即路径长度F可表示为：

(7)

1.2 蚁群算法

蚁群算法(ant colony optimization，ACO)是20世纪90年代初意大利学者Marco Dorigo等模拟蚂蚁觅食及提出的用来解决旅行商和分布式优化问题的一种算法[14]。研究发现，蚂蚁在进行觅食过程中，会在途径的路径上留下一种对同类有吸引性的化学物质：信息素，每一只蚂蚁都会受到其他蚂蚁信息素的影响，也会在经过的路径上释放信息素。蚂蚁在选择路径时，会更大概率的选择信息素较多的路径，这种正反馈效果使得经过的蚂蚁趋向于选择最短的路径。蚁群算法包括两个部分：路径构造和信息素更新。

1)路径构建规则：

在AOC算法中，每只蚂蚁k从当前位置i处，根据状态转移规则决定其下一次移动的构造路径，在每个节点i中，蚂蚁按照伪随机比例规则移动到下一个节点j，其规则如公式：

(8)

式中，Pij表示i到j点的转移概率，其中U表示蚂蚁下一步可到达且尚未访问过的节点集，τij(t)表示节点i和节点j之间的链路中保留的信息素；μ和v分别表示信息素和启发式的影响程度，t代表迭代次数。ηij为的启发式信息，其表达式为公式：

(9)

式中，ηij表示节点i到j的启发式信息，dij是两点间链路的距离。两点间距离越大时，启发式量则越小，蚂蚁在节点i时选择节点j的概率就会变小。启发式信息是一种局部信息，在初始阶段可以指导蚂蚁快速的构造较好解，大大提高算法前期的效率。

2)信息素更新：

信息素更新规则：蚂蚁在进行一次路径选择时，即从当前节点i到下一个节点j后，立即更新信息素，信息素在每个搜索周期中都会更新，其公式为：

τij(t+1)←ρτij(t)+Δτij

(10)

(11)

其中:ρ为信息素挥发率，其范围为0<ρ<1；Δτij表示蚂蚁k在节点i,j之间的信息素增量，它在所走过的边上引起的信息素增量按公式计算为：

otherwise

(12)

其中:C是个常数，称为总信息量；Fk为蚂蚁k遍历所有节点后本次循环所得到的的最优路径。

2 改进蚁群算法

2.1 量子编码与量子旋转门

量子进化算法(Quantum evolutionary algorithm QEA)[15]，是一种基于量子计算的进化算法。

1) 量子比特：

在经典的QEA中，量子比特是最小的信息单元，即Q比特，一个简单的量子比特是一个双态系统，它的状态空间由两个基|0和|1，“|>”为量子态的表示方式。一个量子比特除了可以表示0态和1态之外，还可以处于它们的叠加态，即表示为：|φi>=αi|0>+βi|1>，i=1,2,…n。其中α和β为满足叠加条件|α|2+|β|2=1的任意复数。|α|2和|β|2值代表量子比特在“0”状态或者“1”状态的概率大小。其可表示为：

(13)

该量子比特有2n个状态，例如下式一个具有3个比特位:

(14)

即可表示为

(15)

其状态概率为|001>，|010>，|011>，|100>，|101>，|110>和|111>分别表示为：1/16，3/16，1/16，3/16，1/16，3/16，1/16和3/16。

2)量子旋转门：

在量子理论中，量子比特的改变是通过量子门来实现的，量子旋转门对算法的性能有很大的影响，其更新公式如下：

(16)

其中:i=(1,2,…,m)，[αiβi]T表示量子旋转门处理前后第i个量子比特的概率幅，并满足归一化条件|ai|2+|βi|2=1，θi为旋转角度，其大小和方向采用动态调整或查表得到。

2.2 基于QACA的路径规划

对路径优化算法进行研究，将蚁群算法与量子进化算法融合，提出一种改进的量子蚁群算法(QACA)用于疏散路径优化问题。采用量子比特作为信息素，并通过量子旋转门的操作更新信息素，跳出局部最优解，避免早熟，加快算法的收敛速度。

2.2.1 信息素的量子比特表示

在QACA算法中，其信息素用量子比特可表示为:

Q=(q1,q2,...,qj,...qm)，j=1,2,...,t

(17)

对于每个个体，qj有n位比特，如式(13)所示。

2.2.2 新的信息素更新策略

经典蚁群中，蚂蚁经过的路径上信息素会越来越多，不经过的路径上的信息素则越来越少，且是以迭代次数为指数减少。最后导致某一条路径上信息素最大，其他路径上减少至0，使算法陷入局部最优。而在搜索的后期，由于信息素改变较小，收敛速度变慢。量子蚁群算法引入量子旋转门，用旋转门实现信息素的更新，可以有效的防止早熟和加快收敛。

在量子蚁群算法中，对于量子比特中第j个蚂蚁个体的第i位信息素更新过程(αji,βji)T如下式：

(18)

(19)

旋转门的大小为：

θji=Δθji×s(αji,βji)i=1,2,...,n

(20)

Δθ=0.5*π*exp(-t/tmax)

(21)

图 2 量子门旋转极坐标图

3 算法流程及步骤描述

基于QACA的疏散路径优化流程图如图3。其具体步骤为：

(22)

3)构造路径，将m个蚂蚁个体随机放入源节点上，根据式(8)～(10)中蚂蚁的状态转移规则和转移概率选择节点；

4)评估适应度函数Pt，并计算最优解存入Bt。其评估函数公式为式(7)。

5)节点接收到蚂蚁信息后，通过量子旋转门对量子蚁群进行变换更新。

6)如果循环次数t小于设定的最大循环次数tmax，则返回步骤3，直到当前迭代次数超过最大迭代次数。

7)输出得到最优解的节点，并根据最优解的节点得到最优疏散路径，算法结束。

图3 算法流程图

4 实验结果与分析

为了验证算法的有效性，分别从两方面进行验证其有效性和效率。一方面通过经典QEA与本文改进算法之间的性能比较。另一方面在路径优化方面对基于ACO和基于QACA的解决方案进行比较分析。

4.1 实验分析

将本文QACA算法与经典QEA算法进行比较实验，采用3种基准函数对算法进行对比分析。分别从算法的寻优成功率(rate)，寻优的平均迭代次数(T)以及平均最优值(Av)3个方面来进行评估，验证其有效性。本实验使用3个基准函数如下：

表1 QEA和本文QACA性能比较分析

100

(23)

F2=[-13+x1+((5-x2)·x2-2)·x2]+

100

(24)

(25)

其中：F1和F2具有全局最小值，F3具有全局最大值。实验中，我们设定种群大小为20，量子比特长度为30位，重复试验100次，固定最大迭代次数为1 000。实验结果如表2。由表可知，在F1中，QEA的平均迭代次数略好于QACA。而F2中，虽然QACA的迭代次数相较于QEA多了90次，但其准确率是QEA的两倍多。另外，QACA的最优值可准确到小数点后六位。F3中，QACA在另外两个数值相同的情况下，时间效率方面明显优于经典QEA。综上所述，QACA具有更好的准确性。

4.2 路径疏散实例分析

本文用生成的随机网络模型来表示疏散网络，如图(4～6)所示。模型中每个人都被当做撤离人员，图(a)是具有50个节点的网络实例模型。其疏散区域面积设定为1平方公里。每个相邻节点之间通过直线相连接。撤离人员移动速度设定为2 m/s。即该疏散情况下将疏散人员从节点1危险区域撤离到节点50的安全出口。并设定了三组人群即m=10，m=20，m=30在MATLAB对本文QACA和ACO进行仿真试验。结果如图4～6，实线表示本文QACA搜索到的最佳路径，而虚线表示基于ACO搜索到的最佳路径。并通过两个性能指标l，Et对本文QACA和经典ACO进行比较分析，验证其有效性。如表2～4所示，其中l代表最优路径的长度，Et表示迭代期间找到最优路径所有个体的总撤离时间。因此，当l长度越短，Et的值越小，说明算法的有效性和效率越好。

表2 当n=50、m=10的疏散情况下ACO和QACA比较分析

表3 当n=50、m=20的疏散情况下ACO和QACA比较分析

图4 n=50，m=10，tmax=300的疏散网络

图5 n=50，m=20，tmax=300的疏散网络

图6 n=50，m=30，tmax=300的疏散网络

表4 当n=50、m=30的疏散情况下ACO和QACA比较分析

表2～4分别对应了图4～6不同情况下的最优路径长度和总撤离时间，迭代次数tmax分别设定为50，100，150，200，300，400，本文以表2例，即当n=50、m=10情况下，ACO和QACA的疏散结果分析。从表中可以看出 当t=50时，ACO最优路径的总撤离时间Et略小于QACA，但随着tmax的不断增大，QACA所用总撤离时间和最优路径长度明显少于基于ACO的解决方案。为了更直观表现QACA的有效性，以n=50、m=10时为例绘制不同迭代时Et的趋势图，如图7所示，X轴表示最大迭代次数，Y轴表示总撤离时间，由图中可看出，除t值为50外，基于QACA的总撤离时间均小于ACO算法的总疏散时间，并在当t值为300时，QACA逐渐稳定趋于水平。

图7 n=50，m=10的Et的趋势图

表4～5为群体m大小分别为20，30时的最优路径长路l和疏散时间Et的结果分析。综上所述，基于QACA的路径寻优性能优于基于ACO的寻优能力。当迭代次数很少时，差异很小。但随着数量，次数的增加，本文QACA算法在时间效率方面的优势越来越明显。

5 结束语

建筑消防应急疏散是以在最短的时间内为撤离人员提供最短安全路径。为了提高蚁群优化算法的收敛性和寻优效率，引入量子计算机制，采用量子比特表示信息素，用量子旋转门反馈控制信息素更新。使改进算法具备量子并行计算的高效性，又兼备蚁群算法良好的寻优性能。通过比较基于ACO和基于QACA的疏散路径规划方案比较，仿真结果表明本文的改进算法不仅提高了多样性，还加快了收敛速度，在疏散路径规划问题上能快速的找到最优路径。并且随着迭代次数的增加，其优势趋于明显。此外，研究重点不仅限于两个节点(起始-目的地)之间的单个路径，也适用于多个源节点到多个目的节点路径规划问题。