蟻群算法在多障礙場所疏散路徑規(guī)劃中的應(yīng)用

張嘉琪 張言

摘要：文章將柵格蟻群算法應(yīng)用于多障礙場所的人員動態(tài)疏散中，對該算法提出了一些改進方法，使其搜索效率得到了一定的提高，針對所研究對象具有多障礙物、難疏散的特點，根據(jù)火災(zāi)發(fā)生時場所環(huán)境的變化特點，對場所環(huán)境進行動態(tài)分析，規(guī)劃出在最大限度保證人員安全的前提下的最短路徑，使人員在緊急情況下安全快速地所找到出口，避免緊急情況下找不到出路盲目逃生，大大提高了疏散效率，減少人員傷亡。仿真模擬結(jié)果顯示，該算法是解決動態(tài)疏散路徑規(guī)劃問題的有效方法。

關(guān)鍵詞：安全；蟻群算法；多障礙場所；路徑規(guī)劃

隨著建筑行業(yè)的發(fā)展，建筑物種類和結(jié)構(gòu)越來越多樣化，然而建筑火災(zāi)也隨之發(fā)生地越來越頻繁，由于火災(zāi)造成的人員傷亡和經(jīng)濟損失極為嚴重。尤其是多障礙物的公共場所，由于場所障礙物較多，人員對場所的環(huán)境也不熟悉，所以一旦發(fā)生火災(zāi)，逃生極為困難。當發(fā)生火災(zāi)的時候人員的恐慌和從眾心理使得群眾盲目逃生，傳統(tǒng)疏散指示圖達不到預(yù)期的疏散效果，而且火災(zāi)發(fā)生時火焰和煙氣態(tài)勢的發(fā)展變化，造成路徑通行能力的動態(tài)變化，而目前建筑物中普遍使用的大多為固定方向式指示標志，存在著當安全出口附近發(fā)生火災(zāi)時會將人員引向危險區(qū)域的隱患。蟻群算法是受到自然界中螞蟻覓食行為啟發(fā)而提出的一種仿生進化算法。研究發(fā)現(xiàn)，當發(fā)生火災(zāi)時，人員逃生特性和蟻群覓食有一定的相似性，因此，根據(jù)蟻群算法對建筑空間進行網(wǎng)格模型劃分，定義和描述建筑空間各網(wǎng)格的靜態(tài)屬性和動態(tài)屬性；根據(jù)火災(zāi)報警系統(tǒng)提供的火警信息搜索人員疏散的最優(yōu)路徑，利用軟件程序控制技術(shù)，實現(xiàn)路徑優(yōu)化算法和消防探測控制系統(tǒng)的數(shù)據(jù)傳遞，通過控制程序把最優(yōu)路徑快速規(guī)劃出來，這樣人們可以很直觀地看到當前最優(yōu)逃生路徑，避免在障礙物較多的場所找不到出口，減少了盲目逃生帶來的恐慌。

一、環(huán)境模型的建立

將要規(guī)劃路徑的區(qū)域劃分成大小相同的柵格，將原本有障礙物的柵格標記為不可行區(qū)域，剩下的柵格就是正常情況下的可行區(qū)域。在可行區(qū)域定點安裝溫度和煙氣傳感器，火災(zāi)發(fā)生時，如果某區(qū)域內(nèi)的溫度和煙氣傳感器數(shù)值有任何一個超過了安全閾值，則該區(qū)域內(nèi)的柵格被自動定義為障礙柵格，路徑只能在可行區(qū)域內(nèi)規(guī)劃。

影響動態(tài)疏散的因素有現(xiàn)場溫度、煙氣濃度以及人群擁擠狀況等，對這些因素加以權(quán)重分析得出每個柵格的風(fēng)險值，根據(jù)風(fēng)險最小的原則來規(guī)劃路徑。用下面的函數(shù)來確定由柵格i轉(zhuǎn)移到柵格j的風(fēng)險值大小

式中T、C、ρ分別表示各柵格對應(yīng)的溫度、危險氣體濃度和人流密度，a、b、c為相應(yīng)的權(quán)重系數(shù)， 表示從柵格i到柵格j的路線長度。最優(yōu)疏散路徑 即從當前點到出口累計風(fēng)險值最小的一條路徑

二、柵格蟻群算法的原理及改進

1.傳統(tǒng)蟻群算法的原理

設(shè)要規(guī)劃路徑的起點為S點，目標為O點。螞蟻從起點S出發(fā)尋找路徑，只能從其所在柵格的相鄰柵格中選擇一個前行。第k只螞蟻在t時刻從柵格i選擇柵格j行走的概率為：

表示第k只螞蟻在時段（t，t+1）留在路徑（i，j）上的信息素，列迭代之后，螞蟻最佳的路徑上，從而使算法收斂。

2.蟻群算法的改進

對于路徑規(guī)劃問題，柵格蟻群算法存在可優(yōu)化空間。

因為在火災(zāi)逃生中螞蟻搜索的目標是已知的，所以可以使用目標函數(shù)啟發(fā)法提高螞蟻搜索效率，引入啟發(fā)函數(shù)h（x）如下：

其中，啟發(fā)因子c是一個大于0的常數(shù)，決定了螞蟻受目標啟發(fā)的程度，c越大螞蟻受到的啟發(fā)強度越大。引入該啟發(fā)函數(shù)后，螞蟻的狀態(tài)轉(zhuǎn)移概率變?yōu)椋?/p>

改進之后在進行動態(tài)路徑規(guī)劃時可以減少循環(huán)次數(shù)，從而快速得到較好的路徑規(guī)劃結(jié)果。

三、蟻群算法的流程

設(shè)表示啟發(fā)因子和信息揮發(fā)率。

第一步：初始化m、x、α、β、c、ρ、x、y等參數(shù)；

第二步：判斷本次規(guī)劃是不是首次規(guī)劃，如果是，將信息素初始化為常數(shù)；否則將信息素設(shè)定為上次規(guī)劃保存的信息素值；

第三步：當x小于y時進入循環(huán)，否則轉(zhuǎn)到第八步；

第四步：對每一只螞蟻從起點開始按照式（7）選擇下一個柵格搜索路徑直到找到目標。如果沒有找到目標則讓其回到起點重新搜索并且失敗次數(shù)加一。若失敗次數(shù)累計達到最大允許失敗次數(shù)z則程序結(jié)束并返回未找到路徑；

第五步：對每只螞蟻找到的路徑與全局最佳路徑比較，如果比全局最佳路徑更好則將該路徑更新全局最佳路徑；

第六步：對全局最佳的路徑按照式（8）更新信息素；

第七步：循環(huán)計數(shù)x加一，轉(zhuǎn)到第三步；

第八步：保存本次規(guī)劃時螞蟻產(chǎn)生的信息素；

第九步：程序結(jié)束，將全局最佳路徑作為結(jié)果輸出。

四、仿真實驗

為了驗證柵格蟻群算法在多障礙區(qū)域的路徑規(guī)劃效果，選取某超市作為試驗樣本，

在LabVIEW2015開發(fā)環(huán)境下將實驗?zāi)Ｐ偷慕ㄖ矫鎴D轉(zhuǎn)換為在該環(huán)境下可用的簡易地圖。并在LabView2015開發(fā)環(huán)境下將算法程序按照前文所述的方法和流程編寫出來。

運行該程序，在前面板添加兩個標識點S和O，分別代表起點和出口，該程序規(guī)劃結(jié)果如圖中L1，即為從起點S到出口O的最短路徑，用時60毫秒。如果在這條路徑上選擇一點A設(shè)置為障礙點，并重新規(guī)劃路徑，則該程序規(guī)劃結(jié)果如圖中L2，即為在避開該障礙點A的前提下，從起點S到出口O的最短路徑，用時71毫秒。

五、實驗結(jié)論

該仿真實驗結(jié)果表明，在多障礙場所利用改進后的柵格蟻群算法規(guī)劃逃生路徑是安全可行的，該算法既能保證避開障礙物，也可以實時動態(tài)避開危險區(qū)域，并且在此前提下迅速規(guī)劃出最短的逃生路線。

參考文獻：

陳慶全.基于蟻群算法的動態(tài)人員疏散模擬[J].軟件時空，2012，（10）：424-426.

段鵬飛.面向大型場館疏散的改進多蟻群算法[J].計算機應(yīng)用研究，2013，（02）：357-359.

趙容齊.基于人工勢場法的機器人路徑規(guī)劃研究[D].山東：山東大學(xué)，2008.

王樹西，吳政學(xué).改進的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機科學(xué)，2012，（05）：223-228.

王榮，江東，韓惠.基于Floyd方法的最短路徑算法優(yōu)化算法[J].甘肅科學(xué)學(xué)報，2012，（04）：110-114.

石鐵峰.改進遺傳算法在移動機器人路徑規(guī)劃中的應(yīng)用[J].計算機仿真，2011，（04）：193-195.

邱莉莉.基于改進蟻群算法的機器人路徑規(guī)劃[D].上海：東華大學(xué)，2015.