基于蟻群元胞自動機的地鐵行人疏散模型

杜棋東+陳柔香+許愛軍

摘 要： 針對地鐵站場結構復雜與疏散受行人主觀條件影響等實際情況，宏觀上利用蟻群算法解決復雜建筑結構下大客流尋找最優疏散路徑，微觀上采用元胞自動機智能決策模型，構建融合蟻群算法與元胞自動機的地鐵行人疏散模型，并對廣州地鐵某站場在行人疏散過程中的疏散效率、個體狀態等現象進行討論，其仿真結果可為地鐵編制應急預案、員工培訓、乘客疏散、應急演練提供參考。

關鍵詞： 蟻群； 元胞自動機； 地鐵行人； 疏散

中圖分類號：TP391.4 文獻標志碼：A 文章編號：1006-8228（2018）02-18-04

Abstract： Aiming at the actual situation of complex structure and the evacuation of subways affected by the subjective conditions of pedestrians， this paper uses the ant colony algorithm to solve the large passenger flow under complex building structure to find the optimal evacuation path in the macro view， and on the micro level， uses the intelligent decision model of cellular automaton to construct the underground pedestrian evacuation model of the fusion of ant colony algorithm and cellular automaton. And discuss the evacuation efficiency and individual status of a station in Guangzhou Metro during the evacuation of pedestrians. The simulation results can provide the preparation of contingency plans， staff training， the evacuation of passengers， and emergency drills with a reference.

Key words： ant colony； cellular automaton； subway pedestrian； evacuation

0 引言

行人疏散問題一直是交通安全領域的重要研究內容，早在1971年J.Fruin提出行人的平均行進速度與行人密度的關系曲線，這是對行人疏散的第一個重要的研究成果[1]，英國Sime等人和美國Francis分別提出了ORSET 模型 [2]和預測最小理論疏散時間網絡模型[3]，這些模型較好地指出了行人在疏散時所選擇的逃生路線，但是卻忽略了復雜場所以及行人的心理因素對疏散的影響。

作為復雜場所的地鐵站場，其行人疏散的研究主要集中在路徑算法和疏散模型上，特別是蟻群算法ACO（Ant Colony Optimization）和元胞自動機模型CA（Cellular Automata），王起全等提出蟻群算法能夠使地鐵行人在較短時間內選擇優化的疏散路徑[4]，楊敬等模擬樓層拓撲結構，建立樓層蟻群疏散模型，優化運算時間[5]，許愛軍等為解決蟻群路徑選擇的盲目性和隨機性，提出基于神經網絡自適應蟻群算法[6]，劉真余等對地鐵的行人微觀建模，基于元胞自動機提出兩種疏散規則[7]，田鑫等利用元胞自動機理論創建了地鐵車站火災疏散仿真模型[8]，曹守華等分析地鐵通道內行人行走特征，基于螞蟻元胞自動機對通道雙向人流進行仿真，該模型較好地表達了地鐵雙向通道的行人走行特征[9]，還有學者在智能疏散決策[10-11]，考慮行人引導作用[12]及大型公共建筑疏散[13]等方面有一定的研究。然而上述基于地鐵復雜場地結構、大客流以及行人微觀特征等綜合研究仍不夠系統。

本文在文獻[4]和文獻[11]研究工作的基礎上，對地鐵站場結構特征和行人的信息處理、決策過程進行系統研究，宏觀上利用蟻群算法解決復雜建筑結構下大客流尋找最優疏散路徑，微觀上采用智能體的元胞自動機智能決策模型，構建融合蟻群算法與元胞自動機的行人疏散模型，并對廣州地鐵某站場在行人疏散過程中的疏散效率、行人個體狀態等現象進行討論。

1 蟻群與元胞自動機的定義與特征

1.1 蟻群算法

螞蟻算法真實模擬自然界螞蟻群體覓食的行為，是一種尋找優化路徑的仿生概率型算法，其基本思想是：螞蟻群體在尋找食物源時，會釋放一種信息素，從蟻窩到食物源的路徑上，信息素濃度越高的，代表路徑越近，螞蟻會大概率優先選擇，并釋放信息素增強該路徑的濃度，形成正反饋。從上述思想中，得到螞蟻群體系統模型。

蟻群算法的定義為：定義所有螞蟻，螞蟻智能體為k，在t時刻，從位置i轉移到位置j的轉移概率為：

其中，s為可選擇位置點集合，Xij（t）為t時路徑（i，j）的信息素強度，Mij（t）為t時刻路徑（i，j）的能見度，α、β分別是路徑和能見度的相對重要性。螞蟻群覓食后原路徑返回蟻窩，所需時間為u，其對應元素的信息素需要相應調節，重復循環，可找到參數最優路徑。

1.2 元胞自動機

元胞自動機具有時間離散性、空間離散性、同步性、狀態離散性和有限性等基本特征，是一種具有時空動態特征的空間動力學研究方法。元胞自動機模型主要由元胞狀態集、鄰居以及局部規則組成，所有元胞的狀態同步更新。更新規則是：第k個元胞在t+1時的狀態由自身及鄰居的狀態共同決定，常見鄰居類型有VonNeumann型和Moore型，本文采用Moore型鄰，如圖1。1，2，3，4，5，6，7，8為元胞移動的可選方向，如圖2。endprint

2 基于螞蟻元胞自動機的地鐵行人疏散模型

2.1 有向圖與螞蟻集合

地鐵行人疏散模型基于構建一個有向圖G=（V，C，W），其中V為所有路徑通道節點，C為節點處元胞集合，W為圖中路徑ωi集合，其中，ωi路徑依次經過路徑集合中的各個節點，并且是由螞蟻在每個路徑的元胞集合中選擇確定的，長度固定為1（由目標函數確定螞蟻信息素及轉移概率）。螞蟻集合A1，…，AS，S與路徑規模有關，每只螞蟻從第一個位置，按照轉移概率在各條路徑上轉移直到最后一個位置，轉移概率仍然由信息素的強弱確定，而信息素則由目標函數值確定，函數值越小元胞信息素越強，螞蟻選擇的概率越大。一只螞蟻轉移到最后一個位置節點意味著可以停止尋優，每組螞蟻尋找到n個可行解意味著這組螞蟻可以停止尋優，一次尋優也稱為一次迭代，時間為cycle，在具體的疏散過程中，會明確迭代最大次數或者規定迭代中止條件。

2.2 迭代轉移概率

設u=（u0，…，ut-2，ut-1=i）表示某螞蟻第m次轉移前，已路過的各元胞節點組成的地鐵通道路徑，其中，u0，…，ut-2，ut-1是圖的一部分節點，u0是初始節點位置，i是當前節點位置，j是下一節點位置，xij為該元胞節點的信息素，在上述公示⑴的基礎上，轉移概率為：

在式⑵中，α、β為信息因子和期望因子，Mij（u）為可見度值，Xij（m）為信息素“濃度”，Pij（m，u）表示某螞蟻在第m次迭代中，構造疏散路徑u后，從當前位置i轉移到j的轉移概率。所有螞蟻A1，…，AS按照轉移概率Pij（m，u）依次轉移，構造疏散的可行解；若目前節點位置屬于終點元胞集合，則Pij（m，u）=0，意味著螞蟻在這次迭代中已經完成構造疏散過程。

2.3 信息素濃度

在迭代開始時，設置每個元胞點初始濃度Xij（m）為固定值，之后在每次迭代末，根據⑶進行更新。

在式⑶⑷中，Lij為地鐵通道長度，ζij為地鐵行人通行難易系數，ρ為蒸發因子，Δτij加上信息素蒸發機制，組成信息素的更新規則。

2.4 模糊推理模型

螞蟻算法存在的主要問題是容易陷入局部最優解的困局，為了解決這個問題，本文引入模糊推理模型，即在信息素的更新過程中，通過推理再演變，并增加最優路徑選擇，達到減少陷入局部最優解的概率。考慮對地鐵環境較為熟悉的行人在選擇路徑時主要考慮所處位置到出口的距離以及路徑通道上的密度兩個因素，路徑距離與密度信息均屬于模糊參數，本文采用文獻[11]的模糊推理模型。

在路徑距離方面，將元胞可能選擇的8個方向距離出口位置進行極差標準化處理，距離分成3個模糊集，，參數分別代表距離近，距離中，距離遠；在密度信息方面，在一定的視野范圍內，由人群與障礙物共同決定，密度分成3個模糊集，參數分別代表數量少，數量中，數量多。距離模糊集D和密度模糊集T均作為元胞輸入，輸出方向移動可能性為，其參數分別代表負大，負中，零，正中，正大，其模糊推理規則如表1所示。

表1所示基本原則為：如果距離某個出口遠，障礙物密度大，那么往該出口移動可能性小；如果距離某個出口近，障礙物密度小，那么往該出口移動可能性較大。

3 仿真與驗證

3.1 測試環境

為了驗證基于蟻群元胞自動機的地鐵行人疏散方法的有效性，選取廣州地鐵某站場進行仿真實驗。用于行人出入口的位置有10處，對角線A、B、C、D為地鐵出入口，E～J為地鐵出入閘機口[6]，如圖3所示。

3.2 測試結果

在測試實驗中，將地鐵平面空進行0.4m*0.4m的網格劃分，行人均勻分布在站廳各個位置，在每一時刻上，網格都有可能被障礙物占有，初始化行人數量為30（數量最多不超過300），信息素初始濃度值為0.5，蒸發因子為ρ為0.32，行人當中有60%對地鐵站廳環境熟悉，有40%對環境不熟悉。

從圖4可以看出，對比其他三種疏散算法，最短路徑算法效率最低，行人僅以距離出口近作為惟一出逃路徑缺乏合理的規劃，元胞自動機算法基于行人微觀特征尋找路徑，優于最短路徑算法，然而沒考慮到數量大的群體行為因素，導致其效率仍不高，標準蟻群算法作為尋找最優路徑的算法，使大部分行人移向最優出口，造成一定的擁擠，但效率高于元胞自動機模型。本文方法綜合螞蟻算法與元胞自動機模型二者的特點，疏散效率與其他三種對比較優。

本方法能夠對不同類型的行人在不同狀態下給出分析。第一種狀態：對環境的熟悉程度，從圖5可以看出，對環境熟悉的行人，會根據距離和障礙物（人群）密度綜合考慮挑選前進的方向，整體的疏散速度比較快。第二種狀態：行人不同的體力狀態，從圖6可以看出，體力較好的行人整體疏散速度，明顯優于體力差的行人，實驗結果與現實情況較為吻合。

4 結束語

本文在求解上基于種群的進化算法，利用元胞自動機的模糊推理方法，提出基于蟻群元胞自動機的地鐵行人疏散模型，能夠對不同類型的行人在不同狀態下給出分析，解決復雜結構環境下地鐵站行人疏散的路徑問題。下一步將結合地鐵突發事件如火災、群毆、設備斷電等進行模擬疏散，綜合分析各種因素，提高疏散模型算法的適應性，為地鐵編制應急預案、員工培訓、乘客疏散、應急演練提供更為完善的參考。

參考文獻（References）：

[1] 王理達.地鐵車站人群疏散行為仿真研究[D].北京交通大學碩士學位論文，2006：3-5

[2] 王馳.某地鐵站火災情況下人員安全疏散研究[D].北京交通大學碩士學位論文，2007：3-4

[3] 胡忠日.安全疏散研究的國內外動態和發展趨勢[J].消防科學與技術，2001.6：7-8

[4] 王起全，杜艷洋，張心遠.蟻群算法在地鐵車站內應急疏散的應用[J].消防科學與技術，2015.34（1）：55-58

[5] 楊敬，石明全，韓震峰等.一種蟻群算法疏散模型優化的方法[J].消防科學與技術，2015.34（3）：343-346

[6] 許愛軍，蘇境迎.基于自適應蟻群算法的地鐵人員疏散模型[J].微機處理，2016.1：50-53

[7] 劉真余，芮小平，董承瑋等.元胞自動機地鐵人員疏散模型仿真[J].計算機工程與應用，2009.45（27）：203-248

[8] 田鑫，蘇燕辰，李冬等.地鐵車站火災疏散仿真分析[J].科學技術與工程，2017.17（16）：333-338

[9] 曹守華，袁振洲，趙 丹等.基于螞蟻元胞自動機的地鐵通道雙向行人流仿真[J].系統仿真學報，2009.21（8）：2457-2462

[10] 馬潔，徐瑞華，李璇等.地鐵車站乘客疏散出口選擇行為仿真建模[J].同濟大學學報（自然科學版），2016.44（9）：1407-1414

[11] 張麗娟，張艷芳，趙宜賓等.基于元胞自動機的智能疏散模型的仿真研究[J].系統工程理論與實踐，2015.35（1）：247-253

[12] 高鳳強，顏逾越，許策等.一種考慮引導作用的行人疏散元胞自動機模型[J].交通運輸系統工程與信息，2016.16（6）：60-66

[13] 張培紅，張蕓栗，梅志斌等.大型公共建筑物智能疏散路徑優化自適應蟻群算實現及應用[J].沈陽建筑大學學報（自然科學版），2008.24（6）：1055-1059endprint