基于元胞自動機模型的地鐵人員疏散仿真研究?

許愛軍謝依馨

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

地鐵環(huán)境相對封閉，通道復(fù)雜，發(fā)生火災(zāi)時容易造成群死群傷事件。根據(jù)疏散時人流宏觀流動和個體行為，結(jié)合地鐵建筑結(jié)構(gòu)特征，提出基于元胞自動機建立地鐵應(yīng)急疏散模型，利用遺傳算法淘汰適應(yīng)度低下的網(wǎng)格節(jié)點，從而生成全局最優(yōu)子圖，計算最佳逃生路徑。仿真實驗證明，新模型和算法平均疏散路徑長度最短，能很好地應(yīng)用于地鐵疏散預(yù)案和消防演練之中。

元胞自動機；遺傳算法；地鐵；疏散模型

Class NumberTP393

1 引言

地鐵是城市重要交通工具，也是人流密集公共場所。但地鐵建筑復(fù)雜，環(huán)境相對密閉，大多過往客流對站場環(huán)境不熟悉，一旦發(fā)生火災(zāi)事故極易引起群體恐慌，發(fā)生踐踏事故，甚至造成重大人員傷亡［1］。加強地鐵應(yīng)急預(yù)案，提高發(fā)生事故時乘客疏散效率己成為城市公共安全領(lǐng)域研究的重點和熱點。

疏散過程中受人員之間和人員與環(huán)境之間的相互影響和作用，高密度人群會出現(xiàn)聚集阻塞、自動隊列、震蕩和協(xié)作等現(xiàn)象［2～3］。為模擬疏散方式，業(yè)界提出元胞自動機、流體力學、社會力等仿生疏散模型，以此計算最佳逃生路徑，提高人員逃生和救援效率。其中，流體力學模型為減少計算復(fù)雜度，不考慮流體質(zhì)點之間的摩擦和碰撞導(dǎo)致的能量損失，將疏散人流看為無粘性的流體運動，在人流量較少時模擬精確，但當人流密度達到一定值時，該模型就會失效，并不適用于地鐵密集人員疏散模擬［4］。社會力模型主要考慮疏散人群之間的社會屬性，即人的宏觀流動，忽略人的個體行為。如當火災(zāi)發(fā)生時煙氣、高溫和缺氧對個人造成生理和心理的影響，前者影響個人行進速度和可視范圍，后者會因心理恐慌影響對最佳逃生路徑的判斷，模擬效果與真實地鐵疏散情況差距較大［5］。元胞自動機模型將疏散空間劃分為網(wǎng)格，處于網(wǎng)格中的每個單元叫做元胞。網(wǎng)格中的元胞通過相互作用動態(tài)演化，模擬人群個體行為和群體效應(yīng)。元胞自動機模型能很好地闡釋人群疏散過程中的出口動態(tài)，目前已廣泛應(yīng)用于公眾場合中的人群流動和疏散建模［6～7］。

鑒于此，本文根據(jù)疏散時人流的宏觀流動和個體行為，結(jié)合地鐵建筑結(jié)構(gòu)特征，提出基于元胞自動機建立地鐵應(yīng)急疏散模型，利用遺傳算法淘汰適應(yīng)度低下的網(wǎng)格節(jié)點，從而生成全局最優(yōu)子圖，計算最佳逃生路徑。

2 元胞自動機的定義與特征

元胞自動機是指在具有離散和有限狀態(tài)的元胞組成的元胞空間上，按照一定的局部規(guī)則，在離散的時間序列上演化的動力學系統(tǒng)［8～9］。元胞自動機模型由單個元胞、元胞狀態(tài)、鄰居元胞以及局部規(guī)則組成。

元胞自動機的定義為：定義均勻網(wǎng)格為G，元胞集合為J，其中J={0,1,2,…,i-1}，D為元胞空間維度，k為元胞在t時刻狀態(tài)，狀態(tài)集合為S。SD為狀態(tài)集S的一個分布。元胞鄰域集合為N，元胞鄰居半徑為r，局部變化規(guī)則F滿足f''→f。則在模型中元胞狀態(tài)變遷可以表示為不同時刻t下各個元胞狀態(tài)組合的演化，表示為

元胞狀態(tài)演化通過局部變化規(guī)則f函數(shù)實現(xiàn)，遍歷網(wǎng)格內(nèi)所有元胞，應(yīng)用f演變函數(shù)，得出模型全局演化規(guī)則：

從以上定義可以看出，元胞自動機具有同質(zhì)性（遵循相同的演化規(guī)則）、齊性（分布規(guī)則整齊）、時空局限性（下一時刻狀態(tài)取決于上一時刻自身及其鄰居元胞的狀態(tài)）、狀態(tài)離散有限（只能在有限的離散空間內(nèi)取值）等特征。

3 基于元胞自動機的地鐵火災(zāi)疏散模型

3.1疏散模型

在元胞自動機模型中，將地鐵疏散通道和空間劃分成0.3m×0.3m正方形元胞網(wǎng)格，每個網(wǎng)格僅能存在單個元胞個體，每個元胞個體分為被人占據(jù)和無人占據(jù)兩種情況。網(wǎng)格節(jié)點之間疏散人員按照逃生出口順序沿著網(wǎng)格從一個節(jié)點移動到另一節(jié)點，從而準確展現(xiàn)地鐵建筑結(jié)構(gòu)和障礙物位置，真實表現(xiàn)人群逃生路徑信息。

設(shè)人員疏散方向概率Pm,n為個體選取相鄰網(wǎng)格點（m，n）概率，則Pm,n可以表達式為

其中

其中，Hm,n是相鄰網(wǎng)格點（m，n）被疏散人員占據(jù)情況，Qm,n表示相鄰網(wǎng)格點（m，n）被障礙物占據(jù)情況，F(xiàn)Γ用于評價疏散人員個體對地鐵環(huán)境熟悉度和恐慌度，Tm,n是安全出口位置對網(wǎng)格點（m，n）吸引度，其值為

式中（x，y）是安全出口坐標，疏散個體選擇最優(yōu)逃離路徑為

定義L(xi,yi)為疏散人員i初始坐標，M(x,y)為疏散群體在選擇最優(yōu)路徑時相遇的聚合坐標，疏散個體在M處匯聚后列隊逃離最近逃生出口，則疏散人員選擇的全局最優(yōu)路徑疏散的最少時間需滿足d(x,y)最小值，即：

其中，Aim,n是疏散人員i對網(wǎng)格（m，n）的吸引度。

3.2火災(zāi)擴散衰減模型

定義火災(zāi)擴散和衰減過程為

其中，E是元胞自動機模型中某網(wǎng)格受火災(zāi)影響程度，A是火災(zāi)擴散系數(shù)，B是火災(zāi)衰減系數(shù)，ΔE是火災(zāi)格點與其他網(wǎng)格點之間距離。

4 疏散算法設(shè)計

疏散人員的最優(yōu)逃生路徑可以轉(zhuǎn)變?yōu)榍蠼鈫卧炊嗄康穆窂脚帕薪M合的最優(yōu)算法問題。定義地鐵共有k個目標逃生出口，則全局最優(yōu)路徑Y(jié)為

Y滿足約束條件如下

則疏散人員平均逃離路徑長度為

根據(jù)式（11）求解全局最優(yōu)解。求解全局最優(yōu)算法有蟻群算法、粒子群算法、遺傳算法等。其中蟻群和粒子群算法都容易陷入局部最優(yōu)現(xiàn)象導(dǎo)致算法提前收斂。遺傳算法通過選擇、交叉和變異三種遺傳算子保持物種多樣性，計算復(fù)雜，但能很好解決算法搜索停滯和提前收斂問題。

4.1適應(yīng)度函數(shù)建立

對逃生出口節(jié)點進行編號，范圍是1～p。矩陣pop表示染色體數(shù)量，popsize為矩陣pop行數(shù)，c為矩陣pop列數(shù)，矩陣中每行對應(yīng)pop的每個染色體。Pn為逃生路徑段［p1，p2，p3，…，pn］的累加長度，即逃生總路徑長度，以此建立適應(yīng)度評價函數(shù)為

其中，kru(v0)為平均逃生路徑總長度，kru(x)為網(wǎng)格節(jié)點［x1，x2，x3…，xn］所確定的逃生最優(yōu)路徑。引入遺傳算法目的在于判斷每次生成的路徑子圖是否滿足適應(yīng)度條件，通過循環(huán)迭代淘汰元胞自動機模型中適應(yīng)度低下網(wǎng)格節(jié)點，從而生成全局最優(yōu)子圖。

4.2遺傳算子設(shè)計

定義Pc為單點交叉概率，其值越大，表示遺傳算法中產(chǎn)生新個體速率越快，搜索速度也越大，從而加速解的收斂。交叉概率Pc為

4.3疏散算法的基本流程

step1：初始化種群數(shù)量和最大迭代次數(shù)；

step2：在相鄰的元胞中選擇一個個體作為父代；

step3：選擇鄰居元胞與中心元胞進行交叉和變異操作；

step4：判斷算法是否收斂，否則返回step2元胞操作；

step5：根據(jù)適應(yīng)度函數(shù)判斷新生成的個體是否優(yōu)于元胞，是則替換元胞，否則返回step2，以此淘汰適應(yīng)度低下的網(wǎng)格節(jié)點；

step6：輸出最佳逃生路徑。

新算法流程見圖1所示。

圖1 新算法流程圖

5 仿真測試

5.1測試環(huán)境

為驗證本文所提方法的有效性，以廣州地鐵某站場為例進行仿真實驗。實驗選取標準地鐵口站臺換乘大廳，地鐵疏散出口有10處，其中A～D為站臺出入口，E～J為出入閘［10］，見圖2所示。

圖2 仿真實驗拓撲圖

5.2測試結(jié)果

在測試實驗中，將地鐵換乘站廳劃分成元胞空間為1000*600網(wǎng)格，人員節(jié)點均勻分布于站廳各處，疏散速度為1m/s。在遺傳算法中，初始群體大小pop為200，最大遺傳代數(shù)500，初始化交叉概率Pc＝0.8，變異概率Pm＝0.01。圖3是不同人群規(guī)模與疏散總距離之間的關(guān)系，圖4是不同人群規(guī)模與疏散時間之間的關(guān)系。

圖3 疏散人數(shù)對疏散距離的影響

在圖3，由于人群列隊行進，疏散人數(shù)對疏散距離影響不大，兩者呈線性增長。在圖4，當人數(shù)少于100時疏散時間隨疏散人數(shù)勻速增長，當超過120人次時發(fā)生擁堵，180人次時嚴重擁堵，疏散時間消耗迅速增加。圖5是不同疏散算法對疏散時間的影響。初期疏散人數(shù)少于120人次時，三種算法疏散時間相差不大，新算法略優(yōu)。

隨著疏散人數(shù)的增加，蟻群算法和粒子群算法在不同程度上陷入局部最優(yōu)現(xiàn)象，算法提早收斂。新算法利用遺傳迭代淘汰元胞自動機模型中適應(yīng)度低下的網(wǎng)格節(jié)點，從而生成全局最優(yōu)子圖，疏散時間最短。

6 結(jié)語

本文提出了基于元胞自動機模型建立地鐵應(yīng)急疏散模型。模型利用遺傳迭代淘汰元胞自動機模型中適應(yīng)度低下的網(wǎng)格節(jié)點，從而生成全局最優(yōu)子圖。通過仿真，對不同人群規(guī)模與疏散總距離、疏散時間分別進行模擬，得出結(jié)果：1）疏散人數(shù)與疏散距離兩者呈線性增長，兩者之間的影響關(guān)系不大；2）當疏散人數(shù)達到站場容量某個定值時，疏散時間明顯增加。因此，在地鐵人流高峰時期，進行客流高峰管制對地鐵站的秩序安全有重要作用。本文還分別對粒子群算法、蟻群算法和本文提高的新算法進行了對比分析，結(jié)果顯示三種疏散算法在疏散時間方面，新算法略優(yōu)，但在疏散效率方便，新算法具有明顯優(yōu)勢，能很好地應(yīng)用于地鐵疏散預(yù)案和消防演練之中。

［1］呂春杉，翁文國，楊銳.基于運動模式和元胞自動機的火災(zāi)環(huán)境下人員疏散模型［J］.清華大學學報，2007，47（12）：72-76.

LU Chunshan，WENG Wenguo，YANG Rui.Fire evacua?tion model based on motor schema and cellular automaton［J］.Joumal of Tsinghua Univ（Sci&Tech），2007，47（12）：72-76.

［2］連培昆，李振龍，榮建，等.基于VISSIM微觀交通仿真軟件的導(dǎo)流島機非沖突元胞自動機模型［J］.計算機應(yīng)用，2016，36（6）：1745-1750.

LIAN Peikun，LI Zhenlong，RONG Jian，et al.Cellular au?tomaton model of vehicle-bicycle conflict at channelized islands based on VISSIM microscopic traffic simulation software［J］.Journal of Computer Applications，2016，36（6）：1745-1750.

［3］汪金輝，陸守香.建筑火災(zāi)中人員安全疏散的可靠概率分析模型［J］.中國科學技術(shù)大學學報，2006，36（1）：116-118.

WANG Jinhui，LU Shouxiang.Model of probabilistic risk assessment for evacuation under building fire［J］.Jounal of University of Science and Technology of china，2006，36（1）：116-118.

［4］于群，張敏，曹娜，等.基于模糊元胞自動機的電網(wǎng)故障演化模型［J］.計算機應(yīng)用，2015，35（9）：2682-2686.

YU Qun，ZHANG Min，CAO Na，et al.Power grid fault evolution model based on fuzzy cellular automata［J］.Jour?nal of Computer Applications，2015，35（9）：2682-2686.

［5］魏娟，胡俊，張洪，等.一種元胞自動機與類電磁法相結(jié)合的行人流模型［J］.四川大學學報（自然科學版），2016，53（4）：753-758.

WEI Juan，HU Jun，ZHANG Hong，et al.A pedestrian eca?cuation model based on cellular auto maton and electro?magnetism mechanism［J］.Journal of Si Chuan University（Natural Science edition），2016，53（4）：753-758.

［6］李晶晶，紀慶革.基于遺傳算法優(yōu)化多出口疏散路徑問題［J］.上海師范大學學報（自然科學版），2008，37（4）：383-389.

LI Jingjing，JI Qingge.Research on GA-based optimizin gmulti-exit evacuation path problem［J］.Journal of Shang hai NormalUniversity（Natural Sciences），2008，37（4）：383-389.

［7］曾平安，鄭智捷.利用變值編碼展現(xiàn)元胞自動機的4類經(jīng)典分類模式［J］.計算機科學，2016，43（6A）：139-141.

ZENG Pingan ZHENG Zhijie.Using Variable Value Cod?ing to Show 4 Classical Classification Models of Cellular Automata［J］.Computer Science，2016，43（6A）：139-141.

［8］劉真余，芮小平，董承瑋，等.元胞自動機地鐵人員疏散模型仿真［J］.計算機工程與應(yīng)用，2009，45（27）：203-205.

LIU Zhenyu，RUI Xiaoping，DOND Chengwei，et al.Simu?lation of urgent evacuation in subway station based on Cel-lular Automation［J］.Computer Engineering and Ap?plications，2009，45（27）：203-205.

［9］陸秋琴，楊少敏，黃光球.求解非線性方程組的元胞自動機方法及其全局收斂性證明［J］.計算機應(yīng)用，2012，32（12）：3283-3286.

LU Qiuqin，YANG Shaomin，HUANG Guangqiu.Cellular automata method for solving nonlinear systems of equa?tions and its global convergence proof［J］.計算機應(yīng)用，2012，32（12）：3283-3286.

［10］許愛軍，蘇境迎.基于自適應(yīng)蟻群算法的地鐵人員疏散模型［J］.微處理機，2016，37（01）：50-53.

XU Aijun，SU Jingying.Subway Personnel Evacuation Model Based on Adaptive Ant Colony Algorithm［J］.Mi?cro Processors，2016，37（1）：50-53.

Research on Subway Evacuation Simulation Based on Cellular Automata Model

XU AijunXIE Yixin
（Guangzhou Railway Polytechnic，Guangzhou510430）

Metro subway underground is too complex to cause fire.According to evacuation flow and individual behavior，com?bined with the structural features in subway，this paper put forward a subway emergency evacuation model based on cellular automa?ta，and use genetic algorithm to eliminate unsuitable grid nodes.Simulation results show that the new algorithm can evacuate more than 80%passengers in the shortest time，and has the shortest evacuation routing length，can be used in subway evacuation plans and fire drills.

cellular automata，genetic algorithm，metro，evacuation model

TP393

10.3969/j.issn.1672-9722.2017.05.033

2016年11月5日，

2016年12月26日

2016年度大學生科技創(chuàng)新培育專項資金（編號：pdjh2016b0687）；廣東省科技計劃項目（編號：2015A030401005）資助。

許愛軍，男，教授，研究方向：數(shù)據(jù)管理系統(tǒng)與智能算法、虛擬現(xiàn)實技術(shù)。謝依馨，男，研究方向：虛擬現(xiàn)實技術(shù)。