李智成，李 鋒，莫樂群

（廣東交通職業(yè)技術(shù)學(xué)院，廣州510650）

人群密集公共場所疏散算法設(shè)計研究*

李智成，李 鋒，莫樂群

（廣東交通職業(yè)技術(shù)學(xué)院，廣州510650）

通過統(tǒng)計行人交通參數(shù)數(shù)據(jù)規(guī)律和特點，設(shè)計大型公共場所行人交通狀態(tài)評價方式，提出利用元胞自動機模型模擬人群個體行為和群體效應(yīng)，再利用遺傳迭代算法淘汰適應(yīng)度低下人員節(jié)點，經(jīng)粒子群算法計算逃生路徑，生成全局最優(yōu)子圖，形成疏散方案和緊急預(yù)案。仿真實驗證明，新算法疏散效率較高，為建立完善、科學(xué)城市應(yīng)急體系提供決策與參考。

元胞自動機；遺傳算法；粒子群算法；疏散模型

1 引言

近幾年來公共場所突發(fā)事件層出不窮。在宏觀上，國家政治、經(jīng)濟高速發(fā)展伴隨著社會危機的爆發(fā)期；在微觀上，公共場所人群密集，行人對環(huán)境陌生，突發(fā)事件容易造成群死群傷事件，并且人員密度越大，事故發(fā)生幾率越高，傷亡和財產(chǎn)損失越嚴重。如何對行人交通監(jiān)控、管理和疏散成為目前研究的熱點和難點[1-2]。

在緊急疏散時，行人受到驚嚇或?qū)π颅h(huán)境陌生，個體行為既具有趨眾性，也表現(xiàn)出很大的個體差異，其逃生方向和速率是一個不斷變化的過程[3]。為準確模擬不同個體逃生方式，通過統(tǒng)計行人交通參數(shù)數(shù)據(jù)規(guī)律和特點，設(shè)計大型公共場所行人交通狀態(tài)評價方式，提出利用元胞自動機模型模擬人群個體行為和群體效應(yīng)，通過遺傳迭代算法模擬人群在具體疏散過程中的動態(tài)變化，并淘汰適應(yīng)度低下的人員節(jié)點（模擬人員受傷或者死亡），經(jīng)粒子群算法計算逃生路徑，生成全局最優(yōu)子圖，形成疏散方案和緊急預(yù)案。

2 疏散模型與算法

2.1 疏散模型

公共場所突遇突發(fā)事件時，疏散過程受人員之間和人與環(huán)境之間的相互影響，人群會出現(xiàn)聚集阻塞、自動隊列、趨眾性、震蕩和協(xié)作等現(xiàn)象，其逃生速度和方向是一個不斷變化的過程[4-5]。為模擬人群疏散方式，業(yè)界提出元胞自動機、流體力學(xué)、社會力等仿生疏散模型。其中，流體力學(xué)模型為減少計算復(fù)雜度，不考慮流體質(zhì)點之間的摩擦和碰撞導(dǎo)致的能量損失，將疏散人流看為無粘性的流體運動，在人流量較少時模擬精確，不適合密集公共場所人員建模[6]。社會力模型主要考慮疏散人群之間的社會屬性，即人的宏觀流動，忽略人的個體行為，將個體逃生方式簡單地看成是人流的勻速運動，模擬效果與真實情況差距較大[7-8]。元胞自動機模型將疏散空間劃分為網(wǎng)格，網(wǎng)格中的元胞通過相互作用和動態(tài)演化模擬人群個體行為和群體效應(yīng)。在緊急疏散中，人群會因過度驚嚇在逃生時出現(xiàn)推搡、沖撞、踩踏等事件，為反映個體逃生方式和人員狀態(tài)，文章通過遺傳算法模擬人群疏散過程中的個體動態(tài)變化，并淘汰適應(yīng)度低下的人員節(jié)點，以此檢驗疏散方案效率和公共場所建筑設(shè)計與布局的合理性。

論文通過統(tǒng)計行人交通參數(shù)數(shù)據(jù)規(guī)律和特點，結(jié)合大型公共場所行人交通應(yīng)急疏散的建筑布局特征，如廣場、步道、樓梯等，設(shè)計大型公共場所行人交通狀態(tài)評價方法，將元胞自動機模型、遺傳算法和粒子群算法有機融合，提出密集人群公共場所交通狀態(tài)評價與疏散算法，從而計算逃生路徑，形成疏散方案，讓疏散人員通過團結(jié)互助，有方向，有組織，有秩序地逃離事故現(xiàn)場，并以此檢驗和改進公共場所建筑設(shè)計與布局的合理性。

2.2 疏散算法

要計算疏散人員的最優(yōu)逃生路徑，在數(shù)學(xué)建模上可以轉(zhuǎn)變?yōu)榍蠼鈫卧炊嗄康穆窂脚帕薪M合的優(yōu)化算法問題[9]。求解全局最優(yōu)算法有Dijkstra最短路徑算法、蟻群算法和粒子群算法等。最短路徑算法只是計算行人與逃生出口之間的最短通路，而不是全局最佳路徑，會出現(xiàn)指引行人逃向事故現(xiàn)場的現(xiàn)象。蟻群算法簡單地利用路徑信息素正向反饋機制擇徑，當(dāng)信息素過濃時算法提早收斂，導(dǎo)致所有螞蟻（即行人）都走到同一路徑，導(dǎo)致?lián)砣?。粒子群算法將尋找最?yōu)問題的每個解對應(yīng)搜索空間的每個行人，稱為粒子。每個粒子的初始化向量代表行人位置和逃生速率，每個行人通過尋找附近粒子的最優(yōu)解更新自己逃生方向和速率，迭代生成全局最優(yōu)解，計算逃生路徑，生成全局最優(yōu)子圖。

3 基于元胞自動機的人員疏散模型

3.1 行人交通擁堵評價方式

采用視頻檢測器采集行人交通狀態(tài)，行人交通狀態(tài)由行人密度、速度和流量三個參數(shù)決定。其中密度是單位面積中人數(shù)，速度是人員步行速度，流量是單位時間內(nèi)經(jīng)過總?cè)藬?shù)，三者關(guān)系如下：

根據(jù)Togawa推導(dǎo)的疏散時間公式為：

在一定時期內(nèi)，行人交通狀態(tài)數(shù)據(jù)具有較好的穩(wěn)定性和規(guī)律性。當(dāng)某日行人交通數(shù)據(jù)突然大幅偏離正常趨勢，系統(tǒng)即判為擁堵產(chǎn)生，擁堵程度評價方式為：

3.2 基于元胞自動機模型設(shè)計

元胞自動機(cellular automata，簡稱CA)是指在離散和有限狀態(tài)下由元胞組成的元胞空間，并按照指定規(guī)則演化的動力學(xué)系統(tǒng)。在元胞自動機模型中空間被劃分為網(wǎng)格，處于網(wǎng)格中的每一單元叫做元胞，所有元胞遵循相同規(guī)則變化，通過大量元胞的相互作用模擬群體效應(yīng)和演化過程。論文通過元胞的相互作用和動態(tài)演化模擬疏散過程中人群的個體行為和群體效應(yīng)。

在建模中，文章基于元胞自動機模型將公共場所空間劃分成0.3m×0.3m（擁擠時個人所占據(jù)的空間）正方形網(wǎng)格，每個網(wǎng)格分為有人占據(jù)和無人占據(jù)兩種狀態(tài)。當(dāng)發(fā)生擁堵和應(yīng)急疏散時，行人沿著網(wǎng)格從一節(jié)點移動至下一鄰居節(jié)點，從而模擬人群逃生路徑。

考慮應(yīng)急疏散時行人會表現(xiàn)出相當(dāng)?shù)内叡娦?，文章引入D描述人與人之間的相互影響程度。初始時所有元胞相互影響程度D均為0，當(dāng)鄰居疏散人員從節(jié)點n成功逃逸至下一節(jié)點m時，則節(jié)點m對源節(jié)點n影響值加1，從而定義下一節(jié)點m對原節(jié)點n的選擇概率為：

其中，(x,y)是安全出口坐標。

3.3 遺傳算子設(shè)計

遺傳迭代算法能很好地模擬人群疏散過程中的個體動態(tài)變化，并淘汰適應(yīng)度低下的人員節(jié)點。文章定義交叉概率Pc為：

3.4 逃生路徑算法設(shè)計

疏散人員最佳擇徑可以轉(zhuǎn)變?yōu)榍蠼鈫卧炊嗄康穆窂脚帕薪M合優(yōu)化問題，利用粒子群算法迭代求精計算全局最優(yōu)解。定義公共場所共有k個逃生出口，結(jié)合式（4）元胞選擇概率，元胞粒子找到下一粒子后按照式（8）和（9）更新當(dāng)前位置和速率。

4 仿真測試

4.1 測試環(huán)境

實驗選取廣州某步行街道進行仿真測試，共設(shè)置疏散出口10處，見圖1。測得近30天平均人流量182/min人次，其中某日測得兩處人流量達243/min和256/min人次，超出預(yù)設(shè)范圍，系統(tǒng)判為擁堵產(chǎn)生。

圖1 仿真實驗拓撲圖

4.2 測試結(jié)果

仿真實驗將元胞空間劃分為1000×600網(wǎng)格，疏散人數(shù)為1826人次，密度按實際情況部署，人員疏散速率為1m/s，初始化遺傳總?cè)?00，最大遺傳代數(shù)200，交叉概率Pc＝0.8，變異概率Pm＝0.02，粒子群算法慣性權(quán)重Wmax=0.9，Wmin=0.4。疏散效率見圖2所示。

圖2 疏散效率對比圖

在實際疏散過程中，行人按照逃生指示牌進行疏散，部分行人受趨利避害效應(yīng)和趨眾性影響，導(dǎo)致大量人員涌向①、②、③和④出口，產(chǎn)生新的擁堵，疏散效率較低，全程共花費116秒。新算法基于粒子群全局擇優(yōu)思想，疏散效率較高，在30s內(nèi)疏散近60%人員，總疏散時間為94秒。新算法利用元胞自動機模型和遺傳算法仿真行人疏散狀態(tài)，計算的逃生失敗、受傷和死亡人數(shù)均為0，和實際情況相吻合。

5 結(jié)束語

文章提出基于元胞自動機的人員疏散模型，利用遺傳算法淘汰適應(yīng)度低下人員節(jié)點，經(jīng)粒子群算法計算逃生路徑，疏散效率較高，具有一定的應(yīng)用價值，可以為建立完善、科學(xué)的城市應(yīng)急體系提供決策與參考。

[1]孫德山.元胞自動機研究進展[J].五邑大學(xué)學(xué)校（自然科學(xué)版），2011（4）:22-28.Sun Deshan.Research progress of Cellular Automata[J].University of WuYi University （Natural Science Edition）,2011(4):22-28.

[2]郭玉榮,郭磊,肖巖.基于元胞自動機理論的緊急人員疏散模擬[J].湖南大學(xué)學(xué)報,2011(11),25-29.Guo Yurong,Guo Lei,Xiao Yan.Emergency Evacuation Simulation Based on Cellular Automata Theory[J].Journal of HuNan University,2011(11),25-29.

[3]束鈺,陳全.基于元胞自動機對大型商貿(mào)場所火災(zāi)過程的模擬分析[J].天津理工大學(xué)學(xué)報,2011(1):80-84.Su Yu,Chen Quan.Simulation Analysis of Fire Process in Large Commercial Places Based on Cellular Automata[J].Journal of Tianjin University of Technology,2011(1):80-84.

[4]崔喜紅,李強,陳晉,陳春曉.大型公共場所人員疏散模型研究一考慮個體特性和從眾行為[J].自然災(zāi)害學(xué)報,2005(6):133-140.Cui Xihong,Li Qiang,Chen Jin,Chen Chunxiao.A Study on IndividualCharacteristicsand Conformity Behaviorin Large-scale Public Space Evacuation Models[J].Journal of Natural Disasters,2005(6):133-140.

[5]孟曉靜,楊立中,李健.基于元胞自動機的城市區(qū)域火災(zāi)蔓延概率模型探討[J].中國安全科學(xué)學(xué)報,2008(2):28-33.Meng Xiaojing,Yang Lizhong,Li Jian.Discussion on the Probability Model of Fire Spread in Urban Areas Based on Cellular Automata[J].Journal of Chinese Security Science,2008(2):28-33.

[6]孟俊仙,周淑秋,饒敏.大型建筑內(nèi)人員疏散計算機仿真研究評述[J].計算機應(yīng)用與軟件，2008(3):159-161.Meng Junxian,Zhou Shuqiu,Rao Min.A review of Computer Simulation Study on Evacuation of Personnel in Large Buildings [J].Computer Application and Software,2008(3):159-161.

[7]許愛軍,張文金,易丹.基于VRML的虛擬現(xiàn)實技術(shù)及應(yīng)用[J].計算機與數(shù)字工程,2009(04):186-189.Xu Aijun,Zhang Wen Jin,Yi Dan.Based on VRML Virtual Reality Technology and Application[J].Computer and Digital Engineering,2009(04):186-189.

[8]楊立中,方偉峰,黃銳,鄧志華.基于元胞自動機的火災(zāi)中人員逃生的模型[J].科學(xué)通報,2002(12):896-900.Yang Lizhong,Fang Weifeng,Huang Rui,Deng Zhihua.Model of Evacuation of Personnel Based on Cellular Automata[J].Science Bulletin,2002(12):896-900.

[9]譚惠麗,邱冰,劉慕人,孔令江.房間內(nèi)人群疏散過程的元胞自動機研究[J].廣西師范大學(xué)學(xué)報(自然科學(xué)版),2004(4):1-4.Tan Huili,Qiu Bing,Liu Muren,Kong Lingjiang.Study on Cellular Automata in the Evacuation Process of People in the Room[J].Journal of Guangxi Normal University(Natural Science Edition),2004(4):1-4.

Research on Evacuation Algorithm in Public Places

Li Zhicheng，Li Feng，Mo Lequn
(Guangdong Communication Polytechnic,Guangzhou 510650,China)

Through the statistics of pedestrian traffic parameter data rules and characteristics,a public traffic evaluation model is designed,and the cellular automaton model is used to simulate the behavior of the individual and public effect,using genetic algorithm to eliminate unsuitable grid nodes,using particle swarm algorithm to calculate the escape path.The simulation results show that the new algorithm has high efficiency,and can provide a reference for government to make evacuation plans.

Cellular automata;Genetic algorithm;Particle swarm optimization;Evacuation model

10.3969/j.issn.1002-2279.2017.05.015

TP393

A

1002-2279-（2017）05-0057-04

（1）廣東省大學(xué)生科技創(chuàng)新培育專項資金項目（項目編號：pdjh2017b0621）；（2）全國交通運輸職業(yè)教育教學(xué)指導(dǎo)委員會2015年交通運輸職業(yè)教育科研項目（項目編號：2015B21）；（3）廣東省高等職業(yè)技術(shù)教育研究會重點課題（項目編號：GDGZ15Z007）；（4）中國交通教育研究會教育科學(xué)研究課題（項目編號：1402-136）

李智成（1996—），男，廣東省廣州人，學(xué)生，主研方向：網(wǎng)絡(luò)工程。

李 鋒（1981—），男，廣東省龍川縣人，碩士，講師，主研方向：計算機工程。

莫樂群（1976—），男，廣東省廣州人，碩士，副教授，主研方向：信息系統(tǒng)與信息安全。