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

王 鉀，王慧琴，馮路佳，

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

0 引言

在消防應急疏散研究領域中，路徑規(guī)劃一直是研究的重中之重。在火災事故發(fā)生時，在短時間內(nèi)對撤離人員進行安全高效的疏散和轉移是現(xiàn)代城市消防救援的關鍵問題[1]。路徑優(yōu)化在疏散中起著重要作用，并且是影響和衡量疏散計劃是否可行的標準。目前，國內(nèi)外學者在路徑疏散規(guī)劃方面已經(jīng)進行了大量的研究，并提出了相應的解決方案。常用的路徑規(guī)劃方法有可視圖法[2]、柵格法[3]、人工勢場法[4]以及包括人工神經(jīng)網(wǎng)絡算法[5]、遺傳算法[6]、蟻群算法[7]、粒子群算法[8]等一些智能算法。

蟻群算法作為最具代表性的群體智能算法之一，具有正反饋、魯棒性、分布式計算以及容易同其他算法相結合的特點，在解決路徑規(guī)劃問題上取得了很好的效果。并且，疏散人群在撤離過程中的群體歸屬，自組織等運動特征與蟻群系統(tǒng)有許多共同之處。但是蟻群算法在解決大規(guī)模路徑規(guī)劃問題時存在容易陷入局部最優(yōu)，收斂速度過慢等問題，為了克服這些問題，很多專家學者對其進行了改進優(yōu)化，文獻[8]許凱波等人使用了一種改進信息素二次更新與局部優(yōu)化策略，增強了搜索能力，多樣性更好，但收斂問題卻有待提高；文獻[9]利用全局信息素和局部更新相結合的方法，動態(tài)調(diào)配當前最優(yōu)路徑的信息素，從而使算法跳出局部最優(yōu)，避免停滯。文獻[10]張立毅等人將蟻群與細菌覓食算法融合來改進蟻群算法易死鎖和收斂速度慢的不足。

在現(xiàn)有文獻的基礎上，采用一種融合量子進化算法[11]的改進蟻群算法：量子蟻群算法(Quantum ant colony algorithm，QACA)，集成了蟻群算法和量子進化算法的特性，其群體大小可自由調(diào)控，收斂速度快，具有較強的全局尋優(yōu)能力和豐富的群體多樣性。

1 相關研究

1.1 疏散網(wǎng)絡簡述

在建筑消防應急疏散問題上，疏散計劃的目的是選擇一條最短安全路徑，以最大限度的減少撤離人員從危險區(qū)域到安全地點的所需的總時間。通過建立一個疏散網(wǎng)絡來模擬現(xiàn)實建筑體內(nèi)部情況。將建筑內(nèi)部空間信息抽象為由節(jié)點集和疏散通道集合共同組成網(wǎng)絡數(shù)學模型[12]，節(jié)點用于描述房間、走廊、樓梯和大廳等位置信息，疏散通道表示節(jié)點之間的鏈路通道,采用圖網(wǎng)中的節(jié)點和弧段來模擬撤離人員的流動情況。如圖1所示。

圖1 應急疏散網(wǎng)絡拓撲圖

則路徑優(yōu)化問題可描述為：

(1)

(2)

(3)

(4)

(5)

則：

(6)

對于上述路徑問題，采用加權理想點法[13]用于處理多目標問題。其最優(yōu)解可以通過求解下式單目標優(yōu)化問題得到，即路徑長度F可表示為：

(7)

1.2 蟻群算法

蟻群算法(ant colony optimization，ACO)是20世紀90年代初意大利學者Marco Dorigo等模擬螞蟻覓食及提出的用來解決旅行商和分布式優(yōu)化問題的一種算法[14]。研究發(fā)現(xiàn)，螞蟻在進行覓食過程中，會在途徑的路徑上留下一種對同類有吸引性的化學物質(zhì)：信息素，每一只螞蟻都會受到其他螞蟻信息素的影響，也會在經(jīng)過的路徑上釋放信息素。螞蟻在選擇路徑時，會更大概率的選擇信息素較多的路徑，這種正反饋效果使得經(jīng)過的螞蟻趨向于選擇最短的路徑。蟻群算法包括兩個部分：路徑構造和信息素更新。

1)路徑構建規(guī)則：

在AOC算法中，每只螞蟻k從當前位置i處，根據(jù)狀態(tài)轉移規(guī)則決定其下一次移動的構造路徑，在每個節(jié)點i中，螞蟻按照偽隨機比例規(guī)則移動到下一個節(jié)點j，其規(guī)則如公式：

(8)

式中，Pij表示i到j點的轉移概率，其中U表示螞蟻下一步可到達且尚未訪問過的節(jié)點集，τij(t)表示節(jié)點i和節(jié)點j之間的鏈路中保留的信息素；μ和v分別表示信息素和啟發(fā)式的影響程度，t代表迭代次數(shù)。ηij為的啟發(fā)式信息，其表達式為公式：

(9)

式中，ηij表示節(jié)點i到j的啟發(fā)式信息，dij是兩點間鏈路的距離。兩點間距離越大時，啟發(fā)式量則越小，螞蟻在節(jié)點i時選擇節(jié)點j的概率就會變小。啟發(fā)式信息是一種局部信息，在初始階段可以指導螞蟻快速的構造較好解，大大提高算法前期的效率。

2)信息素更新：

信息素更新規(guī)則：螞蟻在進行一次路徑選擇時，即從當前節(jié)點i到下一個節(jié)點j后，立即更新信息素，信息素在每個搜索周期中都會更新，其公式為：

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

(10)

(11)

其中:ρ為信息素揮發(fā)率，其范圍為0<ρ<1；Δτij表示螞蟻k在節(jié)點i,j之間的信息素增量，它在所走過的邊上引起的信息素增量按公式計算為：

otherwise

(12)

其中:C是個常數(shù)，稱為總信息量；Fk為螞蟻k遍歷所有節(jié)點后本次循環(huán)所得到的的最優(yōu)路徑。

2 改進蟻群算法

2.1 量子編碼與量子旋轉門

量子進化算法(Quantum evolutionary algorithm QEA)[15]，是一種基于量子計算的進化算法。

1) 量子比特：

在經(jīng)典的QEA中，量子比特是最小的信息單元，即Q比特，一個簡單的量子比特是一個雙態(tài)系統(tǒng)，它的狀態(tài)空間由兩個基|0和|1，“|>”為量子態(tài)的表示方式。一個量子比特除了可以表示0態(tài)和1態(tài)之外，還可以處于它們的疊加態(tài)，即表示為：|φi>=αi|0>+βi|1>，i=1,2,…n。其中α和β為滿足疊加條件|α|2+|β|2=1的任意復數(shù)。|α|2和|β|2值代表量子比特在“0”狀態(tài)或者“1”狀態(tài)的概率大小。其可表示為：

(13)

該量子比特有2n個狀態(tài)，例如下式一個具有3個比特位:

(14)

即可表示為

(15)

其狀態(tài)概率為|001>，|010>，|011>，|100>，|101>，|110>和|111>分別表示為：1/16，3/16，1/16，3/16，1/16，3/16，1/16和3/16。

2)量子旋轉門：

在量子理論中，量子比特的改變是通過量子門來實現(xiàn)的，量子旋轉門對算法的性能有很大的影響，其更新公式如下：

(16)

其中:i=(1,2,…,m)，[αiβi]T表示量子旋轉門處理前后第i個量子比特的概率幅，并滿足歸一化條件|ai|2+|βi|2=1，θi為旋轉角度，其大小和方向采用動態(tài)調(diào)整或查表得到。

2.2 基于QACA的路徑規(guī)劃

對路徑優(yōu)化算法進行研究，將蟻群算法與量子進化算法融合，提出一種改進的量子蟻群算法(QACA)用于疏散路徑優(yōu)化問題。采用量子比特作為信息素，并通過量子旋轉門的操作更新信息素，跳出局部最優(yōu)解，避免早熟，加快算法的收斂速度。

2.2.1 信息素的量子比特表示

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

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

(17)

對于每個個體，qj有n位比特，如式(13)所示。

2.2.2 新的信息素更新策略

經(jīng)典蟻群中，螞蟻經(jīng)過的路徑上信息素會越來越多，不經(jīng)過的路徑上的信息素則越來越少，且是以迭代次數(shù)為指數(shù)減少。最后導致某一條路徑上信息素最大，其他路徑上減少至0，使算法陷入局部最優(yōu)。而在搜索的后期，由于信息素改變較小，收斂速度變慢。量子蟻群算法引入量子旋轉門，用旋轉門實現(xiàn)信息素的更新，可以有效的防止早熟和加快收斂。

在量子蟻群算法中，對于量子比特中第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的疏散路徑優(yōu)化流程圖如圖3。其具體步驟為：

(22)

3)構造路徑，將m個螞蟻個體隨機放入源節(jié)點上，根據(jù)式(8)～(10)中螞蟻的狀態(tài)轉移規(guī)則和轉移概率選擇節(jié)點；

4)評估適應度函數(shù)Pt，并計算最優(yōu)解存入Bt。其評估函數(shù)公式為式(7)。

5)節(jié)點接收到螞蟻信息后，通過量子旋轉門對量子蟻群進行變換更新。

6)如果循環(huán)次數(shù)t小于設定的最大循環(huán)次數(shù)tmax，則返回步驟3，直到當前迭代次數(shù)超過最大迭代次數(shù)。

7)輸出得到最優(yōu)解的節(jié)點，并根據(jù)最優(yōu)解的節(jié)點得到最優(yōu)疏散路徑，算法結束。

圖3 算法流程圖

4 實驗結果與分析

為了驗證算法的有效性，分別從兩方面進行驗證其有效性和效率。一方面通過經(jīng)典QEA與本文改進算法之間的性能比較。另一方面在路徑優(yōu)化方面對基于ACO和基于QACA的解決方案進行比較分析。

4.1 實驗分析

將本文QACA算法與經(jīng)典QEA算法進行比較實驗，采用3種基準函數(shù)對算法進行對比分析。分別從算法的尋優(yōu)成功率(rate)，尋優(yōu)的平均迭代次數(shù)(T)以及平均最優(yōu)值(Av)3個方面來進行評估，驗證其有效性。本實驗使用3個基準函數(shù)如下：

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

100

(23)

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

100

(24)

(25)

其中：F1和F2具有全局最小值，F(xiàn)3具有全局最大值。實驗中，我們設定種群大小為20，量子比特長度為30位，重復試驗100次，固定最大迭代次數(shù)為1 000。實驗結果如表2。由表可知，在F1中，QEA的平均迭代次數(shù)略好于QACA。而F2中，雖然QACA的迭代次數(shù)相較于QEA多了90次，但其準確率是QEA的兩倍多。另外，QACA的最優(yōu)值可準確到小數(shù)點后六位。F3中，QACA在另外兩個數(shù)值相同的情況下，時間效率方面明顯優(yōu)于經(jīng)典QEA。綜上所述，QACA具有更好的準確性。

4.2 路徑疏散實例分析

本文用生成的隨機網(wǎng)絡模型來表示疏散網(wǎng)絡，如圖(4～6)所示。模型中每個人都被當做撤離人員，圖(a)是具有50個節(jié)點的網(wǎng)絡實例模型。其疏散區(qū)域面積設定為1平方公里。每個相鄰節(jié)點之間通過直線相連接。撤離人員移動速度設定為2 m/s。即該疏散情況下將疏散人員從節(jié)點1危險區(qū)域撤離到節(jié)點50的安全出口。并設定了三組人群即m=10，m=20，m=30在MATLAB對本文QACA和ACO進行仿真試驗。結果如圖4～6，實線表示本文QACA搜索到的最佳路徑，而虛線表示基于ACO搜索到的最佳路徑。并通過兩個性能指標l，Et對本文QACA和經(jīng)典ACO進行比較分析，驗證其有效性。如表2～4所示，其中l(wèi)代表最優(yōu)路徑的長度，Et表示迭代期間找到最優(yōu)路徑所有個體的總撤離時間。因此，當l長度越短，Et的值越小，說明算法的有效性和效率越好。

表2 當n=50、m=10的疏散情況下ACO和QACA比較分析

表3 當n=50、m=20的疏散情況下ACO和QACA比較分析

圖4 n=50，m=10，tmax=300的疏散網(wǎng)絡

圖5 n=50，m=20，tmax=300的疏散網(wǎng)絡

圖6 n=50，m=30，tmax=300的疏散網(wǎng)絡

表4 當n=50、m=30的疏散情況下ACO和QACA比較分析

表2～4分別對應了圖4～6不同情況下的最優(yōu)路徑長度和總撤離時間，迭代次數(shù)tmax分別設定為50，100，150，200，300，400，本文以表2例，即當n=50、m=10情況下，ACO和QACA的疏散結果分析。從表中可以看出 當t=50時，ACO最優(yōu)路徑的總撤離時間Et略小于QACA，但隨著tmax的不斷增大，QACA所用總撤離時間和最優(yōu)路徑長度明顯少于基于ACO的解決方案。為了更直觀表現(xiàn)QACA的有效性，以n=50、m=10時為例繪制不同迭代時Et的趨勢圖，如圖7所示，X軸表示最大迭代次數(shù)，Y軸表示總撤離時間，由圖中可看出，除t值為50外，基于QACA的總撤離時間均小于ACO算法的總疏散時間，并在當t值為300時，QACA逐漸穩(wěn)定趨于水平。

圖7 n=50，m=10的Et的趨勢圖

表4～5為群體m大小分別為20，30時的最優(yōu)路徑長路l和疏散時間Et的結果分析。綜上所述，基于QACA的路徑尋優(yōu)性能優(yōu)于基于ACO的尋優(yōu)能力。當?shù)螖?shù)很少時，差異很小。但隨著數(shù)量，次數(shù)的增加，本文QACA算法在時間效率方面的優(yōu)勢越來越明顯。

5 結束語

建筑消防應急疏散是以在最短的時間內(nèi)為撤離人員提供最短安全路徑。為了提高蟻群優(yōu)化算法的收斂性和尋優(yōu)效率，引入量子計算機制，采用量子比特表示信息素，用量子旋轉門反饋控制信息素更新。使改進算法具備量子并行計算的高效性，又兼?zhèn)湎伻核惴己玫膶?yōu)性能。通過比較基于ACO和基于QACA的疏散路徑規(guī)劃方案比較，仿真結果表明本文的改進算法不僅提高了多樣性，還加快了收斂速度，在疏散路徑規(guī)劃問題上能快速的找到最優(yōu)路徑。并且隨著迭代次數(shù)的增加，其優(yōu)勢趨于明顯。此外，研究重點不僅限于兩個節(jié)點(起始-目的地)之間的單個路徑，也適用于多個源節(jié)點到多個目的節(jié)點路徑規(guī)劃問題。