基于量子蟻群算法的建筑消防疏散路徑規劃

王 鉀，王慧琴，馮路佳，

(西安建筑科技大學 信息與控制工程學院， 西安 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的疏散路徑規劃方案比較，仿真結果表明本文的改進算法不僅提高了多樣性，還加快了收斂速度，在疏散路徑規劃問題上能快速的找到最優路徑。并且隨著迭代次數的增加，其優勢趨于明顯。此外，研究重點不僅限于兩個節點(起始-目的地)之間的單個路徑，也適用于多個源節點到多個目的節點路徑規劃問題。