蟻群算法在消防疏散平臺上的應用

馮韋韋,裘 炅

(杭州電子科技大學 計算機學院,浙江 杭州 310018)

蟻群算法在消防疏散平臺上的應用

馮韋韋,裘 炅

(杭州電子科技大學 計算機學院,浙江 杭州 310018)

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

蟻群算法;人員疏散路徑優化;動態顯示;地圖可視化顯示

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

1 模型建立

1.1 建筑物空間模型建立

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

1.2 人員選擇策略

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

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

if (dbTemp<=0.0)

nIndex=i;

break;

當移動到一個可行節點時將其設置為MOVED類型并插入非禁忌表中,若該節點為END類型則計算本次行走的路徑長度。

1.3 信息素更新策略

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

2 疏散路徑尋優流程

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

圖1 流程圖

蟻群算法主要包括4個步驟:參數初始化、選擇下一個節點形成可行路徑、更新信息素和獲得最優解[6]。算法實現的過程可如下表示:

(1)初始化。

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

tabuAry.Removeall();

ptCurrent=ptStart;

tabuAry.add(ptCurrent);

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

dbPathLength=0.0.

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

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();

其中,選擇下一個節點的函數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++;

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

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

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

dbTemp=1.0/最優個體走過的路徑長度。

for (int j=0;j<最優個體路徑點數;j++)

pt=bestAnt.tabuAry.GetAt(j);

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

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

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

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

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

(5)若當前迭代次數為Nmax,則記錄最優路徑及路線,否則執行(1)。

(6)將獲得最優集合節點顯示在可視化界面中。

(7)結束。

3 算法可行性分析

3.1 節點可行性策略

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

圖2 路徑圖

3.2 收斂性分析

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

圖3 收斂圖

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

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

4 火災疏散仿真

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

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

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

圖4 房間中疏散模擬

根據人員流動的特點,對出口利用率形成如圖5所示的曲線,其中實線表示上面出口A的流量圖,虛線表示出口B流量圖,當A中流量過多時,B總可以對其保持平衡。

圖5 出口利用圖

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

圖6 多樓層疏散模擬

5 結束語

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

[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] 賈磊,程乃偉.基于蟻群算法的動態疏散路徑改進[J].科技傳播,2013(20):85-86.

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

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

[5] 崔喜紅,李強,陳晉.大型公共場所動態引導人移動路徑設計方法[J].中國安全科學學報,2008(11):48-54,177.

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

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

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

[9] 項前,趙永光.基于多目標蟻群優化的交通路徑優化研究[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—),女,碩士研究生。研究方向:消防物聯。E-mail:475707372@qq.com

10.16180/j.cnki.issn1007-7820.2015.04.004

TP301.6

A

1007-7820(2015)04-013-04