基于自適應蟻群算法的地鐵人員疏散模型?

許愛軍，蘇境迎

（廣州鐵路職業技術學院，廣州510430）

基于自適應蟻群算法的地鐵人員疏散模型?

許愛軍，蘇境迎

（廣州鐵路職業技術學院，廣州510430）

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

疏散模型；BP神經網絡；蟻群算法；通行難易系數；人員疏散；突發事件

1　引　言

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

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

2　蟻群算法在疏散模型中的應用

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

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

鑒于傳統蟻群算法在疏散模型中的不足和地鐵出口的多樣化設計，提出基于BP神經網絡的自適應蟻群算法用于解決地鐵站臺密集人員疏散路徑問題，引入通行難易系數，利用神經網絡的自適應學習能力計算網絡中各節點疏散能力和疏散流量之間的動態關系，為蟻群提供信息素和啟發函數分流指引［6］，從而避免盲目搜索和路徑擁堵問題。

3　BP神經網絡學習方式

新算法利用BP神經網絡的自適應學習方式判定節點通行難易系數，并動態更新節點信息素的疊加濃度和啟發函數，由此計算節點轉移概率。神經網絡的學習方式由通行速度（正向傳播）和疏散時間（反向傳播）兩部分構成［7］。當通行速度期望值與疏散時間結果偏差大于預設閥值，則采用反向傳播梯度調整，重復兩個過程直到偏差小于預設精度，得出通行難易系數，具體算法如下：

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

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

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

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

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

第三步，神經網絡反復計算節點疏散速度，使輸出結果不斷接近最優值。定義輸入層有n個神經元，隱含層有P個神經元，輸出層有q個神經元，初始化神經網絡向量如下：

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

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

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

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

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

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

樣本數據個數：k=1，2，…m

定義精度值ε和最大學習數M，從而計算誤差函數e為：

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

第五步，計算隱含層各神經元輸入與輸出結果：

第六步，根據期望結果和實際輸出值，計算誤差函數對輸出層神經元的偏導數δo（k）：

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

第八步，利用隱含層神經元δh（k）和輸入參數修正連接權值，計算全局誤差為：

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

4　新算法蟻群疏散模型

4.1信息素濃度更新

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

4.2啟發函數更新策略

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

4.3轉移概率

螞蟻個體根據疏散節點通道信息素濃度τij和啟發信息確定前進方向，轉移概率為：

5　仿真測試

5.1測試環境

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

圖1　實驗區域拓撲圖

5.2通行難易系數

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

圖2　通行難易系數ζij圖

5.3仿真結果分析

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

圖3　疏散效率圖

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

表1　疏散人數分布情況表

6　結束語

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

［1］張培紅，張蕓栗，梅志斌，董文輝.大型公共建筑物智能疏散路徑優化自適應蟻群算法實現及應用［J］.沈陽建筑大學學報（自然科學版），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］崔喜紅，李強，陳晉，陳春曉.基于多智能體技術的公共場所人員疏散模型研究［J］.系統仿真學報，2008（2）：1006－1010.CUI Xi－hong，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］.清華大學學報（自然科學版），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］羅元，任愛珠.基于蟻群算法的虛擬現實城市道路交通流模擬［J］.計算機工程與設計，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］周繼彪，陳紅，閆彬.綜合交通樞紐安全應急疏散路徑選擇研究［J］.中國安全科學學報，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］袁媛，汪定偉，蔣忠中.考慮路線復雜度的應急疏散雙目標路徑選擇模型［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］趙寶江，李士勇，余俊.基于自適應路徑選擇和信息素更新的蟻群算法［J］.計算機工程與應用，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的虛擬現實技術及應用［J］.計算機與數字工程，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］梅志斌，董文輝，潘剛.建筑物火災中人員疏散路徑優化自適應蟻群算法［J］.沈陽建筑大學學報（自然科學版），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］許愛軍.基于免疫克隆選擇算法的混合流水車間調度方法［J］.計算機應用與軟件，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

?廣東大學生科技創新培育專項資金（139544）；廣東省科技計劃項目（1015A03041005）

許愛軍（1978－），男，湖南省岳陽縣人，副教授，主研方向：計算機網絡與智能算法、虛擬現實技術。蘇境迎（1994－），男，廣東省潮州市人，學生，主研方向：虛擬現實技術。

2015－08－17