蟻群算法在消防疏散平臺上的應(yīng)用

馮韋韋,裘 炅

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院,浙江 杭州 310018)

蟻群算法在消防疏散平臺上的應(yīng)用

馮韋韋,裘 炅

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院,浙江 杭州 310018)

為保證火災(zāi)現(xiàn)場人員能夠快速安全疏散,在利用火災(zāi)探測系統(tǒng)得到火源位置信息的基礎(chǔ)上,利用數(shù)據(jù)庫技術(shù)對建筑節(jié)點(diǎn)、通道的靜態(tài)和動態(tài)屬性進(jìn)行存儲,并結(jié)合在建筑物空間結(jié)構(gòu)模型的基礎(chǔ)上,利用已改進(jìn)的蟻群算法,找出人員疏散的最優(yōu)路徑,并將其通過智能指示燈動態(tài)顯示方向,室外工作人員依據(jù)可視化界面顯示的可行路徑進(jìn)行實(shí)時、快速調(diào)度,將該層平面圖、疏散路徑信息發(fā)送給事故現(xiàn)場人員。實(shí)驗(yàn)結(jié)果表明,該方法可使被困人員快速找到安全出口,有效減少人員和財(cái)產(chǎn)損失。

蟻群算法;人員疏散路徑優(yōu)化;動態(tài)顯示;地圖可視化顯示

目前國內(nèi)外的建筑多是高樓大廈且結(jié)構(gòu)較為復(fù)雜,如何在多層建筑的多出口中找出最短路徑成為人在緊急情況下最復(fù)雜的表現(xiàn)活動之一,受趨眾性等因素影響表現(xiàn)為疏散速度緩慢、迷路等,大多數(shù)人采用具有正反饋性、分布式計(jì)算機(jī)制且富有建設(shè)性的貪婪啟發(fā)式搜索[1]的蟻群算法獲取最佳路徑。人們提出了很多改進(jìn)的疏散模型應(yīng)用于安全疏散過程,且大多假設(shè)人群在疏散過程中總向最近出口行徑,研究的重點(diǎn)在于降低蟻群算法運(yùn)算時間,誘導(dǎo)蟻群尋找更優(yōu)解。主流方法主要是在通道上以熱輻射通量為限定條件獲得障礙點(diǎn)[2],在比值函數(shù)的基礎(chǔ)上設(shè)計(jì)了動態(tài)引導(dǎo)人移動路徑的方法[3],將遺傳算法的復(fù)制、交叉和變異等遺傳算子引入蟻群算法或多蟻群算法[4],以提高收斂速度和全局搜索能力,另外引入一種確定性搜索方法,加快啟發(fā)式搜索的收斂速度[5],但仍有缺陷。文中根據(jù)基于建筑物中各節(jié)點(diǎn)、通道的拓?fù)浣Y(jié)構(gòu)形成的蟻群算法對緊急疏散進(jìn)行仿真。

1 模型建立

1.1 建筑物空間模型建立

建筑物可抽象為節(jié)點(diǎn)P和通道C組成,由G(P,C)表示,路徑可表示為{G1,G2,…,Gi,…,Gm},m為路徑總數(shù)。P為建筑物中所有節(jié)點(diǎn)的集合,可表示為{P1,P2,…,Pi,…,Pn},節(jié)點(diǎn)可分為普通節(jié)點(diǎn)、障礙節(jié)點(diǎn),障礙節(jié)點(diǎn)為無法通過的節(jié)點(diǎn),普通節(jié)點(diǎn)為除障礙節(jié)點(diǎn)以外的其他節(jié)點(diǎn)。節(jié)點(diǎn)Pi可表示為Pi(xi,yi,t,ni,fi)。其中xi、yi表示節(jié)點(diǎn)在t時刻的坐標(biāo),ni表示在該時刻時位于此節(jié)點(diǎn)的人員數(shù)量,fi表示節(jié)點(diǎn)類型。C是所有通道的集合,可表示為Cij{C12,…,Cij,…,Cmn},Cij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的可連接的通道。對應(yīng)于蟻群算法中模型,疏散模型是以源點(diǎn)為蟻巢,以終點(diǎn)為食物。人群尋找出口的過程就是從源點(diǎn)經(jīng)過一定的節(jié)點(diǎn)、通道到達(dá)終點(diǎn)的過程,不同的是人員疏散結(jié)束后無需返回源點(diǎn)。

1.2 人員選擇策略

節(jié)點(diǎn)可分為0,BARRIER,START,END,MOVED五種類型,人員尋找出口的過程即是從START節(jié)點(diǎn)越過BARRIER節(jié)點(diǎn)選擇0類型的節(jié)點(diǎn)并設(shè)置為MOVED,最終抵達(dá)END節(jié)點(diǎn)。初始化人員所在位置為START節(jié)點(diǎn),從該節(jié)點(diǎn)周圍的8個節(jié)點(diǎn)判斷是否為0節(jié)點(diǎn),若是則計(jì)算周圍節(jié)點(diǎn)中各節(jié)點(diǎn)被選擇的概率prob[i]和概率之和dbTotal,并利用輪盤算法進(jìn)行選擇。在輪盤停止轉(zhuǎn)動則確定其為目標(biāo)節(jié)點(diǎn);若未停止則繼續(xù)搜索節(jié)點(diǎn),其中約束條件為:

if (prob[i]>=0) dbTemp=dbTemp-prob[i];

if (dbTemp<=0.0)

nIndex=i;

break;

當(dāng)移動到一個可行節(jié)點(diǎn)時將其設(shè)置為MOVED類型并插入非禁忌表中,若該節(jié)點(diǎn)為END類型則計(jì)算本次行走的路徑長度。

1.3 信息素更新策略

采用遺傳算法中復(fù)制的思想繼承優(yōu)質(zhì)個體的特性并進(jìn)化,適應(yīng)度高的個體被繼承到下一代的概率大,反之概率則小。本文采用排序選擇的方式,對所有個體進(jìn)行排序來分配個體被選擇的概率進(jìn)而進(jìn)行局部更新。選擇的具體操作細(xì)節(jié)如下:(1)對所有個體按信息素濃度進(jìn)行降序排列。(2)獲得各個個體被選擇的概率值。(3)將各個個體的概率值作為下一代的概率,利用輪盤算法來獲得下一代。(4)初始時刻各疏散通道的信息素濃度相同,設(shè)ζij(0)=C,信息素更新函數(shù)ζij(t+n)=ρ×ζij(t)+Δζij(t,t+n)。ζij(t)為之前所有的信息素,ρ×ζij(t)為殘留下的信息素,Δζij(t,t+n)為此時留下的信息素。信息素更新的步驟為:(1)獲取所有個體的信息素濃度。(2)計(jì)算殘留的信息素濃度。(3)獲得所有個體中路徑較短的某些優(yōu)質(zhì)個體的信息素濃度。(4)利用上式進(jìn)行信息素更新。(4)完畢。

2 疏散路徑尋優(yōu)流程

人員在疏散過程中尋找最優(yōu)路徑的流程如圖1所示。

圖1 流程圖

蟻群算法主要包括4個步驟:參數(shù)初始化、選擇下一個節(jié)點(diǎn)形成可行路徑、更新信息素和獲得最優(yōu)解[6]。算法實(shí)現(xiàn)的過程可如下表示:

(1)初始化。

設(shè)置:t=0;N=0;ζij(t)=C;

tabuAry.Removeall();

ptCurrent=ptStart;

tabuAry.add(ptCurrent);

pMapAry[ptCurrent.x][ptCurrent.y]=1;

dbPathLength=0.0.

(2)判斷下一個節(jié)點(diǎn)是否通行并記錄當(dāng)前位置、走過的路徑集合和走過的位置,當(dāng)此節(jié)點(diǎn)為終點(diǎn)時計(jì)算人員走過的路徑長度,具體代碼如下所示:

while(N<=Nmax)

for (int i=0;i

CPoint ptNext=ChooseNextCity();

tabuAry.Add(ptNext);

pMapAry[ptNext.x][ptNext.y]=MOVED;

ptCurrent=ptNext;

if (ptCurrent==ptEnd)

dbPathLength=CalPathLength();

其中,選擇下一個節(jié)點(diǎn)的函數(shù)ChooseNextCity為:

for (int i=ptCurrent.x-1;i<=ptCurrent.x+1;i++)

for (int j=ptCurrent.y-1;j<=ptCurrent.y+1;j++) nIndex++;

if (從(x0,y0)到(x,y)路徑允許)

prob[nIndex]=pow(pMapTrail[i][j],α)*pow(Q/pMapLen[i][j],β);

dbTotal=dbTotal+prob[nIndex];

nCount++;

為均衡隨機(jī)性與正反饋機(jī)制,采用輪盤算法來實(shí)現(xiàn)“擇優(yōu)錄取”原則上保持選擇的隨機(jī)性,從而彌補(bǔ)貪婪選擇策略,避免陷入局部極值的問題[7]。

(3)從所有螞蟻中獲取前幾名路徑最短的螞蟻,保存為最優(yōu)個體。

(4)遺傳復(fù)制思想來更新信息素。

dbTemp=1.0/最優(yōu)個體走過的路徑長度。

for (int j=0;j<最優(yōu)個體路徑點(diǎn)數(shù);j++)

pt=bestAnt.tabuAry.GetAt(j);

pTrail[pt.x][pt.y]=pTrail[pt.x][pt.y]+dbTemp;

for (int i=0;i<周圍環(huán)境寬度;i++)

for (int j=0;j<周圍環(huán)境高度;j++)

pMapTrail[i][j]=pMapTrail[i][j]*ρ+pTrail[i][j];

保存最短路徑和平均路徑長度。

(5)若當(dāng)前迭代次數(shù)為Nmax,則記錄最優(yōu)路徑及路線,否則執(zhí)行(1)。

(6)將獲得最優(yōu)集合節(jié)點(diǎn)顯示在可視化界面中。

(7)結(jié)束。

3 算法可行性分析

3.1 節(jié)點(diǎn)可行性策略

本文算法將建筑物節(jié)點(diǎn)分為起始、終止、障礙物、未過和已過5種類型,節(jié)點(diǎn)為未過且非障礙物類型作為選擇下個節(jié)點(diǎn)的策略之一,用禁忌表保存走過節(jié)點(diǎn)以防止形成環(huán)路;在當(dāng)前節(jié)點(diǎn)的周圍節(jié)點(diǎn)可通行的情況下,確定由信息素和節(jié)點(diǎn)間距離決定節(jié)點(diǎn)被選擇的概率,用輪盤算法的思想將該概率與概率和的隨機(jī)數(shù)進(jìn)行比較,若隨機(jī)數(shù)小即輪盤停止轉(zhuǎn)動,則記錄該概率從而確定對應(yīng)節(jié)點(diǎn)為下一選擇節(jié)點(diǎn),圖2為起始點(diǎn)到終點(diǎn)間路徑圖。

圖2 路徑圖

3.2 收斂性分析

圖3所示為本文算法中疏散路徑長度與迭代次數(shù)的關(guān)系,上方表示平均路徑曲線,下方表示最短路徑曲線。從圖中可以看出,在40代以前的各代路徑長度不一,波動較大,在40代左右時各代疏散平均路徑和最短路徑幾乎重合,路徑長度為30～35之間時疏散趨于穩(wěn)定。

圖3 收斂圖

3.3 局部收斂與全局搜索均衡性

傳統(tǒng)算法直接采用全局信息素進(jìn)行更新,忽視了最優(yōu)個體的信息素濃度,本文通過遺傳算法保存最優(yōu)個體并及時反饋到信息素的更新,在信息素更新時利用遺留的信息素與最優(yōu)個體的信息素之和來進(jìn)行更新,從而加快了收斂速度。為均衡搜索范圍,使用輪盤算法將周圍選擇節(jié)點(diǎn)隨機(jī)化而不僅局限于信息素濃度大小形成的正反饋機(jī)制,減小信息素對概率的影響而擴(kuò)大了全局搜索能力,實(shí)現(xiàn)了保留較優(yōu)個體的影響且亦能夠進(jìn)行隨機(jī)化全局搜索。

4 火災(zāi)疏散仿真

本文蟻群算法相較最大-最小算法具有較強(qiáng)的優(yōu)越性,對這兩種算法的收斂速度進(jìn)行對比,結(jié)果如表1所示。從表1中可以看出,本文算法比最大-最小算法能夠更快找到最優(yōu)解。

表1 與最大-最小算法的收斂速度比較

某建筑發(fā)生火災(zāi),該建筑內(nèi)的人員都需疏散到安全出口處,通過同一個房間和不同房間這兩種疏散模型來體現(xiàn)仿真的效果。圖4所示為一個容納15人的有兩個出口且有障礙物的房間,隨著時間的推移,人員陸續(xù)走向兩個出口,人員選擇出口的原則是走向較近出口,當(dāng)此條路徑上的人員遇到障礙物時能自行避開障礙物并繼續(xù)前行,在行進(jìn)過程中若該路徑上人員過多,即這條通道中信息素濃度過大,于是搜索全局解,走向另一個出口。

圖4 房間中疏散模擬

根據(jù)人員流動的特點(diǎn),對出口利用率形成如圖5所示的曲線,其中實(shí)線表示上面出口A的流量圖,虛線表示出口B流量圖,當(dāng)A中流量過多時,B總可以對其保持平衡。

圖5 出口利用圖

圖6所示為在多樓層情況下人員的疏散過程,通過其中的路徑線條可以看出,人員都是集中向出口走去,此時與一個房間不同,這里的目的出口只有一個而且在最底層,在樓梯口處會造成擁擠,易發(fā)生事故。

圖6 多樓層疏散模擬

5 結(jié)束語

本文以蟻群算法為基礎(chǔ)求解出人員疏散的最優(yōu)路徑,根據(jù)現(xiàn)場勢情的變化綜合考慮火災(zāi)、通道、人員等的通行能力而進(jìn)行動態(tài)求解最優(yōu)路徑進(jìn)行疏散。針對蟻群算法易收斂局部最優(yōu)的缺陷,提出了結(jié)合輪盤選擇和遺傳復(fù)制算法的思想進(jìn)行節(jié)點(diǎn)選擇決策。目前仍有問題需要解決,可對風(fēng)險(xiǎn)參數(shù)進(jìn)一步修訂以提高實(shí)現(xiàn)的準(zhǔn)確性;需利用多態(tài)蟻群思想對人員功能進(jìn)行分工得出不同類型的信息素軌跡;另外可引用更佳的算法在加速收斂和全局最優(yōu)的基礎(chǔ)上進(jìn)行優(yōu)化,應(yīng)可預(yù)測事故發(fā)展趨勢、判斷事故等級,為部署指揮救援工作提供決策依據(jù)[9]。另外可在某段區(qū)域都有固定的社區(qū)群組,例如學(xué)校、小區(qū)等通常會有論壇,使所在人群都訂閱該論壇的消息,緊急情況發(fā)生時,以類似新聞的功能推送緊急信息,便于事故現(xiàn)場人員對所處環(huán)境進(jìn)行了解。

[1] Marco Dorigo,Vittorio Maniezzo,Alberto Colorni.Ant system optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,1996,26(1):28-41.

[2] 賈磊,程乃偉.基于蟻群算法的動態(tài)疏散路徑改進(jìn)[J].科技傳播,2013(20):85-86.

[3] 邢志祥,丁芙蓉.城市人員密集場所應(yīng)急救援決策支持系統(tǒng)研究進(jìn)展[J].工業(yè)安全與環(huán)保,2014,40(2):59-62.

[4] 李永林,葉春明,劉長平.輪盤賭選擇自適應(yīng)和聲搜索算法[J].計(jì)算機(jī)應(yīng)用研究,2014(6):1665-1668.

[5] 崔喜紅,李強(qiáng),陳晉.大型公共場所動態(tài)引導(dǎo)人移動路徑設(shè)計(jì)方法[J].中國安全科學(xué)學(xué)報(bào),2008(11):48-54,177.

[6] 梅志斌,董文輝,潘剛,等.建筑物火災(zāi)中人員疏散路徑優(yōu)化自適應(yīng)蟻群算法[J].沈陽建筑大學(xué)學(xué)報(bào):自然科學(xué)版,2008(4):671-674.

[7] 段鵬飛,熊盛武,李輝.面向大型場館疏散的改進(jìn)多蟻群算法[J].計(jì)算機(jī)應(yīng)用研究,2013(2):357-359,363.

[8] 陳娟,馬曉慧.基于TSP的蟻群算法研究[J].現(xiàn)代計(jì)算機(jī):專業(yè)版,2013(3):8-11.

[9] 項(xiàng)前,趙永光.基于多目標(biāo)蟻群優(yōu)化的交通路徑優(yōu)化研究[J].微計(jì)算機(jī)信息,2012(5):8-9,47.

Application of Ant Colony Algorithm in Fire Evacuation Platform

FENG Weiwei,QIU Jiong

(College of Computer Science,Hangzhou Dianzi University,Hangzhou 310018,China)

In order to ensure the quick and safe evacuation from the fire,database is used to store information of traffic nodes and the static and dynamic states of the channel of buildings with the help of fire information from the fire detection system.On the basis of the building spatial structure model,the optimal path of evacuation is found by the improved ant colony algorithm,and then the direction is dynamically shown through intelligent indicators.Other related personnel can make a real time and quick scheduling according to the visual interface and then send maps and paths to people who are in fire.Experiments show that this method can make people find the exit more quickly,so it can reduce the loss of personnel and property in fire.

ant colony algorithm;evacuation route optimization;dynamic display;map visualization

2014- 09- 21

馮韋韋(1989—),女,碩士研究生。研究方向:消防物聯(lián)。E-mail:475707372@qq.com

10.16180/j.cnki.issn1007-7820.2015.04.004

TP301.6

A

1007-7820(2015)04-013-04