一種應(yīng)用于火災(zāi)環(huán)境路徑規(guī)劃的螞蟻群算法

鄭延斌,安德宇,李娜,盧玉鋒

(1.河南師范大學(xué) 計算機與信息工程學(xué)院,河南 新鄉(xiāng) 453007;2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室,河南 新鄉(xiāng) 453007)

一種應(yīng)用于火災(zāi)環(huán)境路徑規(guī)劃的螞蟻群算法

鄭延斌1,2,安德宇1*,李娜1,盧玉鋒1

(1.河南師范大學(xué) 計算機與信息工程學(xué)院,河南 新鄉(xiāng) 453007;2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室,河南 新鄉(xiāng) 453007)

在火災(zāi)環(huán)境中,針對蟻群算法容易陷入局部最優(yōu)的問題,文章使用了一種改進的蟻群算法用于解決火災(zāi)環(huán)境中人群疏散的路徑規(guī)劃問題。對蟻群算法的改進分為兩個方面:一是在蟻群算法的啟發(fā)式函數(shù)中考慮人員密度因素;二是動態(tài)自適應(yīng)調(diào)整信息素強度,采取局部和全局信息素更新相結(jié)合的策略更新路徑上的信息素,并引入交叉操作,加快算法的逃逸能力。由于在火災(zāi)環(huán)境中個體情緒差異對路徑選擇的影響較大,在文章的規(guī)劃方法中,為個體建立情緒數(shù)學(xué)模型,不同情緒的個體對路徑的選擇是不同的。仿真實驗表明,文中提出的規(guī)劃方法能夠為不同情緒類型的個體規(guī)劃出最優(yōu)逃生路徑,避免了局部最優(yōu)且收斂速度較快。

火災(zāi)環(huán)境;蟻群算法;人員密度;交叉操作;情緒模型

0 引言

火災(zāi)是各種災(zāi)害中發(fā)生頻率最高且極具毀滅性的災(zāi)害,造成的直接經(jīng)濟損失約為地震的五倍。其中,建筑火災(zāi)是造成經(jīng)濟損失和人員傷亡最嚴重的火災(zāi)類型。由于大型公共場所建筑構(gòu)造復(fù)雜,人流密度大,火災(zāi)安全隱患多,因此在建筑防火設(shè)計工作中的人員安全疏散問題已經(jīng)成為十分重要的環(huán)節(jié)。引進新技術(shù)、發(fā)展新方法,來保證復(fù)雜建筑的高效疏散已成為國內(nèi)外公共安全領(lǐng)域研究的熱點?；馂?zāi)具有毀滅性和不可重復(fù)性,因此使用計算機仿真技術(shù)來模擬火災(zāi)環(huán)境中人員疏散具有重要的現(xiàn)實意義。

人員應(yīng)急疏散問題自從被提出后,國內(nèi)外研究者已經(jīng)取得了一定的成果和進展。計算機模擬人員疏散最早可以追溯到Von Neumann[1]于1951年提出的元胞自動機理論,隨后也有很多學(xué)者提出了例如社會力模型[2]、排隊論模型[3]以及勢能場模型[4]等。但是這些模型側(cè)重考慮人員的微觀作用,忽視了疏散人員作為一個整體的動態(tài)移動過程和機理作用。研究者們?yōu)榱四芨玫貜暮暧^上、從全局的角度做出分析,提出了將蟻群算法應(yīng)用于應(yīng)急疏散的動態(tài)路徑優(yōu)化問題中[5-7]。蟻群算法(Ant Colony Optimization Algorithm,ACO)是由Dorigo等[8]人在1996年提出的模擬自然界真實螞蟻覓食過程的一種仿生算法。蟻群算法相比遺傳算法、神經(jīng)網(wǎng)絡(luò)算法和粒子群算法等智能算法具有獨特的正反饋特性和較強的全局搜索最優(yōu)解的能力,并且在復(fù)雜優(yōu)化問題的求解中頗具優(yōu)勢[9],但是蟻群算法容易陷入局部最優(yōu)或者收斂速度過慢[10]。為此,很多學(xué)者對蟻群算法進行了改進,Liu、Yan[11]提出一種根據(jù)目標點自適應(yīng)調(diào)整啟發(fā)函數(shù)并借鑒狼群分配原則對信息素進行更新的方法,在一定程度上可以避免算法陷入局部最優(yōu),但是路徑上的信息素變化不夠快,縮短算法搜索時間的能力有限;雷春英等[12]在研究火災(zāi)疏散路徑優(yōu)化中,改進的蟻群算法能夠找到最優(yōu)路徑,但是此方法沒有考慮人員密度對個體速度的影響;齊茁[13]考慮火場因素對人員的影響,用自適應(yīng)蟻群算法研究人員的安全疏散問題,但是當疏散個體過多并且建筑物中不止一個出口時,最優(yōu)路徑將不再最優(yōu),沒有考慮到個體情緒的差異性。

針對以上問題,通過改進的蟻群算法,考慮火場環(huán)境、人員密度以及個體情緒的差異性,本文提出一種從全局角度出發(fā)的動態(tài)疏散算法。首先,在啟發(fā)式函數(shù)中,不再以距離的倒數(shù)作為啟發(fā)式函數(shù),而是根據(jù)實時環(huán)境引入火災(zāi)產(chǎn)物和人員密度的影響系數(shù),當量長度代替幾何長度;其次,動態(tài)自適應(yīng)調(diào)整信息素強度Q,采用局部和全局信息素更新相結(jié)合的策略更新路徑上的信息素。在螞蟻進行下一個節(jié)點的選擇時,局部更新已走過路徑上的信息素,避免螞蟻過早的收斂到同一路徑,在蟻群完成一次循環(huán)后引入交叉操作,并對最優(yōu)路徑上的信息素強度進行全局更新,加快算法的收斂速度。同時,借鑒自適應(yīng)的最大最小蟻群系統(tǒng)[14]中的信息素限制,將各路徑上的信息素量限制在一定范圍內(nèi);最后,為個體建立情緒模型,將個體情緒分為松弛、平靜和急躁三種狀態(tài),不同情緒的個體對路徑選擇不同,不再像傳統(tǒng)蟻群算法生成一條最優(yōu)路徑,而是根據(jù)出口數(shù)量的不同生成若干條路徑。實驗證明,本文提出的算法不僅克服了傳統(tǒng)蟻群算法的局限性,加快了收斂速度,并且反映出在發(fā)生火災(zāi)時個體情緒差異對路徑選擇的影響。

1 環(huán)境模型和算法描述

1.1 環(huán)境模型

對于火災(zāi)環(huán)境下的人員疏散過程,高溫、有毒有害氣體(本文指一氧化碳)[15]、能見度是火災(zāi)中影響人員疏散運動時間的關(guān)鍵因素[16]。本文不僅考慮火災(zāi)產(chǎn)物的影響,也考慮了人員密度的影響,在引入溫度影響系數(shù)f1(T),有毒有害氣體濃度影響系數(shù)f2(ρco)以及能見度影響系數(shù)f3(Kc)的基礎(chǔ)上,同時引入人員密度影響系數(shù)f4(D0)。綜合以上四方面因素,確定火災(zāi)產(chǎn)物和人員密度對疏散速度影響的量化方法。同時,火源的熱釋放速率(Heat Release Rate,HRR)[17]也是火災(zāi)發(fā)展的一個重要參數(shù),火災(zāi)的蔓延與發(fā)展要受到它的影響。

由于柵格法易于實現(xiàn)計算機的建模、存儲、處理、更新和分析,可以大大地提高路徑搜索的效率,因此本文采用柵格法表示地圖。

1.1.1 火災(zāi)產(chǎn)物

火災(zāi)中的高溫危害主要是火焰的熱輻射和空氣的對流熱產(chǎn)生的,美國Milke[18]通過統(tǒng)計研究煙氣溫度與人員異動速度的數(shù)據(jù),總結(jié)出煙氣溫度對人員速度的影響系數(shù)計算公式。如式 (1)所示:

(1)

式中,Ts表示火場溫度;T0表示室外常溫溫度,取20℃;vmax取5 m/s;Tc1表示讓人感到不舒服的溫度,取30℃;Tc2表示對人造成傷害的溫度,取60℃;Td表示致人死亡的溫度,取120℃。

將上述默認取值代入式(1),則公式可變?yōu)?

火災(zāi)煙氣中含有大量因燃燒不充分產(chǎn)生的有毒、有害氣體,但是影響最大的是一氧化碳。Milke[18]認為一氧化碳對人員速度的影響系數(shù)計算公式如式(2)所示:

(2)

式中,ρ表示一氧化碳濃度(%);t表示人接觸一氧化碳的時間;f2(ρco)=0表示人暈倒或者死亡。

在火災(zāi)環(huán)境中,用減光系數(shù)Kc表示火場的煙氣濃度,Kc越大,能見度就越低。日本學(xué)者Jin和Yanada[19]開展了大量的實驗,對實驗數(shù)據(jù)進行擬合,得出減光系數(shù)對人員速度的影響系數(shù)表達式如式 (3)所示:

(3)

1.1.2 人員密度

在火災(zāi)發(fā)生時,個體將會以所能達到的最大速度逃離火災(zāi)環(huán)境,但當人員密度越來越大,達到一個臨界值時,個體的速度受到密度的制約,速度將會隨著密度的增加越來越小。本文采用美國國家消防協(xié)會制定的防火安全工程手冊中的流量-密度關(guān)系:q=1.4ρ-0.3724ρ2[20]。該函數(shù)是開口向下的二次函數(shù)關(guān)系,q的最大值是1.31,其對稱軸決定了臨界密度點,即ρ=1.87。當ρ≤1.87時,密度大小對個體速度幾乎沒有影響,本文中的人員密度對速度的影響系數(shù)設(shè)為1;當ρ≥3.75時,q≤0,即人員密度對速度的影響系數(shù)為0;當1.87<ρ<3.75時,人員密度對個體速度的影響系數(shù)是此密度區(qū)間的流量大小比1.31。

在本文的模型中,選擇一定范圍內(nèi)(x×y)的人員密度D0作為計算參數(shù),人員密度對個體速度的影響系數(shù)如式(4)所示:

(4)

式中,當人員密度D0≥3.75/m2表示人員極度擁擠,個體無法移動。

1.1.3 火源的熱輻射

Q=C·M·(t2-t1)

(5)

其中,Q表示熱量,C表示質(zhì)量,M表示該物體的比熱容,t2-t1表示溫度變化。松木的比熱容是2 510。

火災(zāi)中的輻射傳熱起重要作用,本文中采用不考慮輻射強度跟隨波長變化而變化近似計算。將火源邊界看作輻射熱源,其溫度通過空氣向周圍傳遞,從而點燃四周物體。

1.1.4 柵格環(huán)境的構(gòu)造

記AS為個體在二維平面上的凸多邊形有限運動區(qū)域,其內(nèi)部分布著有限數(shù)量的靜態(tài)障礙物和動態(tài)障礙物,靜態(tài)障礙物記為Obj1,Obj2,…,Objn,動態(tài)障礙物包括火災(zāi)環(huán)境中的溫度和有毒有害氣體。在本文中,首先把實際的火災(zāi)環(huán)境抽象為一個刪格地圖,個體在刪格環(huán)境中的移動規(guī)則是一個時間步移動一個刪格;其次柵格的屬性在數(shù)學(xué)模型上被抽象成一個載有位置信息以及其他數(shù)據(jù)信息data(溫度、有毒有害氣體濃度、著火點等)的二維矩陣,其數(shù)學(xué)表達式如(6)所示;最后確定障礙物周圍的刪格為關(guān)鍵節(jié)點。將柵格信息用一個數(shù)組矩陣表示,假設(shè)數(shù)組O11×11,O(i,j)=0表示處于第i行、第j列的柵格為普通柵格,O(i,j)=1表示障礙物柵格,O(i,j)=2表示起火柵格。柵格類型隨火災(zāi)的發(fā)展而發(fā)生變化,根據(jù)障礙物的易燃程度和HRR,普通柵格和障礙物柵格可能轉(zhuǎn)化為起火柵格。

M={[(i,j),data]|xmin≤i≤xmax,ymin≤j≤ymax}

(6)

數(shù)據(jù)信息是判斷柵格是否由普通柵格轉(zhuǎn)化為起火柵格或障礙物柵格的指標。對于普通柵格:

(7)

對于障礙物柵格:

(8)

式中,Tip表示障礙物的燃點。在火災(zāi)疏散中O(i,j)=2表示著火的地點,根據(jù)HRR以及物體的燃點來確定周圍被點燃的物體,如果有毒有害氣體濃度ρ≥0.25,該柵格變成障礙物柵格。在火源的一定范圍內(nèi)(x,y)的柵格狀態(tài)可能變化,這些可能變化的柵格通過檢測HRR確定柵格狀態(tài)是否發(fā)生改變,在本文中,火源范圍的取值是著火點的所有鄰居刪格。如圖1和圖2所示。

Fig.1 When t=t0圖1 在t=t0時刻

Fig.2 When t=t0+t圖2 在t=t0+t時刻

在圖1和圖2中陰影部分表示火災(zāi)環(huán)境中的障礙物,非陰影部分表示個體可以自由移動的區(qū)域。經(jīng)過t后,由于柵格(6,7)不完全燃燒,產(chǎn)生了有毒有害氣體,因此柵格(5,7)和柵格(6,8)從普通柵格轉(zhuǎn)變?yōu)檎系K物柵格。

1.2 算法描述

蟻群算法是通過啟發(fā)式探索策略和蟻群個體間相互協(xié)作產(chǎn)生正反饋來實現(xiàn)最優(yōu)解的搜索,蟻群算法的核心思想是狀態(tài)轉(zhuǎn)移概率和信息素的更新方式。

1.2.1 狀態(tài)轉(zhuǎn)移概率

在算法的初始時刻,各條路徑上的信息量相同,設(shè)τij(0)=C0(C0為常數(shù))。螞蟻k根據(jù)目標點的能見度和路徑上的信息素量作出判斷,t時刻由節(jié)點i轉(zhuǎn)移到節(jié)點j的概率由式(9)所示:

(9)

1.2.2 信息素函數(shù)的更新

隨著時間的推移,以前留下的信息逐漸消逝,用參數(shù)1-ρ表示信息的消逝程度,當蟻群完成一次循環(huán)時,最優(yōu)路徑上的信息量根據(jù)式(10)做調(diào)整:

τij(t+1)=(1-ρ(t)).τij(t)+τij(t)ρ(t)∈(0,1)

(10)

(11)

2 研究方法

蟻群算法主要是根據(jù)信息素和啟發(fā)式搜索相結(jié)合來完成路徑搜索的。在算法初期,通過隨機選擇策略來構(gòu)造路徑,算法收斂速度較慢;在協(xié)作階段,通過蟻群協(xié)作的正反饋作用,信息素的更新使得較優(yōu)路徑被選擇的概率增大,但易導(dǎo)致算法出現(xiàn)停滯現(xiàn)象。在火災(zāi)環(huán)境中,由于個體情緒差異對路徑選擇的影響較大,我們還需考慮個體情緒的差異性,不同情緒狀態(tài)的個體對路徑的選擇不同。

為解決上述問題,本文不僅改進蟻群算法,并且根據(jù)OCEAN人格特征理論[19]將個體情緒分為松弛、平靜和急躁三種情緒狀態(tài)。

2.1 啟發(fā)式函數(shù)的改進

個體活動性指數(shù)Mij(t)受到火災(zāi)產(chǎn)物和人員密度的影響,如式(12)所示:

Mij(t)=fij(T)×fij(ρco)×fij(Kc)×fij(D0)

(12)

疏散人員的速度受到活動性指數(shù)的影響,當量速度如式(13)所示:

Vt=V0×Mij(t)=V0×fij(T)×fij(ρco)×fij(Kc)×fij(D0)

(13)

式中,V0表示個體在不受火災(zāi)影響和人員密度影響的疏散速度fij(T),fij(ρco),fij(Kc),fij(D0)采用經(jīng)驗公式計算。

通道的通行難易系數(shù)如式(14)所示:

(14)

在火災(zāi)的復(fù)雜環(huán)境中,幾何空間上的最短疏散路徑并不等于疏散時間最短的路徑,考慮到人員活動性指數(shù)和路徑的通行難易系數(shù)的影響,疏散路徑的當量長度Dij(t)如式(15)所示:

(15)

式中,Lij是路徑的幾何長度。

啟發(fā)函數(shù)ηij(t)表示從當前節(jié)點到下一個節(jié)點轉(zhuǎn)移的啟發(fā)程度,如(16)所示:

(16)

通過式(16)可知,當溫度、有毒有害氣體濃度、能見度以及人員密度越大,Mij(t)越小,螞蟻選擇該條路徑的概率降低。

2.2 動態(tài)自適應(yīng)調(diào)整信息素強度

在基本蟻群算法中,信息素強度Q始終是一個常數(shù),它的大小直接影響算法的停滯性。為了使螞蟻在搜索過程中路徑上的信息素減少或增多的情況下,隨機搜索和路徑信息的啟發(fā)作用之間繼續(xù)保持“探索”和“利用”的平衡點,本文借鑒最大最小蟻群系統(tǒng)(MMAS)[12]中的信息素限制,將各路徑上的信息素量限制在[fPhrm-min,fPhrm-min]范圍內(nèi),如式(17)所示:

(17)

在螞蟻選擇下一個節(jié)點時,對路徑(i,j)按式(18)進行局部信息素更新,目的是使已經(jīng)走過的路徑對后面的螞蟻產(chǎn)生較小的吸引力,避免螞蟻過早的收斂到同一路徑。

τij=(1-ζ)·τij(t)+ζ·τ0

(18)

式中,ζ為局部信息素揮發(fā)因子,τ0為常數(shù)。

在所有螞蟻完成一次循環(huán)后,迭代最優(yōu)螞蟻與按交叉概率Pc抽取的其他螞蟻之間進行交叉,然后比較兩條路徑是否經(jīng)過了相同的柵格點,在兩條路徑都經(jīng)過的柵格點中隨機選擇其中一個柵格點進行交叉產(chǎn)生變異,若沒有經(jīng)過相同的柵格點,則不進行交叉處理。

在螞蟻搜索最優(yōu)路徑的過程中,如果一段時間內(nèi)最優(yōu)解沒有變化,說明搜索可能陷入某個極值點,但是該極值點未必是全局最優(yōu)解。此時采用強制機制減小要增加的信息量,即時變函數(shù)Q(t)減小,如式(19)所示:

(19)

在完成一次循環(huán)后,通過交叉操作得到最優(yōu)路徑,并對該路徑上的信息素按照式(11)進行全局更新。

2.3 個體情緒的數(shù)學(xué)模型

在疏散過程中,每個個體的內(nèi)在屬性不同,也就是對方向的偏好程度不同,本文根據(jù)OCEAN人格特征理論[21]將個體情緒分為松馳、平靜和急躁三種情緒狀態(tài)，分別用Srelaxed,Scalm,Simpatient表示。

其中OCEAN含義如下:

PO:經(jīng)驗開放性(Openness to Experience);

PC:公正性(Conscientiousness);

PE:外向性(Extroversion);

PA:親和性(Agreeableness);

PN:情緒性(Neuroticism)。

每種要素都包含積極(+)和消極(-)兩個方面,用來衡量不同的行為策略,情緒模型的形容詞描述如表1所示:

表1 情緒狀態(tài)——情緒模型的形容詞描述Table 1 Emotional state-adjective description of emotion model.

對于急躁情緒的個體,傾向于速度更快的路徑,寧愿繞遠路而不愿等待;對于松弛情緒的個體思路簡單,更傾向?qū)嚯x的偏好,選擇距離最短的路徑;而平靜的個體,具有理性的判斷能力,將會傾向于花費時間最短的路徑[22]。

在火災(zāi)環(huán)境中,三種情緒狀態(tài)的個體在數(shù)量上服從正態(tài)分布,急躁個體在多數(shù),而平靜和松弛個體占少數(shù)。在火災(zāi)初期,個體受到火災(zāi)產(chǎn)物的影響較小,隨著火情的蔓延和發(fā)展,個體受到溫度、有毒有害氣體濃度和能見度的影響越來越大,個體的內(nèi)在屬性發(fā)生變化,部分平靜和松弛的個體轉(zhuǎn)化為急躁個體。

在正常情況下,個體都會選擇當量長度最短的路徑,但是火災(zāi)環(huán)境復(fù)雜,不同情緒的個體根據(jù)環(huán)境信息和路徑上的個體數(shù)量做出不同路徑選擇行為。假設(shè)個體總數(shù)量為p,各條路徑上的個體數(shù)量分別為o1,…,oj,…,on(o1表示最短路徑上的個體數(shù)量,o2表示次短路徑上的個體數(shù)量,以此類推,on表示最遠路徑上的個體數(shù)量;n表示路徑總數(shù)量),F=0 表示距離個體i當量長度最短的路徑,F=1表示個體i放棄最短路徑尋求自身最優(yōu)路徑。個體i對路徑的選擇如式(20)所示:

(20)

公式(20)的具體含義如下:

(1)當個體i情緒狀態(tài)屬于Srelaxed時,個體i選擇當前距離自身當量長度最短的路徑o1;

(3)當個體i情緒狀態(tài)屬于Simpatient且不存在其它路徑oj小于當前路徑o1時,個體選擇當前路徑o1,否則個體i放棄o1,尋找其它路徑;

當個體i放棄當量最短路徑后,個體i將選擇次短當量路徑進行同樣的判斷,直至疏散完成。

3 算法步驟

算法先將火災(zāi)環(huán)境作柵格處理,建立環(huán)境模型,在算法搜索過程中,始終將所有路徑上的信息素濃度限制在[fPhrm-min,fPhrm-min]范圍內(nèi)。

輸出其中一個出口的最優(yōu)路徑的算法主要步驟如下:

1)環(huán)境初始化:溫度T、一氧化碳濃度ρco、減光系數(shù)Kc、人員密度D0和通道通行的難易系數(shù);

2)參數(shù)初始化:信息啟發(fā)因子α、期望啟發(fā)因子β、信息素揮發(fā)因子ρ、信息素強度Q、Nc=0、最大迭代次數(shù)Ncmax、螞蟻數(shù)量;

3)算法進行循環(huán)迭代,計算各參數(shù)的值和啟發(fā)函數(shù),第k只螞蟻按式(16)的啟發(fā)函數(shù)計算狀態(tài)轉(zhuǎn)移概率選擇下一個要行進的節(jié)點;

4)按照式(18)進行信息素的局部更新;

5)當所有螞蟻完成一次周游后,找出本次迭代中的最優(yōu)路徑,按照交叉概率Pc選擇一個螞蟻的路徑,和最優(yōu)路徑生成相同柵格信息集合SG,從中選擇一個柵格作為交叉點,進行交叉操作;

6)記錄當前最優(yōu)路徑;

9)信息素按照式(19)中的Q3進行全局更新;

10)判斷是否滿足收斂條件或是達到了最大迭代次數(shù),如果是,轉(zhuǎn)11),否則Nc=Nc+1,轉(zhuǎn)3);

11)輸出結(jié)果。

在輸入此出口的最優(yōu)路徑后,通過上述方法輸出到其他出口的最優(yōu)路徑。不同情緒個體的路徑選擇算法步驟如下:

1)設(shè)置所有路徑的集合S;

2)對個體i首先按式(20)進行判斷,如果F=0,那么個體i選擇最短當量路徑,否則轉(zhuǎn)3);

3)把最短當量路徑從集合S中移除,選擇此時集合S中最短當量路徑,j=j+1;

5)若S非空,重復(fù)步驟3)和4);

6)結(jié)束。

4 實驗仿真與分析

為了驗證本文方法的有效性,設(shè)置三組實驗對改進蟻群算法和不同情緒的個體對路徑選擇進行驗證。首先,對比僅引入火災(zāi)產(chǎn)物的啟發(fā)式函數(shù)與同時引入人員密度的啟發(fā)式函數(shù)對人員選擇節(jié)點的影響;其次,將火災(zāi)環(huán)境分為初期和蔓延兩個階段,對比本文所提出的改進蟻群算法與文獻[10]的收斂速度;最后,根據(jù)出口個數(shù)生成對應(yīng)的路徑數(shù)量,在火災(zāi)的不同階段,顯示不同情緒個體對路徑選擇情況。本文中模擬的是在建筑物內(nèi)的火災(zāi),可燃障礙物的燃點為松木的燃點取值250℃,在火災(zāi)初期火源所釋放的熱量參考美國國家技術(shù)和標準協(xié)會制定的,取值為460 kW,不考慮復(fù)雜建筑情況,通道難易系數(shù)為1。

4.1 實驗一

在本次實驗中,設(shè)置8個節(jié)點,8個節(jié)點的距離矩陣如表2所示。為了驗證幾何長度、文獻[10]中長度和本文長度對路徑選擇的影響,本文計算節(jié)點1分別到節(jié)點2、…、節(jié)點8的路徑選擇,輸入各個節(jié)點初始狀態(tài)的溫度、有毒有害氣體濃度、減光系數(shù)和人員密度參數(shù),如表3所示。

表2 節(jié)點的距離矩陣Table 2 Distance matrix of nodes

節(jié)點1到其他7個節(jié)點之間的路徑長度對比如圖3所示。在圖3中,幾何長度表示以距離的倒數(shù)為啟發(fā)函數(shù),當量長度1表示文獻[10]中當量長度,當量長度2表示本文當量長度。

表3 初始狀態(tài)的參數(shù)Table 3 Parameters of the initial state

由于在一定范圍內(nèi)的溫度對個體速度的影響可能是正向的,當量長度可能小于幾何長度。從圖3中可以得出,火災(zāi)產(chǎn)物和人員密度對啟發(fā)式函數(shù)的影響是不可忽視的,這將影響著個體對路徑的選擇。

Fig.3 Length comparison of nodes圖3 節(jié)點的長度對比

如果不考慮路徑的實際情況,僅從距離的角度利用蟻群算法進行優(yōu)化,得到的運行結(jié)果如下。從節(jié)點1到各個節(jié)點的最優(yōu)路徑為:

1-->2

1-->3

1-->3-->4

1-->2-->5

1-->3-->7-->6

1-->3-->7

1-->2-->5-->8

在文獻[10]中引入火災(zāi)產(chǎn)物對路徑選擇的影響后,從節(jié)點1到各個節(jié)點的最優(yōu)路徑為:

1-->2

1-->3

1-->2-->4

1-->2-->4-->5

1-->2-->4-->7-->6

1-->2-->4-->7

1-->2-->4-->7-->8

在本文中,引入火災(zāi)產(chǎn)物的基礎(chǔ)上,加入人員密度對路徑選擇的影響后,從節(jié)點1到各個節(jié)點的最優(yōu)路徑為:

1-->2

1-->3

1-->3-->4

1-->2-->5

1-->2-->4-->7-->6

1-->2-->4-->7

1-->2-->4-->7-->8

對上述結(jié)果分析可知,文獻[10]和本文中從節(jié)點1到節(jié)點5的路徑選擇不同,文獻[10]中的當量長度小于本文的當量長度,說明引入人員密度的影響是不可忽視的。盡管存在一些節(jié)點的路徑選擇相同,但是文獻[10]中的當量長度總體上是小于本文的當量長度。引入火災(zāi)產(chǎn)物和人員密度的影響后,雖然在路徑選擇時走了更多的幾何距離,但是它考慮了一些實際情況如溫度、有毒有害氣體濃度等因素,逃離到目標節(jié)點所需時間更短,這在應(yīng)急路徑選擇中具有更為重要的意義。

4.2 實驗二

在火災(zāi)環(huán)境下的疏散過程中,火災(zāi)產(chǎn)物的參數(shù)在變化,路徑的當量長度也隨之改變。本文在Matlab仿真環(huán)境中,對算法的有效性進行驗證,初始化動態(tài)自適應(yīng)蟻群算法的參數(shù),參數(shù)設(shè)置:取α=1,β=10,ρ=0.5,Q=100,m=100,Ncmax=200。由于火災(zāi)環(huán)境是動態(tài)變化的,因此把火災(zāi)環(huán)境分為兩個階段:火災(zāi)初期和火災(zāi)蔓延發(fā)展階段。在火災(zāi)初期,火災(zāi)產(chǎn)物對人員的影響較小,設(shè)定起火位置鄰域的溫度、有毒有害氣體濃度、能見度和各個節(jié)點的人員密度;在火災(zāi)發(fā)展蔓延階段,火不斷向周圍釋放熱量,甚至引起其他障礙物燃燒,有毒有害氣體濃度越來越大,并且能見度越來越低,個體將會繞遠路向出口方向移動。為了保證相同環(huán)境,文獻[12]中的蟻群算法也引入人員密度因素,分別在火災(zāi)初期和火災(zāi)蔓延時期的條件下,與本文改進的蟻群算法的收斂性做對比,如圖4所示。

Fig.4 Ant colony algorithm in this paper is compared with the ant colony algorithm in literature 12圖4 本文蟻群算法與文獻[12]算法的對比結(jié)果

從圖4中可以得出,無論是在火災(zāi)初期還是火災(zāi)蔓延發(fā)展階段,本文所提出的改進的蟻群算法收斂速度均比文獻[12]算法收斂速度要快。隨著火勢的發(fā)展,火災(zāi)產(chǎn)物對個體的影響越來越大,根據(jù)HRR,普通柵格轉(zhuǎn)化為起火柵格或者障礙物柵格,個體從起始位置到出口位置的距離也越來越大,時間越久,越不利于疏散。

Fig.5 Individual choice of route in early stage of fire圖5 火災(zāi)初期個體對路徑的選擇情況

4.3 實驗三

本次實驗中設(shè)置了三個出口,假設(shè)共100個個體。個體的情緒狀態(tài)在數(shù)量上服從正態(tài)分布,急躁個體占大多數(shù),松弛個體和平靜個體占少數(shù)。在火災(zāi)初期階段,假設(shè)松弛和平靜的個體的數(shù)量各占20%,急躁個體占60%。在該環(huán)境中,分別生成到各個出口的最優(yōu)路徑,在這三種情緒狀態(tài)下,個體對路徑的選擇如圖5所示。其中,a代表最短當量長度上的個體數(shù)量,b代表次短當量長度上的個體數(shù)量,c代表最遠當量長度的個體數(shù)量。在初始階段,三種情緒狀態(tài)的個體分布在距離出口a最近的位置。

從圖5中的實驗結(jié)果可知:(1)在初始階段,群體運動趨勢與情緒狀態(tài)占多數(shù)的個體運動方向一致。體現(xiàn)一種群體運動的從眾心理;(2)隨著時間的推移,情緒狀態(tài)占少數(shù)個體的差異運動打破了隊形結(jié)構(gòu)使人群運動多樣化。

隨著火勢的蔓延,在高溫、有毒有害氣體濃度等壓力下個體產(chǎn)生恐慌心理,部分平靜和松弛的個體轉(zhuǎn)化為急躁個體,路徑選擇如圖6所示:

從圖6可以看出,隨著急躁個體的增加,個體更積極地尋找路徑,各個出口的利用率增加,驗證了火災(zāi)中人的行為特性,個體在遭遇火災(zāi)等突發(fā)情況時,容易失去正常的思維,注意力都集中在處理緊急情況上,此時會出現(xiàn)超常發(fā)揮的現(xiàn)象。

Fig.6 Individual choice of route in fire spread phase圖6 火災(zāi)蔓延階段個體對路徑的選擇情況

5 結(jié)束語

本文在火災(zāi)環(huán)境的背景下,采用改進的自適應(yīng)蟻群算法來模擬群體疏散行為,克服了微觀模型無法描述的整體群體逃逸行為,將整個疏散過程抽象為一個模擬空間對象隨時間流變化的物理演化過程。把個體的情緒分為平靜、松弛、急躁三類來描述不同情緒個體對路徑選擇不同的狀態(tài),多個個體相互作用與約束形成整個狀態(tài)空間的變化,從而達到整體特性與個體行為同時表現(xiàn)的效果。

在火災(zāi)環(huán)境下的群體疏散還有待在以下幾個方面進行改進:(1)結(jié)合具體工程實例,通過FDS等相關(guān)模擬軟件對建筑空間結(jié)構(gòu)進行建模,并獲取火場動態(tài)參數(shù);(2)在對個體進行情緒建模時,對個體的情緒進行量化,建立更為準確的數(shù)學(xué)模型。

[1] Von Neumann J.The General and Logical Theory of Automata[J].PapersofJohnVonNeumannonComputing&ComputerTheory,1951:1-41.

[2] 黃鵬,劉箴.一種面向人群仿真的改進型社會力模型研究[J].系統(tǒng)仿真學(xué)報,2012,24(9):1916-1919.DOI:10.16182/j.cnki.joss.2012.09.046.

[3] 李明華,袁振洲,許琰,等.基于點排隊模型的多出口疏散優(yōu)化模型研究[J].交通運輸系統(tǒng)工程與信息,2015,15(4):166-172.DOI:10.16097/j.cnki.1009-6744.2015.04.026.

[4] 何銳權(quán).基于勢能場模型的人群疏散仿真研究[D].廣州:中山大學(xué),2013.

[5] Gao Z,Qu Y,Li X,etal.Simulating the Dynamic Escape Process in Large Public Places[J].OperationsResearch,2014,62(6):1344-1357.DOI:10.1287/opre.2014.1312.

[6] Lu Y,He Y,Xia J,etal.The Application of Ant Colony Algorithm in Emergency Rescue with GIS[C]∥IGARSS 2015-2015 IEEE International Geoscience and Remote Sensing Symposium.IEEE,2015:4546-4549.DOI:10.1109/IGARSS.2015.7326839.

[7] 毛新華,王建偉,趙京,等.蟻群算法在道路應(yīng)急疏散策略選擇中的應(yīng)用[J].中國安全科學(xué)學(xué)報,2014,24(10):170-176.DOI:10.16265/j.cnki.issn1003-3033.2014.10.028.

[8] Dorigo M,Maniezzo V,Colorni A.The Ant System:Optimization by a Colony of Cooperating Agents[C]∥IEEE Transactions on Systems,Man,and Cybernetics,1996:29-41.DOI:10.1109/3477.484436.

[9] 游曉明,劉升,呂金秋.一種動態(tài)搜索策略的蟻群算法及其在機器人路徑規(guī)劃中的應(yīng)用[J].控制與決策,2017,32(3):552-556.DOI:10.13195/j.kzyjc.2016.0005.

[10] 夏小云,周育人.蟻群優(yōu)化算法的理論研究進展[J].智能系統(tǒng)學(xué)報,2016,11(1):27-36.DOI:10.11992/tis.201510002.

[11] Liu C,Yan X.Dynamic Path Planning for Mobile Robot based on Improved Ant Colony Optimization Algorithm[J].ActaElectronicaSinica,2011,38(5):65-72.

[12] 雷春英.基于改進蟻群算法的火災(zāi)疏散路徑優(yōu)化研究[D]. 武漢:武漢理工大學(xué),2014.

[13] 齊茁.建筑火災(zāi)中人員疏散自適應(yīng)蟻群算法的研究[D].沈陽:沈陽航空航天大學(xué),2011.

[14] 林基明,班文嬌,王俊義,等.基于并行遺傳-最大最小蟻群算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J].計算機應(yīng)用,2016,36(3):675-680.DOI:10.11772./j.issn.1001-9081.2016.03.675.

[15] 邱榕,范維澄.火災(zāi)常見有害燃燒產(chǎn)物的生物毒理(Ⅰ)——一氧化碳、氰化氫[J]. 火災(zāi)科學(xué),2001,10(3):154-158.

[16] Fang Z M,Song W G,Zhang J,etal.A Multi-Grid Model for Evacuation Coupling with the Effects of Fire Products[J].FireTechnology,2012,48(1):91-104.DOI:10.1007/s10694-010-0173-x.

[17] Babrauskas V,Peacock R D.Heat Release Rate:The Single Most Important Variable in Fire Hazard ☆[J].FireSafetyJournal,1992,18(3):255-272.DOI:10.1016/0379-7112(92)90019-9.

[18] Milke J A.Evaluating the Early Development of Smoke Hazard from Fires in Large Spaces[J].Transactions-AmericanSocietyofHeatingRefrigeratingandAirConditioningEngineers,2000,106(1):627-636.

[19] Jin T,Yamada T.Irritating Effects of Fire Smoke on Visibility[J].FireScience&Technology,1985,5(1):2159-64.

[20] Nelson H E,Mowrer F W.Emergency Movement[C]∥DiNenno P J,Walton W D,eds.The SFPE Handbook of Fire Protection Engineering Bethesda,MD:Society of Fire Protection Engineers,2002:3-367-363-380.

[21] Goldberg L R.An Alternative “description of personality”: the Big-five Factor Structure[J].JournalofPersonality&SocialPsychology,1990,59(6):1216-29.DOI:10.1037/0022-3514.59.6.1216.

[22] Aguirre B E.Emergency Evacuations,Panic,and Social Psychology[J].Psychiatry-interpersonal&BiologicalProcesses,2005,68(68):121-129.DOI:10.1521/psyc.2005.68.2.121.

AntColonyAlgorithmforPathPlanninginFireEnvironment

ZHENG Yanbin1,2,AN Deyu1*,LI Na1,LU Yufeng1

(1.CollegeofComputerandInformationTechnology,HenanNormalUniversity,Xinxiang453007,China;2.EngineeringLaboratoryofIntellectualBusinessandInternetofThingsTechnologies,HenanProvince,Xinxiang453007,China)

In the fire environment, to solve the problem of easily falling into local optimum for ant colony algorithm, an improved ant colony algorithm is proposed for solving the path planning problem of crowd evacuation.The improvement of ant colony algorithm includes two aspects: firstly, personnel density factor is considered in the heuristic function of ant colony algorithm；Secondly,dynamically adaptively adjust the pheromone intensity,local and global pheromone updating strategy are adopted to update the pheromone on the path.The introduction of crossover operation may enhance escape ability of the proposed algorithm. In the fire environment, the individual emotional difference has a great influence on the path choice,so the mathematical model of emotion for the individual is established,where individuals with different emotions have different choices of paths.The simulation results show that the planning method proposed can be used to plan the optimal escape route for individuals with different emotional types,and it avoids the local optimum and convergence speed is faster.

fire environment;ant colony algorithm;personnel density;crossover operation;model of emotion

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.016

2017-04-12；

2017-06-10

鄭延斌(1964-)，男，河南內(nèi)鄉(xiāng)人，教授，博士，主要研究方向：虛擬現(xiàn)實、多智能體系統(tǒng)、對策論。E-mail:zybcgf@163.com

*通信作者：安德宇(AN Deyu )，E-mail:13462307377@163.com

TP391

A

0253-2395(2017)04-0690-12