王 鉀，王慧琴，馮路佳，

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

0 引言

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

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

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

1 相關(guān)研究

1.1 疏散網(wǎng)絡(luò)簡(jiǎn)述

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

圖1 應(yīng)急疏散網(wǎng)絡(luò)拓?fù)鋱D

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

(1)

(2)

(3)

(4)

(5)

則：

(6)

對(duì)于上述路徑問(wèn)題，采用加權(quán)理想點(diǎn)法[13]用于處理多目標(biāo)問(wèn)題。其最優(yōu)解可以通過(guò)求解下式單目標(biāo)優(yōu)化問(wèn)題得到，即路徑長(zhǎng)度F可表示為：

(7)

1.2 蟻群算法

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

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

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

(8)

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

(9)

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

2)信息素更新：

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

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

(10)

(11)

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

otherwise

(12)

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

2 改進(jìn)蟻群算法

2.1 量子編碼與量子旋轉(zhuǎn)門

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

1) 量子比特：

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

(13)

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

(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)量子旋轉(zhuǎn)門：

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

(16)

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

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

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

2.2.1 信息素的量子比特表示

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

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

(17)

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

2.2.2 新的信息素更新策略

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

在量子蟻群算法中，對(duì)于量子比特中第j個(gè)螞蟻個(gè)體的第i位信息素更新過(guò)程(αji,βji)T如下式：

(18)

(19)

旋轉(zhuǎn)門的大小為：

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

(20)

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

(21)

圖 2 量子門旋轉(zhuǎn)極坐標(biāo)圖

3 算法流程及步驟描述

基于QACA的疏散路徑優(yōu)化流程圖如圖3。其具體步驟為：

(22)

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

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

5)節(jié)點(diǎn)接收到螞蟻信息后，通過(guò)量子旋轉(zhuǎn)門對(duì)量子蟻群進(jìn)行變換更新。

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

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

圖3 算法流程圖

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 實(shí)驗(yàn)分析

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

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

100

(23)

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

100

(24)

(25)

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

4.2 路徑疏散實(shí)例分析

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

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

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

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

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

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

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

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

圖7 n=50，m=10的Et的趨勢(shì)圖

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

5 結(jié)束語(yǔ)

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