許愛軍，蘇境迎

（廣州鐵路職業(yè)技術(shù)學(xué)院，廣州510430）

基于自適應(yīng)蟻群算法的地鐵人員疏散模型?

許愛軍，蘇境迎

（廣州鐵路職業(yè)技術(shù)學(xué)院，廣州510430）

針對地鐵突發(fā)事件人員疏散模型與路徑優(yōu)化問題，提出基于神經(jīng)網(wǎng)絡(luò)自適應(yīng)蟻群算法，通過神經(jīng)網(wǎng)絡(luò)的自適應(yīng)能力動態(tài)計算通行難易系數(shù)，為蟻群信息素濃度更新和啟發(fā)函數(shù)提供分流指引，有效避免蟻群因算法提早收斂擁堵于同一路徑。通過仿真實驗證明，新算法可以有效解決初始化蟻群路徑選擇的盲目性和隨機性，能夠在最短時間內(nèi)為密集人群場所提供高效、安全的疏散方案。

疏散模型；BP神經(jīng)網(wǎng)絡(luò)；蟻群算法；通行難易系數(shù)；人員疏散；突發(fā)事件

1　引　言

地鐵作為現(xiàn)代化交通客運樞紐，大都充分利用地下空間，注重城市與服務(wù)功能的融合。但近幾年來地鐵突發(fā)事件層出不窮，在宏觀上，國家政治、經(jīng)濟高速發(fā)展伴隨著社會危機的爆發(fā)；在微觀上，地鐵空間狹小，人群密集，突發(fā)事件容易造成群死群傷。雖然地鐵有針對突發(fā)事件的應(yīng)急演練，但花費成本過高，容易流于形式。如何通過計算機建立疏散模型，仿真逃生路徑，提高應(yīng)急響應(yīng)預(yù)案是目前亟待解決的問題。

人員疏散模型始于1951年Von Neuman提出的元胞自動機理論［1］，直到80年代才應(yīng)用于疏散研究之中。如Kirchnera A提出利用人群之間摩擦力模擬二維元胞自動機［2］，Song基于元胞自動機仿真單出口房間疏散過程［3］。然而元胞自動機模型主要針對疏散個體微觀行為，沒有考慮疏散群體對個人行為的影響和機理，實際應(yīng)用效果不佳。在國內(nèi)，人員疏散算法研究仍屬于起步階段，典型的是以最短路徑作為疏散路由判定依據(jù)［4］，導(dǎo)致瓶頸效應(yīng)嚴重，疏散效率低下。

2　蟻群算法在疏散模型中的應(yīng)用

蟻群算法是基于蟻群覓食行為提出的一種仿生算法。個體螞蟻在所經(jīng)路徑都會釋放出微量信息素，后繼螞蟻則傾向于向信息素濃的方向移動。隨著時間遷移，路徑長度越短，信息素揮發(fā)越少，濃度越大，路徑選擇幾率也越大，走過的螞蟻也越多；路徑越長，信息素揮發(fā)越快，路徑最終被淘汰。信息素的正向反饋機制能夠讓蟻群在最短時間內(nèi)找到一條從巢穴到食物之間的近優(yōu)路線，廣泛應(yīng)用于多目的節(jié)點商旅問題、車輛調(diào)度和網(wǎng)絡(luò)優(yōu)化等領(lǐng)域。

將蟻群算法應(yīng)用于人員疏散模型之中，首先是因為地鐵環(huán)境一般具有多個出口，疏散問題可以轉(zhuǎn)變成一個復(fù)雜的多源多匯問題；其次，在突發(fā)事件中疏散人員置身于陌生環(huán)境或過度恐慌，其行為表現(xiàn)為自組織性和趨眾性，這和蟻群覓食行為極其相似，兼顧個體本能反應(yīng)和群體行為影響，有效彌補了元胞自動機理論的不足。然而在疏散模型中，標準蟻群算法的螞蟻個體根據(jù)附近啟發(fā)信息和信息素濃度選擇下一節(jié)點，并沒有考慮螞蟻流量和通過節(jié)點難易度的動態(tài)關(guān)系，加上初期信息素缺乏，蟻群隨機選擇路徑，導(dǎo)致算法早期在搜索出口過程中會尋找到不必要的節(jié)點。而在算法后期，部分節(jié)點信息素濃度的累加往往會造成大量螞蟻匯聚到同一路徑，算法提早收斂，造成擁堵［5］，結(jié)果與典型的將最短路徑作為疏散路由極其相似。

鑒于傳統(tǒng)蟻群算法在疏散模型中的不足和地鐵出口的多樣化設(shè)計，提出基于BP神經(jīng)網(wǎng)絡(luò)的自適應(yīng)蟻群算法用于解決地鐵站臺密集人員疏散路徑問題，引入通行難易系數(shù)，利用神經(jīng)網(wǎng)絡(luò)的自適應(yīng)學(xué)習(xí)能力計算網(wǎng)絡(luò)中各節(jié)點疏散能力和疏散流量之間的動態(tài)關(guān)系，為蟻群提供信息素和啟發(fā)函數(shù)分流指引［6］，從而避免盲目搜索和路徑擁堵問題。

3　BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方式

新算法利用BP神經(jīng)網(wǎng)絡(luò)的自適應(yīng)學(xué)習(xí)方式判定節(jié)點通行難易系數(shù)，并動態(tài)更新節(jié)點信息素的疊加濃度和啟發(fā)函數(shù)，由此計算節(jié)點轉(zhuǎn)移概率。神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方式由通行速度（正向傳播）和疏散時間（反向傳播）兩部分構(gòu)成［7］。當通行速度期望值與疏散時間結(jié)果偏差大于預(yù)設(shè)閥值，則采用反向傳播梯度調(diào)整，重復(fù)兩個過程直到偏差小于預(yù)設(shè)精度，得出通行難易系數(shù)，具體算法如下：

第一步，定義疏散通道節(jié)點集合為E=｛E12，…，Eij，…，Emn｝，通道Eij表示由節(jié)點Vi到節(jié)點Vj的有向疏散通道。Ei屬性分為靜態(tài)屬性和動態(tài)屬性，靜態(tài)屬性為Eij（Lij，ζij），其中，Lij是疏散通道物理長度，ζij是通行難易系數(shù)，其值為：

通行難易系數(shù)ζij值越大，表示節(jié)點越容易通過。其中，passed－personsij是節(jié)點i疏散到節(jié)點j的人員個數(shù)。

第二步，定義人員活動指數(shù)，由火場溫度fij（t）、有毒氣體濃度fij（ρco）和人員密度fij（Kρ）三個參數(shù)組成，影響人員活動指數(shù)Mij（t）為：

則疏散人員當量通行速度為：

其中，Vt為疏散速度，V0為正常步行基準速度。

第三步，神經(jīng)網(wǎng)絡(luò)反復(fù)計算節(jié)點疏散速度，使輸出結(jié)果不斷接近最優(yōu)值。定義輸入層有n個神經(jīng)元，隱含層有P個神經(jīng)元，輸出層有q個神經(jīng)元，初始化神經(jīng)網(wǎng)絡(luò)向量如下：

輸入向量為：X=（X1，X2，…，Xn）

隱含層輸入向量：hi=（hi1，hi2，…，hip）

隱含層輸出向量：ho=（ho1，ho2，…，hop）

輸出層輸入向量：yi=（yi1，yi2，…，yiq）

輸出層輸出向量：yo=（yo1，yo2，…，yoq）

期望輸出向量：do=（d1，d2，…，dq）

樣本數(shù)據(jù)個數(shù)：k=1，2，…m

定義精度值ε和最大學(xué)習(xí)數(shù)M，從而計算誤差函數(shù)e為：

第四步，隨機選取k個輸入樣本和期望輸出結(jié)果：

第五步，計算隱含層各神經(jīng)元輸入與輸出結(jié)果：

第六步，根據(jù)期望結(jié)果和實際輸出值，計算誤差函數(shù)對輸出層神經(jīng)元的偏導(dǎo)數(shù)δo（k）：

第七步，根據(jù)隱含層到輸出層連接權(quán)值、輸出層δo（k），計算誤差函數(shù)修正連接權(quán)值為：

第八步，利用隱含層神經(jīng)元δh（k）和輸入?yún)?shù)修正連接權(quán)值，計算全局誤差為：

第九步，判斷誤差是否小于預(yù)設(shè)精度或最大迭代次數(shù)，滿足條件則輸出通行難易系數(shù)ζij。

4　新算法蟻群疏散模型

4.1信息素濃度更新

新算法由Lij通道長度和ζij通行難易系數(shù)共同決定節(jié)點Ei的信息素濃度。節(jié)點i疏散到節(jié)點j的信息素按下式更新：

4.2啟發(fā)函數(shù)更新策略

根據(jù)神經(jīng)網(wǎng)絡(luò)中蟻群信息素誘導(dǎo)策略，每個節(jié)點啟發(fā)函數(shù)不再是一個固定值，而是隨著通行難易系數(shù)ζij變化，指引螞蟻選擇下一層節(jié)點或安全節(jié)點。這種啟發(fā)方式既體現(xiàn)疏散過程中的個體行為本能反應(yīng)［8］，又受到疏散人群總體行為影響，避免盲目搜索和路徑擁堵。啟發(fā)函數(shù)反應(yīng)螞蟻個體從節(jié)點i遷移至節(jié)點j的啟發(fā)程度，對避免算法過早收斂起到重要作用。啟發(fā)函數(shù)為：

4.3轉(zhuǎn)移概率

螞蟻個體根據(jù)疏散節(jié)點通道信息素濃度τij和啟發(fā)信息確定前進方向，轉(zhuǎn)移概率為：

5　仿真測試

5.1測試環(huán)境

選取廣州某地鐵口站臺換乘大廳作為實驗區(qū)域，疏散出口共有10處，其中A、B、C、D為站臺出入口，E、F、G、H、I、J為六個換乘出入閘，高峰客流量為500人次，如圖1所示。

圖1　實驗區(qū)域拓撲圖

5.2通行難易系數(shù)

根據(jù)各疏散出口節(jié)點實測的客流量數(shù)據(jù)特點，神經(jīng)網(wǎng)絡(luò)中輸入層采用三層神經(jīng)元，利用C＋＋在Matlab平臺上計算客流量與通行難易系數(shù)的動態(tài)關(guān)系，最大訓(xùn)練次數(shù)為1200，期望誤差目標為0.0001，初始學(xué)習(xí)速率為0.01，初始正常步行基準速度V0為2米／秒，分別計算站臺出入口、換乘出入閘的通行難易系數(shù)ζij與人員活動指數(shù)關(guān)系，如圖2所示。

圖2　通行難易系數(shù)ζij圖

5.3仿真結(jié)果分析

初始螞蟻數(shù)量為20，信息素初始濃度τij為0.5，信息素濃度更新由通行難易系數(shù)ζij動態(tài)指引，蒸發(fā)系數(shù)ρ=0.32，為避免生成螞蟻數(shù)量過大，限制最大循環(huán)次數(shù)Nmax=100。圖3是四種方法疏散效率曲線。從圖中可以看出，新算法在78秒內(nèi)疏散近90%人員。標準蟻群算法疏散效率和時間幾乎成線性關(guān)系，是因為沒有考慮通行難易系數(shù)的動態(tài)變化，大部分螞蟻涌向最優(yōu)出口造成擁擠，但疏散效率略高于元胞自動機模型。元胞自動機模型基于微觀摩擦力獨立尋徑，沒有考慮疏散人群總體行為影響，在優(yōu)化過程中一些疏散個體被引導(dǎo)至其它出口，時間浪費于節(jié)點之間尋徑遷徙。疏散效率最低的是最短路徑算法，疏散人員各自選取最近出口逃生，缺乏合理的路徑規(guī)劃致使較高的人員密度涌向較低疏散能力的節(jié)點。

圖3　疏散效率圖

表1是四種算法疏散人數(shù)情況統(tǒng)計表。由于站臺出入口同行難易系數(shù)大大高于換乘出入閘，新算法大部分螞蟻受啟發(fā)函數(shù)和信息素雙重指引分流，有效減少換乘出入閘擁擠現(xiàn)象。標準蟻群算法在選擇站臺出入口疏散人數(shù)比新算法少80人，是由于蟻群算法初期信息素不足［9］，后期過早收斂造成的。元胞自動機模型站臺出入口和換乘出入閘各自疏散人數(shù)較為均勻，說明摩擦微力在兩種不同疏散類型節(jié)點中找到平衡。最短路徑算法節(jié)點疏散人數(shù)最為均勻，且隨機性較強，部分節(jié)點擁堵現(xiàn)象嚴重。

表1　疏散人數(shù)分布情況表

6　結(jié)束語

提出基于神經(jīng)網(wǎng)絡(luò)的自適應(yīng)蟻群算法用于解決地鐵站臺密集人員疏散路徑問題［10］。通過神經(jīng)網(wǎng)絡(luò)自適應(yīng)能力動態(tài)計算通行難易系數(shù)，為蟻群信息素濃度更新和啟發(fā)函數(shù)提供分流指引，能夠為地鐵等密集人員場所提供高效、安全的疏散方案。

［1］張培紅，張蕓栗，梅志斌，董文輝.大型公共建筑物智能疏散路徑優(yōu)化自適應(yīng)蟻群算法實現(xiàn)及應(yīng)用［J］.沈陽建筑大學(xué)學(xué)報（自然科學(xué)版），2008（6）：121－125.ZHANG Peihong，ZHANG Yunli，MEI Zhibin，DONG Wenhui.Adaptive Ant Colony Algorithm Based Evacuation Route Optimization Model and Application in Large Public Building Fire［J］.Journal of Shenyang Jianzhu University（Natural Science），2008（6）：121－125.

［2］崔喜紅，李強，陳晉，陳春曉.基于多智能體技術(shù)的公共場所人員疏散模型研究［J］.系統(tǒng)仿真學(xué)報，2008（2）：1006－1010.CUI Xi－h(huán)ong，LI Qiang，CHEN Jin，CHEN Chun－xiao. Study on MA－based Model of Occupant Evacuation in Public Facility［J］.Journal of System Simulation，2008（2）：1006－1010.

［3］金美蓮，陳濤，申世飛.城市混合流疏散中不同交通方式配比對疏散時間的影響［J］.清華大學(xué)學(xué)報（自然科學(xué)版），2009（2）：179－182.JINMeilian，CHEN Tao，SHEN Shifei.Influence of transport mode choice in evacuation time in mixed traffic flow evacuation simulations［J］.J Tsinghua Univ（Sci＆Tech），2009（2）：179－182.

［4］羅元，任愛珠.基于蟻群算法的虛擬現(xiàn)實城市道路交通流模擬［J］.計算機工程與設(shè)計，2013（02）：584－593.LUO Yuan，REN Ai－zhu.Urban road traffic flow simulation in virtual reality based on ant colony algorithm［J］.COMPUTER ENGINEERING AND DESIGN，2013（2）：584－593.

［5］周繼彪，陳紅，閆彬.綜合交通樞紐安全應(yīng)急疏散路徑選擇研究［J］.中國安全科學(xué)學(xué)報，2014，24（2）：164－170.ZHOU Ji－biao，CHEN Hong，YAN Bin.Research on emergency evacuation route choice in integrated transport hub［J］.China Safety Science Journal，2014，24（2）：164－170.

［6］袁媛，汪定偉，蔣忠中.考慮路線復(fù)雜度的應(yīng)急疏散雙目標路徑選擇模型［J］.運籌與管理，2008，17（5）：73－79.YUAN Yuan，WANG Ding－wei，JIANG Zhong－zhong.Multi－objective PathSelection Model for Emergency E vacuation Taking into Account the Path Complexity［J］.Operationsresearch And Management Science，2008，17（5）：73－79.

［7］趙寶江，李士勇，余俊.基于自適應(yīng)路徑選擇和信息素更新的蟻群算法［J］.計算機工程與應(yīng)用，2007，43（3）：12－15.ZHAO Bao－jiang，LI Shi－yong，JIN Jun.Ant colony algorithm based on adaptive selection of paths and pheromone up－dating［J］.Computer Engineering and Applications，2007，43（3）：12－15.

［8］許愛軍，張文金，易丹.基于VRML的虛擬現(xiàn)實技術(shù)及應(yīng)用［J］.計算機與數(shù)字工程，2009（4）：186－189.Xu Aijun，Zhang Wenjin，Yi Dan.Virtual Reality Technology and Applications Based on VRML［J］.Computer＆Digital Engineering，2009（4）：186－189.

［9］梅志斌，董文輝，潘剛.建筑物火災(zāi)中人員疏散路徑優(yōu)化自適應(yīng)蟻群算法［J］.沈陽建筑大學(xué)學(xué)報（自然科學(xué)版），2008（4）：163－168.MEI Zhibin，DONG Wenhui，PAN Gang.Adaptive Ant ColonyAlgorithmBasedonEvacuationWayfinding Optimization Model in Building Fire［J］.Journal of Shenyang Jianzhu University（Natural Science），2008（4）：163－168.

［10］許愛軍.基于免疫克隆選擇算法的混合流水車間調(diào)度方法［J］.計算機應(yīng)用與軟件，2013（3）：75－81.Xu Aijun.HYBRID FLOW－SHOP SCHEDULING BASED ON IMMUNE CLONAL SELECTION ALGORITHM［J］.Computer Applications and Software，2013（3）：75－81.

Subway Personnel Evacuation Model Based on Adaptive Ant Colony Algorithm

Xu Aijun，Su Jingying
（Guangzhou Institute of Railway Technology，Guangzhou 510430，China）

Aiming at the problem of emergency evacuation model and route optimization of subway，an adaptive ant colony algorithm，base on neural network，is put forward in this paper，which uses the adaptive ability of neural network to calculate passing difficulty，provides hierarchical guidance for the pheromone concentration updating and heuristic function of ant colony to effectively avoid the problems of all ants congestion in the same path.Finally，the simulation experiments show that the new algorithm can solve the blindness and randomness of the initial ant colony path selection and provide a safe evacuation plan in shortest time for dense crowd.

Evacuation model；BP neural network；Ant colony algorithm；Passing difficulty coefficient；Personnel evacuation；Unexpected event

10.3969／j.issn.1002－2279.2016.01.013

TP393

A

1002－2279（2016）01－0050－04

?廣東大學(xué)生科技創(chuàng)新培育專項資金（139544）；廣東省科技計劃項目（1015A03041005）

許愛軍（1978－），男，湖南省岳陽縣人，副教授，主研方向：計算機網(wǎng)絡(luò)與智能算法、虛擬現(xiàn)實技術(shù)。蘇境迎（1994－），男，廣東省潮州市人，學(xué)生，主研方向：虛擬現(xiàn)實技術(shù)。

2015－08－17