基于元胞自動(dòng)機(jī)模型的地鐵人員疏散仿真研究?

許愛軍謝依馨

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

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

元胞自動(dòng)機(jī)；遺傳算法；地鐵；疏散模型

Class NumberTP393

1 引言

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

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

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

2 元胞自動(dòng)機(jī)的定義與特征

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

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

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

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

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

3.1疏散模型

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

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

其中

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

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

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

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

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

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

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

4 疏散算法設(shè)計(jì)

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

Y滿足約束條件如下

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

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

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

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

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

4.2遺傳算子設(shè)計(jì)

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

4.3疏散算法的基本流程

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

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

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

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

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

step6：輸出最佳逃生路徑。

新算法流程見圖1所示。

圖1 新算法流程圖

5 仿真測試

5.1測試環(huán)境

為驗(yàn)證本文所提方法的有效性，以廣州地鐵某站場為例進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)選取標(biāo)準(zhǔn)地鐵口站臺(tái)換乘大廳，地鐵疏散出口有10處，其中A～D為站臺(tái)出入口，E～J為出入閘［10］，見圖2所示。

圖2 仿真實(shí)驗(yàn)拓?fù)鋱D

5.2測試結(jié)果

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

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

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

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

6 結(jié)語

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

［1］呂春杉，翁文國，楊銳.基于運(yùn)動(dòng)模式和元胞自動(dòng)機(jī)的火災(zāi)環(huán)境下人員疏散模型［J］.清華大學(xué)學(xué)報(bào)，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ī)非沖突元胞自動(dòng)機(jī)模型［J］.計(jì)算機(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］.中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)，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］于群，張敏，曹娜，等.基于模糊元胞自動(dòng)機(jī)的電網(wǎng)故障演化模型［J］.計(jì)算機(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］魏娟，胡俊，張洪，等.一種元胞自動(dòng)機(jī)與類電磁法相結(jié)合的行人流模型［J］.四川大學(xué)學(xué)報(bào)（自然科學(xué)版），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］李晶晶，紀(jì)慶革.基于遺傳算法優(yōu)化多出口疏散路徑問題［J］.上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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)元胞自動(dòng)機(jī)的4類經(jīng)典分類模式［J］.計(jì)算機(jī)科學(xué)，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］劉真余，芮小平，董承瑋，等.元胞自動(dòng)機(jī)地鐵人員疏散模型仿真［J］.計(jì)算機(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］陸秋琴，楊少敏，黃光球.求解非線性方程組的元胞自動(dòng)機(jī)方法及其全局收斂性證明［J］.計(jì)算機(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］.計(jì)算機(jī)應(yīng)用，2012，32（12）：3283-3286.

［10］許愛軍，蘇境迎.基于自適應(yīng)蟻群算法的地鐵人員疏散模型［J］.微處理機(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年度大學(xué)生科技創(chuàng)新培育專項(xiàng)資金（編號(hào)：pdjh2016b0687）；廣東省科技計(jì)劃項(xiàng)目（編號(hào)：2015A030401005）資助。

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